Ogólny opis metody iteracji prostej Banacha
Metoda iteracji prostej Banacha składa się z dwóch etapów.- 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). - Wybieramy przybliżenie x0. Kolejne iteracje obliczamy ze wzoru xn+1 = g(xn)
Szczegółowy opis metody iteracji prostej dla rozpatrywanej funkcji
- Najpierw należy znaleźć funkcję g(x), przekształcając równanie 0 = x3 - 3x - 20 do postaci x = g(x)
- Po przekształceniach uzyskujemy np. jedną z poniższych funkcji:
- Należy wybrać taką funkcję g(x), aby zapewniała zbieżność kolejnych iteracji, tzn. |xn+1 - xn| < |xn - xn-1| czyli kolejna różnica powinna być mniejsza niż poprzednia.
Tego warunku nie spełniają funkcje g1(x), g2(x) i g3(x) - pomijamy tu szczegółowe obliczenia. Tylko funkcja g4(x) gwarantuje spełnienie tego warunku, natomiast sama funkcja g4(x) ma inne ograniczenia, gdyż nie dla każdego x zachodzi x=g4(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ę g4(x) do obliczeń mimo pewnych zastrzeżeń. - Należy po wybraniu przybliżenia x0 policzyć x1 = g(x0) ... itd. dla kolejnych xn, za każdym razem sprawdzając czy |xn - xn-1| < epsilon.
Jeśli ten warunek osiągniemy to przybliżonym miejscem zerowym funkcji f(x) jest ostatnio policzone xn.
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 D0 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 x0 należącego do D0.
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 x0, tzn. taka, że |g(g(x)) - g(x)| < |g(x) - x| dla x postaci gk(x0), k=0,1,...
- x0 - początkowe przybliżenie pierwiastka równania x=g(x).
- epsilon - przyjęta dokładność obliczeń (epsilon>0)
- xbież przybliżona wartość miejsca zerowego funkcji f(x), spełniającego warunek: |xbież - xpoprz| <= epsilon
- Pobierz wartość pierwszego przybliżenia x0. Podstaw xpoprz=x0.
- Oblicz xbież = g(xpoprz), np. xbież = sqrt(3+20/xpoprz)
- Policz różnicę między xbież i xpoprz.
- Jeśli |xbież - xpoprz| <= epsilon zakończ obliczenia - xbież jest szukanym miejscem zerowym funkcji, wpp podstaw jako nowe xpoprz = xbież. Wróć do polecenia 2.
Brak komentarzy:
Prześlij komentarz