\section*{Eigenwerte} Sei $A \in \C^{n \times n}$. Ein $\lambda \in \C$ ist \emph{Eigenwert} von $A$, wenn $\exists v \in \C^n\setminus\{0\} : Av = \lambda v$. \subsection*{Satz von Gerschgorin} $$\mathcal{K}_i := \left\{ z \in \C \middle| |z-a_{i,i}| \leq \sum_{k=1, k\neq i}^n |a_{i,k}| =: r_i \right\}, \ 1 \leq i \leq n$$ Die Vereinigung der Kreisscheiben $\mathcal{K}_i$ enthält alle Eigenwerte von $A \in \C^{n \times n}$: $\sigma(A) \subset \bigcup_{i=1}^n \mathcal{K}_i$ \spacing Ist $M_1 = \bigcup_{j=1}^k \mathcal{K}_{i_j}$ disjunkt von der Vereinigung $M_2$ der übrigen Kreise, so enthält $M_1$ genau $k$ und $M_2$ genau $n-k$ Eigenwerte gezählt entsprechend der algebraischen Vielfachheit. \subsection*{Störung des Eigenwertproblems} Sei $A$ diagonalisierbar mit $A= TDT^{-1}$, $\Delta A \in \C^{n \times n}$ beliebig: $\forall \lambda(A+\Delta A) \in \sigma(A+\Delta A) \ \exists \lambda(A) \in \sigma(A) : |\lambda(A+\Delta A) - \lambda(A)| \leq \kappa_p(T) \|\Delta A\|_p$ mit $1 \leq p \leq \infty$. \spacing Entsprechend lautet die Kondition der Bestimmung von Eigenwerten $\lambda \neq 0$ bzgl. der $p$-Norm: $$\kappa_p(\lambda) \leq \frac{\|A\|_p}{|\lambda|} \kappa_p(T)$$ \subsection*{Mögliche Eigenwertlöser} Das Eigenwertproblem ist äquivalent zur Bestimmung der Nullstellen des char. Polynoms. Nach dem \emph{Satz von Abel} existiert für Polynome von Grad $\geq 5$ bzw. Matrizen von Dimension $\geq 5\times5$ kein exakt arbeitender Eigenwertlöser welcher in endlicher Zeit die Eigenwerte bestimmt. d.h. alle Eigenwertlöser sind iterativ. \subsection*{Potenzmethode} In $A^k$ dominiert der betragsgrößte Eigenwert und diese Dominanz nimmt mit $k$ zu. Somit ist an $A^k v$ der betragsgrößte Eigenwert ablesbar. Für $k = 1, 2, \dots$ und Startvektor $x^0 \in \C^n$: \vspace*{-2mm} $$z^k := Ax^{k-1}, \ x^k := \frac{z^k}{\|z^k\|}$$ Der approx. betragsgrößte Eigenwert ergibt sich: \vspace*{-2mm} $$\tilde\lambda = \langle Ax^k,x^k \rangle_2$$ Potenzmethode konvergiert nicht zwingend gegen einen EV des betragsgrößten EW sondern hat Häufungspunkte welche EV zu diesem EW sind. \subsubsection*{Inverse Potenzmethode} Die Konvergenzgeschwindigkeit der Potenzmethode hängt von $|\frac{\lambda_{r+1}}{\lambda_1}|$, also dem Quotienten des ersten nicht betragsmaximalen Eigenwerts und des betragsmaximalen Eigenwertes ab. Langsame Konvergenz liegt bei $|\frac{\lambda_{r+1}}{\lambda_1}| \approx 1$ vor. \spacing Sei $\tilde\lambda$ Schätzwert für $\lambda_i \in \sigma(A)$ d.h. $|\tilde\lambda - \lambda_i| < |\tilde\lambda - \lambda_j|, \ j \neq i$. Die inverse Potenzmethode: \vspace*{-2mm} $$(A-\tilde\lambda Id_n)z^k = x^{k-1}, \ x^k = \frac{z^k}{\|z^k\|_2}$$ Zur Lösung des linearen Systems wird die LR-Zerlegung von $A- \tilde\lambda Id_n$ bestimmt. Konvergenz: \vspace*{-2mm} $$\lim_{k\to\infty} \langle Ax^k,x^k \rangle_2 = \lambda_i$$ Wird die Approximation $\tilde\lambda$ in jedem Iterationsschritt durch die gefundene Approx. verbessert, so approx. das Verfahren einen EV zum EW $\lambda_i$. \subsection*{Hessenberg- / Tridiagonalgestalt} Eigenwertlöser beginnen i.A. mit der Äquivalenz-umformung von $A \in \C^{n \times n}$ in obere Hessenberg- bzw. Tridiagonalgestalt $\mathcal{H}$. Danach wird $\mathcal{H}$ in eine obere Dreiecks- bzw. Diagonalmatrix äquivalent umgeformt. Die Hauptdiagonale einer solchen Matrix besteht dann aus den Eigenwerten von $A$. \subsection*{QR-Algorithmus} Sei $A = QR$ eine QR-Zerlegung von $A \in \R^{n \times n}$. Eine \emph{QR-Transformation} ist $A \mapsto A':=RQ$. \spacing $A'$ ist orthogonalähnlich zu $A$ und $\sigma(A) = \sigma(A')$. Ist $A$ eine obere Hessenberg- oder symmetrische Tridiagonalmatrix, so hat $A'$ dieselbe Struktur. \spacing Transformiere $A$ in obere Hessenberg- bzw. symmetrische Tridiagonalgestalt. Setze dann $A_0 := A$ und iteriere: $A_k =: Q_kR_k, \ A_{k+1} := R_kQ_k$ für $k = 0,1,2,\dots$. \subsubsection*{QR-Identitäten} Sei $A \in \R^{n \times n}$. Dann gelten für $\{A_k\}_k$: \begin{enumerate}[label=(\alph*)] \item $A_{k+1} = Q_k^T A_k Q_k$ \item $A_{k+1} = Q_{k+1}^T A Q_{k+1}$ mit $Q_{k+1} := Q_0 \cdots Q_k$ \item $A^{k+1} = Q_{k+1} R_{k+1}$ mit $R_{k+1} := R_k \cdots R_0$ \end{enumerate} Diese begründen den Zusammenhang von QR-Algorithmus und Potenzmethode. \subsubsection*{QR mit Spektralverschiebung} Der ursprüngliche QR-Algorithmus konvergiert langsam. Dies lässt sich mit Anwendung auf $\tilde A = A - \mu I_n$ (Shift / Spektralverschiebung) verbessern. \spacing Transformiere $A$ in obere Hessenberg- bzw. symmetrische Tridiagonalgestalt. Setze dann $A_0 := A$ und iteriere: $A_k - \mu_k I_n =: Q_kR_k, \ A_{k+1} := R_kQ_k + \mu_k I_n$ für $k = 0,1,2,\dots$. \spacing Bewährte Shift-Strategie: $\mu_k := (A_k)_{nn}$ $|(A_{k+1})_{n,n-1}| \leq c |(A_k)_{n,n-1}|^2$ (quadratische Konv.) \subsubsection*{Bestimmung der Eigenvektoren} Auf die obere Hessenberg-Form $A_0 = P^T A P$ lässt sich die inverse Potenzmethode mit den berechneten Eigenwertnäherungen als Schätzwert anwenden. Das auftretende LGS $A_0 - \tilde\lambda I_n$ lässt sich effizient mit $n-1$ Givens-Rotationen lösen. \section*{Nichtlineare Gleichungssysteme} Die Berechnung von Nullstellen von nichtlinearer $F : D \subset \R^n \to \R^n$ kann i.A. nur iterativ erfolgen. \subsection*{Konvergenzordnung} Sei $\{x^k\}_{k\in\N_0} \subset \R^n$ gegen $\xi \in \R^n$ konv. Folge. Die Folge ist von Ordnung $p \geq 1$, wenn: $\exists C > 0 : \| x^{k+1}-\xi \| \leq C\|x^k-\xi\|^p$ für $k = 0,1,\dots$ Falls $p=1$ sei zusätzlich $C < 1$. \vspace*{-4mm} \begin{align*} p=1 \ (C<1) & \text{\ \ \emph{lineare Konvergenz}} \\ p\in(1,2) & \text{\ \ \emph{superlineare Konvergenz}} \\ p=2 & \text{\ \ \emph{quadratische Konvergenz}} \\ p=3 & \text{\ \ \emph{kubische Konvergenz}} \end{align*} \subsection*{Lokale Konvergenz} Ein Iterationsverfahren $x^{k+1} = \Phi_k(x^k)$ mit $\Phi_k : D \subset \R^n \to \R^n$ ist \emph{lokal konvergent} gegen $\xi \in \R^n$, wenn: $\exists \text{ Umgebung } U \subset D \text{ von } \xi \ \forall x^0 \in U : \{x^k\}_{k\in\N_0}$ konvergiert gegen $\xi$. Ist $U = D$ so konvergiert das Verfahren global. \subsection*{Nullstellen einer Veränderlichen} Sei $f : [a,b] \to \R$ stetig mit $a < b \in \R$. \subsubsection*{Bisektionsverfahren} Sei $f(a)f(b) < 0$. Dann garantiert der Zwischenwertsatz die Existenz einer Nullstelle $\xi \in (a,b)$. Intervallhalbierung approximiert eine Nullstelle. \vspace*{-4mm} \begin{align*} x_k &:= \frac{b_k+a_0}{2} \\ f(x_k)f(a_k) \leq 0 &\rightsquigarrow a_{k+1} := a_k, \ b_{k+1} := x_k \\ f(x_k)f(a_k) > 0 &\rightsquigarrow a_{k+1} := x_k, \ b_{k+1} := b_k \end{align*} Das Bisektionsverfahren konvergiert mit Abbruchbedingung $|f(x_k)| < \tau$ für bel. $\tau > 0$ in endlich vielen Schritten. Falls $f$ Hölder-stetig mit Ordnung $\alpha \in (0,1]$ ist, konvergiert das Verfahren nach maximal $\left\lceil\log_2((b-a)(\frac{L}{\tau})^{1/\alpha})\right\rceil$ Schritten. \subsubsection*{Sekantenverfahren} Zwei Approximationen $x_{k-1}$ und $x_k$ ergeben neue Approximation $x_{k+1}$ als Nullstelle der Sekante $S_f(x;x_k;x_{k-1}) = f(x_k)+\frac{f(x_{k-1})-f(x_k)}{x_{k-1}-x_k} (x-x_k)$. Rekursion: \vspace*{-4mm} $$x_{k+1} := x_k - \frac{x_k-x_{k-1}}{f(x_k)-f(x_{k-1})}f(x_k)$$ \spacing Sei $f \in C^2(a,b)$, $\exists \xi \in (a,b) : f'(\xi), f''(\xi) \neq 0$. Dann konvergiert das Sekantenverfahren lokal superlinear mit Ordnung $(\sqrt{5}+1)/2 \approx 1.618$. \subsubsection*{Newton-Verfahren} Ersetzen von $\frac{x_k-x_{k-1}}{f(x_k)-f(x_{k-1})}$ im Sekantenverfahren mit dem Kehrwert der Tangentensteigung $\frac{1}{f'(x_k)}$ ergibt das \emph{Newton-Verfahren}: \vspace*{-2mm} $$x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)}$$ $x_{k+1}$ ist Nullstelle der Tangente an $f$ in $x_k$. \spacing Sei $f \in C^2(a,b), \exists \xi \in (a,b) : f'(\xi) \neq 0$. Dann konv. das Newton-Verfahren lokal mit Ordnung $2$. \subsection*{Banachscher Fixpunktsatz} Sei $D \subset \R^n$ abgeschlossen, $\Phi : D \to D$ Kontraktion bzgl. $\|\cdot\|$ mit Kontraktionszahl $q \in [0,1)$. Dann hat $\Phi$ genau einen Fixpunkt $x^\star \in D$. Die Fixpunktiteration $x^{k+1} := \Phi(x^k)$ mit $x^0 \in D$ konv. Es gilt die Fehlerabschätzung: \vspace*{-6mm} $$\forall 0 \leq l \leq k - 1 : \|x^\star - x^k\| \leq \frac{q^{k-l}}{1-q} \|x^{l+1} - x^l\|$$ Für $l=0$ ergibt sich die a priori-Abschätzung: \vspace*{-2mm} $$\|x^\star - x^k\| \leq \frac{q^k}{1-q} \|x^1 - x^0\|$$ Für $l=k-1$ die a posteriori-Abschätzung: \vspace*{-2mm} $$\|x^\star - x^k\| \leq \frac{q}{1-q} \|x^k - x^{k-1}\|$$ \subsubsection*{Lokaler Konvergenzsatz} Sei $\Phi : D \subset \R^n \to \R^n$ stetig differenzierbare Fkt., $D$ offen, $\exists x^\star \in D : f(x^\star)=x^\star$ und $\|\Phi'(x^\star)\| < 1$. \vspace*{1mm} Dann ex. abgeschlossene Umgebung $U \subset D$ von $x^\star$ s.d. $\Phi$ in ihr Kontraktion und Selbstabbildung $\Phi(U) \subset U$ ist sowie die Fixpunktiteration konv. \subsection*{Newton-Verfahren in $\R^n$} Sei $F : D \subset \R^n \to \R^n$ eine nichtlineare Funktion. Zu finden ist ein $x^\star \in D$ mit $F(x^\star) = 0$. \spacing Sei $\Phi(x) := x + G(x,F(x))$ mit $G(x,F(x)) = T(x)F(x)$ wobei $T : D \subset \R^n \to \text{GL}_n(\R)$. Das Nullstellenproblem ein Fixpunktproblem: \vspace*{-2mm} $$\Phi(x^\star) = x^\star \iff F(x^\star) = 0$$ Es ergibt sich das \emph{Newton-Verfahren} für $x^0 \in D$: $x^{k+1} := x^k + s^k, \ F'(x^k)s^k = -F(x^k), \ k = 0,1,2,\dots$ \vspace*{1mm} $s^k$ ist der \emph{$k$-te Newton-Schritt oder Korrektur}. \spacing Für Konvergenzuntersuchungen formuliert: $x^{k+1} = \Phi(x^k)$ mit $\Phi(x) = x - F'(x)^{-1}F(x)$ \subsubsection*{Wohldefiniertheit des Newton-Verfahrens} Sei $x^\star \in D$ Lösung des Nullstellenproblems, $F : D \subset \R^n \to \R^n$ stetig diffbar. mit regulärer $F'(x^\star)$: \begin{enumerate}[label=(\alph*)] \item $\exists$ Umgebung $U$ mit $x^\star \in U \ \forall x^0 \in U : $ Newton-Verfahren ist wohldefiniert und mindestens linear konvergent gegen $x^\star$ \item Ist $F' : D \to \R^{n \times n}$ Hölder-stetig in $U$ mit Ordnung $\alpha \in (0,1]$ dann: \\ $\|x^{k+1}-x^\star\| \leq C_N \|x^k-x^\star\|^{1+\alpha}$ mit $C_N > 0$ \\ Verfahren konv. superlinear mit Ordnung $1+\alpha$ für $\alpha \in (0,1)$ und quadratisch für $\alpha = 1$ \end{enumerate} \subsubsection*{Konvergenzüberprüfung} Eine wichtige Invarianzeigenschaft des Newton-Verfahrens ist, dass $F(\cdot)$ und $G(\cdot) = AF(\cdot)$ für $A \in \text{GL}_n(\R)$ dieselben Nullstellen haben, dass Verfahren sich also auf $F$ oder $G$ anwenden lässt. Der \emph{Monotonietest} $\|F(x^{k+1})\| \leq \vartheta\|F(x^k)\|, \ \vartheta \in (0,1)$ spiegelt dies nicht wieder. Er ist nicht affin-invariant, im Gegensatz zum Newton-Verfahren und dem Nullstellenproblem. \vspace*{1mm} Der \emph{affin-invariante natürliche Monotonietest}: \vspace{-2mm} $$\|F'(x^k)^{-1}F(x^{k+1})\| \leq \vartheta\|F'(x^k)^{-1}F(x^k)\|$$ Praktisch wird das Newton-Verfahren bei Verletzung des Tests mit $\vartheta = \frac{1}{2}$ als divergent gestoppt. \subsubsection*{Stoppstrategie} Ein $x^{k+1}$ wird als Approximation an $x^\star$ aktzeptiert, wenn $\|s^k\| \leq \tau$ mit $s^k := F'(x^k)^{-1}F(x^k)$ ist. $\tau > 0$ ist die gewählte Toleranz. \subsection*{Satz von Kantorowitsch} Sei $F : D \subset \R^n \to \R^n$ Funktion mit Eigenschaften: $\exists \beta, \gamma, \eta > 0 : \beta\gamma\eta \leq \frac{1}{2}$ und $\ x^0 \in D$ s.d.: \begin{enumerate}[label=(\roman*)] \item $F$ ist in $x^0$ diffbar. mit $\|F'(x^0)^{-1}\| \leq \beta$ und $\|F'(x^0)^{-1}F(x^0)\| \leq \eta$ \item $F'$ ist Lipschitz-stetig mit $\gamma$ in abg. Kugel $\overline{B_{\overline r}(x^0)} \subset D$ mit Radius $\overline r \geq r_- := \frac{1-\sqrt{1-2\beta\gamma\eta}}{\beta\gamma}$ \end{enumerate} Dann ex. eine eind. Nst. $x^\star$ von $F$ in $\overline{B_{r_-}(x^0)}$ und das Newton-Verfahren mit $x^0 \in D$ ist wohldef. Weiter gilt: $\|x^k-x^\star\| \leq t_k := \frac{(2\beta\gamma\eta)^{2^k}}{2^k\beta\gamma}$ Zusätzlich ist $x^\star$ die eind. Nst. in offener Kugel $B_R(x^0)$ mit $R=\min\{\overline r,r_+\}$ und $r_+ := \frac{1+\sqrt{1-2\beta\gamma\eta}}{\beta\gamma}$. \subsection*{Inexaktes Newton-Verfahren} \section*{Numerische Integration}