\subsection{Praktische Realisierung des modifizierten Newton--Verfahrens}

Problem bei der Berechnung ist, da{\ss} in jedem Schritt $Df(x^{(k)})$
ausgerechnet werden mu{\ss}. \\
Idee: approximiere $Df(x^{(k)})$ durch 
$\bigtriangleup f (x^{(k)}) = (\bigtriangleup_1 f, \cdots, \bigtriangleup_n f)
(x^{(k)})$ (Differenzenquotientenmatrix), wobei
%
\[
 \bigtriangleup_i f(x) = \frac{f(x_1,\dots,x_{i-1}, x_i + h_i, 
				 x_{i+1},\dots,x_n) 
                              -f(x_1,\dots,x_n)}{h_i} = 
 \frac{f(x+h_ie_i)-f(x)}{h_i}.
\]
%
Schwierigkeiten: 
$h_i$ zu gro{\ss} $\longrightarrow$ schlechte Approximation an $Df(x)$,
$h_i$ zu klein, dann $f(x+he_i) \approx f(x).$\\
W\"ahle $h_i$ so, da{\ss} $f(x)$ und $f(x+he_i)$ ungef\"ahr die $\frac{t}{2}$
ersten Stellen gemeinsam haben ($t$--stellige Rechnung)
\[
 | h_i | \approx \sqrt{eps} \| f(x) \| / \| \bigtriangleup_i f(x)\|
\]
%
\underline{Ausl\"oschung is dann noch ertr\"aglich.} \reversemarginpar\marginpar{\huge \hfill !}\\
Im allgemeinen ist jedoch auch die Berechnung von $\bigtriangleup f$ 
zu teuer daher verwende folgende Vereinfachung mit 
\underline{Satz von Broyden:}
%
\begin{theorem}\label{3.2.20}
Seien $A, B \in \R^{n,n}, b \in \R^n, F:\R^n \to \R^n$
gegeben durch $F(u) = Au+b, \; x,x'\in \R^n$ und $p=x-x', \; q=F(x')-F(x)=Ap.$
Dann gilt f\"ur die Rang--1--Modifikation $B' = B + \frac{1}{p^Tp} (q-Bp)p^T$ 
die Absch\"atzung
\[
\|B'-A\|_2 \le \|B-A\|_2
\]
und $B'p = Ap = q.$
\end{theorem}
%
\proof
$(B'-A) p = Bp + (q-Bp)-Ap = 0.$\\
F\"ur jedes $u \in \R^n$ mit $\|u\|_2 = 1$ existiert ein $v$ mit
\[
 u = \alpha p + v,\; v^Tp = 0, \; \|v\|_2 \le 1.
\]
Also folgt mit $\|u\|_2 = 1$
%
\[
 \|(B'-A)u\|_2 
 = \|(B'-A)v \|_2 
 = \|(B-A)v\|_2
\le\| B-A \|_2 \; \|v\|_2  
\le \|B-A\|_2.
\]
%
Also auch f\"ur $\|B'-A\|_2$, welches das Supremum \"uber alle $u$ ist.
\eproof
%
Also folgt, da{\ss} $DF(x) = A$ von $B'$ genau so gut approximiert wird wie
von $B$. $B'$ und $DF(x)$ transformieren $p$
in denselben Vektor. Die Idee ist nun, $f(x)$ durch eine affine Abbildung
zu approximieren (in der N\"ahe einer Nullstelle) und diese Idee anzuwenden.\\
Ersetze in Algorithmus \ref{3.2.18} den Teil in der Schleife.
%
\begin{algorithmus}[Broyden--Rang 1--Verfahren]\label{3.2.21} \quad\\
\begin{tabular}{lll}
\underline{Input:} & \multicolumn{2}{p{13.5cm}}{
		      $f(x): \R^n \to \R^n$ differenzierbar und 
		      $x^{(0)} \in \R^n$
		     }\\
\underline{Output:}& \multicolumn{2}{p{13.5cm}}{
		      Folge $x^{(k)}, k = 0,1,2,\dots$
                     }\\[2ex]
&FOR& {$k = 0,1,2,\dots$ UNTIL SATISFIED}\\
&   &$d^{(k)}  = B^{-1}_k f (x^{(k)})$\\
&   &$x^{(k+1)}= x^{(k)} - \lambda_k d^{(k)}$\\
&   &$p^{(k)}  = x^{(k+1)} - x^{(k)}$\\
&   &$q^{(k)}  = f^{(x^{(k+1)})} - f(x^{(k)})$\\
&   &$B^{(k+1)}= B_k + \frac{1}{p^{(k)^T} p^{(k)}}
                 (q^{(k)} - B_k p^{(k)}) p^{(k)^T}$\\
&END& 
\end{tabular}
\end{algorithmus}


$\lambda_k$ wird durch n\"aherungsweise Minimierung von
$\|f(x^{(k+1)}) \|^2 \approx \min\limits_{\lambda \ge 0}
\|f(x^{(k)} - \lambda d^{(k)}) \|^2$ bestimmt wie vorher.\\
$B_0 \approx \bigtriangleup f(x^{(0)})$. 
Praktische Erfahrung zeigt, da{\ss} man diese Wahl
von $B_{k+1}$ nur f\"ur $0.5 \le \lambda_k \le 1$ machen sollte, sonst besser
$B_{k+1} = \bigtriangleup f(x_{k+1}).$\\
Die L\"osung des linearen Gleichungssystems
\[
 B_k d^{(k)} = f(x^{(k)})
\]
kann \"uber Rang 1 Aufdatierungsformel sehr leicht gemacht werden.\\
 $\longrightarrow$ \"Ubung \ref{numI/uebung053}: Sherman--Morrison Formel\\ 
 $\longrightarrow$ Zusammenhang modifiziertes Newton -- Sekantenverfahren -- 
andere Verfahren.
