1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
|
\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
|
