%% LyX 1.3 created this file. For more info, see http://www.lyx.org/. %% Do not edit unless you really know what you are doing. \documentclass[german]{amsart} \usepackage[T1]{fontenc} \usepackage[latin1]{inputenc} \usepackage{a4wide} \setlength\parskip{\medskipamount} \setlength\parindent{0pt} \makeindex \usepackage{graphicx} \usepackage{amssymb} \makeatletter %%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands. %% Because html converters don't know tabularnewline \providecommand{\tabularnewline}{\\} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Textclass specific LaTeX commands. \theoremstyle{plain} % \newtheorem{thm}{Theorem}[section] \newtheorem{thm}{Satz}[section] \numberwithin{equation}{section} %% Comment out for sequentially-numbered \numberwithin{figure}{section} %% Comment out for sequentially-numbered \theoremstyle{remark} \newtheorem*{rem*}{Bemerkung} \theoremstyle{plain} \newtheorem{lem}[thm]{Lemma} %%Delete [thm] to re-start numbering \theoremstyle{definition} \newtheorem*{defn*}{Definition} \theoremstyle{definition} \newtheorem*{example*}{Beispiel} \theoremstyle{plain} \newtheorem{algorithm}[thm]{Algorithmus} %%Delete [thm] to re-start numbering \theoremstyle{remark} \newtheorem{rem}[thm]{Bemerkung} \theoremstyle{remark} \newtheorem*{conclusion*}{Folgerung} \theoremstyle{remark} \newtheorem*{summary*}{Zusammenfassung} \theoremstyle{plain} \newtheorem*{lem*}{Lemma} %%Delete [thm] to re-start numbering %%%%%%%%%%%%%%%%%%%%%%%%%%%%%% User specified LaTeX commands. \usepackage{wasysym} \usepackage{floatflt} \newcommand{\R}{\mathbb{R}} \newcommand{\N}{\mathbb{N}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\C}{\mathbb{C}} \newcommand{\contra}{\lightning} \usepackage{babel} \makeatother \begin{document} \title{Numerische Mathematik I} \maketitle \begin{center}{\large Vorlesungsmitschrift}% \footnote{Mitschrift von Stefan Vigerske und Daniel Seifert. Gefundene Fehler bitte an vigerske@mathematik.hu-berlin.de.% } {\large zur Vorlesung von Prof. März im Sommersemester 2002, HU-Berlin}\end{center}{\large \par} \vfill{} Die Numerische Mathematik beschäftigt sich mit der Entwicklung und Analyse (theoretisch und experimentell) von Methoden, Algorithmen und Software zur approximativen Lösung% \footnote{wobei das Berechnen dieser Lösung effektiv und zuverlässig sein soll% } von Problemklassen. Ziele dieser Lehrveranstaltung sind: \begin{enumerate} \item Vermittlung von Grundwissen zu elementaren Problemklassen: \noindent nichtlineare Gleichungen, Minimierungsprobleme, Interpolation, numerische Berechnung von Integralen, Berechnung von Eigenwerten, numerische Lösung von Differentialgleichungen \item Erfahrungen zum Umgang mit numerischer Software \item algorithmisches konstruktives Denken\vfill{} \end{enumerate} \begin{thebibliography}{DH93} \bibitem[SB89]{StoerBulischNumerik1}J. Stoer / R. Bulisch: Numerische Mathematik 1, Springer '89, $\geq$5. Auflage \bibitem[SB90]{StoerBulischNumerik2}J. Stoer / R. Bulisch: Numerische Mathematik 2, Springer '90, $\geq$3. Auflage \bibitem[DH93]{DeuflhardHohmanNumerik}P. Deuflhard, A. Hohman: Numerische Mathematik I, de Gruyter 1993 \bibitem[S79]{Schwetlick}H. Schwetlick, Numerische Lösung nichtlinearer Gleichungen, Dt. Verlag derWissenschaften, Berlin 1979 \bibitem[S93]{SchwarzNumerik}H. R. Schwarz, Numerische Mathematik, B.G. Teubner Stuttgart 1993, 3. Auflage \end{thebibliography} \newpage \tableofcontents{} \newpage \section{Nichtlineare Gleichungen im $\R^{m}$ } Ziel ist die Lösung von Gleichungen \[ \boxed{f(x)=0}\] mit $f:D\subseteq\R^{m}\rightarrow\R^{m}$, wobei $D$ eine offene Menge ist und $f\in C^{1}$. Beispiele: \begin{itemize} \item Extremalpunkte zu $\varphi:\R^{m}\rightarrow\R$, $\varphi\in C^{2}$, $\varphi'\left(x\right)=0$ (Analysis) \medskip{} \item Schnittpunkte von Kurven, ... \medskip{} \item Stationäre Lösung von Differentialgleichungen der Form $x'\left(t\right)=f\left(x\left(t\right)\right)$, wobei $\bar{x}\left(t\right)=c$ ist stationäre Lösung genau dann, wenn $f\left(c\right)=0$. \medskip{} \item Gleichungen in unendlich-dimensionalen Räumen: $F\left(x\right)=0$ / Diskretisierung \end{itemize} \subsection{Einfachste Fälle und Lösbarkeit} \begin{itemize} \item Lineare Gleichungen:\[ f\left(x\right)=Ax-b,\] $x\in\R^{m}$, $A\in L\left(\R^{m}\right)$, $b\in\R^{m}$, $A$ regulär $\leadsto$ $\exists!x^{*}\in\R^{m}$ mit $f\left(x^{*}\right)=0$\[ \leadsto\, x_{*}=A^{-1}b\] In der Praxis wird man diese explizite Lösungsangabe aber nicht benutzen, sondern stattdessen die Gleichung $Ax-b=0$ betrachten. \medskip{} \item $m=1$, $f$ Polynom der Form $f\left(x\right)=a_{0}x^{p}+\ldots+a_{p}$, $a_{i}\in\R$. Dies ist für $p\leq4$ mit Lösungsformel lösbar, allerdings sind auch diese vom numerischen Gesichtspunkt eher unbrauchbar. \medskip{} \item Kurvenschnittstellen:% \begin{figure}[htbp] \begin{center}\includegraphics[% width=0.70\paperwidth, keepaspectratio]{1.eps}\end{center} \caption{Schnittstellen von 2 Kurven} \end{figure} \end{itemize} \begin{rem*} Wir schreiben im folgenden $\left|.\right|$ für die Vektornorm auf $\R^{m},\C^{m}$. Desweiteren sei $\left\Vert .\right\Vert $ die Matrix-Norm auf $L\left(\R^{m}\right),$ induziert durch $\left|.\right|$, $\left\Vert I\right\Vert =1$:\[ A\in L\left(\R^{m},\R^{n}\right):\quad\left\Vert A\right\Vert :=\max_{x\in\R^{m},\left|x\right|=1}\left|Ax\right|=\max_{x\in\R^{m},x\neq0}\frac{\left|Ax\right|}{\left|x\right|}\] \end{rem*} Die Regularität einer Matrix wird uns im folgenden noch öfter als Kriterium für bestimmte Eigenschaften dienen. Da in der Numerischen Mathematik oftmals mit Werten (inkl. Matrizen) gerechnet wird, welche aufgrund von Fehlern leicht vom korrekten Wert abweichen, ist es interessant zu wissen, wie stark eine Matrix sich ändern darf, ohne ihre Regularität zu verlieren: \begin{lem} \label{lem:St=F6rungslemma}(\underbar{Störungslemma}\index{Störungslemma}, \underbar{Banach-Lemma}\index{Banach-Lemma})% \marginpar{Störungs\-lemma% } Seien $A,C\in L\left(\R^{m}\right)$, $A$ sei regulär, $\left\Vert A-C\right\Vert \leq\alpha$ und $\left\Vert A^{-1}\right\Vert \alpha<1$. Dann ist $C$ regulär und es gilt: \[ \boxed{\left\Vert C^{-1}\right\Vert \leq\frac{\left\Vert A^{-1}\right\Vert }{1-\alpha\left\Vert A^{-1}\right\Vert }}\] \end{lem} \begin{proof} ~\begin{eqnarray*} C & = & A\left(I-\underbrace{A^{-1}\left(A-C\right)}_{=:B}\right)=A\left(I-B\right)\\ \left\Vert B\right\Vert & \leq & \left\Vert A^{-1}\right\Vert \cdot\left\Vert A-C\right\Vert \leq\left\Vert A^{-1}\right\Vert \cdot\alpha<1\end{eqnarray*} $\leadsto$ $I-B$ ist regulär% \footnote{Wäre $\left(I-B\right)z=0,z\neq0$ $\leadsto$ $Bz=z,z\neq0$ $\leadsto$ $\frac{\left|Bz\right|}{\left|z\right|}=1$ $\leadsto$ $\left\Vert B\right\Vert ={\displaystyle \max_{z\neq0}}\frac{\left|Bz\right|}{\left|z\right|}\geq1$ \contra. Oder: $B$ ist kontraktiv $\leadsto$ Es ex. genau ein Fixpunkt. Wegen $B\cdot0=0$ muß dann für alle $z\neq0$ $Bz\neq z$ gelten.% } $\leadsto$ $C$ ist regulär, $C^{-1}=\left(I-B\right)^{-1}A^{-1}$\begin{eqnarray*} 1 & = & \left\Vert I\right\Vert =\left\Vert \left(I-B\right)\cdot\left(I-B\right)^{-1}\right\Vert \\ & = & \left\Vert \left(I-B\right)^{-1}-B\left(I-B\right)^{-1}\right\Vert \\ & \geq & \left\Vert \left(I-B\right)^{-1}\right\Vert -\left\Vert B\left(I-B\right)^{-1}\right\Vert \\ & \geq & \left\Vert \left(I-B\right)^{-1}\right\Vert -\left\Vert B\right\Vert \cdot\left\Vert \left(I-B\right)^{-1}\right\Vert \\ & = & \left\Vert \left(I-B\right)^{-1}\right\Vert \cdot\left(1-\left\Vert B\right\Vert \right)\\ \leadsto\,\left\Vert \left(I-B\right)^{-1}\right\Vert & \leq & \frac{1}{1-\left\Vert B\right\Vert }\\ \leadsto\,\left\Vert C^{-1}\right\Vert =\left\Vert \left(I-B\right)^{-1}A^{-1}\right\Vert & \leq & \frac{1}{1-\left\Vert B\right\Vert }\cdot\left\Vert A^{-1}\right\Vert \leq\frac{\left\Vert A^{-1}\right\Vert }{1-\alpha\left\Vert A^{-1}\right\Vert }\end{eqnarray*} \end{proof} \begin{rem*} Sei $A\left(s\right)=\left(a_{i,j}\left(s\right)\right)_{i,j}\in L\left(\R^{n},\R^{m}\right)$, $s\in\left[a,b\right]$. Dann ist $\int_{a}^{b}A$ wie folgt definiert:\begin{eqnarray*} \int_{a}^{b}A\left(s\right)ds & := & \left(\int_{a}^{b}a_{i,j}\left(s\right)ds\right)_{i,j}\end{eqnarray*} Weiterhin gilt\[ \left\Vert \int_{a}^{b}A\left(s\right)ds\right\Vert \leq\left|\int_{a}^{b}\left\Vert A\left(s\right)\right\Vert ds\right|\] \end{rem*} \begin{lem} \label{lem:Integralmittelwertsatz}(\underbar{Integralmittelwertsatz}\index{Integralmittelwertsatz}) % \marginpar{Integral\-mittel\-wert\-satz% } Sei $f\in C^{1}\left(D,\R^{m}\right)$, $D\subseteq\R^{m}$ offen, $x,y\in D,\left[x,y\right]\subset D$. Dann gilt:\[ \boxed{f\left(x\right)-f\left(y\right)=\int_{0}^{1}f'\left(sx+\left(1-s\right)y\right)ds\cdot\left(x-y\right)}\] \end{lem} \begin{proof} Wir fixieren $i\in\left\{ 1,\ldots,m\right\} .$ Sei \[ g_{i}\left(s\right):=f_{i}\left(sx+\left(1-s\right)y\right),\quad s\in\left[0,1\right].\] $g_{i}$ ist stetig differenzierbar auf dem Intervall $\left[0,1\right]$. Hauptsatz der Infinitisimalrechnung:\begin{eqnarray*} g_{i}\left(1\right)-g_{i}\left(0\right) & = & \int_{0}^{1}\frac{d}{ds}g_{i}\left(s\right)ds\\ \leadsto\, f_{i}\left(x\right)-f_{i}\left(y\right) & = & \int_{0}^{1}\sum_{j=1}^{m}\frac{\partial f_{i}}{\partial x_{j}}\left(sx+\left(1-s\right)y\right)\cdot\left(x_{j}-y_{j}\right)ds\\ & = & \sum_{j=1}^{m}\int_{0}^{1}\frac{\partial f_{i}}{\partial x_{j}}\left(sx+\left(1-s\right)y\right)ds\cdot\left(x_{j}-y_{j}\right),\quad i=1,\ldots,m\end{eqnarray*} \end{proof} \subsection{Newton-Verfahren und Sekantenverfahren} \subsubsection{Newton-Verfahren} ~\index{Newton-Verfahren} Sei zunächst $m=1$: Gesucht ist die Lösung von $f\left(x\right)=0$. Wir wählen $x_{0}$ beliebig und berechnen die Tangente $g_{0}$ an $f\left(x_{0}\right)$ (Taylorentwicklung 1. Ordnung):\[ g_{0}\left(x\right):=f\left(x_{0}\right)+f'\left(x_{0}\right)\left(x-x_{0}\right)\] Sei $x_{1}$ die Nullstelle von $g_{0},$ d.h. $g_{0}\left(x_{1}\right)=0.$ Dann gilt \[ x_{1}=x_{0}-f'\left(x_{0}\right)^{-1}\cdot f\left(x_{0}\right)\] Wir wiederholen diese Schritte jetzt. Sei nun $m\geq1$ beliebig: Wir approximieren $f\left(x\right)$ durch \begin{eqnarray*} g_{0}\left(x\right) & := & f\left(x_{0}\right)+f'\left(x_{0}\right)\left(x-x_{0}\right),\quad x_{0}\in D,x\in\R^{m}\end{eqnarray*} (,,Linearisierung'') und lösen zuerst das lineare Problem $g_{0}\left(x\right)=0,$ d.h. \begin{eqnarray*} f'\left(x_{0}\right)\left(x-x_{0}\right) & = & -f\left(x_{0}\right).\\ \leadsto\, x_{1} & = & x_{0}-f'\left(x_{0}\right)^{-1}\cdot f\left(x_{0}\right)\end{eqnarray*} Dabei ist sicherzustellen, daß $f'\left(x_{0}\right)$ regulär ist und $x_{1}\in D$ gilt. Bei dem Newton-Verfahren handelt es sich um ein iteratives Verfahren der linearen Approximierung (iterative Linearisierung) von $f\left(x\right)$ durch \begin{eqnarray*} g_{i}\left(x\right) & := & f\left(x_{i}\right)+f'\left(x_{i}\right)\left(x-x_{i}\right).\end{eqnarray*} Dabei bezeichnen wir $x_{0}$ als Startwert\index{Startwert}. Newton-Verfahren mit Startwert $x_{0}:$% \marginpar{Newton-Verfahren% } \[ \boxed{\begin{array}{rcl} x_{j} & := & x_{j-1}+z_{j}\smallskip\\ \textrm{mit }z_{j}\textrm{ aus }f'\left(x_{j-1}\right)z_{j} & = & -f\left(x_{j-1}\right),\, j\geq1\end{array}}\] \begin{defn*} Das Newton-Verfahren mit dem Startwert $x_{0}$ heißt \underbar{durchführbar}\index{durchführbar}% \marginpar{durch\-führ\-bar% }, falls es eine Folge $\left\{ x_{j}\right\} _{j\geq0}$ gibt, so daß $x_{j}\in D$ und $f'\left(x_{j}\right)$ regulär sind, $j\geq0.$ \end{defn*} \begin{thm} \label{lok_Konvergenzsatz_Newton_Verfahren}\index{Konvergenzsatz!Newton-Verfahren, lokal}\index{Newton-Verfahren!lokale Konvergenz}(lokaler Konvergenzsatz für das Newton-Verfahren)% \marginpar{lokaler Konvergenzsatz% } Sei $f\in C^{1}\left(D,\R^{m}\right)$, $D\subseteq\R^{m}$ offen, $x_{*}\in D$, $f\left(x_{*}\right)=0$ und $f'\left(x_{*}\right)$ regulär. Dann gilt \begin{enumerate} \item Es existiert eine Kugel $\bar{B}\left(x_{*},\rho\right)$, $\rho>0$, derart, daß das Newton-Verfahren mit einem Startwert $x_{0}\in\bar{B}\left(x_{*},\rho\right)$ durchführbar ist und eine gegen $x_{*}$ konvergente Folge $\left\{ x_{j}\right\} _{j\geq0}$ liefert, mit $x_{j}\in\bar{B}\left(x_{*},\rho\right)$. \item Sei $x_{0}\in\bar{B}\left(x_{*},\rho\right)$. Dann gilt\[ \left|x_{j}-x_{*}\right|\leq q_{j}\cdot\left|x_{j-1}-x_{*}\right|,\quad j\geq1\] mit einer Nullfolge $\left\{ q_{j}\right\} _{j\geq1}$. \medskip{} \item Gilt zusätzlich, daß die Jacobi-Matrix Lipschitz-stetig ist, d.h. \[ \left\Vert f'\left(x\right)-f'\left(\bar{x}\right)\right\Vert \leq L\left|x-\bar{x}\right|,\quad x,\bar{x}\in\bar{B}\left(x_{*},\rho\right),L\in\R^{+}\] so gilt die quadratische Konvergenz: \[ \left|x_{j}-x_{*}\right|\leq q_{j}\left|x_{j-1}-x_{*}\right|^{2},\quad j\geq1,q\in\R^{+}\] \newpage \end{enumerate} \end{thm} \begin{proof} ~ \begin{enumerate} \item Da $f'$ in $x_{*}$ stetig ist, existiert zu jedem $\varepsilon>0$ ein $\rho\left(\varepsilon\right)>0$, so daß\[ \left\Vert f'\left(x\right)-f'\left(x_{*}\right)\right\Vert \leq\varepsilon\quad\textrm{für }x\in\bar{B}\left(x_{*},\rho\left(\varepsilon\right)\right)\subset D.\] Sei $\varepsilon>0$ so, daß $\varepsilon\cdot\left\Vert f'\left(x_{*}\right)^{-1}\right\Vert <1$. Nach Störungslemma (L. \ref{lem:St=F6rungslemma}) ist $f'\left(x\right)$ regulär und \[ \left\Vert f'\left(x\right)^{-1}\right\Vert \leq\frac{\left\Vert f'\left(x_{*}\right)^{-1}\right\Vert }{1-\varepsilon\cdot\left\Vert f'\left(x_{*}\right)^{-1}\right\Vert },\quad x\in\bar{B}\left(x_{*},\rho\left(\varepsilon\right)\right)\] Wir wählen einen Startwert $x_{0}\in\bar{B}\left(x_{*},\rho\left(\varepsilon\right)\right)$. Dann gilt:\begin{eqnarray*} x_{1}-x_{*} & = & x_{0}-x_{*}-f'\left(x_{0}\right)^{-1}\cdot f\left(x_{0}\right).\\ \leadsto\, x_{1}-x_{*} & \stackrel{\textrm{L. }\ref{lem:Integralmittelwertsatz}}{=} & x_{0}-x_{*}-f'\left(x_{0}\right)^{-1}\cdot\int_{0}^{1}f'\left(sx_{0}+\left(1-s\right)x_{*}\right)ds\cdot\left(x_{0}-x_{*}\right)\\ & = & f'\left(x_{0}\right)^{-1}\cdot\left\{ f'\left(x_{0}\right)-\int_{0}^{1}f'\left(sx_{0}+\left(1-s\right)x_{*}\right)ds\right\} \cdot\left(x_{0}-x_{*}\right)\\ \leadsto\,\left|x_{1}-x_{*}\right| & \leq & \left\Vert f'\left(x_{0}\right)^{-1}\right\Vert \cdot\int_{0}^{1}\underbrace{\left\Vert f'\left(x_{0}\right)-f'\left(sx_{0}+\left(1-s\right)x_{*}\right)\right\Vert }_{\leq\left\Vert f'\left(x_{0}\right)-f'\left(x_{*}\right)\right\Vert +\left\Vert f'\left(x_{*}\right)-f'\left(sx_{0}+\left(1-s\right)x_{*}\right)\right\Vert <2\varepsilon}ds\cdot\left|x_{0}-x_{*}\right|\\ & \leq & \underbrace{\frac{\left\Vert f'\left(x_{*}\right)^{-1}\right\Vert }{1-\varepsilon\left\Vert f'\left(x_{*}\right)^{-1}\right\Vert }\cdot2\varepsilon}_{=:\eta\left(\varepsilon\right)}\cdot\left|x_{0}-x_{*}\right|\end{eqnarray*} $\eta$ ist stetig und $\eta\left(0\right)=0.$ Gesucht ist ein hinreichend kleines $\varepsilon$ mit $\eta\left(\varepsilon\right)<1$. \medskip{} \noindent Sei $\varepsilon\cdot\left\Vert f'\left(x_{*}\right)^{-1}\right\Vert <\frac{1}{3}$. Dann ist $\eta\left(\varepsilon\right)<1$. Wir fixieren ein solches $\varepsilon$.\\ Sei $\rho:=\rho\left(\varepsilon\right)$, $\eta:=\eta\left(\varepsilon\right)$, $x_{0}\in\bar{B}\left(x_{*},\rho\right)$. Damit ist \begin{eqnarray*} \left|x_{1}-x_{*}\right| & \leq & \eta\left|x_{0}-x_{*}\right|\qquad\leadsto\quad x_{1}\in\bar{B}\left(x_{*},\rho\right)\\ \leadsto\,\left|x_{i}-x_{*}\right| & \leq & \eta\left|x_{i-1}-x_{*}\right|\leq\eta^{i}\left|x_{0}-x_{*}\right|\xrightarrow{i\rightarrow\infty}0.\end{eqnarray*} \item Es gilt\begin{eqnarray*} x_{j}-x_{*} & = & x_{j-1}-x_{*}-f'\left(x_{j-1}\right)^{-1}\left(f\left(x_{j-1}\right)-f\left(x_{*}\right)\right),\textrm{ da }f\left(x_{*}\right)=0\\ & = & f'\left(x_{j-1}\right)^{-1}\left(f'\left(x_{j-1}\right)-\int_{0}^{1}f'\left(sx_{j-1}+\left(1-s\right)x_{*}\right)ds\right)\left(x_{j-1}-x_{*}\right)\\ \leadsto\,\left|x_{j}-x_{*}\right| & \leq & \underbrace{\frac{\left\Vert f'\left(x_{*}\right)^{-1}\right\Vert }{1-\varepsilon\left\Vert f'\left(x_{*}\right)^{-1}\right\Vert }\cdot\int_{0}^{1}\left\Vert \underbrace{f'\left(x_{j-1}\right)}_{\rightarrow f'\left(x_{*}\right)}-\underbrace{f'\left(sx_{j-1}+\left(1-s\right)x_{*}\right)}_{\rightarrow f'\left(x_{*}\right)}\right\Vert }_{=:q_{j}\xrightarrow{j\rightarrow\infty}0}ds\cdot\left|x_{j-1}-x_{*}\right|\end{eqnarray*} \medskip{} \item Wie in $\left(2\right)$ erhalten wir\begin{eqnarray*} \left|x_{j}-x_{*}\right| & \leq & \frac{\left\Vert f'\left(x_{*}\right)^{-1}\right\Vert }{1-\varepsilon\left\Vert f'\left(x_{*}\right)^{-1}\right\Vert }\cdot\int_{0}^{1}\underbrace{\left\Vert f'\left(x_{j-1}\right)-f'\left(sx_{j-1}+\left(1-s\right)x_{*}\right)\right\Vert }_{\leq\left(1-s\right)\cdot L\left|x_{j-1}-x_{*}\right|}ds\cdot\left|x_{j-1}-x_{*}\right|\\ & \leq & \frac{\left\Vert f'\left(x_{*}\right)^{-1}\right\Vert }{1-\varepsilon\left\Vert f'\left(x_{*}\right)^{-1}\right\Vert }\cdot\frac{1}{2}L\cdot\left|x_{j-1}-x_{*}\right|^{2},\qquad q:=\frac{\left\Vert f'\left(x_{*}\right)^{-1}\right\Vert }{1-\varepsilon\left\Vert f'\left(x_{*}\right)^{-1}\right\Vert }\cdot\frac{1}{2}L\end{eqnarray*} \end{enumerate} \end{proof} \pagebreak \begin{defn*} (Begriffe zur Konvergenzgeschwindigkeit\index{Konvergenzgeschwindigkeit}) \begin{itemize} \item Falls eine Folge $\left\{ x_{j}\right\} _{j\geq0}$, die gegen ein $x_{*}$ konvergiert, der Ungleichung% \marginpar{lineare Konvergenz% }\[ \boxed{\left|x_{j}-x_{*}\right|\leq\alpha\left|x_{j-1}-x_{*}\right|,\quad j\geq1,\,\alpha\in\left(0,1\right)}\] genügt, so spricht man von \underbar{linearer Konvergenz}\index{Konvergenz!linear}. \medskip{} \item Gilt eine Ungleichung% \marginpar{überlineare Konvergenz% }\[ \boxed{\left|x_{j}-x_{*}\right|\leq q_{j}\left|x_{j-1}-x_{*}\right|,\quad j\geq1,\, q_{j}\xrightarrow{j\rightarrow\infty}0}\] so spricht man von \underbar{überlinearer Konvergenz}\index{Konvergenz!überlinear} (superlineare Konvergenz). \medskip{} \item Gilt eine Ungleichung% \marginpar{quadratische Konvergenz% }\[ \boxed{\left|x_{j}-x_{*}\right|\leq q\left|x_{j-1}-x_{*}\right|^{2},\quad j\geq1,\, q>0}\] so spricht man von \underbar{quadratischer Konvergenz}\index{Konvergenz!quadratisch}. \end{itemize} \end{defn*} % \begin{defn*} Der \underbar{Einzugsbereich}\index{Einzugsbereich}\index{Newton-Verfahren!Einzugsbereich}% \marginpar{Einzugs\-bereich% } der Nullstelle $x_{*}$ der Funktion $f$ ist die Menge der Startwerte $x_{0}\in D$, für die das Newton-Verfahren durchführbar ist und eine Folge $\left\{ x_{j}\right\} _{j\geq0}\subseteq D$ mit $x_{j}\xrightarrow{j\rightarrow\infty}x_{*}$ liefert. Die Teilmenge des Einzugsbereiches, für welche die Ungleichung $\left|x_{j}-x_{*}\right|\leq q\left|x_{j-1}-x_{*}\right|^{2}$ mit $q>0$ und $j\geq1$ relevant ist, bezeichnen wir als den \underbar{Bereich der quadratischen Konvergenz\index{Bereich der quadratischen Konvergenz}}. \end{defn*} \begin{rem*} (zu Satz \ref{lok_Konvergenzsatz_Newton_Verfahren}): \begin{enumerate} \item Lokale Konvergenz ist naturgemäß bei nichtlinearen Problemen die einzige mögliche Aussage. Globale Konvergenzsätze haben stets eine Einschränkung des Definitionsbereiches beziehungsweise der betrachteten Funktionen zur Folge. \medskip{} \item Kann man auf die Regularität von $f'\left(x_{*}\right)$ verzichten? Die Antwort darauf ist ,,ja'', allerdings sollte man in der Regel nicht auf die Regularität verzichten, wie wir am folgenden Beispiel sehen werden. \begin{example*} Sei $m=1$, $f\left(x\right):=\left(x-1\right)^{k}$, $k>1$ $\leadsto$ $x_{*}=1$ \medskip{} \noindent $f'\left(x\right)=k\cdot\left(x-1\right)^{k-1},\, x_{0}\neq1$\begin{eqnarray*} x_{j} & = & x_{j-1}-\frac{f\left(x_{j-1}\right)}{f'\left(x_{j-1}\right)}=x_{j-1}-\frac{x_{j-1}-1}{k}\\ x_{j}-x_{*}=x_{j}-1 & = & \underbrace{\left(1-\frac{1}{k}\right)}_{=:\alpha}\left(x_{j-1}-1\right)\\ \leadsto\, x_{j} & \xrightarrow{j\rightarrow\infty} & 1\end{eqnarray*} Das Verfahren konvergiert also trotz fehlender Regularität, allerdings ist nur lineare Konvergenz möglich. \end{example*} \end{enumerate} \end{rem*} \newpage \subsubsection{Sekantenverfahren} ~\index{Sekantenverfahren} Zunächst sei $m=1$: Gesucht ist die Lösung von $f(x)=0$. Wir wählen $x_{0}$ und $x_{1}=x_{0}+h$ und berechnen die Sekante durch $f\left(x_{0}\right)$ und $f\left(x_{0}+h\right)$: \vspace{0.3cm} \begin{center}% \begin{figure}[htbp] \begin{center}\includegraphics[% width=0.60\columnwidth]{2.eps}\end{center} \caption{$g_{0}\left(x\right)=f\left(x_{0}\right)+\frac{1}{h}\left(f\left(x_{0}+h\right)-f\left(x_{0}\right)\right)\left(x-x_{0}\right)$} \end{figure} \end{center} \vspace{0.3cm} Für $m\geq1$ definieren wir die Differenzenquotientenmatrix $F\left(x,h\right)\in L\left(\R^{m}\right)$ mit $x\in D$ und hinreichend kleiner Schrittweitenmatrix $h\in L\left(\R^{m}\right)$ als\[ \boxed{\left(F\left(x,h\right)\right)_{i,j}:=\left\{ \begin{array}{cc} {\displaystyle \frac{1}{h_{i,j}}\left(f_{i}\left(x+h_{i,j}e_{j}\right)-f_{i}\left(x\right)\right)} & \textrm{falls }h_{i,j}\neq0\smallskip\\ {\displaystyle \frac{\partial f_{i}}{\partial x_{j}}\left(x\right)} & \textrm{falls }h_{i,j}=0\end{array}\right.\qquad i,j=1,\ldots,m}\] $F\left(x,h\right)$ ist stetig: $F\left(x_{*},0\right)=f'\left(x_{*}\right)$ und es gilt nach dem Hauptsatz der Infinitisimalrechnung:\begin{eqnarray*} \left(F\left(x,h\right)\right)_{i,j} & = & \int_{0}^{1}f_{i}'\left(x+sh_{ij}e_{j}\right)ds\\ F\left(x,0\right) & = & f'\left(x\right)\end{eqnarray*} Sei $x_{*}\in D$, $f\left(x_{*}\right)=0$, $f'\left(x_{*}\right)$ regulär. Dann ist $F\left(x_{*},0\right)=f'\left(x_{*}\right)$ regulär. Iterative Linearisierung: \begin{eqnarray*} g_{j}\left(x\right) & := & f\left(x_{j}\right)+F\left(x_{j},h_{j}\right)\left(x-x_{j}\right)\end{eqnarray*} $f\left(x\right)=0$ wird ersetzt durch $g_{j}\left(x\right)=0$ (lineare Gleichung) mit Lösung $x_{j+1}$: \[ F\left(x_{j},h_{j}\right)\left(x_{j+1}-x_{j}\right)=-f\left(x_{j}\right)\] \begin{algorithm} \underbar{Sekantenverfahren}% \marginpar{Sekanten\-ver\-fahren% } mit Startwert $x_{0}\in D$, $j\geq0$: \begin{enumerate} \item bestimme $F\left(x_{j},h_{j}\right)$ \medskip{} \item bestimme $z_{j+1}$ aus \[ \boxed{F\left(x_{j},h_{j}\right)z_{j+1}=-f\left(x_{j}\right)}\] \medskip{} \item setze \[ \boxed{x_{j+1}:=x_{j}+z_{j+1}}\] \end{enumerate} \end{algorithm} \begin{defn*} Das Sekantenverfahren heißt \underbar{durchführbar}\index{durchführbar}\index{Sekantenverfahren!durchführbar}% \marginpar{durch\-führbar% }, wenn $x_{j}\in D$ und $F\left(x_{j},h_{j}\right)$ regulär sind.\newpage \end{defn*} \begin{thm} \label{thm:lok_Konvergenzsatz_Sekantenverfahren}\index{Konvergenzsatz!Sekantenverfahren, lokal}\index{Sekantenverfahren!lokale Konvergenz}Sei $f\in C^{1}\left(D,\R^{m}\right)$, $D\subseteq\R^{m}$ offen, $x_{*}\in D$, $f\left(x_{*}\right)=0$ und $f'\left(x_{*}\right)$ regulär. Dann gilt:% \marginpar{lokaler Konvergenzsatz% } \begin{enumerate} \item Es gibt $\rho>0$, $\gamma>0$ derart, daß das Sekantenverfahren mit Startwerten $x_{0}\in\bar{B}\left(x_{*},\rho\right)$ und Schrittweiten aus dem Intervall $\left[-\gamma,\gamma\right]$ durchführbar ist und gegen $x_{*}$ konvergente Folgen liefert. \medskip{} \item Falls zusätzlich $h_{j}\xrightarrow{j\rightarrow\infty}0$ gilt, so konvergiert die Folge $\left\{ x_{j}\right\} _{j\geq0}$ überlinear gegen $x_{*}.$ \end{enumerate} \end{thm} \begin{proof} Wir wählen $\varepsilon>0$ mit $\varepsilon\cdot\left\Vert f'\left(x_{*}\right)^{-1}\right\Vert <\frac{1}{3}$. Wegen der Stetigkeit von $F$ existieren $\rho\left(\varepsilon\right)>0$ und $\gamma\left(\varepsilon\right)>0$ mit\[ \left\Vert F\left(x,h\right)-\underbrace{F\left(x_{*},0\right)}_{f'\left(x_{*}\right)}\right\Vert \leq\varepsilon,\quad x\in\bar{B}\left(x_{*},\rho\left(\varepsilon\right)\right),\,\left|h_{i,j}\right|\leq\gamma\left(\varepsilon\right)\] Nach dem Störungslemma (L. \ref{lem:St=F6rungslemma}) ist $F\left(x,h\right)$ regulär für $x\in\bar{B}\left(x_{*},\rho\left(\varepsilon\right)\right)$, $\left|h_{i,j}\right|\leq\gamma\left(\varepsilon\right)$:\[ \left\Vert F\left(x,h\right)^{-1}\right\Vert \leq\frac{\left\Vert f'\left(x_{*}\right)^{-1}\right\Vert }{1-\varepsilon\left\Vert f'\left(x_{*}\right)^{-1}\right\Vert },\quad x\in\bar{B}\left(x_{*},\rho\left(\varepsilon\right)\right),\left|h_{i,j}\right|\leq\gamma\left(\varepsilon\right)\] Sei $\rho:=\rho\left(\varepsilon\right)$, $\gamma:=\gamma\left(\varepsilon\right)$, $x_{0}\in\bar{B}\left(x_{*},\rho\right)$ und$\left|h_{0_{i,k}}\right|\leq\gamma$. $F\left(x_{0},h_{0}\right)$ ist regulär. Dann ist\begin{eqnarray*} x_{1}-x_{*} & = & x_{0}-x_{*}-F\left(x_{0},h_{0}\right)^{-1}\left\{ f\left(x_{0}\right)-f\left(x_{*}\right)\right\} \\ & \stackrel{\textrm{L. }\ref{lem:Integralmittelwertsatz}}{=} & F\left(x_{0},h_{0}\right)^{-1}\left\{ F\left(x_{0},h_{0}\right)-f'\left(x_{*}\right)+f'\left(x_{*}\right)-\int_{0}^{1}f'\left(sx_{0}+\left(1-s\right)x_{*}\right)ds\right\} \left(x_{0}-x_{*}\right)\\ \left|x_{1}-x_{*}\right| & \leq & \frac{\left\Vert f'\left(x_{*}\right)^{-1}\right\Vert }{1-\varepsilon\left\Vert f'\left(x_{*}\right)^{-1}\right\Vert }\left\{ \varepsilon+\varepsilon\right\} \left|x_{0}-x_{*}\right|\\ & = & \eta\left(\varepsilon\right)\left|x_{0}-x_{*}\right|,\quad\eta\left(\varepsilon\right)<1\\ \left|x_{j}-x_{*}\right| & \leq & \eta\left(\varepsilon\right)^{j}\left|x_{0}-x_{*}\right|\xrightarrow{j\rightarrow\infty}0\end{eqnarray*} Gilt nun zusätzlich $h_{j}\xrightarrow{j\rightarrow\infty}0$, so ist\begin{eqnarray*} x_{j}-x_{*} & = & \underbrace{F\left(x_{j},h_{j}\right)^{-1}}_{\xrightarrow{j\rightarrow\infty}f'\left(x_{*}\right)^{-1}}\left\{ \underbrace{F\left(x_{j},h_{j}\right)}_{\xrightarrow{j\rightarrow\infty}F\left(x_{*},0\right)=f'\left(x_{*}\right)}-\int_{0}^{1}\underbrace{f'\left(sx_{j}+\left(1-s\right)x_{*}\right)}_{\xrightarrow{j\rightarrow\infty}f'\left(x_{*}\right)}ds\right\} \left(x_{j-1}-x_{*}\right)\\ \leadsto\,\left|x_{j}-x_{*}\right| & \leq & \underbrace{\left\Vert F\left(x_{j},h_{j}\right)^{-1}\right\Vert }_{\xrightarrow{j\rightarrow\infty}\left\Vert f'\left(x_{*}\right)^{-1}\right\Vert }\cdot\underbrace{\left\Vert F\left(x_{j},h_{j}\right)-\int_{0}^{1}f'\left(sx_{j}+\left(1-s\right)x_{*}\right)ds\right\Vert }_{\xrightarrow{j\rightarrow\infty}0}\cdot\left\Vert x_{j-1}-x_{*}\right\Vert \end{eqnarray*} \end{proof} \begin{rem*} keine quadratische Konvergenz \end{rem*} \subsubsection{Praktische Schrittweitenwahl $h_{j}$} ~\index{Schrittweitenwahl} Bei der Wahl der Schrittweite $h_{j}$ in Abhängigkeit von $f$ und $x_{*}$ gilt zu beachten, daß nur eine schlechte Approximation erzielt wird, wenn $h_{j}$ zu groß gewählt ist. Ist $h_{j}$ zu niedrig, kommt es zu Auslöschungen und Fehlern. Standardvariante: Bezeiche $\varepsilon_{\textrm{abs}}$ die absolute und $\varepsilon_{\textrm{rel}}$ die relative Fehlervorgabe. Sei\begin{eqnarray*} \tau_{j}^{k} & := & \begin{cases} x_{j-1,k}-x_{j,k} & \textrm{falls }\left|x_{j-1,k}-x_{j,k}\right|\geq\varepsilon_{\textrm{rel}}\cdot\left|x_{j,k}\right|+\varepsilon_{\textrm{abs}}\\ \left|x_{j-1}-x_{j}\right| & \textrm{sonst}\end{cases}\qquad k=1,\ldots,m\\ h_{j} & := & \left(\begin{array}{ccc} \tau_{j}^{1} & \cdots & \tau_{j}^{m}\\ \vdots & & \vdots\\ \tau_{j}^{1} & \cdots & \tau_{j}^{m}\end{array}\right)\end{eqnarray*} \begin{eqnarray*} g_{j}\left(x\right) & = & f\left(x_{j}\right)+F\left(x_{j},h_{j}\right)\left(x-x_{j}\right)\\ \leadsto\, g_{j}\left(x_{j}\right) & = & f\left(x_{j}\right)\\ g_{j}\left(x_{j}+\tau_{j}^{k}e_{k}\right) & = & f\left(x_{j}\right)+F\left(x_{j},h_{j}\right)\tau_{j}^{k}e_{k}\\ & = & f\left(x_{j}\right)+\tau_{j}^{k}\frac{1}{\tau_{j}^{k}}\left(f\left(x_{j}+\tau_{j}^{k}e_{k}\right)-f\left(x_{j}\right)\right)\\ & = & f\left(x_{j}+\tau_{j}^{k}e_{k}\right),\qquad k=1,\ldots,m\end{eqnarray*} \subsubsection{Modifikationen des Newton-Verfahrens und Sekantenverfahrens} \begin{enumerate} \item Wird die Faktorisierung (der $F$-Matrix) über mehrere Iterationen hinweg beibehalten, so läßt sich der Rechenaufwand verringern.\begin{eqnarray*} x_{j+1} & = & x_{j}+z_{j+1}\\ z_{j+1}\textrm{ aus }F\left(x_{k_{j}},h_{k_{j}}\right)z_{j+1} & = & -f\left(x_{j}\right),\quad0\leq k_{j}\leq j\end{eqnarray*} Extremfall: $k_{j}=0$ ,,\underbar{Modifizierte} Newton-Verfahren''\index{Newton-Verfahren!modifiziert} \medskip{} \item Dämpfung\index{Dämpfung}\begin{eqnarray*} x_{j+1} & = & x_{j}+\alpha_{j+1}z_{j+1}\\ F\left(x_{j},h_{j}\right)z_{j+1} & = & -f\left(x_{j}\right)\end{eqnarray*} Der Dämpfungsparameter $\alpha_{j+1}\in\left(0,1\right]$ wird so bestimmt (z.B. durch Halbieren von $\alpha_{j}$), daß\[ \left|f\left(x_{j+1}\right)\right|<\left|f\left(x_{j}\right)\right|\] % \begin{figure}[htbp] \begin{center}\includegraphics[% width=0.50\paperwidth, keepaspectratio]{3.eps}\end{center} \caption{ohne Dämpfung} \end{figure} \end{enumerate} Der Vorteil der modifizierten Verfahren ist, daß sie nicht so stark vom Einzugsbereich abhängig sind wie das klassische Newton-Verfahren. \subsection{Quasi-Newton-Verfahren} ~\index{Quasi-Newton-Verfahren} Wir haben eine Funktion $f\left(x\right)$ linear approximiert durch \[ g_{j}\left(x\right):=f\left(x_{j}\right)+A_{j}\left(x-x_{j}\right)\] zur Berechnung von $x_{j}$. Im Newton-Verfahren war dabei $A_{j}$ die Jacobi-Matrix $\left(A_{j}:=f'\left(x_{j}\right)\right)$, im Sekantenverfahren war $A_{j}:=F\left(x_{j},h_{j}\right)$. Bei Funktionen mit hohen Kosten möchte man aber die Zahl der Funktionsaufrufe minimieren.\[ g_{j}\left(x\right):=f\left(x_{j}\right)+A_{j}\left(x-x_{j}\right)\] benutzt zur Berechnung von $x_{j+1}$ wieder ein $A_{j}$ und benötigt damit Funktionsaufrufe, welche wir uns sparen wollen. Nach Broyden\index{Broyden} (1965) können wir $A_{j}$ aus $A_{j-1}$ erhalten, ohne dabei auf die Funktion $f$ zurückgreifen zu müssen (sogenannte Aufdatierung). Festlegung: Quasi-Newton-Bedingung\index{Quasi-Newton-Bedingung}% \marginpar{Quasi-Newton-Bedingung% }:\[ \boxed{g_{j}\left(x_{j-1}\right)=f\left(x_{j-1}\right)}\] Alle Verfahren, in denen die Quasi-Newton-Bedingung gilt, bezeichnen wir als Quasi-Newton-Verfahren. Durch diese Bedingung können wir $A_{j}$ aus $A_{j-1}$ erhalten, ohne dabei auf die Funktion $f$ zurückgreifen zu müssen. Eine alternative Schreibweise für die Quasi-Newton-Bedingung ist:\[ \boxed{A_{j}\underbrace{\left(x_{j}-x_{j-1}\right)}_{=:z_{j}}=\underbrace{f\left(x_{j}\right)-f\left(x_{j-1}\right)}_{=:y_{j}}}\] Ist $z_{j}=0$, so war $f\left(x_{j-1}\right)=0$, also $x_{j-1}$ schon Nullstelle. $g'_{j-1}\left(x\right)=A_{j-1}$, $g'_{j}\left(x\right)=A_{j}$ Wir versuchen folgende Festlegung: $g'_{j}\left(x\right)z=g'_{j-1}\left(x\right)z$, $\forall z\bot z_{j}$. Dies bedeutet gerade, daß für alle $z\bot z_{j}$ mit $z_{j}\neq0$ gilt:\[ \left(A_{j}-A_{j-1}\right)z=0\] Ansatz : \[ A_{j}-A_{j-1}=u_{j}z_{j}^{T}\] mit noch zu bestimmenden $u_{j}\in\R^{m}$. Daraus folgt:\begin{eqnarray*} \left(A_{j}-A_{j-1}\right)z & = & u_{j}z_{j}^{T}z=u_{j}\left\langle z_{j},z\right\rangle =0\quad\textrm{für }z\bot z_{j}\\ \left(A_{j}-A_{j-1}\right)z_{j} & = & \left|z_{j}\right|_{2}^{2}\cdot u_{j}\\ \leadsto\, u_{j} & = & \frac{1}{\left|z_{j}\right|_{2}^{2}}\cdot\left(y_{j}-A_{j-1}z_{j}\right)\end{eqnarray*} Dies führt dann zur \underbar{Rang-Eins-Aufdatierungsformel}\index{Rang-Eins-Aufdatierungsformel} von Broyden ($\textrm{rg}\left(u_{j}z_{j}^{T}\right)=1$):% \marginpar{Auf\-da\-tier\-ungs\-for\-mel Broyden% }\[ \boxed{A_{j}=A_{j-1}+\frac{1}{\left|z_{j}\right|_{2}^{2}}\cdot\left(y_{j}-A_{j-1}z_{j}\right)\cdot z_{j}^{T}}\] \begin{thm} \label{thm:lok_Konvergenz_Quasi-Newton-Verfahren}\index{Quasi-Newton-Verfahren!lokale Konvergenz}\index{Konvergenzsatz!Quasi-Newton-Verfahren, lokal}Sei $f\in C^{1}\left(D,\R^{m}\right)$, $D\subseteq\R^{m}$ offen, $x_{*}\in D$, $f\left(x_{*}\right)=0$ und $f'\left(x_{*}\right)$ regulär. Dann gilt:% \marginpar{lokaler Konvergenzsatz% } \begin{enumerate} \item Für $x_{0}\in\bar{B}\left(x_{*},\rho\right)$, $A_{0}\in\bar{B}_{L\left(\R^{m}\right)}\left(f'\left(x_{*}\right),\delta\right)$ und $\rho,\delta>0$ hinreichend klein ist das Quasi-Newton-Verfahren mit Rang-Eins-Aufdatierung nach Broyden entweder durchführbar mit $x_{j}\stackrel{j\rightarrow\infty}{\longrightarrow}x_{*}$ oder es endet für ein $j_{*}\in\N$ mit $x_{j_{*}}=x_{*}$. \item Die Konvergenz ist überlinear. \end{enumerate} \end{thm} \begin{proof} \cite[S. 143]{Schwetlick} \end{proof} Das Quasi-Newton-Verfahren besitzt nur eine ,,langsame'' überlineare Konvergenz, daher wird es in der Praxis zusammen mit anderen Verfahren benutzt. Anzutreffen ist zum Beispiel die Kombination von Quasi-Newton-Schritten mit Sekanten-Schritten: \begin{itemize} \item Startwert $x_{0}$, $A_{0}=F\left(x_{0},h_{0}\right)$ \medskip{} \item $x_{1}$ als Sekantenschritt ($x_{1}=x_{0}+z_{1}$, $z_{1}$ aus $A_{0}z_{1}=-f\left(x_{0}\right)$), $A_{1}$ aus $A_{0}$ durch Aufdatierung \medskip{} \item Quasi-Newton-Schritte solange, wie die Korrekturen $z_{j+1}$ groß genug sind \medskip{} \item Wenn $z_{j+1}$ klein ist, dann neuer Sekantenschritt (anstatt Aufdatierung, sogenannte ,,Reinitialisierung''). \end{itemize} Weitere Aufdatierungen sind Rang-2, inverse Matrix, strukturerhaltende und symmetrieerhaltende Aufdatierungen. \subsection{Einbettung (Homotopie)} ~\index{Einbettung}\index{Homotopie} Bisher mußte $x_{0}$ immer hinreichend nahe an einer Nullstelle liegen, damit die Verfahren zu einer Lösung kamen (lokale Konvergenz). In diesem Abschnitt behandeln wir die Frage, wie wir ein geeignetes $x_{0}$ finden. $f\left(x\right)=0$, $f:D\subseteq\R^{m}\rightarrow\R^{m}$, $H:D\times\left[0,1\right]\rightarrow\R^{m}$, $H\left(x,1\right)\equiv f\left(x\right)$ Die Lösung der Gleichung $H\left(x,0\right)=0$ sei $x_{0}$ und ,,einfach'' zu beschaffen. Betrachten die Gleichungen $H\left(x,t\right)=0$ für alle $t\in\left[0,1\right]$ mit den Lösungen $x\left(t\right)\in D$ Wenn $x\left(t\right)$ stetig ist, dann existiert für jedes $\bar{t}$ ein $U\left(\bar{t}\right)\subseteq\left[0,1\right],$ so daß $x_{0}$ im Einzugsbereich von $H\left(x,t\right)=0$, $t\in U\left(\bar{t}\right)$, liegt. \begin{example*} künstliche Einbettung \begin{itemize} \item $H\left(x,t\right)=f\left(x\right)+\left(t-1\right)f\left(x_{0}\right)$, $x_{0}\in D$ fest \medskip{} \item $H\left(x,t\right)=tf\left(x\right)+\left(1-t\right)\left(Ax-b\right)$ \end{itemize} \end{example*} Voraussetzungen: \begin{itemize} \item $H:D\times\left[0,1\right]\rightarrow\R^{m}$ stetig \medskip{} \item $D_{x}H\left(x,t\right)$ stetig in $\left(x,t\right)$ \medskip{} \item Es existiert eine Abbildung $x\in C\left(\left[0,1\right],\R^{m}\right)$ stetig mit $x\left(t\right)\in D,\, H\left(x\left(t\right),t\right)=0,\, D_{x}H\left(x\left(t\right),t\right)$ regulär, $t\in\left[0,1\right]$ und es gilt $x_{0}=x\left(0\right),x_{*}=x\left(1\right)$. (Lokale Eindeutigkeit und Existenz von $x\left(t\right)$ folgt aus implizitem Funktionentheorem.) \end{itemize} Wir betrachten eine Zerlegung $0=t_{0}1$ sei $x_{i,0}:=x_{i-1,k_{i-1}}$.\[ \boxed{\begin{array}{rcl} x_{i,j+1} & := & x_{i,j}+z_{i,j+1}\smallskip\\ \textrm{mit }z_{i,j+1}\textrm{ aus }H_{x}\left(x_{i,j},t_{i}\right)z_{i,j+1} & = & -H_{i,j}\left(x_{i,j},t_{i}\right)\end{array}\quad j=0,\ldots,k_{i}-1,\, i=1,\ldots,N}\] \begin{example*} ~\begin{eqnarray*} H\left(x,t\right) & = & f\left(x\right)+\left(t-1\right)f\left(x_{0}\right)\\ D_{x}H\left(x,t\right) & = & f'\left(x\right)\\ \leadsto\, f'\left(x_{i,j}\right)z_{i,j+1} & = & -\left(f\left(x_{i,j}\right)+\left(t_{i}-1\right)f\left(x_{0}\right)\right)\end{eqnarray*} \end{example*} \begin{thm} \label{thm:Konvergenzsatz_eingebetter_Newton}\index{Konvergenzsatz!eingebettetes Newton-Verfahren}\index{Newton-Verfahren!eingebettet!Konvergenz}Sei% \marginpar{Konvergenz\-satz% } $H:D\times\left[0,1\right]\rightarrow\R^{m}$ stetig, $D\subseteq\R^{m}$ offen, $D_{x}H$ stetig und $H\left(x,1\right)=f\left(x\right)$. Es existiere eine Funktion $x\in C\left(\left[0,1\right],\R^{m}\right)$ mit $x\left(t\right)\in D$, $H\left(x\left(t\right),t\right)=0$, $D_{x}H\left(x\left(t\right),t\right)$ regulär für $t\in\left[0,1\right]$.\\ Dann gilt: Für $k\in\N$ und hinreichend feine Zerlegungen $00\,\exists\delta\left(\varepsilon\right)>0\,\forall\left(x,t\right),\left(\bar{x},\bar{t}\right),\left|x-\bar{x}\right|+\left|t-\bar{t}\right|\leq\delta\left(\varepsilon\right):\quad\left\Vert D_{x}H\left(x,t\right)-D_{x}H\left(\bar{x},\bar{t}\right)\right\Vert \leq\varepsilon.\] Sei\[ G\left(t\right):=D_{x}H\left(x\left(t\right),t\right)^{-1},\quad t\in\left[0,1\right]\] $G$ ist eine stetige Matrixfunktion. Da eine stetige Funktion auf einem kompakten Intervall beschränkt ist (Weierstraß), existiert ein $K>0$ mit \[ \left\Vert G\left(t\right)\right\Vert \leq K,\quad t\in\left[0,1\right].\] Wir wählen ein hinreichend kleines $\varepsilon>0$ mit $\varepsilon\cdot K<1$. Aufgrund der gleichmäßigen Stetigkeit gilt dann für $x\in\bar{B}\left(x\left(t\right),\delta\left(\varepsilon\right)\right)\subseteq M$ und $t\in\left[0,1\right]$:\[ \left\Vert D_{x}H\left(x,t\right)-D_{x}H\left(x\left(t\right),t\right)\right\Vert \leq\varepsilon\] Aus dem Störungslemma (L. \ref{lem:St=F6rungslemma}) erhalten wir die Aussage, daß $D_{x}H\left(x,t\right)$ regulär ist und das für $x\in\bar{B}\left(x\left(t\right),\delta\left(\varepsilon\right)\right)$, $t\in\left[0,1\right]$, gilt:\begin{eqnarray*} \left\Vert D_{x}H\left(x,t\right)^{-1}\right\Vert & \leq & \frac{K}{1-\varepsilon\cdot K}\end{eqnarray*} Wir betrachten das Newton-Verfahren für $H\left(x,t\right)=0$ mit festem $t$: Sei $x_{t,0}\in\bar{B}\left(x\left(t\right),\delta\left(\varepsilon\right)\right)$.\begin{eqnarray*} x_{t,1}-x\left(t\right) & = & x_{t,0}-x\left(t\right)-D_{x}H\left(x_{t,0},t\right)^{-1}H\left(x_{t,0},t\right)\\ & = & x_{t,0}-x\left(t\right)-D_{x}H\left(x_{t,0},t\right)^{-1}\left(H\left(x_{t,0},t\right)-\underbrace{H\left(x\left(t\right),t\right)}_{=0}\right)\\ & \stackrel{\left(\textrm{L. }\ref{lem:Integralmittelwertsatz}\right)}{=} & D_{x}H\left(x_{t,0},t\right)^{-1}\left(D_{x}H\left(x_{t,0},t\right)-\int_{0}^{1}D_{x}H\left(sx_{t,0}+\left(1-s\right)x\left(t\right),t\right)ds\right)\cdot\left(x_{t,0}-x\left(t\right)\right)\\ \left|x_{t,1}-x\left(t\right)\right| & \leq & \frac{K}{1-\varepsilon\cdot K}\cdot\underbrace{\left\Vert D_{x}H\left(x_{t,0},t\right)-\int_{0}^{1}D_{x}H\left(sx_{t,0}+\left(1-s\right)x\left(t\right),t\right)ds\right\Vert }_{\leq\varepsilon}\cdot\left|x_{t,0}-x\left(t\right)\right|\\ & \leq & \kappa\left(\varepsilon\right)\cdot\left|x_{t,0}-x\left(t\right)\right|\textrm{ mit }\kappa\left(\varepsilon\right):=\frac{\varepsilon\cdot K}{1-\varepsilon\cdot K}\end{eqnarray*} Für $\varepsilon\cdot K<\frac{1}{2}$ ist $\kappa\left(\varepsilon\right)<1$. Wir wählen dann $\varepsilon$ so, daß $\varepsilon\cdot K<\frac{1}{2}.$ Das Newton-Verfahren ist durchführbar und es gilt\begin{equation} \left|x_{t,j+1}-x\left(t\right)\right|\leq\kappa\left(\varepsilon\right)^{j+1}\cdot\left|x_{t,0}-x\left(t\right)\right|\leq\kappa\left(\varepsilon\right)^{j+1}\cdot\delta\left(\varepsilon\right)\qquad j=1,\ldots,k-1\label{eq:1.4.1}\end{equation} Wir setzen $\delta_{1}:=\delta\left(\varepsilon\right).$ Da $x\in C\left(\left[0,1\right],\R^{m}\right)$ stetig ist (auf der kompakten Menge $\left[0,1\right]$), ist $x$ auch gleichmäßig stetig. Zu $\delta>0$ existiert eine Zerlegung $0=t_{0}^{\left(\delta\right)}0$ $\forall x\neq0$. \end{proof} \begin{rem*} Die Transformation von $Ax=b$ zu $A^{T}Ax=A^{T}b$ bezeichnet man auch als Gauß-Transformation\index{Gauß-Transformation} und $A^{T}Ax=A^{T}b$ heißt ,,Normalgleichung\index{Normalgleichung}''. \end{rem*} Praktische Bestimmung von $x_{*}$: \begin{enumerate} \item Hat $A$ kleine Konditionszahl hat so kann man $A^{T}Ax=A^{T}b$ durch Cholesky-Zerlegung lösen, denn es ist $\textrm{cond}_{2}\left(A^{T}A\right)=\left(\textrm{cond}_{2}\left(A\right)\right)^{2}$. \item Ist $A$ schlecht konditioniert, so sollte man das Householder-Verfahren benutzen: \begin{eqnarray*} QA & = & \left(\begin{array}{c} R\\ 0\end{array}\right),\quad Q\in L\left(\R^{n}\right),Q^{T}=Q^{-1},R\in L\left(\R^{m}\right)\textrm{ reg}.\textrm{ und obere }\triangle-\textrm{Matrix}\\ \varphi\left(x\right) & = & \frac{1}{2}\left|Ax-b\right|_{2}^{2}\\ & = & \frac{1}{2}\left|Q\left(Ax-b\right)\right|_{2}^{2}\\ & = & \frac{1}{2}\left|\left(\begin{array}{c} R\\ 0\end{array}\right)x-\left(\begin{array}{c} \tau_{1}\\ \tau_{2}\end{array}\right)\right|_{2}^{2},\quad\left(\begin{array}{c} \tau_{1}\\ \tau_{2}\end{array}\right):=Qb\\ & = & \frac{1}{2}\left|Rx-\tau_{1}\right|_{2}^{2}+\frac{1}{2}\left|\tau_{2}\right|_{2}^{2}\\ \leadsto\, x_{*} & = & R^{-1}\tau_{1}\qquad\textrm{Also Gleichungssystem }Rx=\tau_{1}\textrm{ lösen.}\end{eqnarray*} \end{enumerate} \begin{rem*} $A^{+}:=\left(A^{T}A\right)^{-1}A^{T}$ heißt Moore-Penrose Inverse\index{Moore-Penrose Inverse} $A^{+}AA^{+}=A^{+}$, $AA^{+}A=A$, $A^{+}A=\left(A^{+}A\right)^{T}$, $AA^{+}=\left(AA^{+}\right)^{T}$ $\leadsto$ $\ker A^{T}\leftrightarrow\textrm{im}A$ \end{rem*} \subsection{Nichtlineare Ausgleichsprobleme} ~ $f\left(x\right)=0$, $x_{0}$ Startwert Wir betrachten die zur Linearisierung\[ g_{0}\left(x\right)=f\left(x_{0}\right)+f'\left(x_{0}\right)\left(x-x_{0}\right)\] gehörige Aufgabe $g_{0}\left(x\right)=0$. Dazu sei\[ x_{1}=x_{0}+z_{1}\qquad\textrm{mit }z_{1}\textrm{ aus }f'\left(x_{0}\right)z_{1}=-f\left(x_{0}\right).\] Hat $f'\left(x_{0}\right)$ vollen Rang, so ist die kleinste Quadrate Lösung dieser Gleichung gegeben durch\[ z_{1}=-\left(f'\left(x_{0}\right)^{T}f'\left(x_{0}\right)\right)^{-1}f'\left(x_{0}\right)^{T}f\left(x_{0}\right)\] \begin{thm} Sei $f\in C^{1}\left(D,\R^{n}\right)$, $D\subseteq\R^{m}$ offen, $n\geq m$, \[ \varphi\left(x\right):=\frac{1}{2}\left|f\left(x\right)\right|_{2}^{2},\quad x\in D.\] Sei $x\in D$ fest, der Rang von $f'\left(x\right)$ gleich $m$, $f'\left(x\right)^{T}f\left(x\right)\neq0.$\\ Dann ist die Gauß-Newton-Richtung\index{Gauß-Newton-Richtung}% \marginpar{Gauß-Newton-Richtung% } \[ \boxed{z_{GN}:=-\left(f'\left(x\right)^{T}f'\left(x\right)\right)^{-1}f'\left(x\right)^{T}f\left(x\right)}\] eine Abstiegsrichtung (s. Seite \pageref{defn_abstiegsrichtung}) für $\varphi$ in $x$. \end{thm} \begin{proof} $\varphi$ ist $C^{1}$, $x\in D$ fest, $z\in\R^{m}$ beliebig, \begin{eqnarray*} \varphi'\left(x\right)z & = & \left\langle f'\left(x\right)^{T}f\left(x\right),z\right\rangle \\ \nabla\varphi\left(x\right) & = & f'\left(x\right)^{T}f\left(x\right).\end{eqnarray*} Dann ist\begin{eqnarray*} \underbrace{\varphi\left(x+\alpha z\right)-\varphi\left(x\right)}_{<0} & = & \underbrace{\alpha\cdot\varphi'\left(x\right)z+o\left(\alpha\right)}_{\varphi'\left(x\right)z<0\,\Leftrightarrow\, z\textrm{ Abstiegsrichtung}},\quad\alpha>0\\ \left\langle \nabla\varphi\left(x\right),z_{GN}\right\rangle & = & -\left\langle f'\left(x\right)^{T}f\left(x\right),\underbrace{\left(f'\left(x\right)^{T}f'\left(x\right)\right)^{-1}}_{=:M=RR^{T}}f'\left(x\right)^{T}f\left(x\right)\right\rangle ,\, M\textrm{ symm}.,\textrm{ pos}.\textrm{def}.\\ & = & -\left|R^{T}\underbrace{f'\left(x\right)^{T}f\left(x\right)}_{\neq0}\right|_{2}^{2}<0\qquad\textrm{da }R\textrm{ regulär ist}\end{eqnarray*} \end{proof} \underbar{Schrittweitenwahl nach Armijo}\index{Schrittweitenwahl!Armijo}\index{Armijo-Schrittweite}% \marginpar{Armijo-Schritt\-weiten\-wahl% }: Sei $\gamma\in\left(0,\frac{1}{2}\right)$ fest $x_{j}$, $\varphi\left(x_{j}\right)$ seien bekannt, $z_{j+1}$ sei Gauß-Newton-Richtung, $\varphi'\left(x_{j}\right)z_{j+1}$ sei berechnet. Betrachte zwei Geraden:% \begin{figure}[htbp] \begin{center}\includegraphics[% width=0.40\paperwidth, keepaspectratio]{6.eps}\end{center} \caption{Schrittweitenwahl nach Armijo} \end{figure} \begin{eqnarray*} g_{1} & : & \varphi\left(x_{j}\right)+\gamma\alpha\varphi'\left(x_{j}\right)z_{j+1}\\ g_{2} & : & \varphi\left(x_{j}\right)+\alpha\varphi'\left(x_{j}\right)z_{j+1}\end{eqnarray*} Test, ob für $\alpha=1$ gilt, daß $\varphi\left(x_{j}+\alpha z_{j+1}\right)\leq\varphi\left(x_{j}\right)+\gamma\alpha\varphi'\left(x_{j}\right)z_{j+1}$. Wenn ja, so $\alpha_{j+1}:=1$. Wenn nein, so $\alpha:=\frac{\alpha}{2}$, neuer Test usw. $\leadsto$ $\alpha_{j+1}\in\left(0,1\right]$ wird so bestimmt, daß\[ \boxed{\varphi\left(x_{j}+\alpha_{j+1}z_{j+1}\right)\leq\varphi\left(x_{j}\right)+\gamma\alpha_{j+1}\cdot\varphi'\left(x_{j}\right)z_{j+1}}\] \begin{defn*} \underbar{Gedämpftes Gauß-Newton-Verfahren\index{Gauß-Newton-Verfahren!gedämpft}}% \marginpar{gedämpftes Gauß-Newton-Verfahren% } mit Startwert $x_{0}$:\[ \boxed{\begin{array}{rcl} x_{j+1} & = & x_{j}+\alpha_{j+1}z_{j+1}\smallskip\\ z_{j+1}\textrm{ aus }f'\left(x_{j}\right)z_{j+1} & = & -f\left(x_{j}\right)\quad\textrm{Kleinste-Quadrate-Lösung}\smallskip\\ \alpha_{j+1}\textrm{ nach Armijo}\end{array}\quad j\geq0}\] \end{defn*} \begin{thm} \label{thm:Konvergenzsatz_gedaempftes_Gauss-Newton}\index{Gauß-Newton-Verfahren!gedämpft!Konvergenz}\index{Konvergenzsatz!Gauß-Newton-Verfahren}Sei $f\in C^{1}\left(\R^{m},\R^{n}\right)$, $n\geq m$, $\varphi\left(x\right):=\frac{1}{2}\left|f\left(x\right)\right|_{2}^{2}$, $x\in\R^{m}$.% \marginpar{Konvergenz\-satz% } Sei $x_{0}\in\R^{m}$ fest und \[ N_{0}:=\left\{ \left.x\in\R^{m}\right|\left|f\left(x\right)\right|_{2}\leq\left|f\left(x_{0}\right)\right|_{2}\right\} \] Für alle $x\in N_{0}$ sei der Rang von $f'\left(x\right)$ gleich $m$ und es gelte mit Konstanten $K,c>0$: \begin{eqnarray*} \left\Vert f'\left(x\right)\right\Vert _{2} & \leq & K\\ \left|f'\left(x\right)z\right|_{2} & \geq & c\cdot\left|z\right|_{2},\quad\forall z\in\R^{m}.\end{eqnarray*} $f'\left(x\right)$ sei Lipschitz-stetig auf $N_{0}$ (d.h. $\left\Vert f'\left(x\right)-f'\left(\bar{x}\right)\right\Vert _{2}\leq L\cdot\left|x-\bar{x}\right|_{2}$). Dann gilt: \begin{enumerate} \item Das gedämpfte Gauß-Newton-Verfahren mit Startwert $x_{0}$ ist durchführbar und liefert eine monoton fallende Folge $\left\{ \varphi\left(x_{j}\right)\right\} _{j\geq0}$. Es gilt $\varphi'\left(x_{j}\right)\xrightarrow{j\rightarrow\infty}0$. \medskip{} \item Ist $N_{0}$ kompakt und hat $\gamma$ auf $N_{0}$ genau einen stationären Punkt $x_{*}\in N_{0}$, so endet das Verfahren entweder wegen $\varphi'\left(x_{k_{*}}\right)=0$ in $x_{k_{*}}=x_{*}$ oder es ist unendlich fortsetzbar und $x_{j}\xrightarrow{j\rightarrow\infty}x_{*}$. \medskip{} \item Gilt in $\left(2\right)$ noch $f\left(x_{*}\right)=0$, so gibt es einen Index $j_{*}\in\N$ mit $\alpha_{j}=1$ für $j\geq j_{*}$ und quadratischer Konvergenz ab $j_{*}$. \end{enumerate} \end{thm} \begin{proof} \cite[§10.2, Satz 10.2.5, Algorithmus 10.2.1]{Schwetlick} \end{proof} \begin{rem} Anstelle des Newton-Verfahren kann auch ein Quasi-Newton- oder Sekantenverfahren benutzt werden. Zum Beispiel Sekanten-Matrix Aufdatierung:\begin{eqnarray*} g_{j}\left(x\right) & := & f\left(x_{j}\right)+\underbrace{f'\left(x_{j}\right)}_{A_{j}}\left(x-x_{j}\right)\end{eqnarray*} \end{rem} \newpage \section{Minimierungsaufgaben (Optimierungsaufgaben)} Wir betrachten eine Funktion $\varphi\in C^{2}\left(\R^{m},\R\right)$, $U\subseteq\R^{m}$. Aufgabe ist es, $\varphi(x)$ für $x\in U$ zu minimieren.\index{Minimierungsproblem} \begin{rem*} Wir bezeichnen dabei $\varphi$ als Zielfunktion\index{Zielfunktion} und $U$ als die Menge der zulässigen Punkte. \end{rem*} Wir betrachten zwei Typen: \begin{enumerate} \item $U=\R^{m}$ oder $U\subseteq\R^{m}$ offen und wir betrachten $\varphi'\left(x\right)=0$. Minimierungsprobleme dieses Typs bezeichnen wir als \underbar{freie bzw. unrestriktive Minimierungsaufgaben}. \medskip{} \item $U\subset\R^{m}$ nichtleer und nicht offen, U wird häufig durch (Un)Gleichungen beschrieben: \[ U=\left\{ \left.x\in\R^{m}\right|g_{i}\left(x\right)\leq0,i=1,\ldots,p;\, g_{p+j}\left(x\right)=0,j=1,\ldots,q\right\} ,\, g_{j}\in C^{1}\left(\R^{m},\R\right),\] zum Beispiel \[ U=\left\{ \left.x\in\R^{2}\right|x_{1}^{2}+y_{1}^{2}-1=0,\,-x^{2}\leq0\right\} \] bezeichnen wir als \underbar{Minimierungsprobleme mit Nebenbedingungen bzw. Restriktionen}. \end{enumerate} \subsection{Freie Minimierungssprobleme} ~\begin{equation} \boxed{\min\left\{ \left.\varphi\left(x\right)\right|x\in\R^{m}\right\} }\label{3.1}\end{equation} \begin{defn*} $x_{*}\in\R^{m}$ heißt \underbar{globale Lösung\index{Lösung!global}} von (\ref{3.1}), falls $\varphi\left(x_{*}\right)\leq\varphi\left(x\right)$ für alle $x\in\R^{m}$. $x_{*}\in\R^{m}$ heißt \underbar{lokale Lösung\index{Lösung!lokal}} von (\ref{3.1}), falls $\varphi\left(x_{*}\right)\leq\varphi\left(x\right)$ für alle $x\in U\left(x_{*}\right)$. \end{defn*} %~ \begin{defn*} \label{defn_abstiegsrichtung}$z\in\R^{m}$ heißt \underbar{Abstiegsrichtung\index{Abstiegsrichtung}} zu $\varphi$ in $x\in\R^{m},$ falls $\varphi\left(x+\alpha z\right)<\varphi\left(x\right)$ für alle hinreichend kleinen $\alpha>0$. \end{defn*} \begin{rem*} $z$ ist Abstiegsrichtung für $\varphi$ in $x$ $\Leftrightarrow$ $\varphi'\left(x\right)z<0$. \end{rem*} \begin{defn*} $x_{*}\in\R^{m}$ heißt \underbar{stationärer Punkt\index{stationärer Punkt}} (Extremalpunkt\index{Extremalpunkt}), falls \[ \varphi'\left(x_{*}\right)z\geq0\quad\forall z\in\R^{m}\] $\left(\Leftrightarrow\,\varphi'\left(x_{*}\right)=0\right)$ \end{defn*} \begin{rem*} Dabei bezeichnen wir $\varphi'\left(x\right)^{T}=\nabla\varphi\left(x\right)$ als Gradient und $\nabla^{2}\varphi\left(x\right)$ als Hessesche Matrix (bei $\varphi\in C^{2}\left(\R^{m},\R\right)$) \end{rem*} Die steilste Abstiegsrichtung zu $\varphi$ in $x$ ist% \marginpar{Gradienten\-verfahren% } \[ \boxed{z_{G}:=-\nabla\varphi\left(x\right)}\] (,,Gradientenverfahren\index{Gradientenverfahren}'' bis circa 1965). \begin{lem} Sei $\varphi\in C^{1}\left(\R^{m},\R\right)$, $x\in\R^{m}$ fest, $\nabla\varphi\left(x\right)\neq0$. Sei $H\in L\left(\R^{m}\right)$ symmetrisch und positiv definit. Dann ist\[ z:=-H\cdot\nabla\varphi\left(x\right)\] Abstiegsrichtung zu $\varphi$ in $x$. \end{lem} \begin{proof} $H=RR^{T}$, \[ \varphi'\left(x\right)z=-\left\langle \nabla\varphi\left(x\right),H\nabla\varphi\left(x\right)\right\rangle =-\left\langle R^{T}\nabla\varphi\left(x\right),R^{T}\nabla\varphi\left(x\right)\right\rangle =-\left|R^{T}\nabla\varphi\left(x\right)\right|_{2}^{2}<0\] \end{proof} \begin{conclusion*} Die Newton-Richtung\index{Newton-Richtung}% \marginpar{Newton-Richtung% }\[ \boxed{z_{N}:=-\left(\nabla^{2}\varphi\left(x\right)\right)^{-1}\cdot\nabla\varphi\left(x\right)}\] für $\varphi$ in $x$, $\varphi\in C^{2}\left(\mathbb{R}^{m},\mathbb{R}\right)$, $x\in\mathbb{R}^{m}$, $\nabla\varphi\left(x\right)\neq0$ ist eine Abstiegsrichtung, falls die Hessematrix $\nabla^{2}\varphi\left(x\right)$ positiv definit ist. \end{conclusion*} \begin{example*} $m=2$\begin{eqnarray*} \varphi\left(x_{1},x_{2}\right) & := & -x_{1}^{2}+x_{2}^{2}+1\\ \nabla\varphi\left(x\right) & = & \left(\begin{array}{c} -2x_{1}\\ 2x_{2}\end{array}\right)\\ \nabla^{2}\varphi\left(x\right) & = & \left(\begin{array}{cc} -2 & 0\\ 0 & 2\end{array}\right)\\ z_{G} & := & -\nabla\varphi\left(x\right)=\left(\begin{array}{c} 2x_{1}\\ -2x_{2}\end{array}\right)\\ z_{N} & = & -\left(\begin{array}{c} x_{1}\\ x_{2}\end{array}\right)\\ \left\langle \nabla\varphi\left(x\right),z_{N}\right\rangle & = & 2\left(x_{1}^{2}-x_{2}^{2}\right)\end{eqnarray*} \end{example*} \begin{lem} \label{lem:3.2}Sei $c\in\R^{m}$ und $W\in L\left(\R^{m}\right)$ symmetrisch und positiv definit. Dann hat\[ \psi\left(x\right):=c^{T}x+\frac{1}{2}x^{T}Wx=\left\langle c,x\right\rangle +\frac{1}{2}\left\langle Wx,x\right\rangle ,\quad x\in\R^{m},\] auf $\R^{m}$ genau einen stationären Punkt $x_{*}$ und es gilt\[ \boxed{x_{*}=-W^{-1}\cdot c}\] $x_{*}$ ist globales Minimum: $\psi\left(x_{*}\right)<\psi\left(x\right)$ $\forall x\in\R^{m}$, $x\neq x_{*}$. \end{lem} \begin{proof} $\psi'\left(x\right)=c^{T}+\left(Wx\right)^{T}$, $\nabla\psi\left(x\right)=c+Wx$ $\nabla\psi\left(x_{*}\right)=0$ $\Leftrightarrow$ $c+Wx_{*}=0$ (inhomogene lineare Gleichung ) $\nabla^{2}\psi\left(x_{*}\right)=W$ ist positiv definit, d.h. $x_{*}$ ist Minimum. \end{proof} \begin{rem*} $\psi$ heißt \underbar{quadratische Zielfunktion}\index{quadratische Zielfunktion}. \end{rem*} Ziel war/ist die Minimierung von $\varphi\left(x\right)$, $x\in\R^{m}$ (\ref{3.1}). Seien nun $x_{j}$, $\nabla\varphi\left(x_{j}\right)$ bereits berechnet, $\varphi\in C^{2}\left(\R^{m},\R\right)$\begin{eqnarray*} \rho_{j}\left(x\right) & := & \varphi\left(x_{j}\right)+\left\langle \nabla\varphi\left(x_{j}\right),x-x_{j}\right\rangle +\frac{1}{2}\left\langle \nabla^{2}\varphi\left(x_{j}\right)\left(x-x_{j}\right),x-x_{j}\right\rangle \\ & = & \varphi\left(x_{j}\right)+\varphi'\left(x_{j}\right)\cdot\left(x-x_{j}\right)+\frac{1}{2}\cdot\left(x-x_{j}\right)^{T}\cdot\nabla^{2}\varphi\left(x_{j}\right)\cdot\left(x-x_{j}\right)\\ \rho_{j}\left(x_{j}\right) & = & \varphi\left(x_{j}\right)\\ \nabla\rho_{j}\left(x\right) & = & \nabla\varphi\left(x_{j}\right)+\nabla^{2}\varphi\left(x_{j}\right)\left(x-x_{j}\right)\\ \nabla\rho_{j}\left(x_{j}\right) & = & \nabla\varphi\left(x_{j}\right)\end{eqnarray*} Falls die Hessematrix $\nabla^{2}\varphi\left(x_{j}\right)$ positiv definit ist, können wir Lemma \ref{lem:3.2} anwenden und erhalten ein $x_{*}$, welches das Minimum dieser Funktionen ist:\[ x_{*}-x_{j}=\underbrace{\left(-\nabla^{2}\varphi\left(x_{j}\right)\right)^{-1}\cdot\nabla\varphi\left(x_{j}\right)}_{\textrm{Newton}-\textrm{Richtung}}\] Wir betrachten nun den Fall, daß $x_{j}$, $\nabla\varphi\left(x_{j}\right)$, $x_{j-1}$ und $\nabla\varphi\left(x_{j-1}\right)$ bereits berechnet sind.\[ \rho_{j-1}\left(x\right):=\varphi\left(x_{j-1}\right)+\left\langle \nabla\varphi\left(x_{j-1}\right),x-x_{j-1}\right\rangle +\frac{1}{2}\left\langle H_{j-1}\cdot\left(x-x_{j-1}\right),x-x_{j-1}\right\rangle \] $\rho_{j-1}$ sei verwendet worden, um $x_{j}$ zu berechnen. Wir setzen desweiteren voraus, daß $H_{j-1}$ symmetrisch und positiv definit ist.\begin{eqnarray*} x_{j} & = & x_{j-1}+\alpha_{j}z_{j}\\ z_{j}\textrm{ aus }H_{j}z_{j} & = & -\nabla\varphi\left(x_{j-1}\right)\textrm{ bestimmt}\end{eqnarray*} Sei\[ \varphi_{j}\left(x\right):=\varphi\left(x_{j}\right)+\left\langle \nabla\varphi\left(x_{j}\right),x-x_{j}\right\rangle +\frac{1}{2}\left\langle H_{j}\left(x-x_{j}\right),x-x_{j}\right\rangle \] Idee: Aufdatierung von $H_{j}$ aus $H_{j-1}$ so, daß $H_{j}$ symmetrisch und positiv definit ist. Es gilt:\begin{eqnarray*} \varphi_{j}\left(x_{j}\right) & = & \varphi\left(x_{j}\right)\\ \nabla\varphi_{j}\left(x\right) & = & \nabla\varphi\left(x_{j}\right)+H_{j}\left(x-x_{j}\right)\\ \nabla\varphi_{j}\left(x_{j}\right) & = & \nabla\varphi\left(x_{j}\right)\end{eqnarray*} Quasi-Newton-Bedingung:\begin{eqnarray*} H_{j}\left(x_{j}-x_{j-1}\right) & = & \nabla\varphi\left(x_{j}\right)-\nabla\varphi\left(x_{j-1}\right)\\ & \Updownarrow\\ \nabla\varphi_{j}\left(x_{j-1}\right) & = & \nabla\varphi\left(x_{j-1}\right)\end{eqnarray*} {[}Aufdatierungsformeln: siehe Jochen Werner, {}``Numerische Mathematik 2'', Vieweg 1992{]} Man spricht hier auch von Quasi-Newton-Richtungen\index{Quasi-Newton-Richtungen}% \marginpar{Quasi-Newton-Richtung% }:\[ \boxed{z_{j+1}:=-H_{j}^{-1}\cdot\nabla\varphi\left(x_{j}\right)\quad H_{j}\textrm{ aus Aufdatierungsformel}}\] Diese Verfahren werden BFGS-Verfahren\index{BFGS-Verfahren} genannt: $\approx1970$ \underbar{B}royden, \underbar{F}letcher, \underbar{G}oldberg, \underbar{S}hanno.\\ Es sind die aktuell besten Verfahren für glatte Minimierung ohne Nebenbedingung mit moderatem $m$. \underbar{Schrittweitenwahl}\index{Schrittweitenwahl}% \marginpar{Schritt\-weiten\-wahl% } ausgehend von $x_{j}$ in Richtung $z_{j+1}$ (Abstiegsrichtung):\[ \psi\left(\alpha\right):=\varphi\left(x_{j}+\alpha z_{j+1}\right)\] % \begin{figure}[htbp] \begin{center}\includegraphics[% width=0.50\paperwidth, keepaspectratio]{7.eps}\end{center} \caption{,,Exakte'' Schrittweite und Armijo-Schrittweitenwahl} \end{figure} \begin{enumerate} \item ,,Exakte'' Schrittweite\index{Schrittweitenwahl!exakt}: kleinstes positives $\alpha_{E}>0$ mit $\psi'\left(\alpha_{E}\right)=0$\begin{eqnarray*} \psi\left(0\right) & = & \varphi\left(x_{j}\right)\\ \psi'\left(\alpha\right) & = & \varphi\left(x_{j}+\alpha z_{j+1}\right)\cdot z_{j+1}\\ \psi'\left(0\right) & = & \varphi\left(x_{j}\right)\cdot z_{j+1}<0\end{eqnarray*} \medskip{} \item Armijo-Schrittweite\index{Armijo-Schrittweite}\index{Schrittweitenwahl!Armijo}, $\gamma\in\left(0,\frac{1}{2}\right)$ \medskip{} \noindent $\alpha_{A}>0$ mit $\psi\left(\alpha_{A}\right)\leq\psi\left(0\right)+\alpha_{A}\cdot\gamma\cdot\psi'\left(0\right)$ (Armijo-Bedingung (A))\[ \varphi\left(x_{j+1}\right)\leq\varphi\left(x_{j}\right)+\alpha_{A}\cdot\gamma\cdot\varphi'\left(x_{j}\right)\cdot z_{j+1}\] \medskip{} \item Powell-Schrittweite\index{Schrittweitenwahl!Powell}\index{Powell-Schrittweite} (Wolfe-Schrittweite\index{Wolfe-Schrittweite}\index{Schrittweitenwahl!Wolfe}) \medskip{} \noindent $\alpha_{PA}>0$ und Bedingung (A) und zusätzlich wird verlangt, daß \[ \psi'\left(\alpha_{PA}\right)\geq\beta\cdot\psi'\left(0\right)\] gilt mit einem Parameter $\beta\in\left(\gamma,1\right)$ \end{enumerate} \underbar{Überlineare} Konvergenz kann für BFGS-Verfahren unter entsprechenden Voraussetzungen bewiesen werden. \subsection{Elementare Ansätze für Minimierung mit Nebenbedingungen} ~\begin{equation} \boxed{\min\left\{ \left.\varphi\left(x\right)\right|x\in U\right\} }\label{Def_phi_U}\end{equation} $U\subseteq\R^{m}$ sei nicht offen \begin{itemize} \item Globale Lösung: $x_{*}\in U$ mit $\varphi\left(x_{*}\right)\leq\varphi\left(x\right),\, x\in U$. \medskip{} \item Lokale Lösung: $x_{*}\in U$ mit $\varphi\left(x_{*}\right)\leq\varphi\left(x\right)$ für $x\in U\cap\mathcal{U}\left(x_{*}\right)$, $\mathcal{U}\left(x_{*}\right)\subseteq\R^{m}$ Umgebung von $x_{*}$ \end{itemize} \begin{enumerate} \item $U$ sei abgeschlossen und konvex, z.B. $U:=\left\{ \left.x\in\R^{m}\right|x_{i}\geq0\right\} $ \medskip{} \noindent Sei $x\in U$, $z=y-x$\[ \varphi\left(x+\alpha\left(y-x\right)\right)-\varphi\left(x\right)=\alpha\cdot\left\langle \nabla\varphi\left(x\right),y-x\right\rangle +o\left(\alpha\right)\] $y-x$ ist Abstiegsrichtung für $\varphi$ in $x$ $\Leftrightarrow$ $\left\langle \nabla\varphi\left(x\right),y-x\right\rangle <0$ \medskip{} \noindent $y\in U$ definiert dann eine ,,zulässige Abstiegsrichtung''. \medskip{} \noindent Extremalbedingung:% \marginpar{projizierte Gradienten% } \[ \boxed{\forall y\in U:\,\left\langle \nabla\varphi\left(x_{*}\right),y-x_{*}\right\rangle \geq0}\] \medskip{} \noindent Dies definiert das Verfahren der \underbar{projizierten Gradienten}\index{Projizierte Gradienten}. \medskip{} \item $U$ ist durch Gleichungen gegeben, z.B. $U:=\left\{ \left.x\in\R^{m}\right|g\left(x\right)=0\right\} $, $g\in C^{1}\left(\R^{m},\R\right)$ \medskip{} \noindent Methode der \underbar{Lagrange-Multiplikatoren}\index{Lagrange-Multiplikatoren}% \marginpar{Lagrange-Multiplikatoren% } \medskip{} \noindent Ersatzfunktion: \[ \boxed{\psi\left(x,\lambda\right):=\varphi\left(x\right)+\lambda g\left(x\right),\quad x\in\R^{m},\lambda\in\R}\] Minimiere $\psi\left(x,\lambda\right)$: \begin{equation} \boxed{\min\left\{ \psi\left(x,\lambda\right)\left|x\in\R^{m},\lambda\in\R\right.\right\} }\label{Def_LagProb}\end{equation} \[ \nabla\psi\left(x,\lambda\right)=\left(\begin{array}{c} \nabla\varphi\left(x\right)+\lambda\cdot\nabla g\left(x\right)\\ g\left(x\right)\end{array}\right)\] $\left(x_{*},\lambda_{*}\right)$ ist stationäre Lösung von (\ref{Def_LagProb}) $\leadsto$ $g\left(x_{*}\right)=0$, d.h. $x_{*}\in U$. \medskip{} \noindent Sei $\left(x_{*},\lambda_{*}\right)$ lokale Lösung von (\ref{Def_LagProb}): \[ \forall x\in\mathcal{U}\left(x_{*}\right)\cap U:\,\varphi\left(x_{*}\right)=\psi\left(x_{*},\lambda_{*}\right)\leq\psi\left(x,\lambda_{*}\right)=\varphi\left(x\right)\] \medskip{} \item Einführung von \underbar{Straftermen}\index{Strafterme}% \marginpar{Strafterme% }: $U=\left\{ \left.x\in\R^{m}\right|g\left(x\right)=0,h\left(x\right)\leq0\right\} $\[ \boxed{\varphi_{\varepsilon}\left(x,t\right):=\varphi\left(x\right)+\frac{1}{\varepsilon}\left\{ \left|g\left(x\right)\right|_{2}^{2}+\left|h\left(x\right)-t\right|_{2}^{2}\right\} ,\quad x\in\R^{m},t\in\R}\] Dann ist $\varphi_{\varepsilon}\left(x,t\right)\geq\varphi\left(x\right)$ und $\varphi_{\varepsilon}\left(x,t\right)=\varphi\left(x\right)$ für $x\in U,$ $t=h\left(x\right)$. \medskip{} \noindent Wir betrachten dann\[ \boxed{\min\left\{ \varphi_{\varepsilon}\left(x,t\right)\left|x\in\R^{m},t\leq0\right.\right\} }\] \end{enumerate} \newpage \section{Interpolation} Ziel der Interpolation ist die Darstellung von Funktionen zur Vereinfachung oder zur Auswertung von Tabellen. \subsection{Interpolationspolynome von Lagrange und Newton} ~ Gegeben seien paarweise voneinander verschiedene \underbar{Stützstellen}\index{Stützstellen} $t_{1},\ldots,t_{n}\in\R$ . $f\left(t_{1}\right),\ldots,f\left(t_{n}\right)\in\R$ seien die Funktionswerte einer Funktion $f$. Gesucht ist nun das Polynom $P$ mit $\textrm{grad}P\leq n-1$, welches den Interpolationsbedingungen\[ P\left(t_{i}\right)=f\left(t_{i}\right),\quad i=1,\ldots,n,\] genügt. Wir nennen $P$ das Interpolationspolynom\index{Interpolationspolynom} zu $f$ und den Stützstellen $t_{1},\ldots,t_{n}$.\index{Stützstellenpolynom} \begin{eqnarray*} \omega\left(t\right) & := & \left(t-t_{1}\right)\cdots\left(t-t_{n}\right)\quad(\textrm{Stützstellenpolynom})\\ p_{i}\left(t\right) & := & \prod_{j=1,j\neq i}^{n}\frac{t-t_{j}}{t_{i}-t_{j}}=\frac{\omega\left(t\right)}{\left(t-t_{i}\right)\omega'\left(t_{i}\right)}\\ \leadsto\, p_{i}\left(t_{k}\right) & = & \delta_{i,k}=\left\{ \begin{array}{cc} 1 & k=i\\ 0 & k\neq i\end{array}\right.,\quad\textrm{grad}p_{i}=n-1\end{eqnarray*} % \marginpar{Inter\-polations\-polynom Lagrange% }\[ \boxed{L\left(t\right):=\sum_{i=1}^{n}p_{i}\left(t\right)f\left(t_{i}\right)}\] Dann ist $L\left(t_{k}\right)=f\left(t_{k}\right)$, $k=1,\ldots,n$ und $\textrm{grad}L\leq n-1$. $L$ ist das \underbar{Interpolationspolynom} \underbar{von} \underbar{Lagrange}\index{Interpolationspolynom!Lagrange}. \underbar{Differenzenquotienten\index{Differenzenquotienten}} (dividierte Differenzen\index{dividierte Differenzen}) zu $f$ und $t_{1},\ldots,t_{n}$:\begin{alignat*}{2} f\left[t_{i_{1}},t_{i_{2}}\right] & :=\frac{f\left(t_{i_{1}}\right)-f\left(t_{i_{2}}\right)}{t_{i_{1}}-t_{i_{2}}} & & \quad\textrm{Differenzenquotient }1.\textrm{ Ordnung}\\ f\left[t_{i_{1}},t_{i_{2}},t_{i_{3}}\right] & :=\frac{f\left[t_{i_{1}},t_{i_{2}}\right]-f\left[t_{i_{2}},t_{i_{3}}\right]}{t_{i_{1}}-t_{i_{3}}} & & \quad\textrm{Differenzenquotient }2.\textrm{ Ordnung}\\ f\left[t_{i_{1}},\ldots,t_{i_{k}}\right] & :=\frac{f\left[t_{i_{1}},\ldots,t_{i_{k-1}}\right]-f\left[t_{i_{2}},\ldots,t_{i_{k}}\right]}{t_{i_{1}}-t_{i_{k}}} & & \quad\textrm{Differenzenquotient }k-1.\textrm{ Ordnung}\end{alignat*} Eigenschaften: \begin{enumerate} \item Bildung der Differenzenquotienten ist eine lineare Operation, denn zu Funktionen $f,g$ und $\alpha,\beta\in\R$, $h:=\alpha f+\beta g$ gilt: \[ h\left[\cdots\right]:=\alpha f\left[\cdots\right]+\beta g\left[\cdots\right]\] \item ~\[ f\left[t_{i_{1}},t_{i_{2}}\right]=\frac{f\left(t_{i_{1}}\right)}{t_{i_{1}}-t_{i_{2}}}+\frac{f\left(t_{i_{2}}\right)}{t_{i_{2}}-t_{i_{1}}}\] Durch Induktion kann gezeigt werden, daß\begin{eqnarray*} f\left[t_{i_{1}},\ldots,t_{i_{k}}\right] & = & \sum_{l=1}^{k}\frac{f\left(t_{i_{l}}\right)}{{\displaystyle \prod_{s=1,s\neq l}^{k}}\left(t_{i_{l}}-t_{i_{s}}\right)}\end{eqnarray*} \item Die Reihenfolge der Argumente in den Differenzenquotienten ist vertauschbar. \end{enumerate} Sei $t\not\in\left\{ t_{1},\ldots,t_{n}\right\} $:\begin{eqnarray*} f\left(t\right) & = & f\left(t_{1}\right)+\left(t-t_{1}\right)\cdot\underbrace{f\left[t_{1},t\right]}_{=f\left[t_{1},t_{2}\right]+\left(t-t_{2}\right)f\left[t_{1},t_{2},t\right]}\\ & = & f\left(t_{1}\right)+\left(t-t_{1}\right)f\left[t_{1},t_{2}\right]+\left(t-t_{1}\right)\left(t-t_{2}\right)f\left[t_{1},t_{2},t_{3}\right]+\ldots+\prod_{i=1}^{n-1}\left(t-t_{i}\right)f\left[t_{1},\ldots,t_{n}\right]\\ & & +\prod_{i=1}^{n}\left(t-t_{i}\right)f\left[t_{1},\ldots,t_{n},t\right]\\ f\left(t_{k}\right) & = & f\left(t_{1}\right)+\left(t_{k}-t_{1}\right)f\left[t_{1},t_{2}\right]+\ldots+\left(t_{k}-t_{1}\right)\cdots\left(t_{k}-t_{k-1}\right)f\left[t_{1},\ldots,t_{k}\right],\quad k=1,\ldots,n\end{eqnarray*} % \marginpar{Inter\-polations\-polynom Newton% }\[ \boxed{N\left(t\right):=f\left(t_{1}\right)+\left(t-t_{1}\right)f\left[t_{1},t_{2}\right]+\left(t-t_{1}\right)\left(t-t_{2}\right)f\left[t_{1},t_{2},t_{3}\right]+\ldots+\prod_{i=1}^{n-1}\left(t-t_{i}\right)f\left[t_{1},\ldots,t_{n}\right]}\] ist ein Polynom mit $\textrm{grad}N\leq n-1$ und wir bezeichnen es als \underbar{Newtonsches} \underbar{Interpolationspolynom}\index{Interpolationspolynom!Newton}. Es gilt $f\left(t_{k}\right)=N\left(t_{k}\right)$, $k=1,\ldots,n$, und $N\left(t\right)\equiv L\left(t\right)$. Das Interpolationspolynom von Lagrange hat den Nachteil, daß man bei ungenügender Genauigkeit alle bisherigen Rechenschritte erneut durchführen muß. Beim Interpolationspolynom von Newton ist dies nicht nötig, da bei zusätzlichen Stützstellen nur zusätzliche Additionen ausgeführt werden müssen. \begin{center}\begin{tabular}{ccccccc} $t_{1}$& $f\left(t_{1}\right)$& & & & & \tabularnewline & & $f\left[t_{1},t_{2}\right]$& & & & \tabularnewline $t_{2}$& $f\left(t_{2}\right)$& & $f\left[t_{1},t_{2},t_{3}\right]$& & & \tabularnewline & & $f\left[t_{2},t_{3}\right]$& & $\ddots$& & \tabularnewline $\vdots$& $\vdots$& & & & $f\left[t_{1},t_{2},\ldots,t_{n}\right]$& \tabularnewline & & & & $\cdot$& & $f\left[t_{1},\ldots,t_{n+1}\right]$\tabularnewline $\vdots$& $\vdots$& & $f\left[t_{n-2},t_{n-1},t_{n}\right]$& & $f\left[t_{2},t_{3},\ldots,t_{n+1}\right]$& \tabularnewline & & $f\left[t_{n-1},t_{n}\right]$& & $\cdot$& & \tabularnewline $t_{n}$& $f\left(t_{n}\right)$& & $f\left[t_{n-1},t_{n},t_{n+1}\right]$& & & \tabularnewline & & $f\left[t_{n},t_{n+1}\right]$& & & & \tabularnewline $t_{n+1}$& $f\left(t_{n+1}\right)$& & & & & \tabularnewline \end{tabular}\end{center} \underbar{Restglied} der Interpolation\index{Restglied der Interpolation}:\begin{eqnarray*} f\left(t\right)-N\left(t\right) & = & \left\{ \begin{array}{cl} 0 & \textrm{für }t\in\left\{ t_{1},\ldots,t_{n}\right\} \smallskip\\ \omega\left(t\right)f\left[t_{1},\ldots,t_{n},t\right] & \textrm{sonst}\end{array}\right.\end{eqnarray*} \begin{lem} \label{lem:4.1}Seien $t_{1},\ldots,t_{k}\in\left[a,b\right]$ paarweise verschiedene Stützstellen, $f\in C^{k-1}\left(\left[a,b\right]\right)$. Dann existiert ein $\theta\in\left[a,b\right]$ mit \[ \boxed{f\left[t_{1},\ldots,t_{k}\right]=\frac{1}{\left(k-1\right)!}\cdot f^{\left(k-1\right)}\left(\theta\right)}\] \end{lem} \begin{rem*} Für $k=2$ ist dies der Mittelwertsatz. \end{rem*} \begin{proof} $\tilde{N}$ sei das Interpolationspolynom zu den Stüztstellen $t_{1},\ldots,t_{k}$ und $f$. Sei \[ \tilde{R}:=f-\tilde{N}\] Dann ist $\tilde{R}\left(t_{i}\right)=0$, $i=1,\ldots,k$, und $\tilde{R}\in C^{k-1}\left(\left[a,b\right]\right)$. $\tilde{R}$ hat mindestens $k$ voneinander verschiedene Nullstellen, $\tilde{R}'$ hat mindestens $k-1$ voneinander verschiedene Nullstellen (Satz von Rolle), usw. Dann hat $\tilde{R}^{\left(k-1\right)}$ mindestens eine Nullstelle $\theta$ und es gilt:\begin{eqnarray*} 0=\tilde{R}^{\left(k-1\right)}\left(\theta\right) & = & f^{\left(k-1\right)}\left(\theta\right)-\tilde{N}^{\left(k-1\right)}\left(\theta\right)\\ & = & f^{\left(k-1\right)}\left(\theta\right)-\left(\prod_{i=1}^{k}\left(t-t_{i}\right)f\left[t_{1},\ldots,t_{k}\right]\right)^{\left(k-1\right)}\\ & = & f^{\left(k-1\right)}\left(\theta\right)-\left(k-1\right)!\cdot f\left[t_{1},\ldots,t_{k}\right]\end{eqnarray*} \end{proof} \begin{thm} \label{thm:Restgliedabschaetzung_Interpolationspolynom}Sei $f\in C^{n}\left(\left[a,b\right]\right)$ und seien $t_{1},\ldots,t_{n}\in\left[a,b\right]$ paarweise voneinander verschieden.% \marginpar{Restglied\-ab\-schätz\-ung% } Sei $P$ das zugehörige Interpolationspolynom. Dann gilt\[ \boxed{\left\Vert f-P\right\Vert _{\infty}\leq\left(b-a\right)^{n}\cdot\frac{1}{n!}\cdot\left\Vert f^{\left(n\right)}\right\Vert _{\infty}}\] \end{thm} %~ \begin{thm} \label{thm:Konvergenz_Interpolationspolynom}\index{Konvergenzsatz!Interpolationspolynom}% \marginpar{Konvergenz\-satz% }Sei $f\in C^{\infty}\left(\left[a,b\right]\right)$, $t_{1},\ldots,t_{n}\in\left[a,b\right]$ paarweise voneinander verschieden und $P_{n}$ sei das Interpolationspolynom zu $t_{1},\ldots,t_{n}$. Weiterhin gelte $\left\Vert f^{\left(n\right)}\right\Vert _{\infty}\leq K\cdot M^{n}$, $n\in\N$. Dann gilt\[ \boxed{\left\Vert f-P_{n}\right\Vert _{\infty}\xrightarrow{n\rightarrow\infty}0}\] \end{thm} \begin{rem*} Die Klasse der Funktionen, die diesen Voraussetzungen genügt, ist sehr klein. \end{rem*} \begin{example*} ~ \begin{itemize} \item Sei \[ f\left(t\right)=\left\{ \begin{array}{cl} e^{-\frac{1}{t^{2}}} & t\in\left(0,1\right]\smallskip\\ 0 & t\in\left[-1,1\right]\end{array}\right.,\] $f\in C^{\infty}$. Wir betrachten die Stütztstellen $t_{1},\ldots,t_{n}\in\left[-1,0\right]$ mit $f\left(t_{i}\right)=0$. \medskip{} \noindent Dann gilt: $P_{n}\left(t\right)\equiv0$, $n\in\N$ und\[ \left|f\left(t\right)-P_{n}\left(t\right)\right|=f\left(t\right)\,\not\rightarrow\,0\,\left(n\rightarrow\infty\right),\quad t\in\left(0,1\right]\] \item Die Runge-Funktion \[ f\left(t\right)=\frac{1}{1+25t^{2}},\quad t\in\left[-1,1\right],\] erfüllt die Voraussetung $\left\Vert f^{(n)}\right\Vert _{\infty}\leq K\cdot M^{n}$ nicht. \end{itemize} \end{example*} \subsection{Interpolierende kubische Splinefunktionen\index{Splinefunktion}} \begin{defn*} Eine Funktion $S\in C^{2}\left(\left[a,b\right]\right)$ heißt \underbar{kubische Splinefunktion}\index{Splinefunktion!kubisch}% \marginpar{kubischer Spline% } (oder kubischer Spline) zur Zerlegung $\pi:\, a=t_{0}\int_{a}^{b}\left(S''\left(t\right)\right)^{2}dt,\quad g\in\mathcal{F},g\neq S}\] \end{thm} \begin{proof} Sei $g\in\mathcal{F}$.\[ \int_{a}^{b}\left(g''\left(t\right)\right)^{2}dt-\int_{a}^{b}\left(S''\left(t\right)\right)^{2}dt=\underbrace{\int_{a}^{b}\left(g''\left(t\right)-S''\left(t\right)\right)^{2}dt}_{\geq0}+\underbrace{2\int_{a}^{b}S''\left(t\right)g''\left(t\right)dt-2\int_{a}^{b}\left(S''\left(t\right)\right)^{2}dt}_{=:I}\] \begin{eqnarray*} \frac{1}{2}I & = & \int_{a}^{b}S''\left(t\right)\left(g''\left(t\right)-S''\left(t\right)\right)dt=\sum_{j=1}^{n}\int_{t_{j-1}}^{t_{j}}S''\left(t\right)\left(g''\left(t\right)-S''\left(t\right)\right)dt\\ & = & \sum_{j=1}^{n}\left(\left.S''\left(t\right)\left(g'\left(t\right)-S'\left(t\right)\right)\right|_{t_{j-1}}^{t_{j}}-\int_{t_{j-1}}^{t_{j}}S'''\left(t\right)\left(g'\left(t\right)-S'\left(t\right)\right)dt\right)\\ & = & \underbrace{S''\left(t_{n}\right)}_{=0}\left(g'\left(t_{n}\right)-S'\left(t_{n}\right)\right)-\underbrace{S''\left(t_{0}\right)}_{=0}\left(g'\left(t_{0}\right)-S'\left(t_{0}\right)\right)-\sum_{j=1}^{n}\int_{t_{j-1}}^{t_{j}}\frac{1}{h_{j}}\left(M_{j}-M_{j-1}\right)\left(g'\left(t\right)-S'\left(t\right)\right)dt\\ & = & -\sum_{j=1}^{n}\frac{1}{h_{j}}\left(M_{j}-M_{j-1}\right)\cdot\underbrace{\left.\left(g\left(t\right)-S\left(t\right)\right)\right|_{t_{j-1}}^{t_{j}}}_{0\textrm{ wg}.\textrm{ Interpolationseigenschaft }g\in\mathcal{F}}=0\end{eqnarray*} Für ein $g\in\mathcal{F}$ gelte \begin{eqnarray*} \int_{a}^{b}\left(g''\left(t\right)-S''\left(t\right)\right)^{2}dt & = & 0\\ \leadsto\, g''\left(t\right) & \equiv & S''\left(t\right)\\ g\left(t\right) & \equiv & S\left(t\right)+\alpha\left(t-t_{0}\right)+\beta\\ f\left(t_{0}\right)=g\left(t_{0}\right) & = & S\left(t_{0}\right)+\beta=f\left(t_{0}\right)+\beta\quad\leadsto\,\beta=0\\ f\left(t_{n}\right)=g\left(t_{n}\right) & = & S\left(t_{n}\right)+\alpha\left(t_{n}-t_{0}\right)=f\left(t_{n}\right)+\alpha\left(t_{n}-t_{0}\right)\quad\leadsto\,\alpha=0\\ \leadsto\, g & \equiv & S\end{eqnarray*} \end{proof} \newpage \section{Numerische Berechnung von Integralen} Sei $f\in C\left(\left[a,b\right]\right)$. $\int_{a}^{b}f\left(t\right)dt=?$ \subsection{Interpolationsformeln} \subsubsection{Gaußsche Quadraturformeln} ~ Unter Benutzung des Lagrangschen Interpolationspolynoms können wir die Gaußsche Quadraturformel (Gauß-Lagrange-Formel)\index{Gaußsche Quadraturformel}\index{Quadraturformel!Gauß}\index{Gauß-Lagrange-Formel} definieren: \[ \int_{a}^{b}f\left(t\right)dt=\int_{a}^{b}\sum_{j=1}^{n}p_{j}\left(t\right)\cdot f\left(t_{j}\right)dt+\underbrace{\int_{a}^{b}\omega\left(t\right)\cdot f\left[t_{1},\ldots,t_{n},t\right]}_{=:R\left(f\right)}\] mit $t_{1},\ldots,t_{n}\in\left[1,b\right]$ paarweise verschieden, $\omega\left(t\right)=\prod_{j=1}^{n}\left(t-t_{j}\right)$ und $p_{j}\left(t\right)$ Lagrange-Polynome (siehe §4.1).% \marginpar{Gaußsche Quadratur\-formel% }\begin{equation} \boxed{\begin{array}{rcl} A_{j} & := & {\displaystyle \int_{a}^{b}p_{j}\left(t\right)dt},\quad j=1,\ldots,n\smallskip\\ {\displaystyle \int_{a}^{b}f\left(t\right)dt} & \approx & {\displaystyle \sum_{j=1}^{n}A_{j}f\left(t_{j}\right)}\end{array}}\label{eq:gauss_quadratur}\end{equation} \begin{eqnarray*} R\left(f\right) & := & \int_{a}^{b}f\left(t\right)dt-\sum_{j=1}^{n}A_{j}f\left(t_{j}\right)\\ & = & \int_{a}^{b}\omega\left(t\right)\cdot f\left[t_{1},\ldots,t_{n},t\right]dt\end{eqnarray*} \begin{defn*} Die Formel (\ref{eq:gauss_quadratur}) ist \underbar{genau\index{genau}\index{Quadraturformel!genau}} $\Leftrightarrow$ statt ,,$\approx$'' steht ,,$=$'', d.h. $R\left(f\right)=0$. \end{defn*} %~ \begin{defn*} Der \underbar{algebraische Genauigkeitsgrad $\mu$\index{Genauigkeitsgrad, algebraisch}\index{Quadraturformel!algebraischer Genauigkeitsgrad}}% \marginpar{algebra\-ischer Genau\-ig\-keits\-grad% } einer Interpolationsformel ist der maximale Grad, den ein Polynom haben kann, damit die Formel genau ist. \end{defn*} Für die Gaußsche Quadraturformel (\ref{eq:gauss_quadratur}) gilt nach Konstruktion $\mu\geq n-1$. Der maximale Genauigkeitsgrad beträgt $2n-1$. \begin{example*} Wir betrachten als Beispiel den Fall $n=1$: \underbar{Rechteckregel}\index{Rechteckregel}\index{Quadraturformel!Rechteckregel}:\begin{eqnarray*} \int_{a}^{b}f\left(t\right)dt & \approx & A_{1}\cdot f\left(t_{1}\right)\\ A_{1} & = & \int_{a}^{b}dt=b-a\end{eqnarray*} % \marginpar{Rechteck\-regel% }\[ \boxed{\int_{a}^{b}f\left(t\right)dt\approx\left(b-a\right)\cdot f\left(t\right)}\] % \begin{figure}[htbp] \begin{center}\includegraphics[% width=0.25\paperwidth]{8.eps}\end{center} \caption{Interpoliertes Integral im Fall $n=1$ (Rechteckregel)} \end{figure} Es ist $\mu\geq0$. Ansatz: $f\left(t\right)=t-t_{1}$, $f\left[t,t_{1}\right]\equiv1$.\begin{eqnarray*} R\left(f\right) & = & \int_{a}^{b}\left(t-t_{1}\right)\cdot f\left[t_{1},t\right]dt\\ & = & \int_{a}^{b}\left(t-t_{1}\right)dt\\ & = & \left\{ \begin{array}{cl} 0 & \textrm{falls }t_{1}=\frac{a+b}{2}\smallskip\\ \neq0 & \textrm{sonst}\end{array}\right.\end{eqnarray*} Falls $t_{1}=\frac{a+b}{2}$, so gilt $\mu=1$, sonst $\mu=0$. \end{example*} Alle Interpolationsformeln sind genau für Polynome 0. Grades und es gilt dann:\[ \int_{a}^{b}dt=\sum_{j=1}^{n}A_{j}=b-a\] Für die Gaußsche Quadraturformel gilt $\mu\leq2n-1$, denn für $f\left(t\right)=\left(\omega\left(t\right)\right)^{2}$, $\omega\left(t\right)=\prod_{i=1}^{n}\left(t-t_{i}\right)$, ist $\textrm{grad}f=2n$ und\[ \int_{a}^{b}f\left(t\right)dt>0,\textrm{ aber }\sum_{j=1}^{n}A_{j}\underbrace{f\left(t_{j}\right)}_{=0}=0\] \begin{thm} Die Interpolationsformel mit $n$ paarweise voneinander verschiedenen Knoten $t_{1},\ldots,t_{n}\in\left[a,b\right]$ hat den algebraischen Genauigkeitsgrad $\mu=2n-1$ genau dann, wenn\[ \int_{a}^{b}\omega\left(t\right)p\left(t\right)dt=0\] für alle Polynome $p$ mit $\mathrm{grad}\left(p\right)\leq n-1$ gilt. \end{thm} \begin{rem*} Polynome $\omega,p$ mit $\left\langle \omega,p\right\rangle _{L_{2}\left(a,b\right)}:=\int_{a}^{b}\omega\left(t\right)p\left(t\right)dt=0$ heißen orthogonale Polynome\index{orthogonale Polynome}\index{Polynom!orthogonal}. \end{rem*} \begin{proof} ~ \begin{description} \item [$\left(\Rightarrow\right)$]Sei $\mu=2n-1$, $\textrm{grad}\left(p\right)\leq n-1$. Wir bilden $f:=\omega\cdot p$, $\textrm{grad}\left(f\right)\leq2n-1$. Dann ist\[ \int_{a}^{b}\omega\left(t\right)p\left(t\right)dt=\sum_{j=1}^{n}A_{j}f\left(t_{j}\right)=0,\qquad\textrm{da }f\left(t_{j}\right)=\underbrace{\omega\left(t_{j}\right)}_{=0}\cdot p\left(t_{j}\right)=0\] \item [$\left(\Leftarrow\right)$]Sei $f$ ein Polynom mit $n\leq\textrm{grad}\left(f\right)\leq2n-1$. Dann existieren Polynome $p$ und $r$, so daß $f=\omega p+r$ und $\textrm{grad}\left(p\right),\textrm{grad}\left(r\right)\leq n-1$. Dann ist wegen $\omega\left(t_{j}\right)=0$:\[ f\left(t_{j}\right)=r\left(t_{j}\right),\quad j=1,\ldots,n.\] \[ \int_{a}^{b}f\left(t\right)dt=\underbrace{\int_{a}^{b}\omega\left(t\right)p\left(t\right)dt}_{=0}+\int_{a}^{b}r\left(t\right)dt=\sum_{j=1}^{n}A_{j}r\left(t_{j}\right)=\sum_{j=1}^{n}A_{j}f\left(t_{j}\right)\] \end{description} \end{proof} \begin{lem} Es gelte für ein Polynom $\tilde{\omega}$, $\mathrm{grad}\tilde{\omega}=n$, die Beziehung\[ \int_{a}^{b}\tilde{\omega}\left(t\right)p\left(t\right)dt=0\] für alle Polynome $p$ mit $\mathrm{grad}\left(p\right)\leq n-1.$ Dann hat $\tilde{\omega}$ in $\left(a,b\right)$ genau $n$ paarweise voneinander verschiedene Nullstellen. \end{lem} \begin{proof} G. Opfer: Numerische Mathematik für Anfänger, Vieweg 1993, S. 103 \end{proof} \begin{defn*} Knoten zum maximalen Genauigkeitsgrad $\mu=2n-1$ heißen \underbar{Gaußsche Knoten}\index{Gaußsche Knoten}. \end{defn*} \subsubsection{Newton-Cotes-Formeln} ~\index{Newton-Cotes-Formeln}\index{Quadraturformel!Newton-Cotes} Bei den Newton-Cotes-Formeln% \marginpar{Newton-Cotes-Formeln% } handelt es sich um Quadraturformeln auf äquidistanten Unterteilungen des Intervalls {[}a,b{]}. D.h. wir betrachten (\ref{eq:gauss_quadratur}) mit $t_{1}=a$, $t_{2}=a+h$,$\ldots$,$t_{n}=a+\left(n-1\right)h=b$.\[ \leadsto\, h=\frac{b-a}{n-1},\quad n\geq2\] \begin{example*} Fall $n=2$: Trapezregel\index{Trapezregel}\index{Quadraturformel!Trapezregel}\begin{eqnarray*} \int_{a}^{b}f\left(t\right)dt & \approx & A_{1}f\left(a\right)+A_{2}f\left(b\right)\\ A_{1} & = & \int_{a}^{b}\frac{t-b}{a-b}dt=\frac{1}{2}\left(b-a\right)\\ A_{2} & = & \int_{a}^{b}\frac{t-a}{b-a}dt=\frac{1}{2}\left(b-a\right)\end{eqnarray*} % \marginpar{Trapezregel% }\[ \boxed{\int_{a}^{b}f\left(t\right)dt\approx\frac{b-a}{2}\left(f\left(a\right)+f\left(b\right)\right)}\] % \begin{figure}[htbp] \begin{center}\includegraphics[% width=0.25\paperwidth, keepaspectratio]{9.eps}\end{center} \caption{Newton-Cotes-Formel für $n=2$: Trapezregel} \end{figure} Es ist $\mu\geq1$. Für $f\left(t\right)=\left(t-a\right)\left(b-t\right)$ ist $\int_{a}^{b}f\left(t\right)dt>0$, aber $\frac{b-a}{2}\left(f\left(a\right)+f\left(b\right)\right)=0$. $\leadsto$ $\mu=1$. \end{example*} Die Newton-Cotes-Formeln haben einen geringeren Genauigkeitsgrad, sind aber andererseits praktischer zu handhaben. \begin{lem} \label{lem:5.3}Sei $f\in C^{2}\left(\left[a,b\right]\right)$. Dann gibt es ein $\theta\in\left[a,b\right]$ mit\[ R\left(f\right):=\int_{a}^{b}f\left(t\right)dt-\frac{1}{2}\left(b-a\right)\left(f\left(a\right)+f\left(b\right)\right)=-\frac{1}{12}\left(b-a\right)^{3}f''\left(\theta\right)\] \end{lem} \begin{proof} ~\[ -R\left(f\right)=-\int_{a}^{b}\left(t-a\right)\left(t-b\right)f\left[a,b,t\right]dt\stackrel{\left(\textrm{L. }\ref{lem:4.1}\right)}{=}\int_{a}^{b}\underbrace{\left(t-a\right)\left(b-t\right)}_{=:g\left(t\right)}\cdot\frac{1}{2}f''\left(\theta_{t}\right)dt\] Es ist $g\geq0$ und $\int_{a}^{b}g=\frac{1}{6}\left(b-a\right)^{3}>0$. Nach dem ersten Mittelwertsatz existiert dann ein $\theta\in\left[a,b\right]$, so daß\[ -R\left(f\right)=\int_{a}^{b}g\left(t\right)dt\cdot\frac{1}{2}f''\left(\theta\right)=\frac{\left(b-a\right)^{3}}{12}\cdot f''\left(\theta\right)\] \end{proof} \subsection{Zusammengesetzte Formeln} ~\index{Quadraturformel!zusammengesetzt} Bisher hatten wir Quadraturformeln kennengelernt, welche durch Integration eines Interpolationspolynoms entstanden sind. Bei zusammengesetzten Quadraturformeln betrachten wir dagegen Funktionen, welche stückweise aus Polynomen zusammengesetzt sind (z.B. kubische Splines). \underbar{Zusammengesetzte} \underbar{(große / iterierte)} \underbar{Trapezregel}\index{Trapezregel!zusammengesetzt (groß, iteriert)}\index{Quadraturformel!Trapezregel!zusammengesetzt}% \marginpar{Trapez\-regel, zusammengesetzt% }: $a=t_{0}<\ldots1$ von einem Mehrschrittverfahren\index{Mehrschrittverfahren} (Zweischritt-, Dreischritt-, ...) Ist $\beta_{0}=0$ so handelt es sich um ein \underbar{explizites Verfahren}\index{explizit}\index{Mehrschrittverfahren!explizit}, anderenfalls um ein \underbar{implizites\index{implizit}\index{Mehrschrittverfahren!implizit}} (in diesem Fall ist pro Schritt ein Gleichungssystem zu lösen). Wir setzen den exakten Lösungswert des AWA in die Näherungsformel ein und betrachten den \underbar{Defekt} (\underbar{,,lokaler Fehler''})\index{Defekt}\index{Fehler!lokal}:% \marginpar{lokaler Fehler% } \[ \boxed{\tau_{l}:=\frac{1}{h}\sum_{j=0}^{k}\alpha_{j}\cdot x\left(t_{l-j}\right)-\sum_{j=0}^{k}\beta_{j}\cdot f\left(x\left(t_{l-j}\right),t_{l-j}\right),\quad l\geq k}\] Da $f\left(x\left(t_{l-j}\right),t_{l-j}\right)=x'\left(t_{l-j}\right)$ können wir auch schreiben:\[ \tau_{l}=\frac{1}{h}\sum_{j=0}^{k}\left(\alpha_{j}x\left(t_{l-j}\right)-h\beta_{j}x'\left(t_{l-j}\right)\right)\] Unter der Voraussetzung, daß die exakte Lösung $x\left(\cdot\right)\in C^{p+1}$ ist, gilt (Taylorentwicklung um $t_{l}$):\begin{eqnarray*} x\left(t_{l-j}\right) & = & \sum_{i=0}^{p+1}\frac{\left(-jh\right)^{i}}{i!}x^{(i)}\left(t_{l}\right)+o\left(h^{p+1}\right)\\ x'\left(t_{l-j}\right) & = & \sum_{i=0}^{p}\frac{\left(-jh\right)^{i}}{i!}x^{(i+1)}\left(t_{l}\right)+o\left(h^{p}\right)\end{eqnarray*} Eingesetzt erhalten wir\begin{eqnarray*} \tau_{l} & = & \frac{1}{h}\sum_{j=0}^{k}\alpha_{j}\cdot x\left(t_{l}\right)+h^{0}\cdot\sum_{j=0}^{k}\left(-\alpha_{j}\cdot j-\beta_{j}\right)x'\left(t_{l}\right)+h^{1}\cdot\sum_{j=0}^{k}\left(\alpha_{j}\cdot\frac{\left(-j\right)^{2}}{2}-\beta_{j}\cdot\left(-1\right)\right)x''\left(t_{l}\right)+\ldots+\\ & & +h^{p}\cdot\sum_{j=0}^{k}\left(\alpha_{j}\frac{\left(-j\right)^{p+1}}{p+1}-\beta_{j}\left(-j\right)^{p}\right)\frac{1}{p!}x^{(p+1)}\left(t_{l}\right)+o\left(h^{p}\right)\end{eqnarray*} \begin{thm} Sind für das lineare $k$-Schrittverfahren (\ref{6.2}) die Bedingungen\begin{equation} \sum_{j=0}^{k}\alpha_{j}=0,\qquad\sum_{j=0}^{k}\left(\alpha_{j}j+\beta_{j}\right)=0,\label{6.3}\end{equation} \begin{eqnarray} \sum_{j=0}^{k}\left(\alpha_{j}\frac{j^{i+1}}{i+1}+\beta_{j}j^{i}\right) & = & 0,\quad i=1,\ldots,p-1,\label{6.4}\end{eqnarray} erfüllt (d.h., bis auf den letzten Summenterm in der obigen Gleichung sind alle anderen Summenterme 0), so gilt bei ausreichend glatten Lösungen $x(\cdot)$, daß\[ \boxed{\tau_{l}=c_{p}x^{(p+1)}\left(t_{l}\right)h^{p}+o\left(h^{p}\right)}\] mit der Fehlerkonstanten \[ c_{p}=\frac{(-1)^{p+1}}{p!}\sum_{j=0}^{k}\left(\alpha_{j}\frac{j^{p+1}}{p+1}+\beta_{j}j^{p}\right)\] \end{thm} Normierung der Verfahren: $\sum_{j=0}^{k}\beta_{j}=1$. \begin{defn*} Ein Verfahren (\ref{6.2}) mit (\ref{6.3}) heißt \underbar{konsistent}\index{Konsistenz}% \marginpar{Konsistenz% }. Gilt zusätzlich (\ref{6.4}), so heißt das Verfahren \underbar{konsistent mit Ordnung\index{Konsistenzordnung}} $p$. \end{defn*} Wichtige Verfahren sind: \begin{enumerate} \item Explizites Euler-Verfahren\index{Euler-Verfahren!explizit} \[ \frac{1}{h}\left(x_{l}-x_{l-1}\right)-f\left(x_{l-1},t_{l-1}\right)=0\] $\alpha_{0}=1$, $\alpha_{1}=-1$, $\beta_{0}=0$ und $\beta_{1}=1$ $\leadsto$ $c_{p}=\frac{1}{2}$, Konsistenzordnung ist $p=1$ \medskip{} \item Implizites Eulerverfahren\index{Euler-Verfahren!implizit} \[ \frac{1}{h}\left(x_{l}-x_{l-1}\right)-f\left(x_{l},t_{l}\right)=0\] $\alpha_{0}=1$, $\alpha_{1}=-1$, $\beta_{0}=1$ und $\beta_{1}=0$ $\leadsto$ $c_{p}=\frac{1}{2}$, Konsistenzordnung ist $p=1$ \medskip{} \item Trapezregel\index{Trapezregel} \[ \frac{1}{h}\left(x_{l}-x_{l-1}\right)-\frac{1}{2}\left(f\left(x_{l},t_{l}\right)+f\left(x_{l-1},t_{l-1}\right)\right)=0\] $\alpha_{0}=1$, $\alpha_{1}=-1$ und $\beta_{0}=\beta_{1}=\frac{1}{2}$ $\leadsto$ $c_{p}=\frac{1}{24}$, Konsistenzordnung ist $p=2$ \medskip{} \item BDF (Backward Differentation Formula)\index{BDF} \[ \frac{1}{h}\sum_{j=0}^{k}\alpha_{j}x_{l-j}-f\left(x_{l},t_{l}\right)=0\] $\beta_{0}=1$, $\beta_{j}=0$ für $j=1,\ldots,k$. Die $\alpha_{0},\ldots,\alpha_{k}$ sind so bestimmt, daß (\ref{6.3}) erfüllt ist und die Konsistenzordnung $p=k$ erreicht wird. \medskip{} \noindent (Das Beispiel (\ref{2Schritt_implizit}) ist $k=2$, das implizite Eulerverfahren ist $k=1$.) \medskip{} \item Adams-Bashforth-Verfahren (Verallgemeinerungen des expliziten Euler-Verfahrens)\index{Adams-Bashforth-Verfahren} \[ \frac{1}{h}\left(x_{l}-x_{l-1}\right)-\sum_{j=1}^{k}\beta_{j}f\left(x_{l-j},t_{l-j}\right)=0\] $\alpha_{0}=1$, $\alpha_{1}=-1$, $\alpha_{j}=0$ für $j=2,\ldots,k$, $\beta_{0}=0$, $\beta_{1},\ldots,\beta_{k}$ sind so gewählt, daß die Konsistenzordnung $p=k$ erreicht wird. \medskip{} \item Adams-Moulton-Verfahren\index{Adams-Moulton-Verfahren} \[ \frac{1}{h}\left(x_{l}-x_{l-1}\right)-\sum_{j=0}^{k}\beta_{j}f\left(x_{l-j},t_{l-j}\right)=0\] $\alpha_{0}=1$, $\alpha_{1}=-1$, $\alpha_{j}=0$ für $j=2,\ldots,k$, $\beta_{0},\ldots,\beta_{k}$ sind so gewählt, daß die Konsistenzordnung $p=k+1$ erreicht wird. \end{enumerate} Das Verfahren (\ref{2Schritt_explizit}) hatte die Werte $k=2$, $\alpha_{0}=-\frac{1}{2}$, $\alpha_{1}=2$, $\alpha_{2}=-\frac{3}{2}$, $\beta_{0}=0$, $\beta_{1}=0$ und $\beta_{2}=1$. Damit hat das Verfahren die Konsistenzordnung 2. Diese Eigenschaft hat also nichts mit der schlechten Qualität dieses Verfahrens zu tun. \begin{defn*} Das Polynom% \marginpar{charakter\-istisches Polynom% } \[ \boxed{\rho\left(\lambda\right):=\sum_{j=0}^{k}\alpha_{j}\lambda^{k-j}}\] heißt \underbar{charakteristisches Polynom\index{charakteristisches Polynom}\index{Polynom!charakteristisch}} des Verfahrens (\ref{6.2}). \end{defn*} \begin{rem} $\rho(1)=\sum_{j=0}^{k}\alpha_{j}=0$ bei konsistenten Verfahren - Die $1$ ist die \underbar{Konsistenznullstelle\index{Konsistenznullstelle}} des charakteristischen Polynoms. \end{rem} Betrachten wir erneut die Beispielsverfahren (\ref{2Schritt_explizit}) und (\ref{2Schritt_implizit}), so sehen wir, daß für (\ref{2Schritt_explizit}) das charakteristische Polynom $\rho(\lambda)=-\frac{1}{2}\lambda^{2}+2\lambda-\frac{3}{2}$ die Nullstellen $\lambda_{1}=1$ und $\lambda_{2}=3$ besitzt. Für (\ref{2Schritt_implizit}) haben wir $\rho(\lambda)=\frac{3}{2}\lambda^{2}-2\lambda+\frac{1}{2}$ mit den Nullstellen $\lambda_{1}=1$ und $\lambda_{2}=\frac{1}{3}$. Wir sehen, daß die Nullstellen des charakteristischen Polynoms des ,,guten'' Verfahrens (\ref{2Schritt_implizit}) im Einheitskreis liegen, während sie beim ,,schlechten'' Verfahren (\ref{2Schritt_explizit}) nicht vollständig im Einheitskreis liegen. Dies führt dazu, daß sich der Fehler aufschaukelt. \subsection{Stabilität und Konvergenz} \begin{defn*} (\underbar{Dahlquistsches Wurzelkriterium}\index{Dahlquistsches Wurzelkriterium}, 1956)% \marginpar{Dahl\-quist\-sches Wurzel\-kriterium% }% \marginpar{stabil% } Ein lineares $k$-Schritt-Verfahren heißt \underbar{stabil\index{stabil}\index{Mehrschrittverfahren!stabil}} ($h\rightarrow0$ stabil), falls die Wurzeln des charakteristischen Polynoms entweder im Innern des komplexen Einheitskreises liegen oder sie liegen auf dem Einheitskreisbogen und sind einfach. \end{defn*} Es ist\[ \max_{l=1,\ldots,n}\left|x_{l}-x\left(t_{l}\right)\right|\leq S\cdot\max_{l=1,\ldots,n}\left|\tau\left(l\right)\right|\] Voraussetzung für DGL:\[ \left|f_{x}\left(x,t\right)\right|\leq L,\quad x\in\R^{m},t\in\left[t_{0},T\right]\] Umformen der k-Schritt-Gleichung:\[ x_{l}=-\sum_{j=1}^{k}\frac{\alpha_{j}}{\alpha_{0}}x_{l-j}+h\sum_{j=0}^{k}\frac{\beta_{i}}{\alpha_{0}}f\left(x_{l-j},t_{l-j}\right)\] Dies ist nur ein theoretischer Wert, in der Praxis treten Rundungsfehler auf:\begin{equation} \tilde{x}_{l}=-\sum_{j=1}^{k}\frac{\alpha_{j}}{\alpha_{0}}\tilde{x}_{l-j}+h\sum_{j=0}^{k}\frac{\beta_{j}}{\alpha_{0}}f\left(\tilde{x}_{l-j},t_{l-j}\right)+\delta_{l},\quad l\geq k\label{6.6}\end{equation} $\delta_{l}$ enthält Rundungsfehler und eventuelle Abbruchfehler. Startwerte $\tilde{x}_{0}=x_{0},\tilde{x}_{1},\ldots,\tilde{x}_{k-1}$ Es ist\[ x\left(t_{l}\right)=-\sum_{j=1}^{k}\frac{\alpha_{j}}{\alpha_{0}}x\left(t_{l-j}\right)+h\sum_{j=0}^{k}\frac{\beta_{j}}{\alpha_{0}}f\left(x\left(t_{l-j}\right),t_{l-j}\right)+h\tau_{l}\] Mit $\varepsilon_{i}:=x\left(t_{i}\right)-\tilde{x}_{i}$, $i\geq0$, wird\[ \varepsilon_{l}=-\sum_{j=1}^{k}\frac{\alpha_{j}}{\alpha_{0}}\varepsilon_{l-j}+h\sum_{j=0}^{k}\frac{\beta_{j}}{\alpha_{0}}\underbrace{\left\{ f\left(x\left(t_{l-j}\right),t_{l-j}\right)-f\left(\tilde{x}_{l-j},t_{l-j}\right)\right\} }_{{\displaystyle \textrm{L. }\ref{lem:Integralmittelwertsatz}:}\,\underbrace{\int_{0}^{1}f_{x}\left(\ldots\right)ds}_{{\displaystyle =:B_{l,j}}}{\displaystyle \cdot\varepsilon_{l-j}}}+h\tau_{l}-\delta_{l},\quad l\geq k\] Es gilt $\left\Vert B_{l,j}\right\Vert \leq L$ für $l\geq k$, $j=0,\ldots,k$. Damit entsteht folgende Rekursion\index{Fehler!global}:% \marginpar{globaler Fehler% }\begin{equation} \boxed{\varepsilon_{l}=-\sum_{j=1}^{k}\frac{\alpha_{j}}{\alpha_{0}}\varepsilon_{l-j}+h\sum_{j=0}^{k}\frac{\beta_{j}}{\alpha_{0}}B_{l,j}\varepsilon_{l-j}+h\tau_{l}-\delta_{l}}\label{6.7}\end{equation} Wunsch:\[ \left|\varepsilon_{l}\right|\leq S\cdot\left\{ \max_{i=k,\ldots,n}\left|\tau_{i}-\frac{1}{h}\delta_{i}\right|+\max_{i=1,\ldots,k-1}\left|\varepsilon_{i}\right|\right\} \] \begin{thm} \label{Konvergenzsatz_Mehrschrittverfahren}\index{Konvergenzsatz!Mehrschrittverfahren}\index{Mehrschrittverfahren!Konvergenz}Sei $\left|f_{x}\left(x,t\right)\right|\leq L$, $x\in\R^{m}$, $t\in\left[t_{0},T\right]$.% \marginpar{Konvergenz\-satz% } Das lineare $k$-Schrittverfahren (\ref{6.2}) sei konsistent und stabil. Es gelte $\left|\beta_{0}\right|h_{*}<\frac{\left|\alpha_{0}\right|}{L}$. Dann gilt: \begin{enumerate} \item Bei Verwendung von Startwerten $x_{i}=x\left(t_{i}\right)$, d.h. $\varepsilon_{i}=0$, $\delta_{i}=0$, $i=0,\ldots,k-1$, gilt\[ \boxed{\max_{l=k,\ldots,n}\left|x\left(t_{l}\right)-x_{l}\right|\leq S\cdot\max_{l=k,\ldots,n}\left|\tau_{l}\right|}\] mit einer Konstanten $S$ gleichmäßig für alle Zerlegungen $t_{0}<\ldots0$ gibt es eine $\C^{m}$-Norm $\left|.\right|_{F,\varepsilon}$ mit der Eigenschaft\[ \left\Vert F\right\Vert _{F,\varepsilon}:=\max_{\left|z\right|_{F,\varepsilon}=1}\left|Fz\right|_{F,\varepsilon}\leq\rho\left(F\right)+\varepsilon\] ($\rho$ sei der Spektralradius). \medskip{} \item Haben alle betragsmaximalen Eigenwerte von $F$ einfache Struktur (algebraische Vielfachheit = geometrische Vielfachheit), so gibt es eine $\C^{m}$-Norm $\left|.\right|_{*}$ mit \[ \left\Vert F\right\Vert _{*}=\rho\left(F\right).\] \newpage \end{enumerate} \end{lem} \begin{proof} ~ \begin{enumerate} \item Sei $F=TJT^{-1}$ mit \[ J=\left(\begin{array}{cccc} \lambda_{1} & \delta_{1} & 0 & 0\\ 0 & \ddots & \ddots & 0\\ 0 & \ddots & \ddots & \delta_{m-1}\\ 0 & 0 & 0 & \lambda_{m}\end{array}\right)\] $\delta_{i}$ sind 0 oder 1, $\left|\lambda_{1}\right|\geq\ldots\geq\left|\lambda_{m}\right|$.\[ J_{\varepsilon}:=\left(\begin{array}{cccc} \lambda_{1} & \varepsilon\delta_{1} & 0 & 0\\ 0 & \ddots & \ddots & 0\\ 0 & \ddots & \ddots & \varepsilon\delta_{m-1}\\ 0 & 0 & 0 & \lambda_{m}\end{array}\right)\] Es gilt $J_{\varepsilon}=D_{\varepsilon}^{-1}JD_{\varepsilon}$ mit \[ D_{\varepsilon}:=\left(\begin{array}{cccc} \varepsilon^{0} & 0 & \cdots & 0\\ 0 & \varepsilon^{1} & \ddots & \vdots\\ \vdots & \ddots & \ddots & 0\\ 0 & \cdots & 0 & \varepsilon^{m-1}\end{array}\right)\] \[ F=T\cdot D_{\varepsilon}\cdot J_{\varepsilon}\cdot D_{\varepsilon}^{-1}\cdot T^{-1}=\left(TD_{\varepsilon}\right)\cdot J_{\varepsilon}\cdot\left(TD_{\varepsilon}\right)^{-1}\] Wir definieren eine Norm auf $\C^{m}$:\[ \left|z\right|_{F,\varepsilon}:=\left|\left(TD_{\varepsilon}\right)^{-1}z\right|_{1},\, z\in\C^{m}\] Induzierte Norm auf $M\in\C^{m}$:\begin{eqnarray*} \left\Vert M\right\Vert _{F,\varepsilon} & := & \max_{\left|z\right|_{F,\varepsilon}=1}\left|Mz\right|_{F,\varepsilon}\\ & = & \max_{\left|\left(TD_{\varepsilon}\right)^{-1}z\right|_{1}=1}\left|\left(TD_{\varepsilon}\right)^{-1}M\left(TD_{\varepsilon}\right)\underbrace{\left(TD_{\varepsilon}\right)^{-1}z}_{w}\right|_{1}\\ & = & \max_{\left|w\right|_{1}=1}\left|\left(TD_{\varepsilon}\right)^{-1}M\left(TD_{\varepsilon}\right)w\right|_{1}\\ & = & \left\Vert \left(TD_{\varepsilon}\right)^{-1}M\left(TD_{\varepsilon}\right)\right\Vert _{1}\end{eqnarray*} Speziell gilt:\[ \left\Vert F\right\Vert _{F,\varepsilon}=\left\Vert \left(TD_{\varepsilon}\right)^{-1}F\left(TD_{\varepsilon}\right)\right\Vert _{1}=\left\Vert J_{\varepsilon}\right\Vert _{1}\leq\max_{i=1,\ldots,m}\left|\lambda_{i}\right|+\varepsilon=\rho\left(F\right)+\varepsilon\] \medskip{} \item $s-1$ sei die Anzahl der betragsmaximalen Eigenwerte. Dann ist $\delta_{i}=0$ für $i=1,\ldots,s-1$:\[ J=\left(\begin{array}{cccccc} \lambda_{1}\\ & \ddots\\ & & \lambda_{s-1} & \delta_{s-1}\\ & & & \lambda_{s} & \ddots\\ & & & & \ddots & \delta_{m-1}\\ & & & & & \lambda_{m}\end{array}\right)\] Wir wählen $\varepsilon$ so, daß $\left|\lambda_{i}\right|+\varepsilon\leq\rho\left(F\right)$, $i=s,\ldots,m$ und wenden $\left(1\right)$ an. \end{enumerate} \end{proof} Explizites Euler-Verfahren\index{Euler-Verfahren!explizit}: $\alpha_{0}=1$, $\alpha_{1}=-1$, $\beta_{0}=0$, $\beta_{1}=1$, $\left\Vert B_{l,j}\right\Vert \leq L$ für $l\geq k=1$, $j=0,1$.\begin{eqnarray*} \varepsilon_{l} & = & \varepsilon_{l-1}+hB_{l,1}\varepsilon_{l-1}+h\left(\tau_{l}-\frac{\delta_{l}}{h}\right),\quad\varepsilon_{0}=0\\ \left|\varepsilon_{l}\right| & \leq & \left(1+hL\right)\cdot\left|\varepsilon_{l-1}\right|+h\cdot\underbrace{\max_{i=1,\ldots,l}\left|\tau_{i}-\frac{\delta_{i}}{h}\right|}_{=:\omega_{l}}\\ & \leq & \left(1+hL\right)^{l}\cdot\left|\varepsilon_{0}\right|+\sum_{i=0}^{l-1}\left(1+hL\right)^{i}\omega_{l}h\\ & = & \left(1+hL\right)^{l}\cdot\left|\varepsilon_{0}\right|+\omega_{l}h\frac{\left(1+hL\right)^{l}-1}{1+hL-1}\\ & \leq & \left(1+hL\right)^{l}\cdot\left(\left|\varepsilon_{0}\right|+\frac{1}{L}\omega_{l}\right),\quad\left(1+hL\right)^{l}\leq e^{hLl}=e^{L\left(t_{l}-t_{0}\right)}\\ & \leq & \max\left(1,\frac{1}{L}\right)\cdot e^{L\left(t_{l}-t_{0}\right)}\cdot\left(\left|\varepsilon_{0}\right|+\omega_{l}\right)\end{eqnarray*} \begin{proof} (von Satz \ref{Konvergenzsatz_Mehrschrittverfahren}): \begin{enumerate} \item Fall $\beta_{0}=0$: Wir führen die $k$-Schritt-Rekursion auf eine 1-Schritt-Rekursion zurück:\begin{eqnarray*} \varepsilon_{l} & = & -\sum_{j=1}^{k}\frac{\alpha_{j}}{\alpha_{0}}\varepsilon_{l-j}+h\sum_{j=1}^{k}\frac{\beta_{j}}{\alpha_{0}}B_{l,j}\varepsilon_{l-j}+h\left(\tau_{l}-\frac{\delta_{l}}{h}\right)\quad l\geq k\\ \varepsilon_{l-1} & = & \varepsilon_{l-1}\\ & \vdots\\ \varepsilon_{l-k+1} & = & \varepsilon_{l-k+1}\\ \leadsto\,\mathcal{E}_{l} & = & \mathcal{A}\cdot\mathcal{E}_{l-1}+h\cdot\mathcal{B}_{l}\cdot\mathcal{E}_{l-1}+h\cdot\Omega_{l}\\ \mathcal{A} & = & \left[\begin{array}{cccc} -\frac{\alpha_{1}}{\alpha_{0}}I & \cdots & \cdots & -\frac{\alpha_{k}}{\alpha_{0}}I\\ I & 0 & \cdots & 0\\ & \ddots & \ddots & \vdots\\ 0 & & I & 0\end{array}\right]\\ \mathcal{B} & = & \left[\begin{array}{ccc} \frac{\beta_{1}}{\alpha_{0}}B_{l,1} & \cdots & \frac{\beta_{k}}{\alpha_{0}}B_{l,k}\\ 0 & \cdots & 0\\ \vdots & \ddots & \vdots\\ 0 & \cdots & 0\end{array}\right]\\ \Omega_{l} & = & \left[\begin{array}{c} \tau_{l}-\frac{\delta_{l}}{h}\\ 0\\ \vdots\\ 0\end{array}\right]\\ \mathcal{E}_{l} & := & \left(\begin{array}{c} \varepsilon_{l}\\ \vdots\\ \varepsilon_{l-k+1}\end{array}\right)\in\R^{mk}\end{eqnarray*} $\mathcal{A}$ ist Frobenius-Blockmatrix, $\mathcal{A}=\left(\begin{array}{cc} -\frac{\alpha_{1}}{\alpha_{0}} & \cdots\\ \vdots & \ddots\end{array}\right)\otimes I$ \medskip{} \noindent Nach dem Dahlquistischen Wurzelkriterium gilt für die Eigenwerte von $\mathcal{A}$: $\left|\lambda_{\mathcal{A}}\right|<1$ oder $\left|\lambda_{\mathcal{A}}\right|=1$ mit algebraischer Vielfachheit = geometrischer Vielfachheit. \medskip{} \noindent Nach Lemma \ref{lem:6.3} existieren dann $\left|.\right|_{*}$ und $\left\Vert .\right\Vert _{*}$ mit $\left\Vert \mathcal{A}\right\Vert _{*}=1$. \medskip{} \noindent Äquivalenz der Normen auf $\R^{mk}$: $Z=\left(\begin{array}{c} z_{1}\\ \vdots\\ z_{k}\end{array}\right),\, z_{i}\in\R^{m},\,\left|Z\right|_{\infty}:={\displaystyle \max_{i=1,\ldots,k}}\left|z_{i}\right|$\[ \gamma_{1}\left|Z\right|_{\infty}\leq\left|Z\right|_{*}\leq\gamma_{2}\left|Z\right|_{\infty}\] \medskip{} \noindent \begin{eqnarray*} \left\Vert \mathcal{B}_{l}\right\Vert _{*} & = & \max_{Z\neq0}\frac{\left|\mathcal{B}_{l}Z\right|_{*}}{\left|Z\right|_{*}}\\ & \leq & \max_{Z\neq0}\frac{\gamma_{2}\left|\mathcal{B}_{l}Z\right|_{\infty}}{\gamma_{1}\left|Z\right|_{\infty}}\\ & = & \frac{\gamma_{2}}{\gamma_{1}}\cdot\left\Vert \mathcal{B}_{l}\right\Vert _{\infty}\\ & = & \frac{\gamma_{2}}{\gamma_{1}}\cdot\sum_{j=1}^{k}\left|\frac{\beta_{j}}{\alpha_{0}}\right|\cdot\left\Vert B_{l,j}\right\Vert \\ & \leq & \underbrace{\frac{\gamma_{2}}{\gamma_{1}}\cdot\sum_{j=1}^{k}\left|\frac{\beta_{j}}{\alpha_{0}}\right|\cdot L}_{=:\tilde{L}}\\ \left|\Omega_{l}\right|_{*} & \leq & \gamma_{2}\cdot\left|\Omega_{l}\right|_{\infty}\\ & = & \gamma_{2}\cdot\left|\tau_{l}-\frac{\delta_{l}}{h}\right|\\ & \leq & \gamma_{2}\cdot\underbrace{\max_{i=k,\ldots,l}\left|\tau_{i}-\frac{\delta_{i}}{h}\right|}_{=\omega_{l}}\\ \leadsto\,\left|\mathcal{E}_{l}\right|_{*} & \leq & \left|\mathcal{E}_{l-1}\right|_{*}+h\cdot\tilde{L}\left|\mathcal{E}_{l-1}\right|_{*}+h\cdot\gamma_{2}\omega_{l}\\ & = & \left(1-h\tilde{L}\right)\cdot\left|\mathcal{E}_{l-1}\right|+h\gamma_{2}\omega_{l}\\ & \leq & \left(1+h\tilde{L}\right)^{l-k+1}\cdot\left|\mathcal{E}_{k-1}\right|_{*}+\sum_{i=0}^{l-k}\left(1+h\tilde{L}\right)^{i}\cdot\gamma_{2}\omega_{l}\cdot h\\ & \leq & \left(1+h\tilde{L}\right)^{l-k+1}\cdot\left\{ \left|\mathcal{E}_{k-1}\right|_{*}+\frac{1}{\tilde{L}}\gamma_{2}\omega_{l}\right\} \\ & \leq & \left(1+h\tilde{L}\right)^{l}\cdot\left\{ \gamma_{2}\cdot\max_{i=1,\ldots,k-1}\left|\varepsilon_{i}\right|+\gamma_{2}\frac{1}{\tilde{L}}\omega_{l}\right\} \quad\left(\varepsilon_{0}=0\right)\\ & \leq & e^{\tilde{L}hl}\cdot\left\{ \gamma_{2}\cdot\max_{i=1,\ldots,k-1}\left|\varepsilon_{i}\right|+\gamma_{2}\frac{1}{\tilde{L}}\omega_{l}\right\} \\ \leadsto\,\left|\varepsilon_{l}\right| & \leq & \left|\mathcal{E}_{l}\right|_{\infty}\leq\frac{1}{\gamma_{1}}\left|\mathcal{E}_{l}\right|_{*}\\ & \leq & \frac{\gamma_{2}}{\gamma_{1}}e^{\tilde{L}hl}\cdot\left\{ \max_{i=1,\ldots,k-1}\left|\varepsilon_{i}\right|+\frac{1}{\tilde{L}}\omega_{l}\right\} \\ K & := & \frac{\gamma_{2}}{\gamma_{1}}\max\left(1,\frac{1}{\tilde{L}}\right)\end{eqnarray*} liefert dann die Behauptung $\left(2\right)$. \item Fall $\beta_{0}\neq0$: Rückführung auf Fall $\beta_{0}=0$: (\ref{6.7}) liefert\begin{eqnarray*} \underbrace{\left(I-h\frac{\beta_{0}}{\alpha_{0}}B_{l,0}\right)}_{H_{l}}\varepsilon_{l} & = & -\sum_{j=1}^{k}\frac{\alpha_{j}}{\alpha_{0}}\varepsilon_{l-j}+h\sum_{j=1}^{k}\frac{\beta_{j}}{\alpha_{0}}B_{l,j}\varepsilon_{l-j}+h\left(\tau_{l}-\frac{\delta_{l}}{h}\right),\quad l\geq k\end{eqnarray*} Dann ist\[ \left\Vert H_{l}-I\right\Vert =h\cdot\left|\frac{\beta_{0}}{\alpha_{0}}\right|\cdot\left\Vert B_{l,0}\right\Vert \leq h\cdot\left|\frac{\beta_{0}}{\alpha_{0}}\right|\cdot L\leq h_{*}\cdot\left|\frac{\beta_{0}}{\alpha_{0}}\right|\cdot L<1\] Nach dem Störungslemma (L. \ref{lem:St=F6rungslemma}) ist dann $H_{l}$ regulär und \begin{eqnarray*} \left\Vert H_{l}^{-1}\right\Vert & \leq & \frac{1}{1-h_{*}\left|\frac{\beta_{0}}{\alpha_{0}}\right|L}\\ H_{l}^{-1} & = & I+h\cdot\frac{\beta_{0}}{\alpha_{0}}H_{l}^{-1}B_{l,0}\end{eqnarray*} \end{enumerate} \begin{summary*} ~\begin{eqnarray*} \varepsilon_{l},\ldots,\varepsilon_{l-k} & & k\textrm{-Schritt-Rekursion der Dimension }m\\ & \Downarrow & \textrm{Aufblasen}\\ \mathcal{E}_{l},\mathcal{E}_{l-1} & & 1\textrm{-Schritt-Rekursion der Dimension }m\cdot k\\ & \Downarrow & \mathcal{A},\textrm{ Lemma }\ref{lem:6.3},\textrm{ Wurzelkriterium}\\ \textrm{Exponentialabschätzung}\\ & \Downarrow\\ \textrm{Rückrechnung}\end{eqnarray*} \end{summary*} \end{proof} \begin{thm} ~ \begin{enumerate} \item Alle Adams-Verfahren\index{Adams-Verfahren} sind stabil. \medskip{} \item Die BDF\index{BDF} ist für $k\leq6$ stabil. \end{enumerate} \end{thm} \begin{proof} ~ \begin{enumerate} \item $\alpha_{0}=1$, $\alpha_{1}=-1$, $\alpha_{i}=0$, $i=2,\ldots,k$ \medskip{} \noindent $\rho\left(\lambda\right)=\lambda^{k}-\lambda^{k-1}$, Nullstellen $\lambda_{1}=1$, $\lambda_{i}=0$, $i=2,\ldots,k$ \medskip{} \item $k=1$: $\lambda_{1}=1$ \medskip{} \noindent $k=2$: $\lambda_{1}=1$, $\lambda_{2}=\frac{1}{3}$ \end{enumerate} \end{proof} \begin{eqnarray*} \left|\varepsilon_{l}\right| & \leq & K\cdot\varepsilon^{\tilde{L}\cdot\left(t_{l}-t_{0}\right)}\cdot\max\left(1,\frac{1}{\tilde{L}}\right)\cdot\left\{ \max_{i=1,\ldots,k}\left|\varepsilon_{i}\right|+\max_{i=k,\ldots,l}\left|\tau_{i}+\frac{\delta_{i}}{h}\right|\right\} \end{eqnarray*} Überschlagsrechnung: Toleranz$=10^{-10}$. Sei $\varepsilon_{l}\approx\tau_{l}+\frac{\delta_{l}}{h}$, $\tau_{l}\approx h^{p}$, $\delta_{l}\approx10^{-15}$. $p=1$: wählen $h=10^{-10}$: $\varepsilon_{l}\approx10^{-10}+\frac{10^{-15}}{10^{-10}}\approx10^{-5}$ $p=2$: wählen $h=10^{-5}$: $\varepsilon_{l}\approx10^{-10}+\frac{10^{-15}}{10^{-5}}\approx10^{-10}$ \subsection{Reflexion des qualitativen asymptotischen Lösungsverhalten auf $\left[t_{0},\infty\right)$} ~ Wir betrachten nun die lineare DGL\begin{equation} \begin{array}{l} x'\left(t\right)=Bx\left(t\right),\quad t\in\left[0,\infty\right),\quad t_{0}=0,\, x\left(0\right)=x_{0}\smallskip\\ \delta_{1},\ldots,\delta_{m}\textrm{ seien die Eigenwerte von }B,\quad\textrm{Re}\delta_{i}<0,\quad i=1,\ldots,m\end{array}\label{6.10}\end{equation} Lösungen der AWA-en für $x_{0}\in\R^{m}$ sind \[ x\left(t\right)=e^{tB}\cdot x_{0}\xrightarrow{t\rightarrow\infty}0.\] $t_{i}:=t_{0}+ih$, $i\in\N$, $h>0$. $x\left(t_{l}\right)\xrightarrow{l\rightarrow\infty}0$ für $x_{0}\in\R^{m}$ und alle $h>0$. Numerisches Verfahren: $\left\{ x_{l}\right\} _{l\geq0}$. Frage: $x_{l}\stackrel{?}{\rightarrow}0$ für $l\rightarrow\infty$. \begin{example*} $m=1$, $x'\left(t\right)=-10^{3}\cdot x\left(t\right)$ $\leadsto$ $x\left(t_{l}\right)=e^{-1000h\cdot l}x_{0}$ \begin{enumerate} \item explizites Euler-Verfahren\index{Euler-Verfahren!explizit}:\[ x_{l}=x_{l-1}-h\cdot10^{3}x_{l-1}=\left(1-h\cdot10^{3}\right)x_{l-1}=\left(1-h\cdot10^{3}\right)^{l}x_{0}\] \medskip{} \noindent Bedingung für Nullfolge: $\left|1-h\cdot10^{3}\right|<1$ $\leadsto$ starke Einschränkung der Schrittweite \medskip{} \item implizites Euler-Verfahren\index{Euler-Verfahren!implizit}:\begin{eqnarray*} x_{l} & = & x_{l-1}-h\cdot10^{3}x_{l}\\ x_{l} & = & \frac{1}{1+h\cdot10^{3}}\cdot x_{l-1}=\left(\frac{1}{1+h\cdot10^{3}}\right)^{l}\cdot x_{0}\xrightarrow{l\rightarrow\infty}0\end{eqnarray*} für beliebige $h>0$, d.h. unabhängig von der Schrittweite konvergiert $x_{l}$. \end{enumerate} \end{example*} \subsubsection{Allgemeines lineares Einschrittverfahren $\left(k=1\right)$} ~ $\alpha_{0}=1$, $\alpha_{1}=-1$, $\beta_{0}+\beta_{1}=1$, $\beta_{0}\geq0$, angewandt auf (\ref{6.10})\begin{eqnarray} \frac{1}{h}\left(x_{l}-x_{l-1}\right) & = & \beta_{0}Bx_{l}+\beta_{1}Bx_{l-1}\label{6.11}\\ \left(I-\beta_{0}hB\right)x_{l} & = & \left(I+\beta_{1}hB\right)x_{l-1}\nonumber \end{eqnarray} $I-\beta_{0}hB$ ist regulär, da für die Eigenwerte $\textrm{Re}\left(1-\beta_{0}h\delta_{i}\right)>1$ gilt, also kein Eigenwert 0 ist.\begin{eqnarray*} x_{l} & = & \mathcal{A}\left(hB\right)\cdot x_{l-1}\textrm{ mit }\mathcal{A}\left(hB\right):=\left(I-\beta_{0}hB\right)^{-1}\left(I+\beta_{1}hB\right)\textrm{ }(\textrm{Übergangsfkt}.)\\ x_{l} & = & \left(\mathcal{A}\left(hB\right)\right)^{l}\cdot x_{0}\end{eqnarray*} $\left(\mathcal{A}\left(hB\right)\right)^{l}\xrightarrow{l\rightarrow\infty}0$ $\Leftrightarrow$ alle Eigenwerte von $\mathcal{A}\left(hB\right)$ liegen im Innern des komplexen Einheitskreises. Die Eigenwerte von $\mathcal{A}\left(hB\right)$ sind $\frac{1+\beta_{1}h\delta_{i}}{1-\beta_{0}h\delta_{i}}$, $i=1,\ldots,m$. Wir definieren:\[ \lambda\left(z\right):=\frac{1+\beta_{1}z}{1-\beta_{0}z},\quad z\in\C\] \begin{defn*} Die Menge\[ \boxed{G:=\left\{ z\in\C\left|\left|\lambda\left(z\right)\right|<1\right.\right\} }\] heißt \underbar{Stabilitätsbereich\index{Stabilitätsbereich}}\index{Einschrittverfahren!Stabilitätsbereich}% \marginpar{Stabilitäts\-bereich% } des Verfahrens. \end{defn*} \begin{thm} Bei Anwendung des Einschrittverfahrens mit $h>0$ auf die DGL (\ref{6.10}) werden für alle $x_{0}\in\R^{m}$ genau dann Nullfolgen $\left\{ x_{l}\right\} _{l\geq0}$ erzeugt, wenn \[ h\sigma_{i}\in G,\quad i=1,\ldots,m.\] \end{thm} \begin{defn*} Ein Verfahren heißt \underbar{A-stabil}\index{A-stabil}\index{stabil!A-}\index{Mehrschrittverfahren!A-stabil}% \marginpar{A-stabil% } (absolut stabil), falls \[ \boxed{\C^{-}:=\left\{ z\in\C\left|\textrm{Re}\left(z\right)<0\right.\right\} \subseteq G}\] \newpage \end{defn*} \begin{example*} ~% \begin{figure}[htbp] \begin{center}\includegraphics[% width=0.80\paperwidth]{10.eps}\end{center} \caption{Stabilitätsbereiche für verschiedene lineare Einschrittverfahren} \end{figure} \begin{itemize} \item expliziter Euler\index{Euler-Verfahren!explizit}: $\lambda\left(z\right)=1+z$ \medskip{} \item impliziter Euler\index{Euler-Verfahren!implizit}: $\lambda\left(z\right)=\frac{1}{1-z}$ \medskip{} \item Trapezregel\index{Trapezregel}: $\lambda\left(z\right)=\frac{1+\frac{1}{2}z}{1-\frac{1}{2}z}$, $G=\C^{-1}$ \end{itemize} \end{example*} \subsubsection{Allgemeines lineares $k$-Schrittverfahren} ~ Das betrachtete $k$-Schrittverfahren sei stabil und konsistent, $\alpha_{0}\neq0$, $\beta_{0}\geq0$. Angewandt auf (\ref{6.10}) ergibt dies: \begin{eqnarray*} \frac{1}{h}\sum_{j=0}^{k}\alpha_{j}x_{l-j} & = & \sum_{j=0}^{k}\beta_{j}Bx_{l-j}\\ \sum_{j=0}^{k}\left(\alpha_{j}I-\beta_{j}\underbrace{hB}_{z}\right)x_{l-j} & = & 0\end{eqnarray*} Konstruiere begleitendes Polynom \[ \boxed{p\left(\lambda,z\right):=\sum_{j=0}^{k}\left(\alpha_{j}-\beta_{j}z\right)\lambda^{k-j},\quad z\in\C,\,\lambda\in\C}\] \begin{defn*} Seien $\lambda_{1}\left(z\right),\ldots,\lambda_{k}\left(z\right)$ die Nullstellen des Polynoms $p\left(\cdot,z\right)$. Dann heißt% \marginpar{Stabilitäts\-bereich% } \[ \boxed{G:=\left\{ z\in\C\left|\left|\lambda_{i}\left(z\right)\right|<1,\quad i=1,\ldots,k\right.\right\} }\] \underbar{Stabilitätsbereich}\index{Stabilitätsbereich}\index{Mehrschrittverfahren!Stabilitätsbereich}. \begin{example*} $k=1$, $\alpha_{0}=1$, $\alpha_{1}=-1$: \begin{eqnarray*} p\left(\lambda,z\right) & = & \left(1-\beta_{0}z\right)\lambda+\left(-1-\beta_{1}z\right)\\ \lambda_{1}\left(z\right) & = & \frac{1+\beta_{1}z}{1-\beta_{0}z}\end{eqnarray*} \end{example*} \end{defn*} Für ein lineares $k$-Schrittverfahren ist\[ \underbrace{\left(\begin{array}{c} x_{l}\\ \vdots\\ x_{l-k+1}\end{array}\right)}_{X_{l}}=\mathbb{A}(hB)\underbrace{\left(\begin{array}{c} x_{l-1}\\ \vdots\\ x_{l-k}\end{array}\right)}_{X_{l-1}}\] mit \[ \mathbb{A}(hb)=\left(\begin{array}{cccc} -\left(\alpha_{0}I-\beta_{0}hB\right)^{-1}\left(\alpha_{1}I-\beta_{1}hB\right) & \ldots & \ldots & -\left(\alpha_{0}I-\beta_{0}hB\right)^{-1}\left(\alpha_{k}I-\beta_{k}hB\right)\\ I & 0\\ & \ddots & \ddots\\ 0 & & I & 0\end{array}\right)\] und $\mathbb{A}(hb)\in L\left(\R^{mk}\right)$ (Block-Frobenius) hat die Eigenwerte $\lambda_{i}\left(h\delta_{j}\right)$, $j=1,\ldots,m$, $i=1,\ldots,k$. \begin{thm} Es gilt: \begin{enumerate} \item Durch ein k-Schrittverfahren ($\alpha_{0}>0$, $\beta_{0}\geq0$) werden bei Anwendung mit der Schrittweite $h>0$ auf eine stabile Differentialgleichung (\ref{6.10}) Nullfolgen erzeugt, falls\[ h\delta_{i}\in G,\quad i=1,\ldots,m\] \item Ist das Verfahren A-stabil, so werden bei Anwendung auf (\ref{6.10}) Nullfolgen unabhängig von der Größe der Schrittweite $h$ erzeugt. \end{enumerate} \end{thm} Beispiel für A-stabile Verfahren sind die Trapezregel, das implizite Euler-Verfahren (BDF mit $k=1$), BDF mit $k=2$. Die BDF für $k=3,4,5,6$ sind ,,fast'' A-stabil. \begin{thm} Kein explizites lineares stabiles und konsistentes Mehrschrittverfahren ist A-stabil\index{stabil!A-}\index{A-stabil}\index{Mehrschrittverfahren!A-stabil}. \end{thm} \begin{proof} Angenommen, ein explizites Verfahren $\left(\beta_{0}=0\right)$ sei A-stabil, das heißt, $\C^{-}\subset G$. Das heißt, für $z\in\C^{-}$ gilt für die Nullstellen des begleitenden Polynoms:\[ \left|\lambda_{i}(z)\right|<1,\quad i=1,\ldots,k\] Als Konsistenzbedingungen haben wir:\begin{eqnarray*} \sum_{j=0}^{k}\alpha_{j} & = & 0\\ \sum_{j=0}^{k}\left(\alpha_{j}j+\beta_{j}\right) & = & 0\end{eqnarray*} und desweiteren gilt das Dahlquistsche Wurzelkriterium. Wir erhalten als begleitendes Polynom:\[ p\left(\lambda,z\right)=\alpha_{0}\left(\lambda^{k}+\left(\frac{\alpha_{1}}{\alpha_{0}}-\frac{\beta_{1}}{\alpha_{0}}z\right)\lambda^{k-1}+\ldots+\left(\frac{\alpha_{k}}{\alpha_{0}}-\frac{\beta_{k}}{\alpha_{0}}z\right)\lambda^{0}\right)\] Nach dem Satz von Vieta gilt für alle $z\in\C^{-}$:\[ \left|\frac{\alpha_{k}}{\alpha_{0}}-\frac{\beta_{k}}{\alpha_{0}}z\right|\leq\left|\lambda_{1}(z)\right|\cdots\left|\lambda_{k}(z)\right|\leq1\] und hieraus folgt sofort $\beta_{k}=0$, da kein Polynom ersten Grades beschränkt sein kann. Wenden wir den gleichen Satz auf die anderen Koeffizienten an, so erhalten wir auch\[ \left|\frac{\alpha_{k-1}}{\alpha_{0}}-\frac{\beta_{k-1}}{\alpha_{0}}z\right|\leq c\] etc und es gilt $\beta_{1}=\ldots=\beta_{k-1}=0$. Aus der Konsistenzbedingung folgt $\rho\left(1\right)=\sum\alpha_{j}=0$ und $\sum\alpha_{j}j=0$. Daraus folgt $\rho'\left(1\right)=0$, d.h. $1$ ist mehrfache Nullstelle des charakteristischen Polynoms. Dies ist ein Widerspruch zur Stabilität (Dahlquistsches Wurzelkriterium). \contra \end{proof} Bezeichnung: \underbar{Steife Differentialgleichungen\index{steife Differentialgleichungen}} sind Differentialgleichungen mit verschieden schnell abklingenden (d.h. für $t\rightarrow\infty$ gegen $0$ konvergierende) Komponenten. (,,mit verschiedenen Zeitkonstanten''). \begin{example*} Sei $m=2$, $x'(t)=\left(\begin{array}{cc} \sigma_{1} & 0\\ 0 & \sigma_{2}\end{array}\right)x(t)$ wobei $\sigma_{1},\sigma_{2}$ die Eigenwerte seien. Dann gilt:\[ e^{hB}=\left(\begin{array}{cc} e^{h\sigma_{1}} & 0\\ 0 & e^{h\sigma_{2}}\end{array}\right)\] Wir betrachten ein Einschrittverfahren: $k=1$, $\alpha_{0}=1$ , $\alpha_{1}=-1$:\[ \mathbb{A}(hB)=\left(I-\beta_{0}hB\right)^{-1}\left(I+\beta_{1}hB\right)=\left(\begin{array}{cc} \lambda_{1}\left(h\sigma_{1}\right) & 0\\ 0 & \lambda_{1}\left(h\sigma_{2}\right)\end{array}\right)\] Sei $h$ moderat, $h\approx0,1$ und $\sigma_{1}\approx-0,1$. Dann ist $\lambda_{1}\left(h\sigma_{1}\right)$ für alle Verfahren eine ,,gute'' Approximation für $e^{h\sigma_{1}}$. Sei $\sigma_{2}=-10^{6}$: \begin{itemize} \item Trapezregel\index{Trapezregel} $\left(\beta_{0}=\beta_{1}=\frac{1}{2}\right)$: \[ \lambda_{1}\left(h\sigma_{2}\right)=\frac{1-\frac{1}{2}10^{6}\cdot0.1}{1+\frac{1}{2}10^{6}\cdot0.1}\approx-1\] \medskip{} \item implizites Euler-Verfahren\index{Euler-Verfahren!implizit} $\left(\beta_{0}=1,\beta_{1}=0\right)$:\[ \lambda_{1}\left(h\sigma_{2}\right)=\frac{1}{1+10^{6}\cdot0.1}\approx10^{-5}\] \end{itemize} \end{example*} \begin{defn*} Ein lineares Mehrschrittverfahren heißt \underbar{L-stabil}\index{L-stabil}\index{stabil!L-}\index{Mehrschrittverfahren!L-stabil}, falls es A-stabil ist und zusätzlich \[ \lim_{\textrm{Re}(z)\rightarrow-\infty}\max_{i=1,\ldots,k}\left|\lambda_{i}(z)\right|=0.\] \end{defn*} Das implizite Eulerverfahren ($\lambda_{1}(z)=\frac{1}{1-z}$) ist L-stabil. Alle BDF\index{BDF} sind ,,fast'' L-stabil. \subsection{Zur praktischen Realisierung} \begin{enumerate} \item Wie kann man $x_{l}$ beim impliziten Verfahren berechnen, wenn $\tilde{x}_{l-k},\ldots,\tilde{x}_{l-1}$ bereits (als Näherung) berechnet sind? Als Gleichung für $x_{l}$ haben wir bereits:\[ \gamma_{l}:=x_{l}-h\frac{\beta_{0}}{\alpha_{0}}f\left(x_{l},t_{l}\right)=\sum_{j=1}^{k}\left(-\frac{\alpha_{j}}{\alpha_{0}}\tilde{x}_{l-j}+\frac{\beta_{j}}{\alpha_{0}}hf\left(\tilde{x}_{l-j},t_{l-j}\right)\right)\] Möglichkeiten: \begin{itemize} \medskip{} \item Newton-Verfahren mit Startwert $x_{l,[0]}:=\tilde{x}_{l-1}$ oder aus explizitem Verfahren \medskip{} \item Fixpunkt-Iteration\index{Fixpunkt-Iteration}:\begin{eqnarray*} \mathbb{B}_{l}(x) & := & h\frac{\beta_{0}}{\alpha_{0}}f\left(x,t_{l}\right)+\gamma_{l},\\ x_{l,\left[i+1\right]} & := & \mathbb{B}_{l}\left(x_{l,[i]}\right),\quad i\geq0.\end{eqnarray*} \[ \left|\mathbb{B}_{l}(x)-\mathbb{B}_{l}(\bar{x})\right|\leq h\left|\frac{\beta_{0}}{\alpha_{0}}\right|L\left|x-\bar{x}\right|,\quad x,\bar{x}\in\R^{m}\] Wegen (\ref{6.10}) erhalten wir \[ h\left|\frac{\beta_{0}}{\alpha_{0}}\right|\left\Vert B\right\Vert <1\] als Konvergenzbedingung für die Iteration. Für $\alpha_{0}=\beta_{0}=0$ muß damit $h\left|\sigma_{i}\right|\leq h||B||<1$ gelten. \medskip{} Die Fixpunkt-Iteration, obwohl sie weniger Rechnungen benötigt, ist in der Praxis nicht ernsthaft anwendbar, da wieder eine Schrittweitenbeschränkung existiert. \end{itemize} \item Schrittweitenänderung\index{Schrittweitenänderung} \medskip{} \noindent Neue Schrittweiten $h_{j}$, $t_{l-j}=t_{l}-jh_{j}$, führen zu neuen Stützstellen $\bar{t}_{l+1-j}:=t_{l+1}-jh_{l+1}$. \medskip{} \noindent Die $\bar{x}_{l+1-j}$ können durch Interpolation bereitgestellt werden. \medskip{} \noindent Eine andere Möglichkeit besteht darin, Formeln für variable Schrittweiten (Adams, BDF) zu benutzen. \medskip{} \item Fehlerabschätzung\index{Fehlerabschätzung}, Fehlerkontrolle \medskip{} \noindent Der exakte Fehler $x\left(t_{l}\right)-\tilde{x}_{l}$ ist nicht verfügbar. Man muß sich also mit einer Abschätzung $\hat{x}_{l}-\tilde{x}_{l}$ begnügen, welche mit einer zweiten Näherung $\hat{x}_{l}$ ($\hat{p}\geq p$, bzw. $\hat{x}$ ist ,,genauer'') bestimmt wird. Dabei soll $\hat{x}_{l}$ mit wenig Aufwand berechnet sein und eine genauere Abschätzung als $\tilde{x}_{l}$ sein (z.B. indem es mit einem Verfahren höherer Konsistenzordnung als $\tilde{x}_{l}$ berechnet wurde). \medskip{} \noindent Gilt $\left|\hat{x}_{l}-\tilde{x}_{l}\right|\leq TOL$, so wird $\tilde{x}_{l}$ als Näherung akzeptiert. Falls nicht, so wiederholen wir den letzten Schritt mit kleinerer Schrittweite. \medskip{} \item Schrittweitensteuerung\index{Schrittweitensteuerung} (Ordnungssteuerung) \medskip{} \noindent Um mit der größtmöglichen Schrittweite für eine Toleranz zu arbeiten, benutzt man Prognosen für die Schrittweite $h_{l+1}$:\[ \tau_{l}=\underbrace{c_{p}x^{\left(p+1\right)}\left(t_{l}\right)h_{l}^{p}}_{=:T_{l}}+o\left(h_{l}^{p+1}\right),\quad\tau_{l+1}=\underbrace{c_{p}x^{\left(p+1\right)}\left(t_{l+1}\right)h_{l+1}^{p}}_{=T_{l+1}}+o\left(h_{l}^{p+1}\right)\] (wir bezeichnen $T_{l}$ als den Hauptteil des Fehlers). \medskip{} \noindent Annahme: $x^{\left(p+1\right)}\left(t_{l}\right)=x^{\left(p+1\right)}\left(t_{l+1}\right)$\begin{eqnarray*} \leadsto\,\frac{T_{l}}{h_{l}^{p}} & = & \frac{T_{l+1}}{h_{l+1}^{p}}\\ \leadsto\, h_{l+1} & = & h_{l}\cdot\sqrt[p]{\left|\frac{T_{l+1}}{T_{l}}\right|}\end{eqnarray*} \medskip{} \noindent Als Ansatz setzen wir $\left|T_{l+1}\right|=\textrm{TOL}$ und berechnen eine Approximation $\tilde{T}_{l}$ von $T_{l}$:\[ \boxed{h_{l+1}:=h_{l}\cdot\sqrt[p]{\frac{\textrm{TOL}}{\left|\tilde{T}_{l}\right|}}}\] \end{enumerate} Literatur: \cite[7. Kapitel]{StoerBulischNumerik2} \newpage \section{Eigenwertaufgaben\index{Eigenwertaufgaben}} Sei $A$ eine $m\times m$-Matrix. Gesucht sind die Eigenwerte $\lambda$ von A: $Az=\lambda z,\, z\neq0$ Eine Möglichkeit, die Eigenwerte zu berechnen ist, $p\left(\lambda\right)$, das charakteristisches Polynom\index{Polynom!charakteristisch}\index{charakteristisches Polynom}, zu benutzen mit $p\left(\lambda\right)=\det\left(A-\lambda I\right)$. \begin{example*} $A=\left(\begin{array}{cccc} 5 & 7 & 6 & 5\\ 7 & 10 & 8 & 7\\ 6 & 8 & 10 & 9\\ 5 & 7 & 9 & 10\end{array}\right),\,\Delta A=\left(\begin{array}{cccc} 0,1\\ \\ & & 0\\ \end{array}\right)$\begin{eqnarray*} p_{A}\left(\lambda\right) & = & \lambda^{4}-35\lambda^{3}+146\lambda^{2}-100\lambda+1\\ p_{A+\Delta A}\left(\lambda\right) & = & \lambda^{4}-35,1\lambda^{3}+149\lambda^{2}-110,6\lambda+7,8\end{eqnarray*} Durch kleinere Störungen der Matrix $A$ verändert sich das charakteristische Polynom nicht unwesentlich. Dieses Verfahren hätte also eine schlechte Kondition. Die mit diesem Verfahren berechneten Eigenwerte für normale Matrizen weichen aber nur ungefähr mit der Störung ab: \begin{center}\begin{tabular}{|c|c|} \hline Eigenwerte von $A$& Eigenwerte von $A+\Delta A$\tabularnewline \hline \hline $0,010$& $0,079$\tabularnewline \hline $0,843$& $0,844$\tabularnewline \hline $3,858$& $3,874$\tabularnewline \hline $30,289$& $30,303$\tabularnewline \hline \end{tabular}\end{center} Für normale Matrizen $\left(A^{T}A=AA^{T}\right)$ liegen die Fehler in den Eigenwerten in der Größenordnung der Fehler der gestörten Matrix. \end{example*} \subsection{Einfache und inverse Vektoriteration zur Bestimmung spezieller Eigenwerte} \subsubsection{Einfache Vektoriteration (von Mises-Iteration)} ~\index{Vektoriteration}\index{von Mises-Iteration} Sei $A$ eine $m\times m$-Matrix und diagonalisierbar, $\lambda_{1},\ldots,\lambda_{m}$ Eigenwerte, $\left|\lambda_{1}\right|\geq\left|\lambda_{2}\right|\geq\ldots\geq\left|\lambda_{m}\right|$, $z_{1},\ldots,z_{m}$ Eigenvektor-Basis in $\C^{m}$.% \marginpar{Vektor\-iteration% }\[ \boxed{x^{\left(0\right)}\in\C^{m},\qquad x^{\left(k\right)}:=Ax^{\left(k-1\right)}=A^{k}x^{\left(0\right)},\quad k\geq1}\] \begin{eqnarray*} x^{\left(0\right)} & = & \alpha_{1}z_{1}+\ldots+\alpha_{m}z_{m}\\ \leadsto\, x^{\left(k\right)} & = & \alpha_{1}\lambda_{1}^{k}z_{1}+\alpha_{2}\lambda_{2}^{k}z_{2}+\ldots+\alpha_{m}\lambda_{m}^{k}z_{m}\\ & = & \lambda_{1}^{k}\left\{ \alpha_{1}z_{1}+\alpha_{2}\left(\frac{\lambda_{2}}{\lambda_{1}}\right)^{k}z_{2}+\ldots+\alpha_{m}\left(\frac{\lambda_{m}}{\lambda_{1}}\right)^{k}z_{m}\right\} \\ \frac{1}{\lambda_{1}^{k}}x^{\left(k\right)} & \xrightarrow{k\rightarrow\infty} & \alpha_{1}z_{1},\textrm{ wenn }\left|\lambda_{1}\right|>\left|\lambda_{2}\right|\end{eqnarray*} Falls $\left|\lambda_{1}\right|=\left|\lambda_{2}\right|=\ldots=\left|\lambda_{s}\right|>\left|\lambda_{s+1}\right|$ und $\lambda_{1}=\lambda_{2}=\ldots=\lambda_{s}$, so folgt \[ \frac{1}{\lambda_{1}^{k}}x^{\left(k\right)}\xrightarrow{k\rightarrow\infty}\alpha_{1}z_{1}+\ldots+\alpha_{s}z_{s},\] wenn $\left(\alpha_{1}z_{1}+\ldots+\alpha_{s}z_{s}\right)_{i}\neq0$, so gilt \begin{eqnarray*} \frac{\frac{1}{\lambda_{1}^{k}}x_{i}^{\left(k\right)}}{\frac{1}{\lambda_{1}^{k-1}}x_{i}^{\left(k-1\right)}} & \xrightarrow{k\rightarrow\infty} & 1\qquad\leadsto\qquad\boxed{\frac{x_{i}^{\left(k\right)}}{x_{i}^{\left(k-1\right)}}\xrightarrow{k\rightarrow\infty}\lambda_{1}}\end{eqnarray*} Dieses Verfahren bezeichnen wir als \underbar{Vektoriteration} zur Bestimmung des betragsgrößten Eigenwertes einer Matrix. Es wird auch als \underbar{von Mises Verfahren} bezeichnet. \subsubsection{Inverse Vektoriteration (nach Wielandt)} ~\index{Wielandt}\index{Vektoriteration!invers} Sei $A$ mit Eigenwerten $\lambda_{1},\ldots,\lambda_{m}$ gegeben. Wir wählen \[ \mu\not\in\left\{ \left.\lambda\in\C\right|\det\left(A-\lambda I\right)=0\right\} .\] Die Matrix $\left(A-\mu I\right)$ ist regulär. Es gelte: \[ \left|\lambda_{j_{*}}-\mu\right|<\left|\lambda_{i}-\mu\right|\quad\textrm{für }\lambda_{i}\neq\lambda_{j_{*}}\] (also sind auch mehrfache Eigenwerte erlaubt). D.h., $\mu$ liegt zu einem Eigenwert näher als zu allen anderen. $\left(A-\mu I\right)^{-1}$ hat die Eigenwerte $\frac{1}{\lambda_{i}-\mu}$, $i=1,\ldots,m$, und es folgt\[ \left|\frac{1}{\lambda_{j_{*}}-\mu}\right|>\left|\frac{1}{\lambda_{i}-\mu}\right|\quad\textrm{für }\lambda_{i}\neq\lambda_{j_{*}}\] Die von Mises-Iteration für $\left(A-\mu I\right)^{-1}$ liefert für $k\geq1$:% \marginpar{inverse Vektor\-iteration% } \[ x^{\left(k\right)}=\left(A-\mu I\right)^{-1}x^{\left(k-1\right)}\] Dies führt zu\[ \boxed{x^{\left(0\right)}\in\C^{m},\qquad\left(A-\mu I\right)x^{\left(k\right)}=x^{\left(k-1\right)},\quad k\geq1}\] und damit\[ \boxed{\frac{x_{i}^{\left(k\right)}}{x_{i}^{\left(k-1\right)}}\xrightarrow{k\rightarrow\infty}\frac{1}{\left|\lambda_{j_{*}}-\mu\right|}}\] \subsection{QR-Verfahren zur Bestimmung aller Eigenwerte einer reellen Matrix} ~ Sei $A\in L\left(\R^{m}\right)$, $A=\left(a_{i,j}\right)$. Vorbemerkung: Zu $G\in L\left(\R^{m}\right)$ gibt es ein $Q\in L\left(\R^{m}\right)$, $Q^{T}=Q^{-1}$, und eine obere Dreiecksmatrix $R\in L\left(\R^{m}\right)$ mit $G=QR$. Mit der Vorgabe $r_{i,i}\geq0$, $i=1,\ldots,m$, ist die Faktorisierung eindeutig. Vereinbarung: Wir setzen $r_{i,i}\geq0$, $i=1,\ldots,m$. QR-Verfahren\index{QR-Verfahren für Eigenwerte}% \marginpar{QR-Verfahren% }:\[ \boxed{A_{0}:=A,\qquad A_{k}=Q_{k}R_{k},\quad A_{k+1}:=R_{k}Q_{k},\quad k\geq0}\] \[ A_{k+1}=Q_{k}^{-1}A_{k}Q_{k}=Q_{k}^{-1}\cdots Q_{0}^{-1}A_{0}Q_{0}\cdots Q_{k}=\left(Q_{0}\cdots Q_{k}\right)^{-1}A\left(Q_{0}\cdots Q_{k}\right),\] also ist $A_{k}$ ähnlich zu $A$ für alle $k\geq0$. \begin{thm} (Satz von Schur)\index{Schur, Satz}: Zu $A\in L\left(\R^{m}\right)$ existiert eine orthogonale Matrix $U\in L\left(\R^{m}\right)$ mit\[ U^{-1}AU=\left[\begin{array}{ccc} R_{1,1} & \cdots & R_{1,s}\\ & \ddots & \vdots\\ 0 & & R_{s,s}\end{array}\right]\] mit Blöcken $R_{i,i}$, die entweder die Größe $1\times1$ haben, oder die Größe $2\times2$. Die $2\times2$ Blöcke haben konjugiert komplexe Eigenwerte. \end{thm} \begin{proof} \cite[S. 275-276]{SchwarzNumerik} \end{proof} $A$ hat \underbar{Hessenberg-Form}\index{Hessenberg-Form}, falls $a_{i,j}=0$ für $i\geq j+2$. Vorteil der Hessenberg-Form: Falls eines der Subdiagonalelemente verschwindet, zerfällt das Eigenwertproblem in solche mit kleinerer Dimension: \begin{eqnarray*} A=\underbrace{\left(\begin{array}{cccc} * & \cdots & \cdots & *\\ * & \ddots & * & \vdots\\ & 0 & \ddots & \vdots\\ 0 & & * & *\end{array}\right)}_{m} & = & \left(\underbrace{\begin{array}{c} A_{1,1}\\ 0\end{array}}_{m_{1}}\underbrace{\begin{array}{c} A_{1,2}\\ A_{2,2}\end{array}}_{m_{2}}\right),\quad A_{1,1},A_{1,2}\textrm{ haben Hessenberg-Form}\\ \det\left(A-\lambda I_{m}\right) & = & \det\left(A_{1,1}-\lambda I_{m_{1}}\right)\cdot\det\left(A_{2,2}-\lambda I_{m_{2}}\right)\end{eqnarray*} Transformation einer Matrix $A$ in Hessenberg-Form: \[ A=\left[\begin{array}{ccc} a_{1,1}\\ a_{2,1} & \cdots\\ \vdots\\ a_{m,1}\end{array}\right]\] Sei $\tilde{Q}_{1}\in L\left(\R^{m-1}\right)$ mit\begin{eqnarray*} \tilde{Q}_{1}\left[\begin{array}{c} a_{2,1}\\ \vdots\\ a_{m,1}\end{array}\right] & = & \left[\begin{array}{c} \gamma_{1}\\ 0\\ \vdots\\ 0\end{array}\right]\\ \bar{Q}_{1} & := & \left[\begin{array}{cc} 1\\ & \tilde{Q}_{1}\end{array}\right]\\ A^{\left(1\right)}:=\bar{Q}_{1}A\bar{Q}_{1}^{T} & = & \left[\begin{array}{ccc} a_{1,1}\\ \gamma_{1} & a_{2,2}^{\left(1\right)} & \cdots\\ 0 & a_{3,2}^{\left(1\right)}\\ \vdots & \vdots\\ 0 & a_{m,2}^{\left(1\right)}\end{array}\right]\end{eqnarray*} Sei $\tilde{Q}_{2}\in L\left(\R^{m-2}\right)$ mit\begin{eqnarray*} \tilde{Q}_{2}\left[\begin{array}{c} a_{3,2}^{\left(1\right)}\\ \vdots\\ a_{m,2}^{\left(1\right)}\end{array}\right] & = & \left[\begin{array}{c} \gamma_{2}\\ 0\\ \vdots\\ 0\end{array}\right]\\ \bar{Q}_{2} & := & \left[\begin{array}{ccc} 1\\ & 1\\ & & \tilde{Q}_{2}\end{array}\right]\\ A^{\left(2\right)}:=\bar{Q}_{2}A^{\left(1\right)}\bar{Q}_{2}^{T} & = & \left[\begin{array}{ccc} a_{1,1}\\ \gamma_{1} & a_{2,2}^{\left(1\right)} & \cdots\\ 0 & \gamma_{2}\\ \vdots & 0\\ \vdots & \vdots\\ 0 & 0\end{array}\right]\end{eqnarray*} usw. $A^{\left(m-2\right)}$ hat Hessenberg-Form. \begin{lem*} Die Hessenberg-Form bleibt unter QR-Transformationen erhalten. Ist $A^{T}=A$, so ist auch $A^{\left(k\right)^{T}}=A^{\left(k\right)}.$ \end{lem*} \begin{thm} Sei $A\in L\left(\R^{m}\right)$ diagonalisierbar, $A=TDT^{-1}$, $D=\mathrm{diag}\left(\lambda_{1},\ldots,\lambda_{m}\right)$, $\left|\lambda_{1}\right|>\left|\lambda_{2}\right|>\ldots>\left|\lambda_{m}\right|>0$. $T^{-1}$ besitze eine LR-Zerlegung. Für den QR-Algorithmus gilt: \[ \boxed{Q_{k}\xrightarrow{k\rightarrow\infty}\mathrm{diag}\left(\frac{\lambda_{1}}{\left|\lambda_{1}\right|},\ldots,\frac{\lambda_{m}}{\left|\lambda_{m}\right|}\right)}\] und \[ \boxed{a_{k,i,i}\xrightarrow{k\rightarrow\infty}\lambda_{i},\quad i=1,\ldots,m}\] \end{thm} \[ \left[\begin{array}{cccc} \ddots & * & \cdots & *\\ \ddots & a_{k,m-2,m-2} & * & *\\ 0 & a_{k,m-1,m-2} & a_{k,m-1,m-1} & *\\ & 0 & a_{k,m,m-1} & a_{k,m,m}\end{array}\right]\] Wenn $a_{k,m,m-1}\approx0$, so ist $a_{k,m,m}\approx\lambda_{m}$ $\leadsto$ Abspaltung Wenn vorher $a_{k,m-1,m-2}\approx0$, so werden die Eigenwerte des Blockes $\left[\begin{array}{cc} a_{k,m-1,m-1} & *\\ a_{k,m,m-1} & a_{k,m,m}\end{array}\right]$ als Näherung für $\lambda_{m-1},\lambda_{m}$ berechnet, danach Abspaltung. \begin{rem*} QR-Algorithmus mit Spektralverschiebung (Shift)\index{QR-Verfahren für Eigenwerte!mit Shift}\begin{eqnarray*} A_{0} & := & A\\ k\geq0:\quad A_{k}-\mu_{k}I & = & Q_{k}R_{k}\\ A_{k+1} & := & \mu_{k}I+R_{k}Q_{k},\end{eqnarray*} z.B. $\mu_{k}=a_{k,m,m}$ \end{rem*} \begin{lem} $A=A^{T}$ habe Hessenberg-Form, $A$ sei nicht zerfallend ($a_{i+1,i}\neq0$, $i=1,\ldots,m$). Dann hat $A$ nur einfache Eigenwerte. \end{lem} \begin{proof} ~\[ A-\lambda I=\left[\underbrace{\begin{array}{ccc} a_{11}-\lambda & *\\ a_{21} & \ddots & \ddots\\ & \ddots & \ddots\\ & & a_{m,m-1}\end{array}}_{m-1\textrm{ lin}.\textrm{ unabh}.\textrm{ Spalten}}\begin{array}{c} \\\\*\\ a_{mm}-\lambda\end{array}\right],\] d.h. Rang$\left(A-\lambda I\right)\geq m-1$ für alle $\lambda$. Falls $\lambda$ Eigenwert zu $A$ ist, so ist Rang$\left(A-\lambda I\right)=m-1$ und $\dim\left(\ker\left(A-\lambda I\right)\right)=1$. Wegen $A^{T}=A$ ist $\lambda$ einfacher Eigenwert. \end{proof} \subsection{Abschätzung von Eigenwerten} ~ Sei $A=\left(a_{i,j}\right)\in\R^{n\times n}$.\[ Ax=\lambda x\,\Leftrightarrow\,\left(\lambda-a_{ii}\right)x_{i}=\sum_{j=1,j\neq i}^{n}a_{i,j}x_{j},\quad1\leq i\leq n\] Sei $k\in\left\{ 1,\ldots,n\right\} $ mit $\left|x_{k}\right|=\left|x\right|_{\infty}$. Dann ist\[ \boxed{\left|\lambda-a_{kk}\right|\leq\sum_{j=1,j\neq k}^{n}\left|a_{k,j}\right|}\] \subsubsection{Satz von Gerschgorin (1931)} ~ Gerschgorin-Kreise\index{Gerschgorin-Kreise}% \marginpar{Gersch\-gorin-Kreise% } \[ \boxed{K_{k}:=\left\{ z\in\C\left|\left|z-a_{kk}\right|\leq r_{k}\right.\right\} \textrm{ mit Radius }r_{k}=\sum_{j=1,j\neq k}^{n}\left|a_{k,j}\right|,\quad k=1,\ldots,n}\] Dann gilt \[ \boxed{\sigma\left(A\right)\subseteq\bigcup_{k=1}^{n}K_{k}}\] \begin{example*} Sei\[ A=\left(\begin{array}{ccc} -1 & 0.5 & 0.5\\ 0.5 & 1 & 0.5\\ 0.5 & 0.5 & 2\end{array}\right)\] % \begin{figure}[htbp] \begin{center}\includegraphics[% width=0.50\paperwidth, keepaspectratio]{11.eps}\end{center} \caption{Gerschorgin-Kreise von $A$} \end{figure} Eigenwerte: $2.33685,$ $-1.16402$, $0.827167$ \end{example*} \newpage \section{Iterations-Verfahren zur Lösung großer linearer Gleichungssysteme} Gesucht ist eine Lösung des linearen Gleichungssystems\[ \boxed{Ax=b}\] mit regulärer Matrix $A\in L\left(\R^{m}\right)$. \begin{itemize} \item $A$ hat spezielle Struktur, bedingt durch seine Herkunft. \item Man ist nur an bestimmter Lösungsgenauigkeit interessiert. \end{itemize} \begin{example*} Für gegebenes $f\in C^{1}$ ist eine eine Funktion $u$ mit\[ -\Delta u=f\left(x,y\right)\qquad\left(x,y\right)\in\Omega=\left(0,1\right)\times\left(0,1\right)\] gesucht. $\Delta$ ist der Laplace-Operator: $\Delta u=\frac{\partial^{2}u}{\partial x_{1}^{2}}+\ldots+\frac{\partial^{2}u}{\partial x_{n}^{2}}$. Also\[ -u_{xx}\left(x,y\right)-u_{yy}\left(x,y\right)=f\left(x,y\right)\] Zudem soll gelten:\[ \left.u\left(x,y\right)\right|_{\partial\Omega}=0\] Wir wählen ein Gitter \[ x_{i}=i\cdot h,\quad y_{j}=j\cdot h,\qquad i,j=0,1,\ldots,m+1,\quad\left(m+1\right)\cdot h=1\] $u_{i,j}$ soll $u\left(x_{i},y_{j}\right)$ approximieren\begin{eqnarray*} u_{xx}\left(x,y\right) & \approx & \frac{1}{h^{2}}\left(u\left(x+h,y\right)-2u\left(x,y\right)+u\left(x-h,y\right)\right)\\ u_{yy}\left(x,y\right) & \approx & \frac{1}{h^{2}}\left(u\left(x,y+h\right)-2u\left(x,y\right)+u\left(x,y-h\right)\right)\end{eqnarray*} Ersetze die Differentialgleichung in jedem ,,inneren'' Gitterpunkt $\left(x_{i},y_{j}\right)$ durch die Differenzengleichung $f_{i,j}:$\[ -\frac{1}{h^{2}}\left(u_{i+1,j}-2u_{i,j}+u_{i-1,j}\right)-\frac{1}{h^{2}}\left(u_{i,j+1}-2u_{i,j}+u_{i,j-1}\right)=f_{i,j},\quad i,j=1,\ldots,m\] ist Bestimmungsgleichung für $m^{2}$ Unbekannte $u_{1,1},u_{2,1},\ldots,u_{m,1},\ldots,u_{m,m}$. Rand: $u_{0,j}=0$, $u_{m+1,j}=0$, $u_{i,0}=0$, $u_{i,m+1}=0$ Man kann zeigen, daß $u_{i,j}-u\left(x_{i},y_{j}\right)=O\left(h^{2}\right)$. Damit reicht die Lösungsgenauigkeit $O\left(h^{2}\right)$ aus! $A_{\left(m\right)}u_{\left(m\right)}=h^{2}f_{\left(m\right)}$ hat ,,sparse'' Struktur:\[ u_{\left(m\right)}=\left(\begin{array}{c} u_{11}\\ u_{12}\\ \vdots\\ u_{mm}\end{array}\right)\qquad A_{\left(m\right)}=\left(\begin{array}{ccccccccc} 4 & -1 & & 0 & -1\\ -1 & \ddots & \ddots & & & \ddots & & & 0\\ & \ddots & \ddots & -1 & & & \ddots\\ 0 & & -1 & 4 & & & & -1\\ -1 & & & & 4 & -1 & & 0\\ & \ddots & & & -1 & \ddots & \ddots & & 0\\ & & \ddots & & & \ddots & \ddots & -1\\ & & & -1 & 0 & & -1 & 4\\ & 0 & & & & 0 & & & \ddots\end{array}\right)\] typisch: Bandstruktur, Symmetrie, Dominanz der Diagonal-Elemente Bei Gauß-Verfahren würde ,,fill in'' passieren. (Durch $LU$-Zerlegung oder Householder können dann vollbesetzte Martizen entstehen, wodurch die ,,sparse''-Struktur verloren geht.) $A\in L\left(\mathbb{R}^{2n}\right)$ hat die Eigenwerte $\lambda_{k,l}=2\left(2-\cos\frac{k\pi}{n+1}-\cos\frac{l\pi}{n+1}\right)$, $k,l=1,\ldots,n$. Wegen $\lambda_{\min}=8\sin^{2}\left(\frac{\pi}{2\left(n+1\right)}\right)$ ist $A$ dann positiv definit. \end{example*} \subsection{Gesamtschritt-, Einzelschritt-, Relaxationsverfahren} ~ Wir formen $Ax=b$ äquivalent in Fixpunktschreibweise um: \[ x=Bx+d\] Iteration:\[ \boxed{x_{0}\in\R^{m},\qquad x_{j}:=Bx_{j-1}+d,\quad j\in\N}\] \begin{thm} Sei $B\in L\left(\R^{m}\right)$, $\rho\left(B\right)<1$ und $d\in\R^{m}$. Dann gilt: \begin{enumerate} \item $\left(I-B\right)$ ist regulär. \medskip{} \item Für beliebige $x_{0}\in\R^{m}$ gilt\[ \boxed{x_{j}\xrightarrow{j\rightarrow\infty}\left(I-B\right)^{-1}d=A^{-1}b}\] \end{enumerate} \end{thm} \begin{proof} ~ \begin{enumerate} \item Wäre $I-B$ singulär, so gäbe es ein $z\in\R^{m}$, $z\neq0$, mit $\left(I-B\right)z=0$, d.h. $1$ wäre Eigenwert von $B$. ~\contra ~zu $\rho\left(B\right)<1$. \medskip{} \item ~\begin{eqnarray*} x_{j} & = & Bx_{j-1}+d\\ & = & B^{2}x_{j-2}+Bd+d\\ & = & B^{j}x_{0}+\sum_{i=0}^{j-1}B^{i}d\\ \left(I-B\right)\cdot\sum_{i=0}^{j-1}B^{i} & = & \sum_{i=0}^{j-1}B^{i}-\sum_{i=1}^{j}B^{i}=I-B^{j}\\ \textrm{also}\quad\sum_{i=0}^{j-1}B^{i} & = & \left(I-B\right)^{-1}\left(I-B\right)\cdot\sum_{i=0}^{j-1}B^{i}=\left(I-B\right)^{-1}\cdot\left(I-B^{j}\right)\end{eqnarray*} Nach Lemma \ref{lem:6.3} existiert eine Norm $\left\Vert \cdot\right\Vert _{*}$ mit $\left\Vert B\right\Vert _{*}\leq\rho\left(B\right)+\varepsilon<1$, also \[ \left\Vert B^{j}\right\Vert _{*}\leq\left\Vert B\right\Vert _{*}^{j}\xrightarrow{j\rightarrow\infty}0\] und\[ \left\Vert \sum_{i=0}^{j-1}B^{i}-\left(I-B\right)^{-1}\right\Vert _{*}\leq\left\Vert \left(I-B\right)^{-1}\right\Vert _{*}\cdot\left\Vert B\right\Vert _{*}^{j}\xrightarrow{j\rightarrow\infty}0,\] also $B^{j}\rightarrow0$, \begin{eqnarray*} \sum_{i=0}^{j-1}B^{i}d & \xrightarrow{j\rightarrow\infty} & \left(I-B\right)^{-1}d\\ \leadsto\, x_{j} & \xrightarrow{j\rightarrow\infty} & \left(I-B\right)^{-1}d\end{eqnarray*} (D.h. Banachscher Fixpunktsatz für lineare Abbildungen mit $\rho<1$.) \end{enumerate} \end{proof} \subsubsection{Gesamtschrittverfahren (Jacobi)} ~\index{Gesamtschrittverfahren} Voraussetzung: $a_{i,i}\neq0$, $i=1,\ldots,m$ $D:=\textrm{diag}\left(a_{1,1},\ldots,a_{m,m}\right)$\[ Ax=b\quad\sim\quad Dx=-\left(A-D\right)x+b\quad\sim\quad x=\underbrace{-D^{-1}\left(A-D\right)}_{B}x+\underbrace{D^{-1}b}_{d}\] % \marginpar{Gesamt\-schritt\-verfahren% }\[ \boxed{x_{i}^{\left(j\right)}=\frac{1}{a_{i,i}}\cdot\left(b_{i}-\sum_{k=1,k\neq i}^{n}a_{i,k}x_{k}^{\left(j-1\right)}\right),\quad1\leq i\leq m}\] \subsubsection{Einschrittverfahren (Gauß-Seidel)} ~\index{Einschrittverfahren} Voraussetzung: $a_{i,j}\neq0$, $i=1,\ldots,m$% \marginpar{Einzel\-schritt\-verfahren% }\[ \boxed{x_{i}^{\left(j\right)}=\frac{1}{a_{i,i}}\left(b_{i}-\sum_{k=1}^{i-1}a_{i,k}x_{k}^{\left(j\right)}-\sum_{k=i+1}^{m}a_{i,k}x_{k}^{\left(j-1\right)}\right)}\] \begin{eqnarray*} A & = & \underbrace{L}_{\textrm{untere }\triangle-\textrm{Matrix}}+\underbrace{D}_{\textrm{Diagonalmatrix}}+\underbrace{R}_{\textrm{obere }\triangle-\textrm{Matrix}}\end{eqnarray*} \begin{eqnarray*} x_{j} & = & -D^{-1}Lx_{j}-D^{-1}Rx_{j-1}+D^{-1}b\\ \left(D+L\right)x_{j} & = & -Rx_{j-1}+b\\ \sim\, x_{j} & = & \underbrace{-\left(D+L\right)^{-1}R}_{B}x_{j-1}+\underbrace{\left(D+L\right)^{-1}b}_{d}\end{eqnarray*} \begin{thm} Sei $A$ \underbar{strikt diagonaldominant}\index{strikt diagonaldominant}, d.h. ${\displaystyle \sum_{j=1,j\neq i}^{m}}\left|a_{i,j}\right|<\left|a_{i,i}\right|$. Für das Gesamt- und das Einzelschrittverfahren gilt dann $\left\Vert B\right\Vert _{\infty}<1$. \end{thm} \begin{proof} Gesamtschrittverfahren: $B=-D^{-1}\left(L+R\right)$\[ \left\Vert B\right\Vert _{\infty}=\max_{i}\sum_{j=1,j\neq i}^{m}\frac{\left|a_{i,j}\right|}{\left|a_{i,i}\right|}<1\] Einzelschritt: $B=-\left(D+L\right)^{-1}R$\[ \left\Vert B\right\Vert _{\infty}=\max_{\left|x\right|_{\infty}=1}\left|Bx\right|_{\infty}\] $\left|x\right|_{\infty}=1$, $y=Bx$ $\leadsto$ $\left|y\right|_{\infty}<1$. Siehe auch \cite[Kapitel 8]{StoerBulischNumerik2} \end{proof} \subsubsection{Relaxations-Verfahren} ~\index{Relaxations-Verfahren} Parameter $\omega$ (Relaxationsparameter zur Konvergenz-Beschleunigung)% \marginpar{Relaxations-Verfahren% }\[ \boxed{x_{j}=\omega\left(-D^{-1}Lx_{j}-D^{-1}Rx_{j-1}+D^{-1}b\right)+\left(1-\omega\right)x_{j-1}}\] \underbar{Idee:} Young 1950, ,,$\rho\left(B\left(\omega\right)\right)\rightarrow\min$''\begin{eqnarray*} B\left(\omega\right) & = & -\left(D+\omega L\right)^{-1}\left\{ \omega R+\left(\omega-1\right)D\right\} ,\quad d=\left(D+\omega L\right)^{-1}\omega b\\ & = & -\left(\frac{1}{\omega}D+L\right)^{-1}\left\{ R+D-\frac{1}{\omega}D\right\} \end{eqnarray*} \begin{thm} Sei $A$ symmetrisch und positiv definit.\[ \omega\in\left(0,2\right)\quad\leadsto\quad\rho\left(B\left(\omega\right)\right)<1\] \end{thm} \begin{proof} $a_{i,i}=\left\langle Ae_{i},e_{i}\right\rangle >0,$ $A^{T}=A$ $\leadsto$ $R=L^{T}$. Sei $Bz=\lambda z$, $z\in\C^{m}$, $\lambda\in\C$ und $\left|z\right|^{2}=1$. Sei $d=\left\langle Dz,z\right\rangle $, $l=\left\langle Lz,z\right\rangle $ und $a=\left\langle Az,z\right\rangle >0$\[ \leadsto\,\lambda=\frac{\left(2-\omega\right)d-\omega a+\omega\left(l-\bar{l}\right)}{\left(2-\omega\right)d+\omega a+\omega\left(l-\bar{l}\right)}\,\leadsto\,\left|\lambda\right|=1\] \end{proof} gebräuchlich: $\omega\in\left[1,2\right)$ SOR-Verfahren \subsection{Mehrgitter-Verfahren} ~\index{Mehrgitter-Verfahren} \[ \boxed{A_{\left(h\right)}x_{h}=b_{h}}\] feines Gitter $h$: $U_{h}$ grobes Gitter $H$: $U_{H}$\begin{eqnarray*} I_{h}^{H}:U_{h}\rightarrow U_{H} & & \textrm{Restriktions-Operator}\\ I_{H}^{h}:U_{H}\rightarrow U_{h} & & \textrm{Fortsetzungs-Operator}\end{eqnarray*} $k$. Schritt eines Zwei-Gitter-Verfahrens: $x_{h}^{k}$ sei bekannt, bestimme $x_{h}^{k+1}$\begin{eqnarray*} u_{h,0}^{k} & := & x_{h}^{k}\\ u_{h,j}^{k} & := & B_{k}u_{h,j-1}^{k}+d_{k},\quad j=1,\ldots,m_{1}\textrm{ }(\textrm{Vorglättung})\\ \delta_{h}^{k} & := & A_{h}u_{h,m_{1}}^{k}-b_{h}\\ v_{h}^{k}\textrm{ Lösung von }A_{H}v_{H}^{k} & = & -I_{h}^{H}\delta_{h}^{k}\\ w_{h,0}^{k} & := & u_{h,m_{1}}^{k}+I_{H}^{h}v_{H}^{k}\quad(\textrm{Grobgitter}-\textrm{Korrektur})\\ w_{h,j}^{k} & := & B_{h}w_{h,j-1}^{k}+d_{k},\quad j=1,\ldots,m_{2}\\ x_{h}^{k+1} & := & w_{h,m_{2}}^{k}\\ x_{h}^{k+1} & = & S_{h}x_{h}^{k}+t_{h}\\ S_{h} & = & B_{h}^{m_{2}}\left(I-I_{H}^{h}A_{H}^{-1}I_{h}^{H}A_{h}\right)B_{h}^{m_{1}}\end{eqnarray*} $\rho\left(S_{h}\right)\leq\gamma<1$ glm. $\forall h$ \printindex{} \end{document}