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

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

${\displaystyle f(x)=0}$

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle 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}}},\,\!}$

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

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

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

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

Див. також: Швидкість збіжності

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Див. також

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

Література

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