Описание классического метода Ньютона - Рафсона

 

Предположим, что уравнение f(X)=0 имеет один корень на интервале [a, b], производные f¢(X) и f¢¢(X) определены, непрерывны и сохраняют постоянные знаки на отрезке [a, b].

Возьмем некоторую точку начального приближения X⁰Î[a, b] и проведем в точке P₀ {X⁰, f(X⁰)} касательную к кривой Y=f(X) до пересечения с осью OX. Абсциссу этой точки пересечения (X¹) можно взять в качестве очередного приближенного значения корня.

Проведя касательную через новую точку P₁{X¹, f(X¹)} и находя точку ее пересечения с OX, получим второе приближение X² к истинному положению корня и т. д.

Уравнение касательной, проходящей через точку P₀, имеет вид:

Y=f(X⁰)+f¢(X⁰)(X–X⁰).

Полагая Y=0, найдем абсциссу X1 точки пересечения касательной и OX

Следующие приближения найдем по формулам:

¼

(4.12)

Процесс вычисления приближений необходимо прекратить при выполнении условия:

(4.13)

где m₁ – наименьшие значение |f¢(X)| на отрезке [a, b],

M₂ – наибольшее значение |f¢¢(X)| на том же отрезке.

При этом будет выполняться равенство:

где e – предельная абсолютная погрешность корня

Начальное приближение X⁰ выбирают так, чтобы было выполнено условие сходимости:

f(X⁰)´f¢¢(X⁰)>0. (4.14)

В противном случае не гарантируется сходимость метода. Чаще всего выбирают X⁰=a или X⁰=b в зависимости от того, в какой из точек выполняется условие сходимости.

 

Модификации метода Ньютона

 

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

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

-Упрощенный метод Ньютона

Если производная функции f¢(X) непрерывна, то ее значение вблизи простого корня почти постоянно. Поэтому можно попытаться вычислить f¢(X) лишь однажды в точке , а затем заменить f¢() постоянной f¢(). В результате получим упрощенную формулу метода Ньютона:

n³0. (4.15)

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

(4.16)

Так как

(4.17)

то для знаменателя q соответствующей геометрической прогрессии имеем:

(4.18)

Следовательно, скорость сходимости тем выше, чем ближе начальное приближение к решению .

 

-Метод ложного положения

В основе этой и следующей модификаций метода Ньютона лежит приближенное равенство:

(4.19)

Оно верно при условии известности Zⁿ и Xⁿ и следует из определения производной:

(4.20)

Пусть C - фиксированная точка, расположенная в окрестности простого корня`X. Заменим в расчетной формуле классического метода Ньютона

производную правой частью формулы (4.19), полагая, что Zⁿ=C.

В результате приходим к формуле ложного положения:

(4.21)

Метод обладает линейной сходимостью. Его можно рассматривать как метод простой итерации с итерационной функцией:

(4.22)

Так как скорость сходимости определяется вблизи корня величиной

(4.22)

то она тем выше, чем ближе окажется выбранная точка C к корню уравнения.

 

- Метод секущих

 

Замена в формуле (4.12) для метода Ньютона производной f¢(X) приближением:

приводит к расчетной формуле для метода секущих:

(4.23)