Метод дотичних(Ньютона-Рафсона)

Матеріал із MachineLearning.

Зміст

Нехай задано функцію дійсного змінного. Потрібно знайти коріння рівняння

Завдання знаходження коренів рівняння (1) зазвичай вирішується у 2 етапи. У першому етапі проводиться відділення коренів, тобто. виділення відрізків, що містять лише один корінь. На другому етапі, використовуючи початкове наближення, будується ітераційний процес, що дозволяє уточнити значення кореня, що відшукується.

Виклад методу

Метод дотичних (Ньютона-Рафсона)

Нехай на відрізку існує єдиний корінь рівняння (1):

а існує, безперервна і відмінна від нуля на . Перепишемо (2) наступним чином:

і застосуємо до цього виразу формулу Лагранжа:

Замінимо на , а - і отримаємо формулу ітераційного процесу:

Метод дотичних має (коли сходиться) квадратичну швидкість збіжності:

Модифікований метод дотичних

Якщо ми хочемо уникнути обчислення похідної на кожному кроці, то можна взяти замість де - початкове наближення:

На відміну від звичайного методу дотичних, модифікованому методі надається менше вимог до вибору початкового наближення, а так само гарантовано відсутність поділу на нуль, якщо

Однак модифікований метод має один суттєвий недолік: лінійну швидкість збіжності:

Геометрична інтерпретація

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

Збіжність методу

Зауважимо, що метод дотичних є окремим випадком методу простих ітерацій.

Метод простих ітерацій сходиться тоді і лише тоді, коли

Підставимо востання умова вираз для g(x) (4) і отримаємо умову збіжності методу дотичних:

Сформулюємо теорему про квадратичну швидкість збіжності методу дотичних:

Теорема.Нехай - простий речовий корінь рівняння, а функція - двічі диференційована в деякій околиці, причому перша похідна ніде не звертається в нуль.

Тоді, дотримуючись позначень

при виборі початкового наближення з тієї ж околиці такого, що

буде сходитися до , причому для похибки на k-му етапі буде справедлива оцінка:

Числовий приклад

Розглянемо функцію За допомогою методу (3) знайдемо корінь рівняння Вихідний код програми, яка шукає корінь рівняння методом дотичних, викладено у розділі "Файли".

Візьмемо як початкове наближення і точність У результаті за 5 ітерацій отримаємо корінь

Рекомендації програмісту

Критерій зупинки

Як правило, беруть один із наступних критеріїв зупинки:

1. - значення функції на даній ітерації поменшало заданого ε.
2. - Зміна х k в результаті ітерації стало менше заданого ε.

Помилки округлення

У методі дотичних, як і інших ітераційних методах розв'язання рівнянь, помилка округленняне накопичується. Загальна помилка округлення дорівнює помилці, що виникла в останній ітерації, і не залежить від арифметичних операцій, що виконувались у попередніх ітераціях.

Висновок

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

---