Построим эффективный алгоритм вычисления корней уравнения. Пусть задано начальное приближение . Вычислим в этой точке значение функции и её производной . Рассмотрим графическую иллюстрацию метода:
.
Далее получим следующее приближение в точке , проводя касательную из точки () до пересечения с осью абсцисс:
(8)
Продолжая этот процесс, получим известную формулу Ньютона:
(9)
y
x
Рис. 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=x0, то следующее приближение найдем из уравнения x1=g(x0), далее x2=g(x1),... Продолжая этот процесс, получим рекуррентную формулу метода простой итерации
xk+1=g(xk) (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. Задать начальное приближение х(0) так, чтобы выполнилось условие
f(x(0))*f’’(x(0))>0. (16)
Задать малое положительное число ε, как точность вычислений. Положить к = 0.
2. Вычислить х(к+1) по формуле (9):
.
3. Если | x(k+1) - x(k) | < ε, то процесс вычисления прекратить и положить х* = x(k+1). Иначе увеличить к на 1 (к = к + 1) и перейти к пункту 2.