Ітераційні методи та оператор стиску.

Метод дихотомії є прикладом ітераційного методу (або ж методу послідовних наближень) розв’язування рівнянь. У цих методах завжди формують послідовність х_n наближень, де кожне наступне обчислюється з попередніх за певним (рекурентним) правилом; наближення х_n збігаються до точного значення кореня рівняння. Але ж найчастіше у таких методах рівняння f (x) = 0 замінюють еквівалентним х = φ(х), де φ(х) – деяка неперервна функція (φ(х) = х – f (x) наприклад). Далі обирають початкове наближення х₀ і послідовно обчислюють наступні наближення: х_k = φ(х_k-1), k = 1,2,…. Якщо послідовність х_k має границю х^*, тобто = х^*, то ця границя буде розв’язком рівняння х = φ(х). Справді, х^* = х_k = φ(х_k-1) = φ( х_k-1) = φ(х^*). Для кожної такої функції φ(х) отримуємо свій ітераційний метод, який іноді називають стаціонарним або методом простої ітерації.

Метод простої ітерації має простий геометричний зміст. Побудуємо графіки функцій y = x і y = φ(х). Абсциса точки перетину графіків цих функцій є коренем рівняння х = φ(х).

в г

Рисунок 1

Довільно вибираємо точку х₀ і проводимо через неї пряму, паралельну осі ординат до перетину з кривою у = φ(х) у точці А₀ (х₀, φ(х₀)). З точки А₀ проведемо пряму, паралельну осі абсцис, до перетину з прямою у = х. В результаті дістанемо точку В₁ з ординатою φ(х₀). Спроектувавши точку В₁ на вісь Ох, знаходимо абсцису х₁ = φ(х₀). Аналогічно через х₁ проводимо пряму, паралельну осі орди­нат, до перетину з кривою у = φ(х) в точці А₁(х₁, φ(х₁)). З точки А₁ проводимо пряму, паралельну осі абсцис, до перетину з прямою у = х в точці В₂(х₂, φ(х₂))), абсциса якої х₂ = φ(х₁) і т.д. В результаті спільні абсциси точок А₁ і В₁, А₂ і В₂, … є послідовними наближеннями х₁, х₂, х₃,... кореня х*.

На рисунку зображено випадки: а) 0 < φ'(х) <1; б) – 1 < φ'(х) <0; в) < φ'(х) > 1; г) φ'(х) < -1.

Якщо │φ'(х)│< 1, то послідовні наближення х_k збігаються до кореня х*, якщо │φ'(х)│>1, то послідовні наближення віддаляються від ньо­го.

Як правило, збіжність наближень забезпечує наступна умова.

Означення 1. Функція φ(х) на відрізку задовольняє умові Ліпшиця, якщо для будь – яких точок х, х′ є │φ(х) – φ(х′)│≤ q│x – x′│, де q – деяке число, яке називають константою Ліпшиця.

За теоремою Лагранжа умова Ліпшиця з константою q буде виконана для функції φ(х) на відрізку , якщо на цьому відрізку існує φ′(х), причому (х є ). Якщо q < 1, то ітераційний процес х_k = φ(х_k-1) на відрізку – це частковий випадок добре відомого з функціонального аналізу оператору стиску.

Означення 2. Нехай R – метричний простір, ρ – відстань (метрика) на цьому просторі, А – оператор, визначений на R. Оператор А називають оператором стиску, якщо існує таке додатне число q < 1, що ρ(Ах, Ах′) < q ∙ ρ(х, х′) для будь – яких х, х′ є R. Точку х є R називають нерухомою точкою оператора А, якщо Ах = х.

Основою для дослідження збіжності ітераційних процесів є наступна теорема Банаха.

Теорема 4 (принцип стискуючих відображень). Якщо оператор стиску А визначений на повному метричному просторі R, то в R він має єдину нерухому точку, до якої збігається ітераційний процес х_k = Ах_k-1 (k = 1,2,…) при будь – якій початковій точці х₀ є R.

Доведення. Нехай х₀ – довільна точка простору R, х_k = Ах_k-1 (k = 1,2,…). Доведемо, що послідовність х_k фундаментальна. Справді,

ρ(х_k+1, х_k) = ρ(Aх_k, Aх_k-1) ≤ qρ(х_k, х_k-1) = ρ(Aх_k-1, Aх_k-2) ≤ q²ρ(х_k-1, х_k-2) ≤ … ≤ q^kρ(х₁, х₀).

Отже, якщо m > k, то, скориставшись правилом трикутника, маємо:

ρ(х_m, х_k) ≤ ρ(х_m, х_k+1) + ρ(х_k+1, х_k) ≤ ρ(х_m, х_k+2) + ρ(х_k+2, х_k+1) + ρ(х_k+1, х_k) ≤ … ≤

ρ(х_m, х_m-1) + … + ρ(х_k+2, х_k+1) + ρ(х_k+1, х_k) ≤ (q^m-1 + … + q^k+1 + q^k)ρ(х₁, х₀) =

= ρ(х₁, х₀) ≤ ρ(х₁, х₀).

Тому для як завгодно малого ε > 0 існує таке натуральне N(ε), що при m > k > N(ε) виконуватиметься нерівність

ρ(х_m, х_k) ≤ ρ(х₁, х₀) ≤ ε. (1)

Це означає, що послідовність х_k фундаментальна. Оскільки метричний простір R повний, то існує границя х_k = х^* є R. Далі: х^* є нерухомою точкою оператора А, тобто Ах^* = х^*. Справді, з ρ(Aх_k, Aх^*) ≤ qρ(х_k, х^*) та ρ(х_k, х^*) → 0 (k → ∞) випливає, що Ах_k = Ах^*. Але Ах_k = х_k+1 → х^*, звідки х^* = Ах^*.

Нарешті доведемо, що х^* – єдина нерухома точка оператора А. Припустимо, що x і y – дві різні нерухомі точки А: Ах = х, Аy = y, ρ(х, y) ≠ 0. Але А – оператор стиску, звідки ρ(х, y) = ρ(Ах, Аy) ≤ qρ(х, y), що неможливо оскільки q < 1. Теорему доведено.

Теорема 5. Нехай рівняння х = φ(х) має корінь х^* і в деякому околі R = {x: │x – х^*│≤ r} цього кореня функція φ(х) задовольняє умові Ліпшиця │φ(х) – φ(х′)│≤ q│x – x′│ з константою Ліпшиця q < 1. Тоді

1) y = φ(х) є стискуючим відображенням на R.

2) R – відрізок ізоляції кореня х^*.

3) Ітераційний процес х_k = φ(х_k-1) на R збігається до х^* при будь – якому початковому х₀.

4) Швидкість цієї збіжності характеризується нерівністю │x_k – x*│ ≤ q^k│x₀ – x*│.

Доведення. 1) Функція φ(х) відображає відрізок R у самого себе: φ(R) R. Справді, якщо х є R, то y = φ(х) також належить R оскільки │y – x*│ = │φ(х) – φ(х*)│ ≤ q│x – x*│ ≤ r. Множина точок відрізка R є повним метричним простором з відстанню ρ(х, х′) = │x – x′│. За умовою теореми ρ(φ(х), φ(х′)) = │φ(х) – φ(х′)│ ≤ q│x – x′│ = q ∙ ρ(х, х′), 0 < q < 1. Отже відображення y = φ(х) є оператором стиску на R за означенням.

2) Тому з принципу стискуючих відображень випливає, що на R існує одна і тільки одна нерухома точка відображення y = φ(х) і за умовою це x*, випливає також і 3).

4) З умови Ліпшиця маємо: │x_k – x*│ = │φ(х_k-1) – φ(х*)│ ≤ q│x_k-1 – x*│ = q│φ(х_k-2) – φ(х*)│ ≤ q²│x_k-2 – x*│ ≤ … ≤ q^k│x₀ – x*│. Теорему доведено.

Отже, послідовність x_k збігається до х^* принаймні із швидкістю геометричної прогресії із знаменником q: чим менше q, тим збіг швидше.