4.4. Метод Ньютона

Метод Ньютона называется также методом касательных или методом линеаризации. Если x_n есть некоторое приближение к корню , a f(x) имеет непрерывную производную, то уравнение (4.1) можно приближенно (используя первые два члена разложения в ряд Тейлора) представить следующим образом:

f () f ()+ () f () = 0. (4.7)

Выразив из (4.7) , получим итерационный процесс:

. (4.8)

Геометрически этот процесс означает замену на каждой итерации графика y = f(x) касательной к нему (рис. 4.4).

x₀

x₁

x₂

x₃

y

f (x)

x

Рис 4.4. Итерационная процедура решения уравнения f(x)=0 методом Ньютона

Метод Ньютона можно рассматривать как частный случай метода простых итераций. Уравнение (4.1) можно [2] представить в виде () = . Тогда (x) = . Если есть p-кратный корень уравнения (1), то вблизи него f(x)  a(x - )^p; отсюда (x) = , т. е. 0  (x) < 1, откуда следует сходимость итерации к корню любой кратности при достаточно близком начальном приближении. Для простого корня р = 1 и (x) = 0. Скорость сходимости соответствует скорости геометрической прогрессии. При произвольном нулевом приближении итерации сходятся, если всюду |ff"| < (f ')², в противном случае сходимость будет не при любом нулевом приближении, а только в некоторой окрестности корня.

На практике, часто имеют место случаи, когда это требование не выполняется (рис. 4.5).

y

_ x

Рис.4.5. Пример неудачно выбранного начального приближения

4.5. Метод секущих

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

. (4.9)

Для начала процесса надо задать х₀ и х₁ (рис. 4.6.). Такие процессы, где для вычисления очередного приближения надо знать два предыдущих, называют двухшаговыми.

y

Рис. 4.6. Метод секущих

Эти, казалось бы, небольшие изменения сильно влияют на характер итераций. Например, сходимость итераций может быть немонотонной не только вдали от корня, но и в малой окрестности корня. Скорость сходимости также изменяется, становится медленнее.