sheet.tex (10342B)
1 \documentclass[11pt, a4paper, twoside]{article} 2 \usepackage[ 3 a4paper, 4 headsep=5mm, 5 footskip=0mm, 6 top=12mm, 7 left=10mm, 8 right=10mm, 9 bottom=10mm 10 ]{geometry} 11 \usepackage{amsmath} 12 \usepackage{gauss} 13 \usepackage{nicematrix} 14 \usepackage{tikz} 15 \usepackage{amsfonts} 16 \usepackage{makecell} 17 \usepackage{multicol} 18 \usepackage[noend]{algorithm2e} 19 \usepackage[utf8]{inputenc} 20 \usepackage{fancyhdr} 21 \usepackage{tikz} 22 \usetikzlibrary{arrows,automata,positioning, graphs, graphdrawing} 23 \usegdlibrary {trees} 24 \usepackage{hyperref} 25 \hypersetup{ 26 colorlinks=true, 27 linkcolor=blue, 28 filecolor=magenta, 29 urlcolor=cyan, 30 pdftitle={Overleaf Example}, 31 pdfpagemode=FullScreen, 32 } 33 34 \setlength{\algomargin}{0pt} 35 36 \begin{document} 37 \pagestyle{fancy} 38 \fancyhead{} 39 \fancyhead[L]{Numerische Mathematik für die Fachrichtungen Informatik} 40 \fancyhead[R]{Gero Beckmann - \url{https://github.com/Geronymos/}} 41 \fancyfoot{} 42 \fancyfoot[R]{\thepage} 43 \newenvironment{definition}[1]{\noindent\textbf{#1:}}{} 44 \section{Computergenauigkeit} 45 46 \[ 47 FL = \{ +- B^e \Sigma_{l=1}^{l_m} a_l B^{-l} : e = e_{min} + 48 \Sigma_{l=0}^{L_e-1} c_l B^l, a_l, c_l \in \{0, ..., B-1 \}, a \neq 0 \} \cup 49 \{ 0 \} \subset \mathbb{Q} \\ 50 \] 51 52 \begin{multicols}{2} 53 \section{Normen und Kondition} 54 55 \begin{align*} 56 \|A\|_1 &= \max_{n=0,...,N} \Sigma_{m=0}^{N} |a_{mn}| & \text{Spaltennorm} \\ 57 \|A\|_2 &= \sqrt {\max \lambda \text{ von } A^T A} & \text{Spektralnorm} \\ 58 \|A\|_\infty &= \max_{m=0,...,N} \Sigma_{n=0}^{N} |a_{mn}| & \text{Zeilennorm} \\ 59 \end{align*} 60 61 \subsection{Kondition} 62 63 \begin{align*} 64 \kappa(A) &= \|A\|\|A^{-1}\| \\ 65 \kappa(A) &= \frac{\max_{\|y\|=1} \|A_y\|}{\min_{\|z\|=1} \|Az\|} \\ 66 \kappa_2(A^TA) &= \kappa_2(A)^2 = \sqrt{\frac{\max \lambda \text{ von } A^TA}{\min \lambda}} 67 \end{align*} 68 \end{multicols} 69 70 \begin{multicols}{2} 71 \section{Cholesky-Zerlegung} 72 73 \begin{enumerate} 74 \item Berechne $A=LL^T$ 75 \item Löse durch Vorwärtssubstitution $Ly = b$ 76 \item Löse durch rückwärtssubstitution $L^T = y$ 77 \end{enumerate} 78 79 \begin{align*} 80 Ax &= b \\ 81 A &= \begin{pmatrix} 82 l_{11} & & \\ 83 l_{21} & l_{22} & \\ 84 l_{31} & l_{32} & l_{33} 85 \end{pmatrix} \begin{pmatrix} 86 l_{11} & l_{21} & l_{31} \\ 87 & l_{22} & l_{32} \\ 88 & & l_{33} 89 \end{pmatrix} 90 \end{align*} 91 92 \end{multicols} 93 94 \hspace{-.6cm} 95 \begin{minipage}{.42\textwidth} 96 \section{LR-Zerlegung} 97 98 \begin{enumerate} 99 \item Berechne Zerlegung $A = CR$ 100 \item Löse $Ly = b$ durch Vorwaärtssubstitution 101 \item Löse $Rx =y$ durch Rückwärtssubstitution 102 \end{enumerate} 103 \end{minipage} 104 \hspace{-2cm} 105 \begin{minipage}{.6\textwidth} 106 \hspace{-10cm} 107 \begin{align*} 108 \begin{gmatrix}[p] 109 1 & 4 & -1 \\ 110 3 & 0 & 5 \\ 111 2 & 2 & 1 112 \rowops 113 \add[-3]{0}{1} 114 \add[-2]{0}{2} 115 \end{gmatrix} \leadsto \begin{pNiceMatrix} 116 1 & 4 & -1 \\ 117 3 & -12 & 8 \\ 118 2 & -6 & 3 119 \CodeAfter 120 \tikz \draw (2-|1) -| (4-|2); 121 \end{pNiceMatrix} \begin{gmatrix} 122 \\ \\ 123 \rowops 124 \add[\frac{1}{-2}]{1}{2} 125 \end{gmatrix} \leadsto \begin{pNiceMatrix} 126 1 & 4 & -1 \\ 127 3 & -12 & 8 \\ 128 2 & \frac 1 2 & -1 129 \CodeAfter 130 \tikz \draw (2-|1) -| (3-|2) -| (4-|3); 131 \end{pNiceMatrix} \\ 132 \Rightarrow L = \begin{pmatrix} 133 1 & 0& 0 \\ 134 3 & 1 & 0 \\ 135 2 & \frac 1 2 & 1 136 \end{pmatrix}, R = \begin{pmatrix} 137 1 & 4 & -1 \\ 138 0 & -12 & 8 \\ 139 0 & 0 & -1 140 \end{pmatrix} 141 \end{align*} 142 \end{minipage} 143 144 \subsection{Mit Pivotwahl / Permutationsmatrix $PA = LR$} 145 146 \begin{enumerate} 147 \item Berechne Zerlegung $PA = LR$ durch Gauß-Elimitation 148 \item Löse $Ly = Pb$ durch Vorwärtssubstition 149 \item Löse $Rx = y$ durch Rückwärtssubstitution 150 \end{enumerate} 151 \def\rowswapfromlabel#1{#1} 152 \def\rowswaptolabel#1{#1} 153 \def\colswapfromlabel#1{#1} 154 \def\colswaptolabel#1{#1} 155 \begin{align*} 156 \begin{pmatrix} 157 1 \\ 2 \\ 3 158 \end{pmatrix} 159 \begin{gmatrix}[p] 160 1 & 2 & 2 \\ 161 -2 & -2 & 4 \\ 162 2 & 4 & 2 163 \rowops 164 \swap[|-2| > |1|][]01 165 \end{gmatrix} \leadsto 166 \begin{pmatrix} 167 2 \\ 1 \\ 3 168 \end{pmatrix} 169 \begin{gmatrix}[p] 170 -2 & -2 & 4 \\ 171 1 & 2 & 2 \\ 172 2 & 4 & 2 173 \rowops 174 \add[\frac 1 2 ]01 175 \add[1]02 176 \end{gmatrix} \leadsto 177 \begin{pmatrix} 178 2 \\ 1 \\ 3 179 \end{pmatrix} 180 \begin{pNiceMatrix} 181 -2 & -2 & 4 \\ 182 -\frac 1 2 & 1 & 4 \\ 183 -1 & 2 & 6 184 \CodeAfter 185 \tikz \draw (2-|1) -| (4-|2); 186 \end{pNiceMatrix} 187 \begin{gmatrix} 188 \\ \\ 189 \rowops 190 \swap[|2| > |1|]12 191 \end{gmatrix} \\ \leadsto 192 \begin{pmatrix} 193 2 \\ 3 \\ 1 194 \end{pmatrix} 195 \begin{pNiceMatrix} 196 -2 & -2 & 4 \\ 197 -1 & 2 & 6 \\ 198 -\frac 1 2 & 1 & 4 199 \CodeAfter 200 \tikz \draw (2-|1) -| (4-|2); 201 \end{pNiceMatrix} 202 \begin{gmatrix} 203 \\ \\ 204 \rowops 205 \add[-\frac 1 2]12 206 \end{gmatrix} \leadsto 207 \begin{pmatrix} 208 2 \\ 3 \\ 1 209 \end{pmatrix} 210 \begin{pNiceMatrix} 211 -2 & -2 & 4 \\ 212 -1 & 2 & 6 \\ 213 -\frac 1 2 & \frac 1 2 & 1 214 \CodeAfter 215 \tikz \draw (2-|1) -| (3-|2) -| (4-|3); 216 \end{pNiceMatrix} \Rightarrow 217 L = \begin{pmatrix} 218 1 & 0 & 0 \\ 219 -1 & 1 & 0 \\ 220 -\frac12 & \frac12 &1 221 \end{pmatrix}, 222 R = \begin{pmatrix} 223 -2 & -2 & 4 \\ 224 0 & 2 & 6 \\ 225 0 & 0 & 1 226 \end{pmatrix}, 227 P = \begin{pmatrix} 228 0 & 1 & 0 \\ 229 0 & 0 & 1 \\ 230 1 & 0 & 0 231 \end{pmatrix} 232 \end{align*} 233 234 Für Eliminierung in Spalte n werden Zeilen so getauscht, dass in der n-ten 235 Spaten ab dre n-ten Zeile, sodass das Betraglich größte Element in Zeile n 236 steht. 237 238 \newpage 239 240 \begin{multicols}{2} 241 242 \section{QR-Zerlegung $A = QR$} 243 244 \begin{enumerate} 245 \item Bestimme Matrizen Q und R durch Householder-Transformationen 246 \item Löse $Qx = b$ ($Q^{-1} = Q^T$, also $c = Q^Tb$) 247 \item Löse $Rx = c$ durch Rückwärtssubstitution 248 \end{enumerate} 249 250 \begin{enumerate} 251 \item Bestimme Teilmatrix $A'^{(j-1)}$ 252 \item Berechne $v^{(j)} = {a'}_{I}^{(j-1)} + sign({a'}_{II}^{(j-1)}) \cdot \| {a'}_I^{(j-1)} \| e_I$ 253 \item Berechne $H'^{(j-1)} = I - \frac {2v^{(j)}v^{(j)T}} {v^{(j)T}v^{(j)}}$ 254 \item Bestime $H^{(j)} = \begin{pmatrix} 1 & 0 \\ 0 & H'^{(j-1)}\end{pmatrix}$ 255 \item Berechne $A^{(j)} = H^{(j)}A^{(j-1)}$ bis $A^{(j)} = R$ 256 \end{enumerate} 257 258 \begin{align*} 259 j = 1 \rightarrow j = k = min(m-1, n) \\ 260 Q^T = H^{(k)} \cdot ... \cdot H^{(2)} H^{(1)} 261 \end{align*} 262 263 \subsection{Minimale Fehlerquote} 264 265 \[ 266 |y_i - f(x_i)|_2^2 = \Sigma_{i=1}^{N} (y_i - f(x_i))^2 267 \] 268 269 \subsection{Ausgleichssystem} 270 271 Der Vektor $x \in \mathbb{R}^N$ löst genau dann $\|Ax -b \|_2 = min!$, falls er 272 $A^TAx = A^Tb$ (Normalgleichung) löst. 273 274 \columnbreak 275 276 \section{Singilärwertzerlegung} 277 278 \begin{enumerate} 279 \item Rechne $S = A^TA$ 280 \item Berechne EW und EV von S 281 \item Bilde ONB $u_1, u_2, ..., u_N$ aus EV von S 282 \item Berechne $\sigma_k = \sqrt{\lambda_k}$ 283 \item $U = \begin{pNiceArray}{c|c|c} U_1 & ... & U_k \end{pNiceArray} = 284 diag(\sqrt{\lambda_1}, ..., \sqrt{\lambda_k}) = 285 diag(\sigma_1, ..., \sigma_k) = \Sigma$ 286 \item $V = A U \Sigma^{-1}$ 287 \end{enumerate} 288 289 \subsection{Pseudoinverse } 290 $A^+ = U \Sigma^{-1} V^T$ ; ist A regulär dann gilt $A^{-1} = A^+$ 291 292 \subsection{Normalengleichung} 293 $|Ax-b|_2=Min!$ durch $x = A^+b$ gelöst 294 295 \end{multicols} 296 297 \section{Hessenbergform (rechte-obere Dreiecksmatrix ab der unterren Nebendiagonale)} 298 299 \subsection{Tridiagonal (Nur Haupt- und Nebendiagonale)} 300 301 \begin{align*} 302 \text{TeilmatrixA }&{A'}^{(j-1)} \\ 303 w^{(j)} &= {a'}_{I}^{(j-1)} + sign({a'}_{Ii}^{(j-1)}) \cdot \|{a'}_{I}^{(j-1)}\|_2 \cdot e_I \\ 304 {Q'}^{(j-1)} &= I - \frac {2 w^{j} w^{(j)T}} {w^{(j)T} w^{(j)}} \\ 305 Q^{(j)} &= \begin{pmatrix} 1 & 0 \\ 0 && {Q'}^{(j-1)} \end{pmatrix} \\ 306 H^{(j)} &= Q^{T(j)} A^{(j-1)} Q^{(j)} 307 \end{align*} 308 309 \subsection{Jacobi-Verfahren (Lösung von Ax =b) / Gesamtschrittverfahren} 310 \begin{align*} 311 x_m^{k+1} &= \frac 1 {A[m;m]} (b_m - \Sigma_{n \neq m} A[m,n] x_n^k) &\text{für $m=1, ..., M$} \\ 312 x^{k+1} &= x^k + D^{-1} (b - Ax^k) & A = D + (L + U) \\ 313 & &\text{(diagonal + (strikte linke untere / rechte obere))} 314 \end{align*} 315 316 \subsection{Gauß-Seidel-verfahren / Einzelschrittverfahren} 317 \begin{align*} 318 x_m^{k+1} &= \frac 1 {A[m;m]} (b_m - \Sigma_{n=1}^{m-1} A[m,n] x_n^{k+1} - \Sigma_{k=m+1}^{N} A[m,n] x_n^k) \\ 319 x^{k+1} &= x^k + (D + L)^{-1} (b - Ax^k) 320 \end{align*} 321 322 \subsection{CG-Verfahren} 323 \begin{align*} 324 a 325 \end{align*} 326 327 \subsection{GMRES} 328 \begin{align*} 329 a 330 \end{align*} 331 332 Energienorm $\|x\|_A = \sqrt{x^TAx}$ 333 334 SKP $<x,y> = x^TAy$ 335 336 \subsection{Krylov-Raum} 337 338 \section{Spline Interpolation} 339 340 \begin{align*} 341 & s'(a) = v_0 \text{ und } s'(b) = v_N & \text{hermitisch} \\ 342 & s''(a) = s''(b) = 0 & \text{natürlich} \\ 343 & s'(a) = s'(b) \text{ und } s''(a) = s''(b) & \text{periodisch} 344 \end{align*} 345 346 \section{Newton-Verfahren} 347 \[ 348 x^{n+1} = x^n - \frac {f(x^n)} {f'(x^n)} 349 \] 350 351 \section{Quadraturformel} 352 353 Gewichte $b_k \in [0,1]$, Knoten $c_k \in [0,1]$, Stützstelle $a + c_k (b-a)$ 354 355 \[ 356 \int_a^b f(x)dx \approx (b - a) \Sigma_{k=1}^s b_k f(a+c_k (b-a)) 357 \] 358 359 \begin{tabular}{llll} 360 Rechteckregel & $s=1$ & $b_1=1$ & $c_1=0$ \\ 361 Mittelpunktregel & $s=1$ & $b_1=1$ & $c_1 = \frac12$ \\ 362 Trapezregel & $s=2$ & $b_1 = b_2 = \frac12$ & $c_1 = 0, c_2 = 1$ \\ 363 Simpsonregel & $s=3$ & $b_1 = b_3 = \frac16, b_2 = \frac46$ & $c_1 = 0, c_2 = \frac12, c_3 = 1$ 364 \end{tabular} 365 366 Symmetrische Quadraturformel $c_k = 1 - c_{s+1-k}$, $b_k = b_{s+1-k}$ 367 368 Ordung $p$ $\frac1q = \Sigma_{k=1}^S b_k c_k^{q-1}$ für alle $q=1, .., p$ nicht für $q = p+1$! 369 370 \section{Polynom-Interpolation} 371 372 \subsection{Lagrange} 373 374 \begin{align*} 375 & p(x) = \Sigma_{n=0}^N f_n L_n(x) & 376 L_n(x) = \Pi_{j=0, j \neq n}^N \frac{x - x_j}{x_n - x_j} 377 \end{align*} 378 379 Lebesque-Konstante 380 \[ 381 \Lambda_N := \max_{x \in [a,b]} \Sigma_{n=0}^{N} |L_n(x)| 382 \] 383 384 \subsection{Newton-Darstellung} 385 386 \begin{tabular}{c|c|c|c|c} 387 $f_n$ & 1 & 6 & -3 & 3 \\ 388 \hline 389 $x_n$ & -1 & 0 & 1 & 3 390 \end{tabular} 391 392 \[ 393 \begin{NiceArray}{c|cccc} 394 x_0 = -1 & f_0 = 1 & & & \\ 395 x_1 = 0 & f_1 = 6 & \frac{1-6}{-1-0} = 5 & & \\ 396 x_2 = 1 & f_2 = -3 & \frac{6+3}{0-1} = -9 & \frac{5+9}{-1-1} = -7 & \\ 397 x_3 = 3 & f_3 = 3 & \frac{-3-3}{1-3} = 3 & \frac{-9-3}{0-3} = 4 & \frac{-7-4}{-1-3} = \frac{11}{4} 398 \end{NiceArray} 399 \] 400 401 \begin{align*} 402 p(x) &= 1 + 5(x-(-1)) -7(x-(-1))(x-0) + \frac{11}4 (x-(-1))(x-0)(x-1) \\ 403 p(x) &= f_{0,0} + f_{0,1}(x-x_0) + ... + f_{0,N}(x-x_0) \cdot ... \cdot (x-x_{N-1}) 404 \end{align*} 405 406 \end{document}