28. Метод Ньютона. Сходимость метода Ньютона.

Пусть начальное приближение известно. Заменим отрезком ряда Тейлора

и за следующее приближение возьмем корень уравнения т. е.

Вообще, если итерация известна, то следующее приближение в методе Ньютона определяется по правилу

(1).

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

Сходимость метода Ньютона

Предположим, что уравнение

(1).

Имеет простой вещественный корень вида , так что .

Будем предполагать, что дважды дифференцируема в окрестности корня .Исследуем сходимость метода Ньютона.

(2).

Заметим прежде всего, что (2) можно рассматривать как частный случай метода простой итерации

(3).

для которого

(4).

Из сходимости метода простой итерации следует, что для сходимости метода (3) достаточно потребовать, чтобы в некоторой окрестности искомого корня выполнялось неравенство

(5). .

Для функции (4) имеем:

и если — корень , то . Поэтому найдется окрестность корня, в которой выполнено неравенство (5). Тем самым при надлежащем выборе начального приближения метод Ньютона сходится. Однако следствием малости в окрестности является не просто сходимость, а сходимость существенно более быстрая, чем в общем случае метода простой итерации. В следующей теореме

доказано, что метод Ньютона имеет квадратичную сходимость, т. е. что он сходится и погрешность на (й+1)-й итерации пропорциональна квадрату погрешности на й-й итерации, т.е.

Теорема 1. Пусть х. — простой вещественный корень уравнения (1) и пусть в окрестности

Предположим, что непрерывна в и

(6). ,

причём

(7).

Тогда если , то метод Ньютона(2) сходится, причем для погрешности справедлива оценка

(8). ,

где

(9).

Доказательство. Из уравнения (2) получим

, или же, упростив,

(10).

где

(11). .

Заметим, что и

(12).

Далее, воспользовавшись тождеством и выражением (12) для , получим

Так как функция не меняет знак на отрезке интегрирования, можно воспользоваться формулой среднего значения и записать, что

,где .

Обращаясь к (10), получим

(13). ,

т.е. погрешность на (k+1)-й итерации пропорциональна квадрату погрешности на k-й итерации.

Докажем оценку (8) по индукции. При k = 0 из (13) получим

(14).

По условию теоремы , и поэтому согласно первому из условий (6) имеем . Кроме того,

т. е. . Но тогда согласно (6) . Таким образом, приходим к оценке

, совпадающей с оценкой (8) при .

Предположим, что оценка (8) выполняется при , и докажем, что она выполняется и при . При выражение (13) принимает вид

(15).

Покажем, что . Действительно, из (8) при имеем

, т. е. а, следовательно, . Теперь можно воспользоваться условиями (6) и оценить . Отсюда и из (15) получим

, Из этого неравенства и из неравенства (8), имеющего следующий вид при :

, получим оценку ,

т.е. оценку (8) при . Из оценки (8) следует сходимость метода (2), так как для правая часть неравенства (8) стремится к нулю при . Теорема 1 доказана.

Такая быстрая сходимость метода Ньютона гарантируется лишь при очень хороших, т. е. близких к точному решению, начальных приближениях. Если начальное приближение выбрано неудачно, то метод может сходиться медленно, либо не сойдется вообще.