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

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

$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 має неперервну другу похідну $x^*$ — простий корінь рівняння і початкове наближення $x_0$ лежить достатньо близько до $x^*$, то метод Ньютона має квадратичну збіжність, тобто похибка на (n+1)-й ітерації пропорційна квадрату похибки на n-й ітерації.

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

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

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

Література

• Н.Н.Калиткин. Численные методы. М.: Наука, 1978.
• Б.П.Демидович, И.А.Марон, Э.З.Шувалова. Численные методы анализа. М.: Наука, 1967.
• М.Я.Лященко, М.С.Головань. Чисельні методи: Підручник. – К.: Либідь, 1996. – 288 с.