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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

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) \ne 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^2f''(\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}|\le C\epsilon_n^2,

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

|\epsilon_n|\le\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)\!

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

Література[ред.ред. код]

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