Метод простих ітерацій

Постановка задачі

Нехай є функція.
Потрібно знайти корінь цієї функції: такий при якому
Рішення необхідно знайти чисельно, тобто для реалізації на ЕОМ. Для вирішення цього завдання пропонується використовувати метод простих ітерацій.

Метод простих ітерацій в загальному вигляді

Замінимо вихідне рівняння на еквівалентну, і будемо будувати ітерації за правилом ">. Таким чином метод простої ітерації - це однокроковий ітераційний процес. Для того, що б почати цей процес, необхідно знати початкове наближення. З'ясуємо умови збіжності методу і вибір початкового наближення.

Збіжність методу простих ітерацій

Метод сходиться, якщо при послідовність <> має межу.
Позначимо околицях точки радіуса, тобто.
Теорема 1. Якщо Липшиц-неперервна з константою на, тобто виконується

при цьому якщо також виконано

має єдине рішення на і метод простої ітерації сходиться до вирішення при будь-якому виборі початкового наближення Так само справедлива оцінка: рівняння не має інших рішень і метод простої ітерації сходиться до вирішення при

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

Розглянемо графік функції. Це озночает, що рішення рівняння і - це точка перетину з прямою:

І наступна ітерація "> - це координата перетину горизонтальної прямої точки з прямою.

З малюнка наочно видно вимога збіжності. Чим ближче похідна до, тим швидше сходиться алгоритм. Залежно від знака похідної поблизу рішення наближення можуть будується по різному. Якщо, то кожне наступне наближення будується з іншого боку від кореня:

метод релаксації

Так як для збіжності методу дуже важливий вибір функції, її зазвичай беруть виду.

Де не змінює знака на відрізку, на якому шукається корінь функції.
Покладемо і розглянемо метод в цьому випадку.
Тоді отримаємо метод 'релаксації':

для якого, і метод сходиться за умови

Нехай в деякій околиці кореня виконуються умови

Тоді метод релаксації сходиться при

вибір параметра

Оцінимо похибка методу релаксації