\section{Fixpunktverfahren}
Wandle das Nullstellenproblem in ein Fixpunktproblem um.
%
\eq{3.1.1}
 x = \Phi (x).
\en
%
Dies ist im allgemeinen auf viele Arten m\"oglich, die \"aquivalent oder 
nicht \"aquivalent sein k\"onnen.
%
\begin{example}\label{3.1.2} $e^x - \sin x = 0$\\
M\"ogliche Fixpunktgleichungen (nicht alle \"aquivalent)
%
\[
\begin{array}{clcl}
 a) & x & = & e^x - \sin x + x\\
 b) & x & = & \sin x - e^x +x\\
 c) & x & = & \arcsin (e^x), \quad \mbox { f\"ur } x < 0\\
 d) & x & = & \ln (\sin x), \quad \mbox { f\"ur } (-2n \pi, 2n \pi + \pi),
    n = 1,2,3,\dots
\end{array}
\]
%
Alle haben unterschiedliche numerische Eigenschaften.\\
$\longrightarrow$ {\"Ubung} \ref{numI/uebung043} 
\end{example}
%
Die Idee des Fixpunktverfahrens ist es, die
Folge
%
\eq{3.1.3} 
 x^{(i+1)} = \Phi (x^{(i)}), \quad i = 0,1,2,\dots
\en
%
mit gegebenem Startwert $x_1$ zu erzeugen. 
%
\begin{theorem}[Banachscher Fixpunktsatz]\label{3.1.4} \quad
Sei $D\subseteq D_\Phi \subseteq \R^m$ ein abgeschlossenes Gebiet und $\Phi$
eine kontrahierende Abbildung von $D$ in sich, d.h.
%
\begin{itemize}
\item [a)] $\Phi: D \longrightarrow D$
\item [b)] $\Phi$ kontrahierend, d.h. $\exists \; \alpha < 1$ und
eine Norm $\| \bullet\|$, so da{\ss} 
\end{itemize}
%
\eq{3.1.5}
 \| \Phi (x) - \Phi (y) \| \le \alpha \| x-y \|, \quad \forall x, y \in D.
\en
%
Dann gilt:
\begin{itemize}
\item [i)] Es gibt genau einen Fixpunkt $\hat{x}$ von 
(\ref{3.1.1}) in $D$.
\item [ii)] Die Fixpunktiteration (\ref{3.1.3}) konvergiert f\"ur jeden
Startwert $x^{(0)} \in D$ gegen $\hat{x}$.
\item [iii)] Es gelten die Fehlerabsch\"atzungen
%
\eqa
\label{3.1.6} \| \hat{x} - x^{(n)} \| & \le & \frac{\alpha^n}{1-\alpha}
  \|x^{(1)} - x^{(0)}\| \quad \mbox { a priori}\\
%
\label{3.1.7} \| \hat{x} - x^{(n)} \| & \le & \frac{\alpha}{1-\alpha}
  \|x^{(n)} - x^{(n-1)}\| \quad \mbox { a posteriori }
\ena
\end{itemize}
\end{theorem}
%
\proof
$x^{(0)} \in D \Longrightarrow x^{(n)} = \Phi (x^{(n-1)}) \in D$,
f\"ur alle $n = 1,2,\dots $
%
\begin{eqnarray*}
 \|x^{(n+1)} - x^{(n)} \| & = & \| \Phi (x^{(n)}) - \Phi (x^{(n-1)}) \| \\
 & \le & \alpha \| x^{(n)} - x^{(n-1)} \| \le \alpha^2 \| x^{(n-1)} - x^{(n-2)} \|\\
 & \le & \alpha ^n \| x^{(1)} - x^{(0)} \|
\end{eqnarray*}
\begin{eqnarray*}
 \|x^{(n+k)} - x^{(n)} \| & \le & \sum\limits^k_{i=1} \|x^{(n+i)}-
                        x^{(n+i-1)}\| \\
 & \le & \sum\limits^k_{i=1} \alpha^{n+i-1} \|x^{(1)} - x^{(0)} \| \\
 & \le & \alpha^n \|x^{(1)} - x^{(0)} \| \sum\limits^k_{i=1} \alpha^{i-1}\\
 & \le &  \frac{\alpha^n}{1-\alpha} \|x^{(1)} - x^{(0)} \|
\end{eqnarray*}
%
$\Longrightarrow$ Folge konvergiert, da Cauchy--Folge und $\R^m$ vollst\"andig.\\
$\Phi$ ist stetig. Dies folgt bereits aus der Kontraktionseigenschaft (\ref{3.1.5}).
Somit ist der Grenzwert Fixpunkt von $\Phi$, wegen 
\[
\hat{x}\equiv\lim_{n\mapsto \infty} x^{(n+1)}
=\lim_{n\mapsto \infty} \Phi(x^{(n)})
=\Phi(\lim_{n\mapsto \infty} x^{(n)}) =\Phi(\hat{x}).
\]
Eindeutigkeit. Seien $\hat{x},\bar{x}$ Fixpunkte von $\Phi$.
\[
 \|\hat{x}-\bar{x}\|
=\|\Phi(\hat{x})-\Phi(\bar{x})\|
\leqslant \alpha \|\hat{x}-\bar{x}\|.
\]
Wegen $\alpha<1$ kann nur $\hat{x}=\bar{x}$ gelten.

%
\begin{eqnarray*}
 \|x^{(n+k)} - x^{(n)} \| & \le & 
 \frac{\alpha^n}{1-\alpha} \|x^{(1)} - x^{(0)} \|\\
 \stackrel{k \to \infty}{\Longrightarrow} \| \hat{x} - x^{(n)} \| & \le &
 \frac{\alpha^n}{1-\alpha} \|x^{(1)} - x^{(0)} \| \Longleftrightarrow
 (3.7) % (\ref{3.1.6}).
\end{eqnarray*}
%
\[
 n = 1 \Longrightarrow \| \hat{x} - x^{(1)} \| \le
 \frac{\alpha}{1-\alpha} \| x^{(1)} - x^{(0)} \|
\]
%
ersetze $x^{(1)}$ durch $x^{(n)}, x^{(0)}$ durch $x^{(n-1)}$
so folgt (\ref{3.1.7}).
\eproof
%
\begin{grf}\label{grf1}\quad Graphische Veranschaulichung der Konvergenz $m=1$.
\unitlength1cm
\begin{center}
\begin{picture}(8,7.5)
% \put(0,0){\epsfig{file=includeps/bild4.ps,height=8cm,clip=}}
\put(0,0){\includegraphics[width=0.50\linewidth,height=0.50\linewidth]{includeps/bild4}}
\end{picture}
\end{center}
\end{grf}
%
\begin{definition}\label{3.1.8}
Ein Fixpunkt $\hat{x}$ hei{\ss}t \underline{anziehend}, wenn die Iteration
(\ref{3.1.3}) f\"ur alle gen\"ugend nahe bei $\hat{x}$ gelegenen
Startwerte $x^{(0)} \neq \hat{x}$ gegen $\hat{x}$ konvergiert.

Ein Fixpunkt $\hat{x}$ hei{\ss}t absto{\ss}end, wenn es eine offene Kugel
$U_\varepsilon$ um $\hat{x}$  gibt, so da{\ss} f\"ur alle 
$x^{(0)} \in U_\varepsilon\setminus\{\hat{x}\}$ ein $m$ existiert, 
so da{\ss} $x^{(m)} \not\in U_\varepsilon$.
\end{definition}

\newpage
\begin{grf}\label{grf2}\quad {Absto{\ss}ender Fixpunkt / Anziehender Fixpunkt.}
\unitlength1cm
\begin{center}
\begin{picture}(12,8)
% \put(-1,0){\epsfig{file=includeps/bild3.ps,height=8cm,clip=}}
\put(-1,0){\includegraphics[width=0.95\linewidth,height=0.50\linewidth]{includeps/bild3}}
\end{picture}
\end{center}
\end{grf}

%
\begin{theorem}\label{3.1.9}
Sei $D\subseteq D_\Phi \subseteq \R^m$ abgeschlossen und konvex und nehme an,
da{\ss} \newline
$\displaystyle D\Phi = \left[ \begin{array}{ccc}
    \frac{\partial \Phi_1 (x)}{\partial x_1}  & \cdots & \frac{\partial \Phi_1 (x)}
    {\partial x_m}\\
    \vdots & & \vdots\\
    \frac{\partial \Phi_m (x)}{\partial x_1} & \cdots & 
    \frac{\partial \Phi_m (x)}
    {\partial x_m} \end{array}\right]$ existiert und stetig ist. Falls es
eine Norm gibt, so da{\ss}
$\|D\Phi (x) \| \le \alpha < 1$,  so ist $\Phi$ in  $D$
kontrahierend mit Lipschitzkonstante $\alpha$.
\end{theorem}
%
\proof
$\Longrightarrow$ \"Ubung \ref{numI/uebung040}.
\eproof
%
Ist $D\Phi(\hat{x})$ stetig und $\|D\Phi (\hat{x}) \| < 1$ so ist
$\hat{x}$ anziehend. Ein Fixpunkt ist im allgemeinen nicht anziehend,
falls einer der Eigenwerte von $D\Phi (x)$ vom Betrag gr\"o{\ss}er $1$
ist. \\
$\Longrightarrow$ \"Ubung.
%
\begin{definition}\label{3.1.10}
Eine Iterationsfolge $\{x^{(i)} \}^\infty_{i=0}$, die f\"ur $p \ge 1$
%
\eq{3.1.11}
 \|x^{(i+1)} - \xi \| \le c \| x^{(i)} - \xi \|^p \quad i = 0,1,2 \cdots 
\en
%
und $c < 1$ f\"ur $p = 1$ erf\"ullt, hei{\ss}t Folge von mindestens $p$--ter
Ordnung. 
\end{definition}
%
\begin{corollary}\label{3.1.12}
Das Fixpunktverfahren (\ref{3.1.3}) sofern es konvergiert, ist konvergent
von mindestens 1.~Ordnung (linear konvergent).
\end{corollary}

Kosten f\"ur Iteration (\ref{3.1.3}): 
eine Auswertung von $\Phi (x)$ pro Iteration,
Anzahl der Iterationen aus Fehlersch\"atzung ablesbar. \\
Versuche h\"ohere Konvergenzordnung zu bekommen.
%
