4037602950

2 1. Wiadomości wstępne

1.2 Iteracja

Jedną z podstawowych operacji, często stosowanych w metodach numerycznych, jest iteracja (łac. iteratio - powtarzanie). Formalnie iteracja jest powtarzaniem pewnej ustalonej sekwencji wyrażeń.

W celu przybliżenia pojęcia iteracji rozważymy rozwiązywanie równania w ogólnej postaci:

x = f(x).    (1.1)

Zakładamy, że / (x) jest funkcją różniczkowalną, a jej wartości można obliczyć dla dowolnej wartości zmiennej rzeczywistej x. Metoda iteracyjna polega na wybraniu wartości początkowej aro i wyliczeniu wartości funkcji:

xi = f(x o).    (1.2)

Następnie obliczoną wartość ari wykorzystujemy do obliczenia wartości X2 i następnych:

X2 = f(x l), *3 = f(x ₂),

Zi+1 = /(i i)-

Poszczególne wyliczenie Zj+i nazywamy iteracją. W procesie iteracji otrzymujemy ciąg wartości Xi. Taki ciąg może być zbieżny do wartości granicznej:

}(1-3)

Mówimy, że dla x = a, spełnione jest nasze równanie. W procesie iteracji zakładamy, że wraz ze wzrostem i, wzrasta dokładność rozwiązania. Zazwyczaj rozwiązania są asymptotyczne, nie możemy obliczać ciągu iteracyjnego w nieskończoność. Zawsze jest pytanie, kiedy należy przerwać proces iteracji. Odpowiedź jest prosta -przerywamy proces iteracji, gdy osiągniemy zakładaną dokładność. Ustalenie „zakładanej dokładności” nie jest zadaniem trywialnym. Na Rysunku 1.1 pokazana jest interpretacja geometryczna metody rozwiązania naszego równania (1.1). Pierwiastek równania (1.1) otrzymany jest jako punkt przecięcia się krzywej y = f(x) oraz prostej y — x. Rozpoczynamy proces iteracji wybierając punkt o współrzędnych (xo,f(xo)). Obliczamy kolejny punkt x\ — f(x0). Z Rysunku 1.1 widzimy wyraźnie, że metoda jest zbieżna, w kolejnych krokach iteracyjnych zbliżamy się monotonicznie do szukanego rozwiązania. Nie zawsze proces iteracyjny jest zbieżny. Na rysunku 1.2 pokazano przykład iteracji rozbieżnej. W trakcie procesu iteracyjnego, kolejne wartości oddalają się coraz wyraźniej od wartości prawdziwej rozwiązania równania (1.1).

Metodę iteracyjną zilustrujemy klasycznym przykładem wyliczania pierwiastka kwadratowego. Zgodnie z tradycją, wynalezienie tej metody przypisujemy I. Newtonowi. Równanie kwadratowe:

(1-4)

x — a,