Алгоритм метода Ньютона

Построим эффективный алгоритм вычисления корней уравнения. Пусть задано начальное приближение . Вычислим в этой точке значение функции и её производной . Рассмотрим графическую иллюстрацию метода:

Далее получим следующее приближение в точке , проводя касательную из точки () до пересечения с осью абсцисс:

(8)

Продолжая этот процесс, получим известную формулу Ньютона:

(9)

Рис. 1.

Приведем простейшую рекурсивную подпрограмму-функцию:

function X_Newt(x,eps:real):real;

var y:real;

begin

y:=x-f(x)/f1(x);

if abs(f(x)) > eps

then X_Newt:=X_Newt(y,eps)

else X_Newt:=y

end;

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

Преобразуем уравнение (1) к эквивалентному уравнению вида:

x=g(x) (10)

В случае метода касательных . Если известно начальное приближение к корню x=x₀, то следующее приближение найдем из уравнения x₁=g(x₀), далее x₂=g(x₁),... Продолжая этот процесс, получим рекуррентную формулу метода простой итерации

x_k+1=g(x_k) (11)

Итерационный процесс продолжается до тех пор, пока не будут выполнены условия (5-7).

Всегда ли описанный вычислительный процесс приводит к искомому решению? При каких условиях он будет сходящимся? Для ответа на эти вопросы опять обратимся к геометрической иллюстрации метода.

Корень уравнения представляется точкой пересечения функций y=x и y=g(x). Как видно из рис. 3(а), если выполняется условие , то процесс сходится, иначе – расходится (рис3(б)).

(a) (б)

Рис. 3.

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

(12)

Переход от уравнения f(x)=0 к уравнению х=g(x) можно осуществлять различными способами. При этом важно, чтобы выбранная функция g(x) удовлетворяла условию (12). К примеру, если функцию f(x) умножить на произвольную константу q и добавить к обеим частям уравнения (1) переменную х, то g(x)=q*f(x)+x. Выберем константу q такой, чтобы скорость сходимости алгоритма была самой высокой. Если 1<g’(x)<0, то сходимость итерационного процесса будет двусторонней. Производная по х от этой функции: g’(x)=1+q*f’(x). Наибольшую сходимость получим при g’(x)=0, тогда q= - 1/f’(x) и формула (11) переходит в формулу Ньютона (9).

Метод Ньютона обладает высокой скоростью сходимости, однако он не всегда сходится. Условие сходимости , где g(x) = x – f(x)/ f’(x), сводится к требованию .

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

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

(13)

Другой метод модификации – замена производной конечной разностью

(14)

Тогда (15)

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

Запишем в общем виде алгоритм метода Ньютона.

1. Задать начальное приближение х⁽⁰⁾ так, чтобы выполнилось условие

f(x⁽⁰⁾)*f’’(x⁽⁰⁾)>0. (16)

Задать малое положительное число ε, как точность вычислений. Положить к = 0.

2. Вычислить х^(к+1) по формуле (9):