Numerik I Wintersemester 97/98 Dr. Walter Oevel 4. 11. 1997

Ü b u n g s b l a t t 3

Aufgabe 7: (Eine Banach-Iteration) Löse x = exp(−x)/2 =: Φ(x). Man überzeuge sich graphisch, daß genau eine Lösung x^{∗} ∈ A := [0, 1] existiert.

a) Zeige Φ(A) ⊂ A und bestimme eine Kontraktionskonstante. (2)

b) Nach wievielen Schritten x_{i} = Φ(x_{i−1}) mit dem Start x_{0} = 0 ist eine absolute Genauigkeit |x_{i} − x^{∗}| ≤ 10^{−10} garantiert? (3)

c) Für x_{0} = 0: liste x_{1}, …, x_{10} mit den a priori und a posteriori Abschätzungen auf. (4)

Aufgabe 8: (Zur Fehlerabschätzung bei Banach-Iterationen: beweise Satz 3.10) Der Fixpunkt x^{∗} = Φ(x^{∗}) einer Kontraktion Φ soll bestimmt werden. Es sei Φ̃ die mit dem Auswertungsfehler |Φ̃(x)−Φ(x)| ≤ |ΔΦ| behaftete numerische Iterationsfunktion. Man bricht die Iteration x̃_{i} = Φ̃(x̃_{i−1}) ab, sobald der Folgenpunkt in der absoluten Genauigkeit ϵ ≪ 1 “stationär” wird, d.h. |x̃_{i} − x̃_{i−1}| ≤ ϵ gilt. Zeige, daß x̃_{i} den Fixpunkt bis auf die absolute Genauigkeit

|x̃_{i} − x^{∗}| ≤ \frac{k ϵ + |ΔΦ|}{1 − k}

bestimmt, wobei k eine Kontraktionskonstante von Φ ist. (4)

Anleitung: x̃_{i} −x^{∗} = Φ̃(x̃_{i−1})−Φ(x̃_{i−1})+Φ(x̃_{i−1})−Φ(x^{∗}) , |Φ(x̃_{i−1})−Φ(x^{∗})| ≤ k |x̃_{i−1} −x̃_{i} +x̃_{i} −x^{∗}| . Anmerkung: Die typische (nicht exakte) Vorgehensweise in der Praxis ist wie folgt. Ohne Fehlerbetrachtungen wird einfach mit einem geeigneten Startpunkt iteriert, man beobachtet die für die geforderte Genauigkeit signifikanten Stellen der Folgenglieder und bricht ab, sobald sich diese nicht mehr ändern. Warum ist dies bei linear konvergierenden Verfahren zweifelhaft, bei “höheren” Verfahren (sehr kleines k) mit entsprechender Vorsicht jedoch durchaus akzeptabel?

Aufgabe 9: (Konvergenzbeschleunigung nach Aitken) Bei linear konvergierenden Banach-Iterationen werden Zahlenfolgen (x_{i}) konstruiert, die in der Form x_{i+1} − x^{∗} ≈ k (x_{i} − x^{∗}) auf den Grenzwert x^{∗} zustreben. Aus gegebenen Werten x_{i}, x_{i+1} und x_{i+2} läßt sich mit x_{i+1} − x^{∗} ≈ k (x_{i} − x^{∗}) , x_{i+2} − x^{∗} ≈ k (x_{i+1} − x^{∗}) der Wert von x^{∗} “berechnen”.

a) Zeige, daß sich die zugeordnete Folge y_{i} = x_{i} − \frac{(x_{i+1} − x_{i})^{2}}{x_{i+2} − 2 x_{i+1} + x_{i}} von Schätz-

werten ergibt. (2)

b) Diese Schätzwerte konvergieren in der Regel “schneller“ gegen den Grenzwert x^{∗}. Beweise die folgende Aussage: (5)

Die Folge (x_{i}) konvergiere gegen x^{∗}, für die “lokalen Kontraktionskonstanten” k_{i} := (x_{i+1} − x^{∗})/(x_{i} − x^{∗}) gelte k := lim_{i→∞} k_{i} ∈ (−1, 1) . Dann existiert die zugeordnete “Aitken-Folge” (y_{i}) für hinreichend große Indizes und es gilt

lim_{i→∞} \frac{y_{i} − x^{∗}}{x_{i} − x^{∗}} = 0 .

Anleitung: zeige (y_{i} − x^{∗})/(x_{i} − x^{∗}) = k_{i}(k_{i+1} − k_{i})/(k_{i}k_{i+1} − 2k_{i} + 1) . Anmerkung: Mit den auf Folgen wirkenden Differenzenoperatoren

Δ : (x_{i}) → (x_{i+1} − x_{i}) , Δ^{2} : (x_{i}) → Δ(Δ(x_{i})) = (x_{i+2} − 2 x_{i+1} + x_{i})

läßt sich die Aitken-Folge als y_{i} = x_{i} − (Δ(x_{i}))_{i}^{2}/(Δ^{2}(x_{i}))_{i} darstellen. Diese Konvergenzbeschleunigung wird daher auch als Δ^{2}-Verfahren bezeichnet.

Abgabe: Mittwoch, 12. 11. 97, in den Übungsgruppen