\section*{Gleitkomma-Arithmetik} Für $e_{min}, e_{max} \in \mathbb{Z}$, $e_{min} < e_{max}$ ist ein Gleitkommasystem wie folgt definiert: \vspace*{-4mm} \begin{align*} \mathcal{F} &= \mathcal{F}(\beta,t,e_{min},e_{max}) \\ &= \{ \pm m \beta^{e-t} | m \in \N, \beta^{t-1} \leq m \leq \beta^t - 1 \lor m = 0, \\ & \hspace*{16mm}e_{min} \leq e \leq e_{max} \} \end{align*} $x \in \mathcal{F} \setminus \{0\} \Rightarrow \beta^{e_{min}-1} \leq |x| \leq \beta^{e_{max}}(1-\beta^{-1})$. \subsection*{Normalisierte Darstellung} Für $d_1 \neq 0$, $0 < d_1 \leq \beta - 1$: $x=\pm \beta^e ( \frac{d_1}{\beta^1} + \frac{d_2}{\beta^2} + \cdots + \frac{d_t}{\beta^t} ) =: \pm 0.d_1 d_2 \cdots d_t \cdot \beta^e$ \subsection*{Relative Maschinengenauigkeit} $fl(x) \in \mathcal{F}$ ist die $x \in \R$ am nächsten liegende Gleitkommazahl. Für relative Maschinengenauigkeit $\epsilon := \frac{1}{2} \beta^{1-t}$: $\frac{|fl(x)-x|}{|x|} < \epsilon$, $\frac{|fl(x)-x|}{|fl(x)|} \leq \epsilon$ \subsection*{Arithmetische Grundoperationen} Für $x, y \in \mathcal{F}$ sind Operationen $o \in \{x,-,*,\div\}$ bzgl. eines Gleitkommasystems definiert: $\tilde o(x,y) := fl(o(x,y))$ Zu beachten ist hier die Ungültigkeit der Assoziativ- und Distributivgesetze. \subsection*{Kondition mathematischer Probleme} Die Konditionszahl eines mathematischen Problems $(f, x)$ ist die kleinste Zahl $\kappa_f(x) \geq 0$ mit: \vspace*{-4mm} $$\frac{\|f(x + \Delta x) - f(x) \|_Y}{\|f(x)\|_Y} \leq \kappa_f(x) \frac{\|\Delta x\|_X}{\|x\|_X} + o(\|\Delta x \|_X)$$ Für $\|\Delta x\|_X \rightarrow 0$. Ein Problem $(f, x)$ ist gut konditioniert für \emph{kleine} und schlecht konditioniert für \emph{große} Konditionszahlen $\kappa_f(x)$. \subsubsection*{Kondition stetig differenzierbarer Fkt.} Für $f \in C^1(E, \R^m)$ in Umgebung $E \subseteq \R^n$ von $x$: \vspace*{-2mm} $$\kappa_f(x) = \frac{\|f'(x)\| \cdot \|x\|_X}{\|f(x)\|_Y}$$ \section*{Vektor- und Matrixnormen} \subsection*{Induzierte Matrixnorm / Operatornorm} Für Normen $\| \cdot \|_\circ$, $\| \cdot \|_\star$ auf $\K^n$ bzw. $\K^m$ ist eine Matrixnorm $\| \cdot \| : \K^{m \times n} \rightarrow [0,\infty)$ auf dem Vektorraum der $m \times n$-Matrizen definiert: \vspace*{-4mm} $$\|A\| := \max_{v \in \K^n \setminus \{0\}} \frac{\|Av\|_\star}{\|v\|_\circ} = \max_{\{v \in \K^n | \|v\|_\circ = 1 \}} \|Av\|_\star$$ \subsubsection*{Eigenschaften} Für $A \in \K^{m \times n}$ gilt $\forall v \in \K^n : \|Av\|_\star \leq \|A\| \cdot \|v\|_\circ$ Submultiplikativität: $\|AB\| \leq \|A\| \cdot \|B\|$ \subsubsection*{Matrix-$p$-Normen} Induzierte Matrixnorm bei Wahl der $p$-Normen über $\K^n$ bzw. $\K^m$: \vspace*{-4mm} $$\|A\|_p := \max_{\{v \in \K^n | \|v\|_p = 1 \}} \|Av\|_p \text{ für } 1 \leq p \leq \infty$$ \subsubsection*{Spaltensummennorm} Für $A = (a_1, \cdots, a_n)$ mit $a_j \in \K^m$: \vspace*{-4mm} $$\|A\|_1 = \max_{1 \leq j \leq n} \|a_j\|_1 = \max_{1 \leq j \leq n} \sum_{i=1}^m |a_{i,j}|$$ \subsubsection*{Zeilensummennorm} \vspace*{-4mm} $$\|A\|_\infty = \max_{1 \leq i \leq m} \sum_{j=1}^n |a_{i,j}|$$ \subsubsection*{Spektralnorm} Die Matrix-$2$-Norm wird so genannt, da $\|A\|_2 = \sqrt{\lambda_{max}(A^H A)}$ für $\lambda_{max}(A^H A)$ als Bezeichner des größten Eigenwerts von $A^H A \in \K^{n \times n}$. $\|A\|_2 = \|A^H\|_2$, $\|A^H A\|_2 = \|A\|_2^2$ $\|Q A\|_2 = \|A\|_2$ für unitäre $Q$. \subsection*{Kondition einer Matrix} Für $A \in \K^{n \times n} \in GL_n{\R}$, $\|\cdot\|$ induzierte Matrixnorm: \vspace*{-4mm} \begin{align*} \kappa(A) &= \|A\| \cdot \|A^{-1}\| \\ 1 = \|Id\| = \|AA^{-1}\| &\leq \|A\| \cdot \|A^{-1}\| = \kappa(A) \end{align*} \section*{Besondere Matrizen} \subsection*{Diagonaldominante Matrizen} $A \in \R^{n \times n}$ ist diagonaldominant, falls: $\forall i \in \{1,\cdots,n\} : |a_{i,i}| > \sum_{j=1,j\neq i}^n |a_{i,j}|$ Insbesondere sind solche $A$ regulär. \subsection*{Positiv definite Matrizen} $A \in \R^{n \times n}$ ist positiv definit d.h. $A > 0$ falls $A=A^T$ und $\forall x \in \R^n \setminus \{0\} : x^TAx > 0$. \subsection*{Hessenberg-Matrizen} Fast obere / untere Dreiecksmatrix wobei 1. untere / obere Nebendiagonale besetzt sein kann. \section*{Direkte Verfahren zur LGS Lösung} \subsection*{Cramersche Regel} Sei $A = (a_{i,j})_{ij} \in GL_n(\R)$, $b \in \R^n$, $A[j] = (a_1, \cdots, a_{j-1}, b, a_{j+1}, \cdots, a_n) \in \R^{n \times n}$, $a_k$ k-ter Spaltenvektor von $A$. Dann bildet $x_j = \frac{det(A[j])}{det(A)}$ für $j = 1, \cdots, n$ die eindeutige Lösung $x \in \R^n$ s.d. $Ax=b$. Aufgrund des hohen Aufwands von allg. mehr als $(n+1)!$ arithmetischen Operationen ist die Cramersche Regel nur von theoretischer Bedeutung. \subsection*{Lösung gestaffelter Systeme} Obere Dreicksmatrizen können mittels Rückwärtssubstitution, untere Dreiecksmatrizen mittels Vorwärtssubstitution in $\mathcal{O}(n^2)$ gelöst werden. \subsection*{LR-Zerlegung} $A = LR$ wobei $L$ untere Dreiecksmatrix mit $1$-Diagonale und $R$ obere Dreicksmatrix. \subsubsection*{Berechnung LR-Zerlegung} Die LR-Zerlegung existiert insofern die Diagonaleinträge nicht verschwinden. Insbesondere gilt dies für diagonaldominante Matrizen. \begin{enumerate} \item Spaltenweises nullen der der unteren Einträge mittels \emph{Gauß}, Matrizen $L_1, \cdots, L_{n-1}$ \item $L = L_1^{-1} \cdots L_{n-1}^{-1}$, $R=L_{n-1} \cdots L_1 A$ \end{enumerate} \subsubsection*{Lösung $Ax=b$ mittels LR-Zerlegung} \begin{enumerate} \item $A=LR$ berechnen \item $Lz=b$ Vorwärtssubstitution \item $Rx=z$ Rückwärtssubstitution \end{enumerate} \subsubsection*{Spaltenpivotsuche} Die normale LR-Zerlegung ist nur Vorwärts- und nicht Rückwärtsstabil. Dies kann durch Spaltenpivotsuche verbessert werden. Hier wird in jedem Schritt mittels einer Permutationsmatrix immer mit der größten verbleibenden Zeile eliminiert. \vspace{1mm} Für alle regulären Matrizen existiert eine Spaltenpivotsuchen LR-Zerlegung so, dass $PA=LR$. \subsection*{Cholesky-Zerlegung} Für $A > 0$ existiert untere Dreiecksmatrix $L$ mit positiver Diagonale, so dass $A = LL^T$ \subsection*{QR-Faktorisierung} Für alle $A \in \R^{m \times n}$ mit $m \geq n$ und $Rang(A)=n$ existiert $A=QR$ mit unitärem $Q \in \R^{m \times m}$ und injektiver oberer Dreiecksmatrix $R$. \subsubsection*{Householder-Reflexionen} $$H(v) := Id_m - 2 \frac{vv^T}{v^Tv} = Id_m - 2 \frac{vv^T}{\|v\|_2^2} \text{ für } \forall v \in \R^m \setminus \{0\}$$ Solche Householder-Reflexionen $H(v)$ sind orthogonal, d.h. $H(v)^T=H(v)$ und $H(v)^2=Id_m$. Wegen $H(v)v=v-2v=-v$ und $\forall w \in spann\{v\}^\perp : H(w)w=w$ ist $H(v)$ Spiegelung an der Hyperebene $spann\{v\}^\perp$. Solche Reflexionen können durch wiederholte Anwendung Matrizen in obere Dreiecksgestalt überführen: \vspace{1mm} Gesucht ist $v \in \R^m$ für $y \in \R^m$ s.d.: \vspace{-2mm} $$H(v)y=y - 2 \frac{\skp{v,y}}{\|v\|_2^2}v \overset{!}{=} \alpha e_1$$ Vermeidung von Auslöschung: $\alpha := -sign(y_1)\|y\|_2$ Es ergibt sich mit $v:=y-\alpha e_1$: $H(y-\alpha e_1)y=\alpha e_1$. \vspace{1mm} Seien $Q_k$ die sukzessiven, auf $m \times m$ erweiterten, Householder-Reflexionen. Dann gilt: \vspace{1mm} $R:=Q_p \cdots Q_1 A$, $Q:=Q_1^T \cdots Q_p^T$ s.d. $A=QR$. \subsubsection*{Givens-Rotationen} Mit $c^2 + s^2 = 1, c, s \in \R$ und $l < k$: $$G(l,k) := \left(\begin{smallmatrix} 1 & & & & & & & & & & \\ & \diagdown & & & & & & & & & \\ & & 1 & & & & & & & & \\ & & & c & & & & s & & & \\ & & & & 1 & & & & & & \\ & & & & & \diagdown & & & & & \\ & & & & & & 1 & & & & \\ & & & -s & & & & c & & & \\ & & & & & & & & 1 & & \\ & & & & & & & & & \diagdown & \\ & & & & & & & & & & 1 \end{smallmatrix}\right)$$ Wobei $c$ das Diagonalelement der $l$-ten und $k$-ten Zeile, $s$ $k$-tes Element der $l$-ten Zeile, $-s$ $l$-tes Element der $k$-ten Zeile. Givens-Rotationen sind orthogonal, $G(l,k)A$ unterscheidet sich von $A$ nur in der $l$-ten und $k$-ten Zeile. \vspace{-4mm} $$(G(l,k)x)_i = \begin{cases} cx_l + sx_k & i=l \\ -sx_l + cx_k & i=k \\ x_i & \text{sonst} \end{cases}$$ $\exists \varphi \in (0,2\pi] : c=\cos{\varphi}, s=\sin{\varphi}$ d.h. $G(l,k)$ ist Rotation um $\varphi$ in Ebene $spann\{e_l,e_k\}$. Ziel: $k$-te Komponente von $x$ nullen für $x_l^2+x_k^2 \neq 0$. \vspace{-4mm} \begin{align*} |x_l| > |x_k| : &\tau := \frac{x_k}{x_l}, c := \frac{1}{\sqrt{1+\tau^2}}, s := c\tau \\ |x_l| \leq |x_k| : &\tau := \frac{x_l}{x_k}, s := \frac{1}{\sqrt{1+\tau^2}}, c := s\tau \end{align*} Mit einer solchen Givens-Rotation können einzelne Matrixelemente genullt und $A \in \R^{m \times n}$ so sukzessive in eine obere Dreiecksmatrix transformiert werden. QR mit Householder ist ungefähr doppelt so schnell wie mit Givens. Diese sind daher nur bei strukturierten Matrizen wie Tridiagonal- oder Hessenberg-Matrizen sinnvoll einzusetzen. \section*{Lineare Ausgleichsprobleme} Finde $u^* \in \R^n$: $\|Au^*-b\|_2 = \min_{u\in \R^n} \|Au-b\|_2$ Es sind äquivalent: \begin{enumerate}[label=(\alph*)] \item $u^*$ löst Ausgleichsproblem \item $u^*$ löst Normalengleichung $A^TAu^*=A^Tb$ \item $u^*$ erfüllt $Au^* = P_Ab$ mit Ortogonalprojekt. $P_A : \R^m \rightarrow \R^m$ auf Bild von $A$ \end{enumerate} Das Residuum $Au^*-b$ steht normal zu Bild von $A$. Ein Ausgleichsproblem ist eindeutig lösbar gdw. $Kern(A) = \{0\}$. Die Lösung mit minimaler euklidischer Norm wird Minimum-Norm-Lösung $u^+$ genannt. \subsection*{Singulärwertzerlegung} Sei $A \in \R^{m \times n}$ mit $r=Rang(A) \leq \min\{m,n\}$. Dann existiert $A=USV^T$ mit orthogonalen $U \in \R^{m \times m}$, $V \in \R^{n \times n}$ sowie Diagonalmatrix $S \in \R^{m \times n}$. \section*{Iterative Verfahren zur LGS Lösung} Ein iteratives Verfahren zur Lösung von $Au=b$ liefert zu Startvektor $u^0 \in \R^n$ eine Folge $\{u^k\}_{k\in \N_0} \subset \R^n$ mittels $\Psi_k : (\R^n)^{k+1} \rightarrow \R^n$ durch $u^{k+1} = \Psi_k(u^0, \cdots, u^k)$. Ein Verfahren konvergiert falls $\forall u^0 \in \R^n$, $b \in \R^n : \lim_{k\to \infty} u^k = A^{-1}b$ \subsection*{Abbruchkriterium} Direkte Löser liefern bei exakter Arithmetik nach endlich vielen Schritten $A^{-1}b$. Bei iterativen Lösern gilt im allg. $\forall k \in \N : u^k \neq A^{-1}b$. Ein Abbruchkriterium mit Toleranz $\tau > 0$ ist z.B. $\|u^m-u^{m-1}\| \leq \tau$ oder das relative Residuum von $u^m$: $\frac{\|Au^m-b\|}{\|b\|} \leq \tau$ \subsection*{Lineare Iterationsverfahren} \subsection*{Krylow-Raum-Verfahren} \subsection*{cg-Verfahren} \subsection*{GMRES-Verfahren} \section*{Interpolation}