\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*{Positive Definitheit}

$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$.

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

\section*{Lineare Ausgleichsprobleme}

\section*{Iterative Verfahren zur LGS Lösung}

\subsection*{Krylow-Raum-Verfahren}

\subsection*{cg-Verfahren}

\subsection*{GMRES-Verfahren}

\section*{Interpolation}
