1.4.4 Metoda iteracji prostej Banacha

Ogólny opis metody iteracji prostej Banacha

Metoda iteracji prostej Banacha składa się z dwóch etapów.

1. Najpierw równanie f(x) = 0 przekształcamy do równoważnej postaci x = g(x)
   (takie przekształcenie jest zawsze wykonalne (np. dodając x do obu stron równania f(x)=0) i zazwyczaj można je wykonać kilkoma sposobami).
2. Wybieramy przybliżenie x₀. Kolejne iteracje obliczamy ze wzoru x_n+1 = g(x_n)

Szczegółowy opis metody iteracji prostej dla rozpatrywanej funkcji

1. Najpierw należy znaleźć funkcję g(x), przekształcając równanie 0 = x³ - 3x - 20 do postaci x = g(x)
2. Po przekształceniach uzyskujemy np. jedną z poniższych funkcji:
   
   
3. Należy wybrać taką funkcję g(x), aby zapewniała zbieżność kolejnych iteracji, tzn. |x_n+1 - x_n| < |x_n - x_n-1| czyli kolejna różnica powinna być mniejsza niż poprzednia.
   Tego warunku nie spełniają funkcje g₁(x), g₂(x) i g₃(x) - pomijamy tu szczegółowe obliczenia. Tylko funkcja g₄(x) gwarantuje spełnienie tego warunku, natomiast sama funkcja g₄(x) ma inne ograniczenia, gdyż nie dla każdego x zachodzi x=g₄(x) <-> f(x)=0. Należy z obliczeń wyłączyć -20/3 < x oraz x < =0. Po wstępnym zbadaniu funkcji f(x) wiemy, że najlepiej poszukiwać jej miejsca zerowego w zakresie x należącym do przedziału [1, 5], zatem można przyjąć funkcję g₄(x) do obliczeń mimo pewnych zastrzeżeń.
4. Należy po wybraniu przybliżenia x₀ policzyć x₁ = g(x₀) ... itd. dla kolejnych x_n, za każdym razem sprawdzając czy |x_n - x_n-1| < epsilon.
   Jeśli ten warunek osiągniemy to przybliżonym miejscem zerowym funkcji f(x) jest ostatnio policzone x_n.

Z czego to wynika?

Metoda iteracji prostej należy do tzw. metod iteracyjnych stałopunktowych. To podejście do wyznaczania miejsca zerowego jest oparte na metodzie Banacha.
Poniżej wykresu wykazuję, że istnieje stała 0 <= L <= 1 np. L=0,6 taka, że
|g(x) - g(y)| <= L * |x -y| dla każdego x, y należącego do D₀ czyli g(x) jest odwzorowaniem zwężającym.
Zgodnie z twierdzeniem Banacha o kontrakcji równanie x=g(x) ma dokładnie jedno rozwiązanie x^*, oraz

dla dowolnego przybliżenia początkowego x₀ należącego do D₀.
Ponieważ równanie x=g(x) jest równaniem równoważnym (tzn. ma te same rozwiązania) co równanie f(x), zaś x dla którego zachodzi równość x=g(x) jest punktem stałym odwzorowania g, więc znajdując rozwiązanie x^* równania x=g(x) znajdujemy jednocześnie rozwiązanie równania f(x)=0.
Na stronie Numerki autor przedstawił ilustację graficzną prezentującą dwa warunki gdy metoda iteracj prostej jest zbieżna i rozbieżna.

Specyfikacja

Dane:

• funkcja g(x) zbieżna dla zadanego punktu x₀, tzn. taka, że |g(g(x)) - g(x)| < |g(x) - x| dla x postaci g^k(x₀), k=0,1,...
• x₀ - początkowe przybliżenie pierwiastka równania x=g(x).
• epsilon - przyjęta dokładność obliczeń (epsilon>0)

Uwaga. g(x) jest równaniem równoważnym otrzymanym po zastąpieniu równania wyjściowego f(x) = 0 przez x=g(x) Wyniki:

• x_bież przybliżona wartość miejsca zerowego funkcji f(x), spełniającego warunek: |x_bież - x_poprz| <= epsilon

Algorytm:

1. Pobierz wartość pierwszego przybliżenia x₀. Podstaw x_poprz=x₀.
2. Oblicz x_bież = g(x_poprz), np. x_bież = sqrt(3+20/x_poprz)
3. Policz różnicę między x_bież i x_poprz.
4. Jeśli |x_bież - x_poprz| <= epsilon zakończ obliczenia - x_bież jest szukanym miejscem zerowym funkcji, wpp podstaw jako nowe x_poprz = x_bież. Wróć do polecenia 2.