\subsection{Anwendung auf modifiziertes Newtonverfahren}

Wir wenden nun zur L\"osung von $f(x) = 0$ das Minimierungsverfahren \ref{3.2.13}
auf $h(x) = f(x)^T f(x)$ an.\\
Als Suchrichtung $s^{(k)}$ in Punkt $x^{(k)}$ w\"ahlen wir den nomierten Newtonvektor
\[
 s^{(k)} = \frac{d^{(k)}}{\|d^{(k)} \|} \mbox { mit } 
 d^{(k)} = Df (x^{(k)})^{-1} f(x^{(k)}).
\]
%
(Immer definiert falls $Df(x^{(k)})^{-1}$ existiert.)
%
\begin{lemma}\label{3.2.17}
Sei $x$ so, da{\ss}
 $d(x) = Df(x)^{-1} f(x)$ existiert und nicht verschwindet. Dann gilt
\[
s(x) = \frac{d(x)}{\|d(x)\|} \in D (\gamma,x), \; \mbox{\rm f\"ur alle }
0 < \gamma < \bar{\gamma} (x),
\]
wobei 
\[
 \bar{\gamma}(x) = \frac{1}{\mathrm{cond}_2(Df(x))}
 = \frac{1}{\|Df (x) \|_2 \| Df (x)^{-1} \|_2}.
\]
\end{lemma}
%
\proof
$Dh (x) = 2f^T (x) Df (x).$ Submultiplikativit\"at von $\|\bullet\|_2$ liefert
%
\begin{eqnarray*}
 \| f^T (x) Df (x) \|_2 & \le & \| Df (x) \|_2 \; \| f(x) \|_2\\
 \| Df (x)^{-1} f(x) \|_2 & \le & \|Df (x)^{-1} \|_2 \; \| f (x) \|_2
\end{eqnarray*}
%
und daher
%
\begin{eqnarray*}
 \frac{Dh (x) s}{\| Dh (x) \|} & = &
 \frac{f(x)^T Df(x)Df(x)^{-1} f(x)}{\| Df(x)^{-1} f(x)\| \; \|f^T(x) Df(x)\|}\\
 & \ge & \frac{1}{\mathrm{cond}_2(Df(x))}\\
 & > &  0.
\end{eqnarray*}
%
F\"ur alle $\gamma$ mit $0 < \gamma < \frac{1}{\mathrm{cond}_2(Df(x))}$
gilt also $s \in D(\gamma, x)$.
\eproof
%
Falls $Df(x)^{-1}$ existiert folgt also, da{\ss} 
$Dh(x) =0 \Longleftrightarrow f(x)=0.$ Damit erhalten wir das modifizierte
Newtonverfahren.
%
\begin{algorithmus}\label{3.2.18}\quad\\
\begin{tabular}{llll}
\underline{Input:} & \multicolumn{3}{p{13.5cm}}{
                      Differenzierbare Funktion $f(x) : \R^n \to \R^n$
                      sowie Startwert $x^{(0)} \in \R^n$.
		     }\\
\underline{Output:}& \multicolumn{3}{p{13.5cm}}{
                      Folge $x^{(k)}, \; k = 0,1,2,\dots$ die gegen Nullstelle
		      von $f$ konvergiert.
                     }\\[2ex]
&FOR& \multicolumn{2}{l}{$k = 0,1,2,\dots$ UNTIL SATISFIED}\\
&   &Berechne&\multicolumn{1}{p{10.5cm}}{
               $d^{(k)} = Df (x^{(k)})^{-1} f(x^{(k)})$, 
               (lineares Gleichungssystem mit $QR$)
              }\\[1ex]
&   &        &\multicolumn{1}{p{10.5cm}}{
               $\gamma_k = \frac{1}{\mathrm{cond}_2 (Df(x^{(k)}))}$,  
	       fast frei aus $QR$
              }\\[1.6ex]
&   &Setze   &\multicolumn{1}{p{10.5cm}}{
               $h_k (\tau) = h (x^{(k)} - \tau d^{(k)}) 
                           = f(x^{(k)}-\tau d^{(k)})^T
                             f(x^{(k)}- \tau d^{(k)})$.
              }\\[1ex]
&   &Bestimme&\multicolumn{1}{p{10.5cm}}{
               $ j \ge 0$, so da{\ss} 
               $ h_k (2^{-j}) \le h_k (0) - 2^{-j} \frac{\gamma_k}{4}
               \| d^{(k)} \| \; \| Dh (x^{(k)}) \|$.
              }\\[1ex]
&   &Bestimme&\multicolumn{1}{p{10.5cm}}{
               $\lambda_k$ und $x^{(k+1)} = x^{(k)} - \lambda_k d^{(k)}$, 
               so da{\ss} gilt
	       \[
       		h(x^{(k+1)}) = \min\limits_{0 \le i \le j} h_k (2^{-i}).
	       \]
	      }\\
&END& 
\end{tabular}
\end{algorithmus}


\underline{Kosten:} Pro Schritt
\begin{itemize}
\item [a)] Berechnung von $Df(x^{(k)})$
\item [b)] L\"osung von $Df(x^{(k)}) d^{(k)} = f(x^{(k)})$
\item [c)] eindimensionale Minimierung.
\end{itemize}
%
\underline{Fehleranalyse:} 
b) mit $QR$ klar. a),c) h\"angt von $f$ ab.

\"Uber dieses Verfahren hat man die folgende Konvergenzaussage:
%
\begin{theorem}\label{3.2.19}
Gegeben sei $f: \R^n \to \R^n, x^{(0)} \in \R^m$ mit
\begin{itemize}
\item [a)] $K = \{ x| \; h(x) \le h(x_0)\},\; h(x) = f^T (x) f(x)$ ist kompakt.
\item [b)] $f$ ist auf Umgebung von $K$ stetig differenzierbar.
\item [c)] $Df(x)^{-1}$ existiert f\"ur alle $x \in K$.
\end{itemize}
%
Dann ist die Folge $\{x^{(k)} \}$, die in Algorithmus \ref{3.2.18} erzeugt 
wird, wohldefiniert und es gilt
\begin{itemize}
\item [a)] $x^{(k)} \in K, \; \forall \, k = 0,1,2, \dots, \{x^{(k)} \}$ 
	   besitzt mindestens H\"aufungspunkt $\hat{x} \in K.$
\item [b)] Jeder H\"aufungspunkt $\hat{x}$ von $\{x^{(k)} \}$ ist Nullstelle 
           von $f$.
\end{itemize}
\end{theorem}
%
\proof
hier nicht, siehe z.B. Stoer.
\eproof
%
$\longrightarrow$ \"Ubung.\\
Die Voraussetzungen geben die Klassen von Funktionen an,
auf die Alg. \ref{3.2.18} anwendbar ist. 
