next up previous contents
Nächste Seite: Konvergenzordnung Aufwärts: Nichtlineare Gleichungen in einer Vorherige Seite: Maschinengenauigkeit   Inhalt


Fixpunkt-Iteration

Im Abschnitt 2.5 haben wir bereits Fixpunkte von Funktionen durch wiederholtes Einsetzen bestimmt.

\begin{displaymath}\rule{\textwidth}{0.3mm}\end{displaymath}

Fixpunkt-Iteration
Gegeben eine Funktion $\phi(x)$ und ein Startwert $x^{(0)}$. Gesucht ein Fixpunkt $\xi$ von $\phi$.
$x^{(0)}$ als Startwert gegeben.
Iterationsvorschrift
     $x^{(k+1)} = \phi(x^{(k)})$ für $k=0,1,2\ldots$

\begin{displaymath}\rule{\textwidth}{0.3mm}\end{displaymath}

Viele numerische Verfahren lassen sich als Spezialfälle einer Fixpunkt-Iteration betrachten. Aussagen über die Konvergenz von Fixpunkt-Iterationen sind deswegen von allgemeiner Bedeutung.


\begin{displaymath}\rule{\textwidth}{0.3mm}\end{displaymath}

Fixpunkt-Iteration konvergiert für kontrahierende Abbildungen
Die Funktion $\phi(x)$ besitze einen Fixpunkt $\xi$: $\phi(\xi)=\xi$. Sei ferner $I$ ein offenes Intervall der Form $(\xi-r,\xi+r)$ um den Fixpunkt $\xi$, sodass $\phi$ in $I$ eine kontrahierende Abbildung ist, d.h.

\begin{displaymath}\vert\phi(x)-\phi(y)\vert \leq C \vert x-y\vert\;,\quad C<1\end{displaymath}

gilt für alle $x,y\in I$.

Dann konvergiert die Fixpunkt-Iteration $x^{(k+1)} = \phi(x^{(k)})$ mindestens linear gegen $\xi$ für alle $x^{(0)}\in I$.

\begin{displaymath}\rule{\textwidth}{0.3mm}\end{displaymath}

Beweis: Zuerst zeigt man durch Induktion: $x^{(k)}\in I$ für alle $k=0,1,2\ldots$: Die Aussage ist laut Voraussetzung richtig für $k=0$. Nun ist

\begin{displaymath}\vert x^{(k+1)}-\xi\vert = \vert\phi(x^{(k)}) - \phi(\xi)\vert \leq C \vert x^{(k)}-\xi\vert\;.\end{displaymath}

Nach der Induktionsannahme liegt $x^{(k)} \in I$, also weniger als $r$ von $\xi$ entfernt: $\vert x^{(k)}-\xi\vert<r$. Da $C<1$, ist also auch

\begin{displaymath}\vert x^{(k+1)}-\xi\vert<r \quad \mbox{und}\quad x^{(k+1)}\in I\end{displaymath}

Aus dem Induktionsbeweis folgt unmittelbar für die Fehler $\epsilon^{(k)}=\vert x^{(k)}-\xi\vert$ und $\epsilon^{(k+1)}=\vert x^{(k+1)}-\xi\vert$ :

\begin{displaymath}\epsilon^{(k+1)}\leq C \epsilon^{(k)} \leq C^k\epsilon_0\;.\end{displaymath}

Bemerkung: Ist $\phi$ in einer Umgebung von $\xi$ stetig differenzierbar und $\vert\phi'(\xi)\vert<1$, so ist in einer Umgebung von $\xi$ die Kontraktionseigenschaft erfüllt: Wegen der Stetigkeit von $\phi'$ gibt es ein offenes Intervall $I$ um $\xi$, in dem $\phi'\leq C<1$ gilt. Für $x,y \in I$ gilt nach dem Mittelwertsatz der Differentialrechnung

\begin{displaymath}\phi(x)-\phi(y) = (x-y)\phi'(\eta) \quad\mbox{für }\eta\in I\;.\end{displaymath}

Damit ist auch

\begin{displaymath}\vert\phi(x)-\phi(y)\vert \leq C \vert x-y\vert\;,\quad C<1\end{displaymath}

Eine Kurzfassung dieser Aussage:

\begin{displaymath}\rule{\textwidth}{0.3mm}\end{displaymath}

Das Fixpunktverfahren konvergiert lokal, falls $\vert\phi'(\xi)\vert<1$.

\begin{displaymath}\rule{\textwidth}{0.3mm}\end{displaymath}

Das Konvergenzverhalten des Algorithmus für verschiedene $f$ wird in Abbildung 7 graphisch dargestellt.

Abbildung: Fixpunkt-Iteration in graphischer Darstellung für verschiedene Funktionen $f$. Mögliche Fälle: Einseitige Annäherung an den Fixpunkt, falls in einer Umgebung des Fixpunktes $0<f'<1$; alternierende Konvergenz, falls $-1<f'<0$, Divergenz falls $f'>1$ oder $f'<-1$.
\begin{figure}\rule{-10mm}{0mm}\rule{155mm}{0.2mm}
\epsfxsize =14cm
\epsfbox{d:...
...ra/nmictw/tex/eps/abb1_5cd.EPS}\rule{-10mm}{0mm}\rule{155mm}{0.2mm}
\end{figure}


next up previous contents
Nächste Seite: Konvergenzordnung Aufwärts: Nichtlineare Gleichungen in einer Vorherige Seite: Maschinengenauigkeit   Inhalt
brand 2005-02-23