Метод Ньютона-Рафсона, також відомий як Метод Ньютона, являє собою узагальнений метод пошуку кореня рівняння
| (1) |
Приймемо x = xj в якості j-го наближення до кореня рівняння (1). Припустимо, що xj не є рішенням. Отже,. Припустимо також, що ми отримали розкладання в ряд Тейлора для рівняння (1) відносно точки x = xj:
| (2) |
Якщо приймемо як наступного члена x = xj +1, то рівняння (2) буде мати вигляд:
| (3) |
Тепер припустимо, що справедливо необов'язкове допущення того, що попереднє наближення xj було задовільним, так що xj +1 - xj мало. Якщо це припущення вірне, ми можемо знехтувати членами вищого порядку в рівнянні (3), так як n-й ступінь малої величини значно менше, ніж мала величина для n> = 2. У цьому випадку рівняння (3) може бути апроксимовані наступним чином:
| (4) |
Нашою метою є вибір такого xj +1, щоб воно стало рішенням рівняння (1). Отже, якщо наше попереднє припущення справедливе, xj +1 повинно бути вибрано таким, що. Прирівнявши рівняння (4) до нуля і вирішивши щодо xj +1, отримаємо:
| (5) |
Рівняння (5) називається рівнянням Ньютона - Рафсона. Якщо наше припущення, що призвело до висновку рівняння (5), справедливо, цей алгоритм буде збіжним, але тільки в тому випадку, якщо точка початкового наближення досить близька до точки рішення. Геометрична інтерпретація сходиться методу Ньютона - Рафсона наведена на рис. 1а.
| а) метод сходиться | б) метод не сходиться |
Рис.1. Геометрична інтерпретація методу Ньютона - Рафсона
Однак, якщо точка початкового наближення далека від точки вирішення, то метод Ньютона - Рафсона може не сходитися зовсім. Геометрична інтерпретація не сходиться методу Ньютона - Рафсона наведена на рис. 1б.
Алгоритм
Призначення: пошук рішення рівняння (1)
Вхід:
Початкове наближення x0
Точність (число ітерацій I)
Вихід:
xI - рішення рівняння (1)
Ініціалізація:
calculate f '(x0)
Кроки:
1. repeat:
2. calculate xi using (5)
3. let i = i +1
4. if i> I then break the cycle
end of repeat
Модифікація алгоритму Ньютона для розв'язання системи кількох рівнянь полягає в лінеаризації відповідних функцій багатьох змінних, тобто апроксимації їх лінійною залежністю з допомогою приватних похідних. Наприклад, для нульової ітерації у випадку системи двох рівнянь:
Щоб відшукати точку, відповідну кожної нової ітерації, потрібно дорівняти обидва рівності нулю, тобто вирішити на кожному кроці отриману систему лінійних рівнянь.