Fixpunktiteration

Studium

x_{n+1} = \varphi(x_n), \qquad |x_n - x^*| \leq \frac{L^n}{1 - L} \, |x_1 - x_0|

Voraussetzung: $\varphi([a, b]) \subseteq [a, b],$ $|\varphi(x) - \varphi(y)| \leq L \, |x - y|$ $auf$ $[a, b],$ $0 \leq L < 1,$ $x_0 \in [a, b]$

$\varphi$: Iterationsfunktion, deren Fixpunkt gesucht ist
$x_n$: n-te Näherung
$x_0$: Startwert
$x^*$: Fixpunkt, also Lösung von x = φ(x)
$L$: Kontraktionskonstante (Lipschitz-Konstante kleiner als 1)
$n$: Anzahl der Iterationsschritte

Bei der Fixpunktiteration setzt man jede Näherung wieder in φ ein; ist φ eine Kontraktion, konvergiert das gegen den Fixpunkt.

Erklärung

Viele Gleichungen lassen sich in die Form $x = \varphi(x)$ bringen. Eine Lösung heißt Fixpunkt von $\varphi$ . Bei der Fixpunktiteration wählt man einen Startwert $x_0$ und setzt jedes Ergebnis wieder in $\varphi$ ein.

Ob das konvergiert, sagt der Banachsche Fixpunktsatz: Bildet $\varphi$ ein abgeschlossenes Intervall $[a, b]$ in sich ab und ist dort eine Kontraktion, d.h. $|\varphi(x) - \varphi(y)| \leq L \, |x - y|$ mit $L < 1$ , dann gilt:

Es gibt genau einen Fixpunkt $x^*$ in $[a, b]$ .
Die Iteration konvergiert für jeden Startwert aus $[a, b]$ gegen $x^*$ .
Es gilt die A-priori-Abschätzung $|x_n - x^*| \leq \frac{L^n}{1 - L} |x_1 - x_0|$ und die A-posteriori-Abschätzung $|x_n - x^*| \leq \frac{L}{1 - L} |x_n - x_{n-1}|$ .

Ist $\varphi$ differenzierbar, kann man $L = \max_{[a, b]} |\varphi'(x)|$ wählen. Die Konvergenz ist im Allgemeinen linear: Der Fehler schrumpft pro Schritt etwa um den Faktor $|\varphi'(x^*)|$ . Das Newton-Verfahren ist eine Fixpunktiteration mit $\varphi(x) = x - \frac{f(x)}{f'(x)}$ , bei der für eine einfache Nullstelle $\varphi'(x^*) = 0$ ist.

Beispiele

Die Gleichung $x = \cos x$ mit $\varphi(x) = \cos x$ und $x_0 = 1$ :

x_1 = \cos 1 \approx 0{,}5403, \quad x_2 \approx 0{,}8576, \quad x_3 \approx 0{,}6543, \quad \ldots \quad \to x^* \approx 0{,}739085

Auf $[0, 1]$ bildet $\cos$ in sich ab, und $|\varphi'(x)| = |\sin x| \leq \sin 1 \approx 0{,}8415 = L$ . Weil $L$ nahe bei $1$ liegt, konvergiert die Folge langsam und pendelt um den Fixpunkt.

Die Gleichung $x^2 = 2$ lässt sich unterschiedlich umformen. Mit $\varphi(x) = \frac{2}{x}$ und $x_0 = 1$ pendelt die Folge zwischen $1$ und $2$ , denn $|\varphi'(\sqrt{2})| = 1$ . Mit $\varphi(x) = \frac{1}{2}\left(x + \frac{2}{x}\right)$ ist $\varphi'(\sqrt{2}) = 0$ , und die Folge $1;\ 1{,}5;\ \frac{17}{12};\ \ldots$ konvergiert sehr schnell gegen $\sqrt{2}$ .

Mit $L = 0{,}5$ und $|x_1 - x_0| = 0{,}5$ ist der Fehler nach $n$ Schritten höchstens $\frac{0{,}5^n}{0{,}5} \cdot 0{,}5 = 2^{-n}$ . Für $2^{-n} \leq 10^{-6}$ reichen $n = 20$ Schritte, $n = 19$ reicht nach der Schranke noch nicht.

Typische Fehler

Nur $|\varphi'(x)| < 1$ prüfen und vergessen, dass $\varphi$ das Intervall in sich abbilden muss.
Eine ungünstige Umformung wählen. Dieselbe Gleichung kann mit einer Iterationsfunktion konvergieren und mit einer anderen divergieren oder pendeln.
$|x_{n} - x_{n-1}|$ klein für den Fehler halten. Bei $L$ nahe $1$ ist der tatsächliche Fehler bis zu $\frac{L}{1 - L}$ -mal größer.

Fixpunktiteration