4.1. Banachscher Fixpunktsatz

Da sich im Allgemeinen keine geschlossenen Lösungen für nichtlineare Gleichungen der Form (4.1) angeben lassen, ist der Standardansatz eine iterative Approximation der Lösung zu berechnen, wie beim Beispiel des Heron-Verfahrens zur Berechnung der Quadratwurzel in Beispiel 2.14. Wir betrachten dazu allgemeine Fixpunktiterationen der Form

(4.2)\[ x_{k+1} \: = \: G(x_k),\]

für eine Funktion \(G \colon \R^n \rightarrow \R^n\) mit denen wir sukzessive die Lösung der Fixpunktgleichung

\[x \: = \: G(x)\]

approximieren.

Man beachte, dass es in den meisten Fällen genügt Fixpunktiterationen zu betrachten, die nur auf der letzten Iterierten \(x^k \in \R^n\) basieren, wie folgende Bemerkung erklärt.

Bemerkung 4.1

Liegt ein allgemeines Fixpunktverfahren der folgenden Form vor

\[x_{k+1} \ = \ G(x_k,x_{k-1},\ldots,x_{k-m}),\]

mit \(G \colon \underbrace{\R^n \times \ldots \times \R^n}_{m \text{-mal}} \rightarrow \R^n\) und \(m\in \mathbb{N}, m > 1\), so müssen wir das Problem nur in den entsprechenden Vektorraum \(\R^{m\times n}\) einbetten mit \(\tilde x_k \coloneqq (x_k,x_{k-1},\ldots,x_{k-m})\) und erhalten \(x_{k+1}\) als Funktion von \(\tilde x_k\) durch

\[x_{k+1} \ = \ \tilde{G}(\tilde{x}_k).\]

Natürlich sollte die Fixpunktgleichung (4.2) mit der allgemeinen Funktion \(G\) zum ursprünglichen Nullstellenproblem (4.1) mit der Funktion \(F\) äquivalent sein. Dazu müssen wir das Nullstellenproblem lediglich zu einer Fixpunktgleichung umformen, z.B. durch

\[x \ = \ \underbrace{x+F(x)}_{=: G(x)}, \qquad x \ = \ \underbrace{x-F(x)}_{=: G(x)}, \qquad x \ = \ \underbrace{x+H(F(x))}_{=: G(x)},\]

mit einer invertierbaren Funktion \(H \colon \R^n \rightarrow \R^n\) für die \(H(0)=0\) gilt.

Wir haben also eine große Auswahl an Fixpunktiterationen und es stellt sich die Frage, welche sich am Besten für eine numerische Lösung eignen. Dies versuchen wir an dem folgenden einfachen Beispiel zu verstehen.

Beispiel 4.1 (Verhalten von Fixpunktiterationsverfahren)

Betrachten wir zunächst das Nullstellenproblem

\[F(x) \ \coloneqq \ x - e^{x-1} \ = \ 0,\]

mit der eindeutigen Nullstelle \(\overline{x}=1\). Versuchen wir zunächst die kanonische Wahl einer Fixpunktfunktion

\[G_1(x) \ \coloneqq \ e^{x-1},\]

so kann man zeigen, dass für einen beliebigen Startwert \(x_0 > 1\) der Fixpunktiteration \(x_1 \coloneqq e^{x_0-1} > x_0\) gilt auf Grund des Wachstums der Exponentialfunktion. Analog folgt \(x_{k+1} > x_k, k \in \mathbb{N}\) für jede Iteration. Die Fixpunktiteration führt also von der Lösung \(\overline{x} = 1\) weg und divergiert, egal wie nahe der Startwert \(x_0 > 1\) bei der Nullstelle \(\overline{x}\) von \(F\) liegt.

Als Alternative betrachten wir eine Fixpunktiteration der Form

\[G_2(x) \ \coloneqq \ 1+ \log x.\]

Diese kann ebenfalls zur Lösung des nichtlinearen Nullstellenproblems \(F(x) = 0\) genutzt werden, da im Falle von \(G_2(\overline{x}) = \overline{x}\) für die Nullstellengleichung gilt:

\[F(\overline{x}) \ = \ \overline{x} - e^{\overline{x}-1} \ = \ \overline{x} - e^{G_2(\overline{x})-1} \ = \ \overline{x} - \underbrace{e^{ 1 + \log \overline{x} - 1}}_{= \overline{x}} \ = \ 0.\]

In diesem Fall gilt nun für einen Startwert \(x_0 > 1\), dass

\[1 \: \leq \: x_1 = 1+ \log x_0 \: < \: x_0\]

ist und analog erhalten wir, dass die Iterationen \(x_{k+1} < x_k, k \in \mathbb{N}\) eine monoton fallende Folge bilden, die durch \(1\) nach unten beschränkt ist. Man kann nun zeigen, dass die Fixpunktiteration tatsächlich gegen den Fixpunkt \(\overline{x} = 1\) konvergiert, was gleichzeitig die Nullstelle der nichtlinearen Funktion \(F\) ist.

Der Grund für das unterschiedliche Verhalten der beiden diskutierten Fixpunktiterationen ist vor allem die lokale Steigung im Punkt \(\overline{x}=1\). Während \(G_1'(1) > 1\) gilt, so ist \(0 < G_2'(1) < 1\).

Wir sehen also, dass wir für Konvergenz einer Fixpunktiteration eine Schranke an die Variation der Funktion \(G\) brauchen. Das passende mathematische Konzept ist die Kontraktivität, die in folgender Definition eingeführt wird.

Definition 4.1 (Kontraktivität)

Eine Funktion \(G:X \rightarrow X\) auf einem normierten Raum \(X\) heißt kontraktiv auf einer Teilmenge \(D\subset X\), wenn sie die Menge \(D\) in sich selbst abbildet mit \(G(D) \subset D\) und außerdem Lipschitz-stetig mit Konstante kleiner eins ist, d.h. es existiert ein \(q < 1\), so dass

\[\Vert G(x) - G(y) \Vert \ \leq \ q \Vert x - y\Vert\]

für alle \(x,y \in D\) gilt. Die Konstante \(q < 1\) wird manchmal auch als Kontraktionskonstante bezeichnet.

Unter einer Kontraktivitätsannahme zeigt der Banachsche Fixpunktsatz die Konvergenz der Fixpunktiteration.

Satz 4.1 (Banachscher Fixpunktsatz)

Sei \(X\) ein Banachraum (ein vollständiger normierter Raum) und \(D \subset X\) eine nichtleere, abgeschlossene Teilmenge. Sei außerdem \(G : X \rightarrow X\) eine kontraktive Funktion auf \(D\). Dann existiert ein eindeutiger Fixpunkt \(\overline{x} \in D\) mit \(\overline{x} = G(\overline{x})\) und die Fixpunktiteration \(x_{k+1}=G(x_k)\) konvergiert für jeden Startpunkt \(x_0 \in D\) gegen diesen Fixpunkt.

Proof. Wir zeigen zunächst, dass die Folge der Iterationen \((x_k)_{k\in\N} \subset D\) eine Cauchy-Folge ist. Dazu wenden wir die Dreiecksungleichung der Norm auf eine konstruierte Teleskopsumme an und erhalten somit

\[\Vert x_{k+m} - x_k \Vert \ = \ \Vert \sum_{j=0}^{m-1} x_{k+j+1} - x_{k+j} \Vert \ \leq \ \sum_{j=0}^{m-1} \Vert x_{k+j+1} - x_{k+j} \Vert \ = \ \sum_{j=k}^{k+m-1} \Vert x_{ j+1} - x_{ j} \Vert.\]

Wegen der Definition der Fixpunktiteration und der angenommenen Kontraktivität von \(G\) folgt induktiv

\[\Vert x_{j+1} - x_j \Vert \ = \ \Vert G(x_j) - G(x_{j-1}) \Vert \ \leq \ q \Vert x_j - x_{j-1} \Vert \ \leq \ \ldots \ \leq \ q^j \Vert x_1 - x_0 \Vert.\]

Also erhalten wir insgesamt für den Abstand zweier Folgenglieder \(x_{k+m}\) und \(x_k\):

\[\begin{split} \Vert x_{k+m} - x_k \Vert \ &\leq \ \sum_{j=k}^{k+m-1} q^j \Vert x_1 - x_0 \Vert \ = \ q^k \Vert x_1 - x_0 \Vert \sum_{j=0}^{m-1} q^j \\ \ &\leq \ q^k \Vert x_1 - x_0 \Vert \sum_{j=0}^{\infty} q^j \ = \ \frac{q^k}{1-q} \Vert x_1 - x_0 \Vert. \end{split}\]

Wegen \(q<1\) handelt es sich um eine konvergente geometrische Reihe und für \(k \rightarrow \infty\) konvergiert außerdem die rechte Seite unabhängig von \(m\) gegen Null. Damit ist \((x_k)_{k\in\N} \subset D\) also eine Cauchy-Folge und wegen der Vollständigkeit des Banachraums \(X\) existiert ein Grenzwert \(\overline{x} \in D\).

Der Grenzwert \(\overline{x} \in D\) ist ein Fixpunkt von \(G\), da wir wegen der Lipschitz-Stetigkeit von \(G\) folgern können:

\[\overline{x} \ = \ \lim_{k\rightarrow \infty} x_{k+1} \ = \ \lim_{k\rightarrow \infty} G(x_k) \ = \ G(\lim_{k\rightarrow \infty} x_k) \ = \ G(\overline{x}).\]

Die Eindeutigkeit des Fixpunktes \(\overline{x} \in D\) können wir abschließend aus der Kontraktivität folgern. Seien \(\overline{x}_1, \overline{x}_2 \in D\) zwei Fixpunkte, dann gilt

\[\Vert \overline{x}_1 - \overline{x}_2 \Vert \ = \ \Vert G(\overline{x}_1) - G(\overline{x}_2) \Vert \ \leq \ q \Vert \overline{x}_1 - \overline{x}_2 \Vert.\]

Dies ist wegen \(q <1\) nur möglich, falls \(\overline{x}_1 = \overline{x}_2\) gilt. ◻

Neben der Konvergenz von Fixpunktverfahren können wir auch äußerst nützliche Fehlerabschätzungen für den Abstand der Iterierten vom Fixpunkt herleiten, wie das folgende Korollar zeigt.

Korollar 4.1 (A-priori und a-posteriori Abschätzungen)

Unter den Voraussetzungen von Satz 4.1 gelten die a-priori Fehlerabschätzung

\[\Vert x_k - \overline{x} \Vert \ \leq \ q^k \Vert x_0 - \overline{x} \Vert\]

und die a-posteriori Fehlerabschätzung

\[\Vert x_k - \overline{x} \Vert \ \leq \ \frac{q^k}{1-q} \Vert x_0 - x_1 \Vert.\]

Proof. Die erste Abschätzung folgt induktiv aus

\[\Vert x_k - \overline{x} \Vert \ = \ \Vert G(x_{k-1}) - G(\overline{x}) \Vert \ \leq \ q \Vert x_{k-1} - \overline{x} \Vert \ \leq \ \ldots \ \leq \ q^k \Vert x_0 - \overline{x} \Vert.\]

Die zweite Abschätzung folgt im Grenzwert \(m \rightarrow \infty\) aus der Abschätzung

\[\Vert x_{k+m} - x_k \Vert \ \leq \ \frac{q^k}{1-q} \Vert x_0 - x_1 \Vert,\]

die wir im Beweis des Banachschen Fixpunktsatzes hergeleitet haben. ◻

Die Aussage des Banachschen Fixpunktsatzes in Satz 4.1 ist nur lokal für eine Umgebung \(D \subset X\) des Fixpunktes \(\overline{x} \in D\) gegeben, in der die Funktion \(G\) der Fixpunktiteration kontrahierend ist. Dies ist für viele mathematische Anwendungen in der Praxis sehr relevant, denn für die meisten nichtlinearen Gleichungen erhalten wir Konvergenz nur in einer lokalen Umgebung einer Lösung, d.h. wenn der Startwert \(x_0 \in D\) nahe genug beim Fixpunkt \(\overline{x} \in D\) liegt. Für andere Startwerte außerhalb der Teilmenge \(D\) kann die Iteration divergieren oder sogar gegen eine andere Lösung konvergieren.

Wir sehen dieses Verhalten zum Teil auch schon beim Heron-Verfahren in Beispiel 2.14. Für positive Startwerte konvergiert das Verfahren gegen die positive Wurzel, für negative Startwerte gegen die negative Wurzel. Dazwischen hat man für den speziellen Startwert \(x_0=0\) Divergenz, die in diesem Fall eine extreme Form hat, da das Verfahren für diesen Punkt gar nicht definiert ist.