Метод Ньютона – Рафсона

Метод Ньютона часто используется на завершающем этапе минимизации, когда x – точка минимума грубо найдена другим, менее трудоемким методом и требуется найти x с большой точностью. Кроме того, если функция ¦(x) содержит члены, включающие x в третьей и более высоких степенях, то непосредственное получение аналитического решения уравнения ¦ (x) = 0 может оказаться затруднительным. В таких случаях используются приближенные методы последовательного поиска стационарной точки функции ¦(x). Ньютон разработал схему, ориентированную на нахождение корня нелинейного уравнения, которая позднее была уточнена Рафсоном.

В рамках схемы Ньютона – Рафсона предполагается, что ¦(x) – дважды дифференцируемая функция, причем ¦ (x) > 0 (это гарантирует выпуклость ¦(x)). Работа алгоритма начинается в точке x , которая представляет начальное приближение координаты стационарной точки, или корня уравнения ¦ (x) = 0. В очередной точке x (k = 0,1,…) строится линейная аппроксимация функции ¦ (x), и точка, в которой аппроксимирующая линейная функция обращается в нуль, принимается в качестве следующего приближения x (рис. 5.10). Если точка x принята в качестве текущего приближения к стационарной точке, то уравнение

касательной к графику точке x = x

имеет вид

y = ¦(x ) + ¦ (x )(x - x ).

Точка x = x , найденная из условия y = 0, определяется формулой

x = x - ¦(x )/¦ (x ).

Полагая ¦(x) = ¦ (x), тогда для решения уравнения ¦ (x) = 0 необходимо построить последовательность

x = x - , k = 0,1,…, (5.10)

где x – точка, выбранная в качестве начального приближения.

Рис. 5.10. Метод Ньютона – Рафсона (сходимость)

В зависимости от выбора начальной точки и вида функции алгоритм может, как сходиться к истинной стационарной точке, так и расходиться, что отражено на рис. 5.11. Если начальная точка расположена правее x , то получаемые в результате последовательных приближений точки удаляются от стационарной точки x .

Рис. 5.11. Метод Ньютона – Рафсона (отсутствие сходимости)

Оценка скорости сходимости может быть сформулирована следующим образом. Пусть ¦(x) – дважды дифференцируемая на E функция, причем ¦ (x) ³ m > 0 при всех x Î E и ¦ (x) удовлетворяет условию Липшица на X с константой L. Тогда, если начальное приближение x удовлетворяет условию