Fixpunktiteration

Tippe auf einem Taschenrechner (im Bogenmaß) eine beliebige Zahl ein und drücke immer wieder die Taste cos. Nach einigen Dutzend Tastendrücken bleibt die Anzeige bei $0{,}739085\ldots$ stehen. Diese Zahl ändert sich durch cos nicht mehr – sie ist ein Fixpunkt. Genau so funktioniert die Fixpunktiteration, mit der man Gleichungen näherungsweise löst.

Was ist ein Fixpunkt?

Eine Zahl $x^*$ heißt Fixpunkt der Funktion $\varphi$ (gelesen „phi“), wenn $\varphi(x^*) = x^*$ gilt – die Funktion lässt sie unverändert. Im Koordinatensystem sind Fixpunkte die Schnittpunkte des Graphen von $\varphi$ mit der Winkelhalbierenden $y = x$.

Jede Gleichung $f(x) = 0$ lässt sich auf viele Arten in die Form $x = \varphi(x)$ bringen. Dann ist jede Lösung der Gleichung ein Fixpunkt von $\varphi$. Aus $\cos(x) - x = 0$ wird zum Beispiel $x = \cos(x)$.

Das Verfahren

Du wählst einen Startwert $x_0$ und setzt immer wieder das letzte Ergebnis ein:

Kommen sich die Werte immer näher, nähert sich die Folge einem Fixpunkt. Für $\varphi(x) = \cos(x)$ und $x_0 = 1$:

Die Werte springen abwechselnd über und unter den Fixpunkt $x^* \approx 0{,}739085$ und kommen ihm dabei immer näher – allerdings recht langsam.

Das Bild heißt Spinnwebdiagramm: Vom Punkt $x_n$ geht es senkrecht zum Graphen von $\varphi$ (das liefert $\varphi(x_n) = x_{n+1}$), dann waagerecht zur Geraden $y = x$ (dort hat der Punkt die x-Koordinate $x_{n+1}$) – und wieder von vorn.

Wann konvergiert die Iteration?

Entscheidend ist die Steigung von $\varphi$ im Fixpunkt. Ist $x_n$ nahe bei $x^*$, dann gilt ungefähr

Der Abstand zum Fixpunkt wird also in jedem Schritt ungefähr mit $\varphi'(x^*)$ multipliziert.

Bei $\varphi(x) = \cos(x)$ ist $\varphi'(x^*) = -\sin(0{,}739085) \approx -0{,}67$. Darum die Spirale – und darum das langsame Tempo: Der Fehler schrumpft pro Schritt nur um etwa ein Drittel.

Eine Gleichung – zwei Umformungen

Die Gleichung $x^3 + x - 1 = 0$ hat genau eine Lösung $x^* \approx 0{,}6823$. Man kann sie zum Beispiel so umformen:

• $x = 1 - x^3$, also $\varphi_1(x) = 1 - x^3$ mit $\varphi_1'(x^*) = -3(x^*)^2 \approx -1{,}40$,
• $x \cdot (1 + x^2) = 1$, also $\varphi_2(x) = \frac{1}{1 + x^2}$ mit $\varphi_2'(x^*) = \frac{-2x^*}{(1 + (x^*)^2)^2} \approx -0{,}64$.

Beide Folgen starten bei $0{,}7$ – also ganz dicht an der Lösung. Mit $\varphi_1$ entfernen sich die Werte trotzdem immer weiter, mit $\varphi_2$ pendeln sie sich ein. Vor dem Rechnen lohnt sich deshalb immer der Blick auf $|\varphi'|$.

Rechner: Fixpunktiteration mit Spinnwebdiagramm

Konvergenzbedingung: Ist |φ′(x)| < 1 in einer Umgebung des Fixpunkts und startest Du dort, dann konvergiert die Iteration gegen x*.

Rechenweg

1. Iterieren

   Setze den letzten Wert in φ ein: x₁ = φ(x₀), x₂ = φ(x₁) und so weiter. Werden die Abstände aufeinanderfolgender Werte immer kleiner, nähert sich die Folge einem Fixpunkt x* mit φ(x*) = x*.

   k	xk	|xk − xk−1|
   0	1
   1	1,5	0,5
   2	1,4166666667	0,0833333333
   3	1,4142156863	0,0024509804
   4	1,4142135624	0,0000021239
   5	1,4142135624	1,594946 · 10^-12
   6	1,4142135624	0

2. Fixpunkt und Konvergenz

   φ′(x*) ist (fast) 0: Die Iteration konvergiert hier besonders schnell – ähnlich wie das Newton-Verfahren.

   \[x^* \approx 1{,}4142135624\]

   \[\varphi(x^*) \approx 1{,}4142135624\]

   \[\varphi'(x^*) \approx 0\]

Spinnwebdiagramm

Orange: senkrecht zum Graphen von φ, waagerecht zur Winkelhalbierenden y = x – so entsteht x₁, x₂, … Der Fixpunkt ist der Schnittpunkt von φ mit y = x.

Online üben

Stelle den Taschenrechner auf Bogenmaß (RAD), wenn sin oder cos vorkommt. Mehrere Werte trennst Du mit Semikolon.

Weitere Näherungsverfahren: Intervallhalbierung und Newton-Verfahren. Folgen und ihre Grenzwerte behandelt die Seite Folgen und Reihen.

Weiterlesen: Fixpunktiteration, Fixpunktsatz von Banach bei Wikipedia

Passt dazu