Eine Fixpunktiteration (oder auch ein Fixpunktverfahren) ist in der Mathematik ein numerisches Verfahren zur näherungsweisen Bestimmung von Lösungen einer Gleichung oder eines Gleichungssystems. Die Gleichung muss dazu zuerst in eine Fixpunktgleichung, also in eine Gleichung der Form

${\displaystyle \varphi (x)=x}$

mit einer Funktion ${\displaystyle \varphi }$ umgeformt werden. Anschließend wird eine Startnäherung ${\displaystyle x_{0}}$ gewählt und ${\displaystyle x_{1}=\varphi (x_{0})}$ berechnet. Das Ergebnis wird wieder in die Funktion ${\displaystyle \varphi }$ eingesetzt, ${\displaystyle x_{2}=\varphi (x_{1})}$ und so weiter. Unter geeigneten Zusatzvoraussetzungen nähert sich die so erhaltene Folge ${\displaystyle x_{0},x_{1},x_{2},\dotsc }$ einer Lösung von ${\displaystyle \varphi (x)=x}$ und somit einer Lösung des ursprünglichen Problems immer weiter an.

Allgemeines Verfahren

Gegeben seien eine Funktion ${\displaystyle \varphi \colon M\to M}$, die eine Menge ${\displaystyle M}$ in sich selbst abbildet, sowie ein Startelement ${\displaystyle x_{0}\in M}$. Die durch das zugehörige Fixpunktverfahren erzeugte Folge ${\displaystyle (x_{k})_{k\in \mathbb {N} _{0}}}$ in ${\displaystyle M}$ ist dann iterativ definiert durch

${\displaystyle x_{k+1}=\varphi (x_{k})}$   für ${\displaystyle k\in \mathbb {N} _{0}}$.

Wenn auf der Menge ${\displaystyle M}$ ein Konvergenzbegriff vorhanden ist, kann man sich fragen, ob diese Folge gegen einen Fixpunkt von ${\displaystyle \varphi }$, das heißt gegen ein ${\displaystyle x^{*}}$ mit ${\displaystyle \varphi (x^{*})=x^{*}}$ konvergiert. Der banachsche Fixpunktsatz gibt relativ allgemeine Bedingungen an, unter denen das der Fall ist: Ist ${\displaystyle M}$ ein vollständiger metrischer Raum, also beispielsweise eine abgeschlossene Teilmenge des ${\displaystyle \mathbb {R} ^{n}}$ oder ein Banachraum, und ${\displaystyle \varphi }$ eine Kontraktion, dann existiert in der Menge ${\displaystyle M}$ genau ein Fixpunkt ${\displaystyle x^{*}}$ von ${\displaystyle \varphi }$ und die durch das Fixpunktverfahren erzeugte Folge konvergiert für beliebige ${\displaystyle x_{0}\in M}$ gegen ${\displaystyle x^{*}}$.

Beispiele

Gesucht ist die positive Lösung der Gleichung

${\displaystyle 2-x^{2}=e^{x}}$.

Durch Logarithmieren erhält man die Fixpunktgleichung

${\displaystyle \ln(2-x^{2})=x}$.

Die durch ${\displaystyle \varphi (x)=\ln(2-x^{2})}$ gegebene Iterationsfunktion bildet beispielsweise das Intervall ${\displaystyle M=[0{,}2;0{,}7]}$ in sich selbst ab und ist auf ${\displaystyle M}$ eine Kontraktion (siehe nebenstehende Abbildung).

Ausgehend vom Startwert ${\displaystyle x_{0}=0{,}2}$ ergibt sich für die nächsten Iterationsschritte ${\displaystyle x_{1}=\varphi (x_{0})\approx 0{,}6729}$, ${\displaystyle x_{2}=\varphi (x_{1})\approx 0{,}4364}$, ${\displaystyle x_{3}=\varphi (x_{2})\approx 0{,}5931}$ usw. Bei der Näherung nach 20 Schritten ${\displaystyle x_{20}\approx 0{,}5373}$ stimmen bereits die ersten vier Nachkommastellen mit der exakten Lösung überein.

Auch das Heron-Verfahren stellt eine Fixpunktiteration dar. Für ${\textstyle a>0}$ hat die Funktion ${\textstyle \varphi (x)={\frac {1}{2}}\cdot \left(x+{\frac {a}{x}}\right)}$ den (positiven) Fixpunkt ${\textstyle x={\sqrt {a}}}$, so dass ${\textstyle \varphi (x)}$ zur numerischen Bestimmung von ${\textstyle {\sqrt {a}}}$ verwendet werden kann.

Ein Satz zur Existenz und Eindeutigkeit

Sei ${\displaystyle f\colon [a,b]\to [a,b]\subset \mathbb {R} }$ eine stetig differenzierbare Fixpunktiterationsfunktion mit ${\displaystyle f(a)>a,f(b)<b}$ und ${\displaystyle f'(x)\neq 1}$ für alle ${\displaystyle x}$ aus ${\displaystyle (a,b)}$. Dann existiert genau ein Fixpunkt ${\displaystyle x^{*}}$ aus ${\displaystyle (a,b)}$ mit ${\displaystyle f(x^{*})=x^{*}}$.

Lineare Fixpunktverfahren

Nichtlineare Gleichungen

Das Newton-Verfahren kann als Fixpunktiteration betrachtet werden. Allgemein wird die Konvergenz mit Hilfe des banachschen Fixpunktsatzes sichergestellt, die betrachtete Funktion muss also insbesondere im betrachteten Gebiet eine Kontraktion sein.

Literatur

• Wolfgang Dahmen, Arnold Reusken: Numerik für Ingenieure und Naturwissenschaftler. 2. Auflage. Springer-Verlag, Berlin 2008, ISBN 978-3-540-76492-2.
• Martin Hermann: Numerische Mathematik, Band 1: Algebraische Probleme. 4., überarbeitete und erweiterte Auflage. Walter de Gruyter Verlag, Berlin und Boston 2020. ISBN 978-3-11-065665-7.

Einzelnachweise

1. ↑ Passende Umformungen: Nullstellen und Fixpunkte. (Nicht mehr online verfügbar.) In: Montanuniversität Leoben. 23. Februar 2005, archiviert vom Original am 22. August 2019; abgerufen am 27. August 2019.