128

Kapitel 8

Banach-Iteration

Aus Zeitgründen ist dieses Kapitel nicht ”offizieller“ Bestandteil der Vorlesung (sprich: ist nicht prüfungsrelevant). Es wird jedoch wärmstens empfohlen, dieses Kapitel in Heimarbeit zu lesen und zu verstehen. Speziell gibt es kein Physikerdasein ohne Kenntnis des Newton-Verfahrens (Abschnitt 8.2).

8.1 Der Banachsche Fixpunktsatz

Wir definieren den Begriff einer kontrahierenden Abbildung:

Definition 8.1:

Eine Abbildung Φ : A ⊂ ℂ → ℂ heißt ”Kontraktion in A“, wenn eine ”Kontraktionskonstante“ k ∈ [0, 1) existiert, so dass für alle x, y ∈ A gilt:

|Φ(x) − Φ(y)| ≤ k · |x − y|.

Zur Namensgebung: der Abstand zweier Bildpunkte |Φ(x) − Φ(y)| einer Kontraktion ist stets kleiner als der Abstand der Urbildpunkte |x − y|.

Bemerkung 8.2: Kontraktionen sind automatisch stetig: Für jede konvergierende Folge (z_{n}) konvergiert Φ(z_{n}), und es gilt

lim_{n→∞} Φ(z_{n}) = Φ( lim_{n→∞} z_{n}).

Dies ist leicht einzusehen. Sei z^{∗} der Grenzwert von (z_{n}). Die Kontraktionseigenschaft liefert

0 ≤ |Φ(z_{n}) − Φ(z^{∗})| < |z_{n} − z^{∗}|.

Wegen der Konvergenz z_{n} → z^{∗} ist die rechte Seite eine reelle Nullfolge. Mit Satz 2.17 folgt, dass |Φ(z_{n}) − Φ(z^{∗})| eine Nullfolge ist, was die Konvergenz Φ(z_{n}) → Φ(z^{∗}) bedeutet.

Der folgende wichtige Fixpunktsatz für kontrahierende Abbildungen geht auf Stefan Banach (polnischer Mathematiker, 1892 – 1945) zurück. Er setzt neben der Kontraktionseigenschaft als wichtige Annahme voraus, dass die Kontraktion ihren Definitionsbereich in sich selbst abbildet:

Satz 8.3: (”BFS“: der Banachsche Fixpunktsatz)

Sei Φ : A → A eine Kontraktion in einer abgeschlossenen Menge A ⊂ ℂ mit einer Kontraktionskonstanten k < 1 . Dann

a) existiert ein eindeutig bestimmter Fixpunkt z^{∗} = Φ(z^{∗}) ∈ A,

b) konvergiert jede Folge z_{n+1} = Φ(z_{n}) mit beliebigem Startwert z_{0} ∈ A gegen z^{∗},

c) gelten für jede solche Folge die Abschätzungen

|z_{n} − z^{∗}| ≤ \frac{k}{1 − k} · |z_{n} − z_{n−1}| ≤ \frac{k^{n}}{1 − k} · |z_{1} − z_{0}|.
“a posteriori”  “a priori”

Vom (wiederum sehr technischen) Beweis braucht man eigentlich nur zu wissen, dass man zeigen kann, dass die per z_{n+1} = Φ(z_{n}) konstruierten Folgen Cauchy– Folgen sind. Der Fixpunkt ergibt sich dann über den Grenzwert der Folgen, dessen Existenz mittels Satz 2.28 gesichert ist. Aus der Kontraktionseigenschaft folgt die Eindeutigkeit (alle Folgen konvergieren gegen denselben Grenzwert). Für technisch Interessierte ist der Beweis der Vollständigkeit halber angegeben:

Beweis: Zeige: (z_{n}) ist Cauchy-Folge.

\begin{aligned}|z_{n+m} − z_{n}| & = & |z_{n+m} − z_{n+m−1} + z_{n+m−1} ∓ ⋯ − z_{n+1} + z_{n+1} − z_{n}| \\ & ≤ & |z_{n+m} − z_{n+m−1}| + |z_{n+m−1} − z_{n+m−2}| + ⋯ + |z_{n+1} − z_{n}| \end{aligned}

für jedes n, m ≥ 0. Aus |z_{j} −z_{j−1}| = |Φ(z_{j−1})−Φ(z_{j−2})| ≤ k ·|z_{j−1} −z_{j−2}|, d.h.,

|z_{j} − z_{j−1}| ≤ k · |z_{j−1} − z_{j−2}| ≤ k^{2} · |z_{j−2} − z_{j−3}| ≤ …

folgt

|z_{n+m} − z_{n}| ≤ k^{m−1} · |z_{n+1} − z_{n}| + k^{m−2} · |z_{n+1} − z_{n}| + ⋯ + |z_{n+1} − z_{n}|

= (1 + k + k^{2} + ⋯ + k^{m−1}) · |z_{n+1} − z_{n}| = \frac{1 − k^{m}}{1 − k} · |z_{n+1} − z_{n}|

≤ \frac{|z_{n+1} − z_{n}|}{1 − k} ≤^{(#)} \frac{k |z_{n} − z_{n−1}|}{1 − k} ≤ \frac{k^{2} |z_{n−1} − z_{n−2}|}{1 − k} ≤ ⋯ ≤^{(##)} \frac{k^{n} |z_{1} − z_{0}|}{1 − k}.

Mit k^{n} → 0 folgt die Cauchy-Eigenschaft. Es existiert somit ein Grenzwert z^{∗}. Mit z_{0} ∈ A und Φ : A → A folgt z_{n} ∈ A ⇒ z^{∗} ist Häufungspunkt von A ⇒ z^{∗} ∈ A (abgeschlossen). Da Φ im Sinne von Bemerkung 8.2 stetig ist:

z^{∗} = lim_{n→∞} z_{n+1} = lim_{i→∞} Φ(z_{n}) = Φ( lim_{n→∞} z_{n}) = Φ(z^{∗}) .

Eindeutigkeit: für einen weiteren Fixpunkt z^{∗∗} ≠ z^{∗} folgt der Widerspruch

|z^{∗} − z^{∗∗}| = |Φ(z^{∗}) − Φ(z^{∗∗})| ≤ k · |z^{∗} − z^{∗∗}| < |z^{∗} − z^{∗∗}| .

Die Abschätzungen c) ergeben sich aus (#) und (##):

lim_{m→∞} |z_{n+m} − z_{n}| = |z^{∗} − z_{n}| ≤^{(#)} \frac{k}{1 − k} |z_{n} − z_{n−1}| ≤^{(##)} \frac{k^{n}}{1 − k} |z_{1} − z_{0}| .

Q.E.D.

Interpretation und Anwendung 8.4:

Eine Gleichung f(z) = 0 sei zu lösen. Der BFS gibt ein Rezept, wie man Näherungen für die Lösung konstruieren kann:

1) Formuliere die Gleichung f(z) = 0 in ein äquivalentes Fixpunktproblem z = Φ(z) um.

2) Ist Φ kontrahierend auf einer Umgebung A der Lösung und bildet Φ diese Menge A auf sich selbst ab, so läßt sich der BFS anwenden: wähle einen beliebigen Punkt z_{0} ∈ A und iteriere z_{n+1} = Φ(z_{n}). Diese Folge konvergiert gegen eine Lösung des Fixpunktproblems und damit gegen eine Lösung des Ausgangsproblems f(z) = 0.

3) Hat man durch Abschätzungen eine Kontraktionskonstante k für die Menge A gefunden, kann man mit den a-priori- bzw. a-posteriori-Abschätzungen bestimmen, wie weit man noch von der Lösung entfernt ist und abbrechen, sobald eine vorgegebene Zielgenauigkeit erreicht ist.

Mit der a-priori-Abschätzung kann man aus dem Startpunkt z_{0} und dem nächsten Punkt z_{1} sofort ermitteln, wie oft man höchstens iterieren muß, um die Zielgenauigkeit zu erreichen (die Iterationswerte werden dafür nicht benötigt). Nachdem die Iteration durchgeführt worden ist und Zahlenwerte für z_{n} vorliegen, kann man a-posteriori abschätzen, welche Approximationsgenauigkeit nun wirklich erreicht ist (die a-posteriori-Abschätzung ist prinzipiell genauer als die a-priori-Abschätzung).

8.2 Das Newton-Verfahren

Hier eine für die Praxis besonders wichtige Anwendung des BFS. Es geht darum, numerische Approximationen von Nullstellen x^{∗} einer Funktion zu konstruieren. Die prinzipielle Idee ist, eine Zahlenfolge (x_{n}) zu konstruieren, die gegen einen Grenzwert x^{∗} mit f(x^{∗}) = 0 konvergiert. Für hinreichend großes n bricht man die Iteration ab und akzeptiert x_{n} als eine Approximation von x^{∗}. Zunächst hat man die Aufgabe, ein Nullstellenproblem f(x^{∗}) = 0 in ein Fixpunktproblem x^{∗} = Φ(x^{∗}) umzuformulieren, um den BFS anwenden zu können.

Bemerkung 8.5: Es gibt viele Wege, eine gegebene Gleichung f(x) = 0 in eine Fixpunktgleichung x = Φ(x) umzuformen, z.B.

Φ(x) = x − g(x) · f(x)

mit einer (praktisch beliebig wählbaren) Funktion g(x). Ist f(x) differenzierbar und ist die Lösung im Sinne von Definition 1.24 eine einfache Nullstelle, so ist g(x) = 1/f′(x) eine ausgezeichnete Wahl. Die Iteration lautet dann

x_{n+1} = Φ(x_{n}) = x_{n} − \frac{f(x_{n})}{f′(x_{n})} (das ”Newton-Verfahren“).

Es gibt folgende einfache geometrische Interpretation des Newton-Verfahrens. Sei x_{n} ein Approximation einer Nullstelle von f(x). Ersetze f(x) in einer Umgebung von x_{n} durch die Tangente

t(x) = f(x_{n}) + (x − x_{n}) · f′(x_{n}).

Die Nullstelle der Tangente ist: t(x) = 0 ⇒ x = x_{n} − \frac{f(x_{n})}{f′(x_{n})}, also:

Der Newton-Nachfolger x_{n+1} = x_{n} − f(x_{n})/f′(x_{n}) von x_{n} ist die Nullstelle der Tangente von f am Punkt x_{n}.

Hier eine Beispiel-Graphik (mit MuPAD 3.0) zur Demonstration:

>> f:= x -> x^4 - 2: x0:= 1.5:
>> plot(plot::Function2d(f(x), x = 1.1..1.6, Color = RGB::Red),
        plot::Function2d(f(x0) + (x - x0)*f'(x0),
                         x = x0 - f(x0)/f'(x0) .. x0,
                         Color = RGB::Black),
        plot::Line2d([x0, 0], [x0, f(x0)], Color = RGB::Black),
        TicksNumber = None,
        XTicksAt = [x0 = "x[n]", x0 - f(x0)/f'(x0) = "x[n+1]"],
        Height = 4*unit::cm, Width = 8*unit::cm)

Hier einige numerische Werte bei der Berechnung von \sqrt[4]{2} durch Lösen von f(x) = x^{4} − 2 = 0:

>> f:= x -> float(x^4 - 2): x0:= 1.5:
>> Phi:= x -> x - f(x)/f'(x):
>> x0 := 1.5
                              1.5
>> x1 := Phi(x0)
                          1.273148148
>> x2 := Phi(x1)
                          1.19714982
>> x3 := Phi(x2)
                          1.189285812
>> x4 := Phi(x3)
                          1.189207123
>> x5 := Phi(x4)
                          1.189207115

Bemerkung 8.6: Man kann zeigen, dass es immer eine (eventuell kleine) Umgebung A einer Nullstelle von f gibt, auf der Φ eine Kontraktion ist und für die Φ(A) ⊂ A gilt. Damit gilt der BFS auf einer (leider oft nicht konkret bekannten) Umgebung einer Lösung, und es gilt:

Für hinreichend genaue Startwerte x_{0} dicht bei einer Lösung x^{∗} von f(x) = 0 konvergiert die Newton-Folge x_{n+1} = x_{n} − f(x_{n})/f′(x_{n}) gegen x^{∗}.

Bei einfachen Nullstellen ist die Konvergenz beim Newton-Verfahren sehr schnell, da die Kontraktionskonstanten auf kleinen Umgebungen der Lösung prinzipiell sehr klein sind. Gilt f′(x^{∗}) ≠ 0 an der Nullstelle x^{∗}, so erhält man durch Taylor-Entwicklung um x^{∗}:

f(x) = \underbrace{f(x^{∗})}_{=0} +f′(x^{∗}) · (x − x^{∗}) + \frac{f′′(x^{∗})}{2} · (x − x^{∗})^{2} + …,

134 KAPITEL 8. BANACH-ITERATION

f′(x) = f′(x^{∗}) + f′′(x^{∗}) · (x − x^{∗}) + …,

⇒ x_{n+1} − x^{∗} = x_{n} − x^{∗} − \frac{f′(x^{∗}) · (x_{n} − x^{∗}) + \frac{f′′(x^{∗})}{2} · (x_{n} − x^{∗})^{2} + …}{f′(x^{∗}) + f′′(x^{∗}) · (x_{n} − x^{∗}) + …}

= (x_{n} − x^{∗}) · (1 − \frac{f′(x^{∗}) + \frac{f′′(x^{∗})}{2} · (x_{n} − x^{∗}) + O((x − x^{∗})^{2})}{f′(x^{∗}) + f′′(x^{∗}) · (x_{n} − x^{∗}) + …})

= (x_{n} − x^{∗}) · \frac{−\frac{f′′(x^{∗})}{2} · (x_{n} − x^{∗}) + O((x − x^{∗})^{2})}{f′(x^{∗}) + f′′(x^{∗}) · (x_{n} − x^{∗}) + …}

= (x_{n} − x^{∗})^{2} · \frac{−\frac{f′′(x^{∗})}{2} + O(x_{n} − x^{∗})}{f′(x^{∗}) + O(x_{n} − x^{∗})}

≈ − (x_{n} − x^{∗})^{2} · \frac{f′′(x^{∗})}{2 · f′(x^{∗})}.

Ist der Approximationsfehler x_{n} − x^{∗} erst einmal klein, so wird er durch Quadrieren sehr schnell sehr klein (man nennt dies ”quadratische Konvergenz“).

Beispiel 8.7: In einer Softwareumgebung gebe es die Grundarithmetik, aber keine Wurzelfunktion. Um diese zu implementieren, soll die Gleichung y^{2} = b für gegebenes positives b ∈ ℝ nach y gelöst werden. Mittels Division durch eine geeignete 4er-Potenz kann b auf das Interval [1, 4] transformiert werden (in Binärdarstellung kostet dies nichts). Sei nun a = b/4^{n} ∈ [1, 4]. Ist x ∈ [1, 2] eine Lösung von x^{2} = a, so ist y = 2^{n} · x die gesuchte Lösung des Ausgangsproblems y^{2} = b.

Das verbleibende Problem ist also, ein x ∈ [1, 2] zu finden, das das Nullstellenproblem f(x) = x^{2} − a = 0 mit a ∈ [1, 4] erfüllt. Hierzu soll das Newton–Verfahren benutzt werden. Betrachte also

Φ(x) = x − \frac{f(x)}{f′(x)} = x − \frac{x^{2} − a}{2 · x} = \frac{x^{2} + a}{2 · x} = \frac{1}{2} · (x + \frac{a}{x}).

Die entsprechende Iteration lautet also

x_{n+1} = \frac{1}{2} · (x_{n} + \frac{a}{x_{n}} ).

Das Verfahren konvergiert sehr schnell gegen x^{∗} = \sqrt{a}. Beispiel: a = 2, x_{0} = 1.5:

x_{0} = 1.5, x_{1} = 1.416666666..., x_{2} = 1.414215686...,
x_{3} = 1.414213562..., x_{4} = 1.414213562..., …

Die folgende Analyse ist wiederum sehr technisch und an technisch Interessierte addressiert:

Analyse: betrachte das Intervall A = [\sqrt{a}, \frac{1+a}{2}], das die Lösung \sqrt{a} enthält. (Dieses Intervall fällt hier vom Himmel.) Die folgenden Rechnungen zeigen, dass dieses Intervall

8.2. DAS NEWTON-VERFAHREN 135

in der Tat so ist, dass der BFS angewendet werden kann.

Es ist zunächst zu zeigen, dass Φ(A) ⊂ A gilt. In Erinnerung an die Schule berechnen wir dazu

Φ′(x) = \frac{1}{2} · (1 − \frac{a}{x^{2}} ) = \frac{x^{2} − a}{2 · x^{2}} ≥ 0

für x ∈ [\sqrt{a}, \frac{1+a}{2}]. Die Funktion ist also in diesem Bereich monoton steigend, und damit gilt

Φ(\sqrt{a}) = \sqrt{a} ≤ Φ(x) ≤ Φ(\frac{1 + a}{2}) = \frac{1 + a}{4} + \frac{a}{1 + a} ≤ \frac{1 + a}{2}

für alle x ∈ [\sqrt{a}, \frac{1+a}{2}]. Als Kontraktionskonstante auf A schätzt man ab:

|Φ(x) − Φ(y)| = \frac{1}{2} · |x + \frac{a}{x} − y − \frac{a}{y}| = \frac{1}{2} · |x − y − \frac{a · (x − y)}{x · y}|

= \frac{|x − y|}{2} · |1 − \frac{a}{x · y} | = \frac{|x − y|}{2} · (1 − \frac{a}{x · y} ) ≤ \frac{|x − y|}{2} · (1 − \frac{a}{(\frac{a+1}{2})^{2}} )

= |x − y| · \frac{1}{2} · (\frac{a − 1}{a + 1})^{2}.

Also, in Abhängigkeit von a ist

k = \frac{1}{2} · (\frac{a − 1}{a + 1})^{2}

eine Kontraktionskonstante für Φ über A. Für alle a ∈ [1, 4] gilt k ≤ 0.18, d.h., Φ ist auf A in der Tat eine Kontraktion.

Speziell, für a = 2 ist k = 1/18 ≈ 0.0555 …. Starten wir mit x_{0} = 3/2, so ergibt sich x_{1} = 17/12 und die a-priori-Abschätzung liefert

|x_{n} − \sqrt{2}| ≤ \frac{k^{n}}{1 − k} · |x_{0} − x_{1}| = \frac{3}{34 · 18^{n}} .

Nach n = 5 Schritten ergibt sich beispielsweise

|x_{5} − \sqrt{2}| ≤ 4.7 · 10^{−8},

d.h., x_{5} beschreibt garantiert die ersten 7 bis 8 Dezimalstellen von \sqrt{2} korrekt. (In Wirklichkeit ist x_{5} schon wesentlich genauer, aber mehr gibt die a-priori-Abschätzung nicht her.)

Bemerkung 8.8: Das letzte Beispiel hat gezeigt, dass das Abschätzen von Kontraktionskonstanten mühselig ist. Es geht aber auch einfacher! Für stetig differenzierbares Φ gilt, dass

k = sup {|Φ′(x)|; x ∈ A}

die bestmögliche (weil kleinste) Kontraktionskonstante über einem Intervall A ⊂ ℝ ist. Um dies einzusehen, brauchen wir nur den Mittelwertsatz der Differentialrechnung 6.20 zu betrachten. Es gilt

\frac{Φ(x) − Φ(x)}{x − y} = Φ′(ξ)

mit ξ im Intervall zwischen x und y. Es folgt

|Φ(x) − Φ(x)| = |Φ′(ξ)| · |x − y| ≤ k · |x − y|,

wobei k das obige Supremum ist.

Bemerkung 8.9: Im Fall skalarer Gleichungen f(x) = 0 hat das Newton-Verfahren angenehme lokale Eigenschaften: Der Erfolg ist garantiert, wenn nur der Startpunkt x_{0} hinreichend gut ist. Dies gilt sogar bei p-fach entarteten Nullstellen (bei denen für p > 1 die quadratische Konvergenz dann allerdings zu linearer Konvergenz mit der asymptotischen Kontraktionskonstanten k = 1 − 1/p wird). Die globalen Eigenschaften des Newton-Verfahrens sind deutlich weniger glorreich. Gerät die Newton-Folge in die Nähe eines lokalen Extremums, wird die Iteration x → x − f(x)/f′(x) in der Nähe einer Nullstelle von f′ ausgewertet, und die Iterationspunkte können weit weg landen.