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

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

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

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 с.