Методы второго порядка

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

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

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

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

.

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

(8.41)

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

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

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