Лекция: Методы второго порядка

Методы применимы к дважды дифференцируемым функциям. При этом предъявляются высокие требования к точности вычисления производных. Наиболее удачными считаются задачи, в которых известно аналитическое выражение первой производной, а еще лучше – и второй.

Здесь приводится только один из наиболее часто используемых методов – метод Ньютона – Рафсона.

Он основан на линейной аппроксимации первой производной минимизируемой функции f в окрестности текущей точки xk:

В стационарной точке аппроксимации, которая принимается за очередное приближение xk+1, производная равна нулю:

.

Отсюда следует рекуррентная формула для построения последовательности приближений к искомому минимуму:

(8.41)

Очевидно, что применение (8.41) возможно только при условии, что для каждого k. Поиск завершается по условию достижения точности, заданной величиной первой производной | f '(xk) | < e1 или расстоянием между двумя точками |xk+1-xk | < e. Возможно одновременное использование этих условий.

В общем случае процедура (8.41) не гарантирует сходимость к стационарной точке. Если начальная точка достаточно близка к стационарной, то метод сходится. При сходимости обеспечивается высокая скорость приближения к минимуму. На рис. 8.14 приведен случай сходимости метода. Очередному приближению соответствует точка пересечения оси x аппроксимирующей прямой. Как видно, последовательность точек x0,x1,x2,… приближается к минимуму x* .

Для некоторых функций результат поиска зависит от выбора начальной точки. Так, например, при начальной точке, взятой правее максимуму производной, так как показано на рис. 8.15, метод расходится.