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 3: Konvergenz untersuchen
-
Aufgabe 1
\(x^3 - 2x - 5\) \(= 0:\ x = \sqrt[3]{2x + 5}\ \text{oder}\ x\) \(= \frac{x^3 - 5}{2}\)? Welche Form konvergiert (erste/zweite)?\(x^* \approx 2{,}0946:\ |\varphi_1'(x^*)|\) \(\approx 0{,}15,\) \(|\varphi_2'(x^*)|\) \(\approx 6{,}58\) \(\Rightarrow\) erste Form
-
Aufgabe 2
\(\varphi(x) = \frac{x^2 + 15}{8}:\) Fixpunkte \(x_1^* < x_2^* \text{ und } \varphi'(x_1^*);\) \(\varphi'(x_2^*)\ ?\)\(φ′(x₁*); φ′(x₂*)\)\(x^2 - 8x + 15\) \(= 0:\ x_1^*\) \(= 3,\) \(x_2^* = 5;\) \(\varphi'(x) = \frac{2x}{8}:\ \frac{3}{4}\ (\)anziehend\(),\) \(\frac{5}{4}\ (\)abstoßend\()\)
-
Aufgabe 3
\(x^3 + x - 1\) \(= 0:\ x = \frac{1}{1 + x^2}\ \text{oder}\ x\) \(= 1 - x^3\)? Welche Form konvergiert (erste/zweite)?\(x^* \approx 0{,}6823:\ |\varphi_1'(x^*)|\) \(\approx 0{,}64,\) \(|\varphi_2'(x^*)|\) \(\approx 1{,}4\) \(\Rightarrow\) erste Form
-
Aufgabe 4
\(e^x - 3x = 0:\ x = \frac{e^x}{3}\ \text{oder}\ x = \ln(3x)\)? Welche Form konvergiert (erste/zweite)?\(x^* \approx 0{,}6191:\ |\varphi_1'(x^*)|\) \(\approx 0{,}62,\) \(|\varphi_2'(x^*)|\) \(\approx 1{,}62\) \(\Rightarrow\) erste Form
-
Aufgabe 5
\(\varphi(x) = \frac{x^2 + 12}{7}:\) Fixpunkte \(x_1^* < x_2^* \text{ und } \varphi'(x_1^*);\) \(\varphi'(x_2^*)\ ?\)\(φ′(x₁*); φ′(x₂*)\)\(x^2 - 7x + 12\) \(= 0:\ x_1^*\) \(= 3,\) \(x_2^* = 4;\) \(\varphi'(x) = \frac{2x}{7}:\ \frac{6}{7}\ (\)anziehend\(),\) \(\frac{8}{7}\ (\)abstoßend\()\)
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