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$:
| n | $x_n$ | n | $x_n$ |
|---|---|---|---|
| 0 | 1 | 20 | 0,739184 |
| 1 | 0,540302 | 21 | 0,739018 |
| 2 | 0,857553 | 22 | 0,73913 |
| 3 | 0,65429 | 23 | 0,739055 |
| 4 | 0,79348 | 24 | 0,739106 |
| 5 | 0,701369 | 25 | 0,739071 |
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.
| Steigung im Fixpunkt | Verhalten | Bild |
|---|---|---|
| $0 < \varphi'(x^*) < 1$ | konvergiert, Werte nähern sich von einer Seite | Treppe |
| $-1 < \varphi'(x^*) < 0$ | konvergiert, Werte springen abwechselnd über und unter $x^*$ | Spirale nach innen |
| $\varphi'(x^*) = 0$ | konvergiert besonders schnell | sehr kurze Spirale bzw. Treppe |
| $|\varphi'(x^*)| > 1$ | der Fixpunkt stößt ab – die Werte entfernen sich | Treppe bzw. Spirale nach außen |
Merke
Gilt $|\varphi'(x)| < 1$ in einer Umgebung des Fixpunkts und startest Du dort, dann konvergiert die Fixpunktiteration gegen $x^*$. Je kleiner $|\varphi'(x^*)|$, desto schneller. (Genauer fasst das der Fixpunktsatz von Banach.)
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.
Spinnwebdiagramm zum Ausprobieren
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$.
| n | mit $\varphi_1$ | mit $\varphi_2$ |
|---|---|---|
| 0 | 0,7 | 0,7 |
| 1 | 0,657 | 0,67114 |
| 2 | 0,71641 | 0,68945 |
| 3 | 0,63231 | 0,67781 |
| 4 | 0,74719 | 0,6852 |
| 5 | 0,58285 | 0,6805 |
| 6 | 0,802 | 0,68349 |
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'|$.
Das Newton-Verfahren ist auch eine Fixpunktiteration
Mit $\varphi(x) = x - \frac{f(x)}{f'(x)}$ ist die Fixpunktiteration genau das Newton-Verfahren. An einer einfachen Nullstelle gilt hier $\varphi'(x^*) = 0$ – deshalb ist Newton so schnell. Ein bekanntes Beispiel ist das Heron-Verfahren für Wurzeln: $\varphi(x) = \frac{1}{2}\left(x + \frac{a}{x}\right)$ hat den Fixpunkt $\sqrt{a}$.
Rechner: Fixpunktiteration mit Spinnwebdiagramm
Online üben
Stelle den Taschenrechner auf Bogenmaß (RAD), wenn sin oder cos vorkommt. Mehrere Werte trennst Du mit Semikolon.
Stufe 2: Iterieren
-
Aufgabe 1
\(\varphi(x) = \frac{1}{2}\left(x + \frac{3}{x}\right),\) \(x_0 = 2:\ x_3\) (4 Nachkommastellen)\(x_1 \approx 1{,}75,\) \(x_2 \approx 1{,}732143,\) \(x_3 \approx 1{,}732051\)
-
Aufgabe 2
\(\varphi(x) = \sqrt[3]{x + 1},\) \(x_0 = 2:\ x_3\) (4 Nachkommastellen)\(x_1 \approx 1{,}44225,\) \(x_2 \approx 1{,}346677,\) \(x_3 \approx 1{,}328876\)
-
Aufgabe 3
\(\varphi(x) = \frac{1}{1 + x},\) \(x_0 = 1:\ x_3\) (4 Nachkommastellen)\(x_1 \approx 0{,}5,\) \(x_2 \approx 0{,}666667,\) \(x_3 \approx 0{,}6\)
-
Aufgabe 4
\(\varphi(x) = \sqrt{x + 3},\) \(x_0 = 0:\ x_3\) (4 Nachkommastellen)\(x_1 \approx 1{,}732051,\) \(x_2 \approx 2{,}175328,\) \(x_3 \approx 2{,}274935\)
-
Aufgabe 5
\(\varphi(x) = \frac{1}{2}\left(x + \frac{3}{x}\right),\) \(x_0 = 1:\ x_3\) (4 Nachkommastellen)\(x_1 \approx 2,\) \(x_2 \approx 1{,}75,\) \(x_3 \approx 1{,}732143\)
Tippe Deine Lösung ein und klicke auf „Prüfen“ (oder drücke Enter). Brüche als 3/4, Dezimalzahlen mit Komma, mehrere Lösungen mit ; trennen, Potenzen als x^2, Wurzeln als sqrt(5). Punkte: 10 für richtig beim ersten Versuch, 6 nach einem Fehlversuch, 5 mit Tipp, 0 wenn Du Dir vorher die Lösung anschaust. Deine Punkte und Abzeichen siehst Du unter Mein Training.
Arbeitsblatt: Fixpunktiteration
Eine volle DIN-A4-Seite Aufgaben mit Lösungsblatt zum Ausdrucken – bei jedem Klick neue Aufgaben. Klasse 11–13.
Weitere Näherungsverfahren: Intervallhalbierung und Newton-Verfahren. Folgen und ihre Grenzwerte behandelt die Seite Folgen und Reihen.
Weiterlesen: Fixpunktiteration, Fixpunktsatz von Banach bei Wikipedia