Методы оптимизации. Рейзлин В.И. - 11 стр.

UptoLike

ВУЗ: 

ТПУ | Томск

Составители: 

Рубрика: 

предположения об унимодальности естественно утверждать, что точка минимума
не может находиться левее точки z. Другими словами, интервал x≤z подлежит
исключению. С другой стороны, если f?(z)>0, то точка минимума не может
находиться правее z и интервал x≥z можно исключить /2/. Приведенные
рассуждения лежат в основе логической структуры метода средней точки,
который иногда называют поиском Больцано.
Определим две точки L и R таким образом, что f?(L)<0 и f?(R)>0.
Стационарная точка расположена между L и R. Вычислим значение производной
функции в средней точке рассматриваемого интервала z=(L+R)/2. Если f?(z)>0,
то интервал (z, R) можно исключить из интервала поиска. С другой стороны, если
f?(z)<0, то можно исключить интервал (L, z). Ниже дается формализованное
описание шагов алгоритма.
Шаг 1. Положить R=b, L=a; при этом f?(a)<0 и f?(b)>0.
Шаг 2. Вычислить z=(R+L)/2 и f?(z).
Шаг 3.Если | f?(z)|≤E, закончить поиск. В противном случае, если f?(z)<0,
положить L=z и перейти к шагу 2. Если f?(z)>0, положить R=z и перейти к шагу
2.
Следует отметить, что логическая структура поиска в соответствии с
изложенным методом исключения интервалов основана лишь на исследовании
знака производной независимо от значений, которые эта производная принимает.
1.3.3. Метод секущих
Метод секущих, являющийся комбинацией метода Ньютона и общей схемы
исключения интервалов, ориентирован на нахождение корня уравнения f?(x) в
интервале (a, b), если, разумеется, такой корень существует.
Предположим, что в процессе поиска стационарной точки функции f(x) в
интервале (a, b) обнаружены две точки L и R, в которых знаки производной
различны. В этом случае алгоритм метода секущих позволяет аппроксимировать
функцию f?(x) «секущей прямой» (прямой линией, соединяющей две точки) и
найти точку, в которой секущая графика f?(x) пересекает ось абсцисс (рис. 1.5).
Таким образом, следующее приближение к стационарной точке х* определяется
по формуле
)LR/()]L(f)R(f[
)R(f
Rz
. (1.7)
Если | f?(z)|≤E, поиск следует закончить. В противном случае необходимо
выбрать одну из точек L или R таким образом, чтобы знаки производной в этой
точке и точке z были различны, а затем повторить основной шаг алгоритма /2/.

Страницы