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

Метод Ньютона (також метод дотичних, метод Ньютона — Рафсона) — метод наближеного знаходження кореня дійсного рівняння:

$f(x)=0$

де f диференційована функція. Послідовні наближення методу Ньютона обчислюються за формулами

$x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}.$

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

Обґрунтування методу

Розкладаючи в околі початкового наближення $x_{0}$ функцію f в ряд Тейлора і відкидаючи члени порядку вище 1, одержуємо наближену рівність, справедливу в деякому околі $x_{0}$:

Ілюстрація методу Ньютона (синім зображена функція $\scriptstyle {f(x)}$, нуль якої необхідно знайти, червоним — дотична в точці наближення

$f(x)\cong f(x_{0})+f'(x_{0})(x-x_{0}).$

Оскільки шукається корінь f(x) то в лівій стороні формули можна поставити 0, і перше наближення:

$x_{1}=x_{0}-{\frac {f(x_{0})}{f'(x_{0})}}\,\!$

одержується внаслідок елементарних перетворень.

Можна також дати геометричну інтерпретацію. Основна ідея методу полягає в наступному: задається початкове наближення поблизу кореня, після чого будується дотична до досліджуваної функції в точці наближення, для якої знаходиться перетин з віссю абсцис. Точка перетину і береться як наступне наближення. І так далі, поки не буде досягнута необхідна точність. Формула наближення може бути виведена таким чином:

$f'(x_{n})=\mathrm {tg} \,\alpha ={\frac {\Delta y}{\Delta x}}={\frac {f(x_{n})-0}{x_{n}-x_{n+1}}}={\frac {0-f(x_{n})}{x_{n+1}-x_{n}}},\,\!$

де $\alpha$ — кут нахилу дотичної в точці $x_{n}\!.$

Отже, шуканий вираз для $x_{n+1}\,$ має вигляд:

$x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}.\,\!$

Швидкість збіжності

Збіжність дуже швидка, якщо вона взагалі є. Припустимо, що $f^{''}$ є неперервною, і що $f^{'}(x)\neq 0$ у деякому околі кореня $x^{*}$ (достатньо великому, щоб уся послідовність $x_{0},\dots$ перебувала в цьому околі.) Нехай $\epsilon _{n}=x_{n}-x^{*}.$ Тоді ми можемо здійснити розклад у ряд Тейлора в околі $x_{n},$ і обчислити його у $x=x^{*}:$

$0=f(x^{*})=f(x_{n})+(x^{*}-x_{n})f'(x_{n})+{\frac {1}{2}}(x^{*}-x_{n})^{2}f''(\xi ),$

для деякого $\xi \in int(x_{n},x^{*}).$ Також у нас є рівняння:

$0=f(x_{n})+(x_{n+1}-x_{n})f'(x_{n}).$

Віднімаючи ці два рівняння, отримуємо:

$0=-\epsilon _{n+1}f'(x_{n})+{\frac {1}{2}}\epsilon _{n}^{2}f''(\xi ),$

$\epsilon _{n+1}={\frac {1}{2}}{\frac {f''(\xi )}{f'(x_{n})}}\epsilon _{n}^{2}.$

Наші припущення гарантують, що співвідношення ${\frac {f''(\xi )}{f'(x_{n})}}$ існує і збігається до певної границі $(f''(x^{*})/f'(x^{*}))$ коли $n\to \infty .$ Отже, послідовність рівномірно обмежена в $n,$ і ми можемо записати

$|\epsilon _{n+1}|\leq C\epsilon _{n}^{2},$

де $C>0$ є деяким числом (яке залежить від $f,$ але не від $n.)$ З цього випливає, що

$|\epsilon _{n}|\leq {\frac {1}{C}}(C\epsilon _{0})^{2^{n}}.$

Ми кажемо, що метод має квадратичну збіжність. Кількість правильних цифр підноситься до квадрату на кожній ітерації. Тоді коли метод бісекції має лише лінійну збіжність.

Збіжність гарантовано, коли початкова точка $x_{0}$ достатньо близька до (невідомого) кореня $x^{*},$ у сенсі, що $|C\epsilon _{0}|<1.$

Модифікований метод Ньютона

$x_{n+1}=x_{n}-{\frac {1}{f'(x_{0})}}f(x_{n})\!$

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

Див. також

• Метод Лобачевського — Греффе

Література

• Григорій Михайлович Фіхтенгольц. Курс диференціального та інтегрального числення. — 2023. — 1900+ с.(укр.)
• Н.Н.Калиткин. Численные методы. М.: Наука, 1978.
• Б.П.Демидович, И.А.Марон, Э.З.Шувалова. Численные методы анализа. М.: Наука, 1967.
• М.Я.Лященко, М.С.Головань. Чисельні методи: Підручник. – К.: Либідь, 1996. – 288 с.