\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*{Inexakte Newton-Verfahren}

Hier wird der Newton-Schritt $s^k$ zu Beginn nur grob approximiert und nur in der Nähe der Nullstelle präzise berechnet. Dies dient der Reduktion der Rechenzeit bei Beibehaltung der quadratischen Konvergenz. Für $x^0 \in D, k = 0,1,2,\dots$:

\vspace*{-4mm}
$$x^{k+1} := x^k + s^k, \ \|F'(x^k)s^k + F(x^k)\| \leq \eta_k \|F(x^k)\|$$

Hierbei ist $\{\eta_k\}_k \subset [0,1)$ die Toleranz.

Der inexakte Schritt wird aus $F'(x^k)s^k = -F(x^k)$ bestimmt, s.d. das relative Residuum kleiner gleich $\eta_k$ ist. Dies ist über frühes Stoppen von iterativen Lösern wie GMRES zu erreichen.

\section*{Nichtlineare Ausgleichsprobleme}

Sei $F : D \subset \R^n \to \R^m$ mit $n \neq m$.

\vspace*{1mm}

Finde die Lösung einer Minimierungsaufgabe: $x^\star \in D : g(x^\star) = \min_{x \in D}g(x)$ mit $g(x) := \|F(x)\|^2$.

\vspace*{1mm}

$\|\cdot\|$ sei die Euklidische Norm $\|\cdot\|_2$.

\subsection*{Gauß-Newton-Verfahren}

Ziel ist die Bestimmung von $n$ Parametern $x$ einer Modellfunktion $\varphi$ mit Hilfe von $m$ Messungen.

Sei $\{(t_i,b_i) : 1 \leq i \leq \ell\} \subset \R^d \times \R^p$ Meßdatensatz mit Meßpunkten $t_i \in \R^d$ und Meßwerten $b_i \in \R^p$.

\columnbreak

Modell $\varphi(t_i;x) = b_i$ wird identifiziert mit:

\vspace*{-2mm}
$$F(x) := \begin{pmatrix} \varphi(t_1;x) - b_1 \\ \vdots \\ \varphi(t_\ell;x) - b_\ell \end{pmatrix} \in \R^m, \ m=\ell p$$

Konkret gelößt wird das lokale Minima $x^\star$ von $g$ mit $\nabla g(x^\star) = 0$ und $\mathcal{H}g(x^\star)$ positiv definit.

\vspace*{-4mm}
\begin{align*}
	\nabla g(x) &= 2F(x)^T F'(x) \\
	G(x^\star) :&= \frac{1}{2} \nabla g(x^\star)^T = F'(x^\star)^T F(x^\star) = 0
\end{align*}

Nullstelle wird mit Newton-Verfahren bestimmt.

\vspace*{-2mm}
$$G'(x) \approx F'(x)^T F'(x)$$

Für $x$ in der Nähe eines Minimums von $g$.

Das konkrete \emph{Gauß-Newton-Verfahren}:

\vspace{-4mm}
$$x^{k+1} := x^k + s^k, \ s^k := -F'(x^k)^+ F(x^k), \ k = 0,1,2,\dots$$

Wobei $F'(x)^+ = (F'(x)^T F'(x))^{-1} F'(x)^T$.

\subsubsection*{Konvergenz des Gauß-Newton-Verfahrens}

Sei $F : D \subset \R^n \to \R^m$ stetig differenzierbar, $m \geq n$ und habe Lösung $x^\star$ s.d. $F'$ Maximalrang hat: $F'(x^\star)$ ist injektiv. Weiter gelte für $\kappa \in [0,1)$ $\|F'(x)^+ F(x^\star)\| \leq \kappa \|x-x^\star\|$ lokal um $x^\star$. Dann:

\begin{enumerate}[label=(\alph*)]
	\item Das Gauß-Newton-Verfahren konvergiert lokal mindestens linear gegen $x^\star$ 
	\item Ist $F'$ Hölder-stetig mit Ordnung $\alpha \in (0,1]$ in der Nähe von $x^\star$ so gilt: \\ $\|x^{k+1}-x^\star\| \leq C_{GN}\|x^k-x^\star\|^{1+\alpha} + \kappa\|x^k-x^\star\|$ Falls $F(x^\star) = 0$ gilt, ist die Konvergenz superlinear von Ordnung $1+\alpha$. Sonst linear.
\end{enumerate}

\section*{Numerische Integration}
