Fixpunktiteration

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

\varphi (x)=x

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

Allgemeines Verfahren

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

x_{{k+1}}=\varphi (x_{k})   für k \in \N_0.

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

Beispiel

Grafische Darstellung der eindimensionalen Fixpunktiteration

Gesucht ist die positive Lösung der Gleichung

2-x^{2}=e^{x}.

Durch Logarithmieren erhält man die Fixpunktgleichung

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

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

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

Ein Satz zur Existenz und Eindeutigkeit

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

Beweis

Man setze F(x):=f(x)-x. Dann ist F(a)>0,F(b)<0. Aus dem Zwischenwertsatz folgt, dass es mindestens eine Nullstelle x^{*}\in [a,b] gibt mit F(x^{*})=0. Gäbe es eine zweite Nullstelle, etwa x^{{**}}, dann müsste es wegen F(x^{*})=F(x^{{**}}) nach dem Satz von Rolle einen Punkt {\check  x} aus dem Intervall (x^{*},x^{{**}}) geben mit F'({\check  x})=0, was f'({\check  x})=1 impliziert im Widerspruch zur Annahme. Also ist der Fixpunkt x^{*} eindeutig.

Beispiel

Für die Funktion f(x)={\frac  {x^{3}-1}{x^{3}-2}} gilt auf [-1,+1]:

Daraus folgt mit dem Satz oben, dass f in (-1,+1) genau einen Fixpunkt besitzt (x^{*}\approx 0{,}4722129517).

Lineare Fixpunktverfahren

Konstruktionsidee

Ein wichtiger Spezialfall der Fixpunktiteration sind die Splitting-Verfahren. Um ein lineares Gleichungssystem

Ax=b

mit einer nicht-singulären n×n-Matrix A und einem Vektor b in eine Fixpunktgleichung umzuformen, zerlegt man die Matrix A mit Hilfe einer nicht-singulären n×n-Matrix B in

A=B+(A-B).

Damit folgt

Ax=b
Bx+(A-B)x=b
\Rightarrow x=B^{{-1}}b-B^{{-1}}(A-B)x=(E-B^{{-1}}A)x+B^{{-1}}b,

wobei E die Einheitsmatrix bezeichnet.

Das lineare Gleichungssystem Ax=b ist dann äquivalent zu der Fixpunktaufgabe x=\varphi (x) mit

\varphi (x)=(E-B^{{-1}}A)x+B^{{-1}}b.

Man erhält für einen vorgegebenen Startvektor x_{0} folgendes Iterationsverfahren für k=0,1,\ldots

x_{{k+1}}=(E-B^{{-1}}A)x_{k}+B^{{-1}}b,

und die zugehörige Iterationsmatrix lautet: E-B^{{-1}}A.

Konvergenz

Aus dem banachschen Fixpunktsatz und weiteren Überlegungen folgt dann, dass diese Fixpunktverfahren genau dann für jeden Startvektor x_{0} konvergieren, falls der Spektralradius der Iterationsmatrix

\rho (E-B^{{-1}}A)=\max _{i}|\lambda _{i}(E-B^{{-1}}A)|<1.

\rho (E-B^{{-1}}A) sollte möglichst klein sein, da dadurch die Konvergenzgeschwindigkeit bestimmt wird.

Spezielle Verfahren

Auf obiger Konstruktionsidee basieren folgende bekannte Verfahren zur Lösung von linearen Gleichungssystemen:

Bemerkungen

Iterationsverfahren der Form x_{{k+1}}=Mx_{k}+v, k = 0, 1, ... sind

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.

Trenner
Basierend auf einem Artikel in: Wikipedia.de
Seitenende
Seite zurück
©  biancahoegel.de
Datum der letzten Änderung:  Jena, den: 05.02. 2019