Метод касательных (Ньютона-Рафсона)

Пусть на отрезке $[a,b]$ существует единственный корень уравнения (1): $x*$

(2)

$f(x*)=0$ ,

а $f'(x)$ существует, непрерывна и отлична от нуля на $[a,b]$ . Перепишем (2) следующим образом:

$f(x^k+(x*-x^k))=0$

и применим к этому выражению формулу Лагранжа:

$f(x^k)+f'(\bar{x})(x*-x^k)=0, \;\bar{x} \in [a,b].$

Заменим $\bar x$ на $x^k$ , а $x*$ - на $x^{k+1}$ и получим формулу итерационного процесса:

$f(x^k)+f'(x^k)(x^{k+1}-x^k)=0.$

Выразим отсюда $x^{k+1}$ :

(3)

$x^{k+1}=x^k-\frac{f(x^k)}{f'(x^k)}.$

Метод касательных имеет (когда сходится) квадратичную скорость сходимости: $|x^{k+1}-x*|=O((x^k-x*)^2).$

Модифицированный метод касательных

Если мы хотим избежать вычисления производной на каждом шаге, то можно взять $f'(x^0)$ вместо $f'(x),$ где $x^0$ - начальное приближение:

$x^{k+1}=x^k-\frac{f(x^k)}{f'(x^0)}.$

В отличие от обычного метода касательных, в модифицированном методе предоставляется меньше требований к выбору начального приближения, а так же гарантировано отсутствие деления на ноль, если $f'(x^0) \ne 0.$

Однако модифицированный метод имеет один существенный недостаток: линейную скорость сходимости: $|x^{k+1}-x*|=O(x^k-x*).$

Геометрическая интерпретация

Метод касательных

Метод Ньютона-Рафсона называют также методом касательных, т.к. новое приближение $x^{k+1}$ является абсциссой точки пересечения касательной, проведенной в точке $(x^k,f(x^k))$ к графику функции $f(x)$ , с осью ОХ.

Сходимость метода

Заметим, что метод касательных является частным случаем метода простых итераций

$x^{k+1}=g(x^k),\; k=0,1,\ldots,$

для которого

(4)

$g(x)=x-\frac{f(x)}{f'(x)}.$

Метод простых итераций сходится тогда и только тогда, когда

$|g'(x)|\le q < 1,$

Подставим в последнее условие выражение для g(x) (4) и получим условие сходимости метода касательных:

$\left|\frac{f(x)f''(x)}{(f'(x))^2}\right| \le q < 1.$

Сформулируем теорему о квадратичной скорости сходимости метода касательных:

Теорема. Пусть $x*$ - простой вещественный корень уравнения $f(x) = 0$ , а функция $f(x)$ - дважды дифференцируема в некоторой окрестности $U_r(x*)$ , причем первая произодная нигде не обращается в нуль.