path: root/content/numerik_2.tex

\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} :