Метод Ньютона
Метод Ньютона (також метод дотичних, метод Ньютона — Рафсона) — метод наближеного знаходження кореня дійсного рівняння:
де f диференційована функція. Послідовні наближення методу Ньютона обчислюються за формулами
Узагальнення і варіації методу використовуються для обчислення коренів системи нелінійних рівнянь, знаходження екстремуму функції, обчислення коренів комплексного рівняння.
Обґрунтування методу
Розкладаючи в околі початкового наближення функцію f в ряд Тейлора і відкидаючи члени порядку вище 1, одержуємо наближену рівність, справедливу в деякому околі :
Оскільки шукається корінь f(x) то в лівій стороні формули можна поставити 0, і перше наближення:
одержується внаслідок елементарних перетворень.
Можна також дати геометричну інтерпретацію. Основна ідея методу полягає в наступному: задається початкове наближення поблизу кореня, після чого будується дотична до досліджуваної функції в точці наближення, для якої знаходиться перетин з віссю абсцис. Точка перетину і береться як наступне наближення. І так далі, поки не буде досягнута необхідна точність. Формула наближення може бути виведена таким чином:
де — кут нахилу дотичної в точці
Отже, шуканий вираз для має вигляд:
Швидкість збіжності
Збіжність дуже швидка, якщо вона взагалі є. Припустимо, що є неперервною, і що у деякому околі кореня (достатньо великому, щоб уся послідовність перебувала в цьому околі.) Нехай Тоді ми можемо здійснити розклад у ряд Тейлора в околі і обчислити його у
для деякого Також у нас є рівняння:
Віднімаючи ці два рівняння, отримуємо:
Наші припущення гарантують, що співвідношення існує і збігається до певної границі коли Отже, послідовність рівномірно обмежена в і ми можемо записати
де є деяким числом (яке залежить від але не від З цього випливає, що
Ми кажемо, що метод має квадратичну збіжність. Кількість правильних цифр підноситься до квадрату на кожній ітерації. Тоді коли метод бісекції має лише лінійну збіжність.
Збіжність гарантовано, коли початкова точка достатньо близька до (невідомого) кореня у сенсі, що
Модифікований метод Ньютона
дозволяє не обчислювати похідну на кожній ітерації, а, отже, і позбутися можливого ділення на нуль. Однак цей алгоритм має тільки лінійну збіжність.
Див. також
Література
- Н.Н.Калиткин. Численные методы. М.: Наука, 1978.
- Б.П.Демидович, И.А.Марон, Э.З.Шувалова. Численные методы анализа. М.: Наука, 1967.
- М.Я.Лященко, М.С.Головань. Чисельні методи: Підручник. – К.: Либідь, 1996. – 288 с.