path: root/sheet.tex

\documentclass[11pt, a4paper, twoside]{article}
\usepackage[
    a4paper,
    headsep=5mm,
    footskip=0mm,
    top=12mm,
    left=10mm,
    right=10mm,
    bottom=10mm
]{geometry}
\usepackage{amsmath}
\usepackage{gauss}
\usepackage{nicematrix}
\usepackage{tikz}
\usepackage{amsfonts}
\usepackage{makecell}
\usepackage{multicol}
\usepackage[noend]{algorithm2e}
\usepackage[utf8]{inputenc}
\usepackage{fancyhdr}
\usepackage{tikz}
\usetikzlibrary{arrows,automata,positioning, graphs, graphdrawing}
\usegdlibrary {trees} 
\usepackage{hyperref}
\hypersetup{
    colorlinks=true,
    linkcolor=blue,
    filecolor=magenta,      
    urlcolor=cyan,
    pdftitle={Overleaf Example},
    pdfpagemode=FullScreen,
    }

\setlength{\algomargin}{0pt}

\begin{document}
\pagestyle{fancy}
\fancyhead{}
\fancyhead[L]{Numerische Mathematik für die Fachrichtungen Informatik}
\fancyhead[R]{Gero Beckmann - \url{https://github.com/Geronymos/}}
\fancyfoot{}
\fancyfoot[R]{\thepage}
\newenvironment{definition}[1]{\noindent\textbf{#1:}}{}
\section{Computergenauigkeit}

\[
  FL = \{ +- B^e \Sigma_{l=1}^{l_m} a_l B^{-l} : e = e_{min} +
  \Sigma_{l=0}^{L_e-1} c_l B^l, a_l, c_l \in \{0, ..., B-1 \}, a \neq 0 \} \cup
  \{ 0 \} \subset \mathbb{Q} \\
\]

\begin{multicols}{2}
\section{Normen und Kondition}

\begin{align*}
  \|A\|_1 &= \max_{n=0,...,N} \Sigma_{m=0}^{N} |a_{mn}| & \text{Spaltennorm} \\
  \|A\|_2 &= \sqrt {\max \lambda \text{ von } A^T A} & \text{Spektralnorm} \\
  \|A\|_\infty &= \max_{m=0,...,N} \Sigma_{n=0}^{N} |a_{mn}| & \text{Zeilennorm} \\
\end{align*}

\subsection{Kondition}

\begin{align*}
  \kappa(A) &= \|A\|\|A^{-1}\| \\
  \kappa(A) &= \frac{\max_{\|y\|=1} \|A_y\|}{\min_{\|z\|=1} \|Az\|} \\
  \kappa_2(A^TA) &= \kappa_2(A)^2 = \sqrt{\frac{\max \lambda \text{ von } A^TA}{\min \lambda}}
\end{align*}
\end{multicols}

\begin{multicols}{2}
\section{Cholesky-Zerlegung}

\begin{enumerate}
  \item Berechne $A=LL^T$
  \item Löse durch Vorwärtssubstitution $Ly = b$
  \item Löse durch rückwärtssubstitution $L^T = y$
\end{enumerate}

\begin{align*}
  Ax &= b \\
  A &= \begin{pmatrix}
  l_{11} & & \\
  l_{21} & l_{22} & \\
  l_{31} & l_{32} & l_{33}
\end{pmatrix} \begin{pmatrix}
  l_{11} & l_{21} & l_{31} \\
         & l_{22} & l_{32} \\
         &        & l_{33}
\end{pmatrix}
  \end{align*}

\end{multicols}

\hspace{-.6cm}
\begin{minipage}{.42\textwidth}
\section{LR-Zerlegung}

\begin{enumerate}
  \item Berechne Zerlegung $A = CR$
  \item Löse $Ly = b$ durch Vorwaärtssubstitution
  \item Löse $Rx =y$ durch Rückwärtssubstitution
\end{enumerate}
\end{minipage}
\hspace{-2cm}
\begin{minipage}{.6\textwidth}
  \hspace{-10cm}
  \begin{align*}
  \begin{gmatrix}[p]
  1 & 4 & -1 \\
  3 & 0 & 5 \\
  2 & 2 & 1
  \rowops
    \add[-3]{0}{1}
    \add[-2]{0}{2}
  \end{gmatrix} \leadsto \begin{pNiceMatrix}
    1 & 4 & -1 \\
    3 & -12 & 8 \\
    2 & -6 & 3 
    \CodeAfter
    \tikz \draw (2-|1) -| (4-|2); 
  \end{pNiceMatrix} \begin{gmatrix}
    \\ \\ 
    \rowops
    \add[\frac{1}{-2}]{1}{2}
  \end{gmatrix} \leadsto \begin{pNiceMatrix}
    1 & 4 & -1 \\ 
    3 & -12 & 8 \\ 
    2 & \frac 1 2 & -1
    \CodeAfter
    \tikz \draw (2-|1) -| (3-|2) -| (4-|3); 
  \end{pNiceMatrix} \\
  \Rightarrow L = \begin{pmatrix}
    1 & 0& 0 \\
    3 & 1 & 0 \\ 
    2 & \frac 1 2 & 1
  \end{pmatrix}, R = \begin{pmatrix}
    1 & 4 & -1 \\
    0 & -12 & 8 \\
    0 & 0 & -1
  \end{pmatrix}
\end{align*}
\end{minipage}

\subsection{Mit Pivotwahl / Permutationsmatrix $PA = LR$}

\begin{enumerate}
  \item Berechne Zerlegung $PA = LR$ durch Gauß-Elimitation
  \item Löse $Ly = Pb$ durch Vorwärtssubstition
  \item Löse $Rx = y$ durch Rückwärtssubstitution
\end{enumerate}
\def\rowswapfromlabel#1{#1}
\def\rowswaptolabel#1{#1}
\def\colswapfromlabel#1{#1}
\def\colswaptolabel#1{#1}
\begin{align*}
  \begin{pmatrix}
    1 \\ 2 \\ 3
  \end{pmatrix}
  \begin{gmatrix}[p]
    1 & 2 & 2 \\
    -2 & -2 & 4 \\
    2 & 4 & 2
    \rowops
    \swap[|-2| > |1|][]01
  \end{gmatrix} \leadsto
  \begin{pmatrix}
    2 \\ 1 \\ 3
  \end{pmatrix}
  \begin{gmatrix}[p]
    -2 & -2 & 4 \\
    1 & 2 & 2 \\
    2 & 4 & 2 
    \rowops
    \add[\frac 1 2 ]01
    \add[1]02
  \end{gmatrix} \leadsto
  \begin{pmatrix}
    2 \\ 1 \\ 3
  \end{pmatrix}
  \begin{pNiceMatrix}
    -2 & -2 & 4 \\
    -\frac 1 2 & 1 & 4 \\
    -1 & 2 & 6
    \CodeAfter
    \tikz \draw (2-|1) -| (4-|2);
  \end{pNiceMatrix}
  \begin{gmatrix}
    \\ \\ 
    \rowops
    \swap[|2| > |1|]12
  \end{gmatrix} \\ \leadsto
  \begin{pmatrix}
    2 \\ 3 \\ 1
  \end{pmatrix}
  \begin{pNiceMatrix}
    -2 & -2 & 4 \\
    -1 & 2 & 6 \\
    -\frac 1 2 & 1 & 4
    \CodeAfter
    \tikz \draw (2-|1) -| (4-|2);
  \end{pNiceMatrix}
  \begin{gmatrix}
    \\ \\ 
    \rowops
    \add[-\frac 1 2]12
  \end{gmatrix} \leadsto
  \begin{pmatrix}
    2 \\ 3 \\ 1
  \end{pmatrix}
  \begin{pNiceMatrix}
    -2 & -2 & 4 \\
    -1 & 2 & 6 \\
    -\frac 1 2 & \frac 1 2 & 1
    \CodeAfter
    \tikz \draw (2-|1) -| (3-|2) -| (4-|3);
  \end{pNiceMatrix} \Rightarrow
  L = \begin{pmatrix}
    1 & 0 & 0 \\
    -1 & 1 & 0 \\
    -\frac12 & \frac12 &1
    \end{pmatrix}, 
    R = \begin{pmatrix}
      -2 & -2 & 4 \\ 
      0 & 2 & 6 \\ 
      0 & 0 & 1 
      \end{pmatrix},
      P = \begin{pmatrix}
        0 & 1 & 0 \\ 
        0 & 0 & 1 \\ 
        1 & 0 & 0
      \end{pmatrix}
\end{align*}

Für Eliminierung in Spalte n werden Zeilen so getauscht, dass in der n-ten
Spaten ab dre n-ten Zeile, sodass das Betraglich größte Element in Zeile n
steht. 

\newpage

\begin{multicols}{2}

\section{QR-Zerlegung $A = QR$}

\begin{enumerate}
  \item Bestimme Matrizen Q und R durch Householder-Transformationen
  \item Löse $Qx = b$ ($Q^{-1} = Q^T$, also $c = Q^Tb$)
  \item Löse $Rx = c$ durch Rückwärtssubstitution
\end{enumerate}

\begin{enumerate}
  \item Bestimme Teilmatrix $A'^{(j-1)}$
  \item Berechne $v^{(j)} = {a'}_{I}^{(j-1)} + sign({a'}_{II}^{(j-1)}) \cdot \| {a'}_I^{(j-1)} \| e_I$
  \item Berechne $H'^{(j-1)} = I - \frac {2v^{(j)}v^{(j)T}} {v^{(j)T}v^{(j)}}$
  \item Bestime $H^{(j)} = \begin{pmatrix} 1 & 0 \\ 0 & H'^{(j-1)}\end{pmatrix}$
    \item Berechne $A^{(j)} = H^{(j)}A^{(j-1)}$ bis $A^{(j)} = R$
\end{enumerate}

\begin{align*}
  j = 1 \rightarrow j = k = min(m-1, n) \\
  Q^T = H^{(k)} \cdot ... \cdot H^{(2)} H^{(1)}
\end{align*}

\subsection{Minimale Fehlerquote}

\[
  |y_i - f(x_i)|_2^2 = \Sigma_{i=1}^{N} (y_i - f(x_i))^2
\]

\subsection{Ausgleichssystem}

Der Vektor $x \in \mathbb{R}^N$ löst genau dann $\|Ax -b \|_2 = min!$, falls er
$A^TAx = A^Tb$ (Normalgleichung) löst. 

\columnbreak

\section{Singilärwertzerlegung}

\begin{enumerate}
  \item Rechne $S = A^TA$
  \item Berechne EW und EV von S
  \item Bilde ONB $u_1, u_2, ..., u_N$ aus EV von S
  \item Berechne $\sigma_k = \sqrt{\lambda_k}$
  \item $U = \begin{pNiceArray}{c|c|c} U_1 & ... & U_k \end{pNiceArray} =
      diag(\sqrt{\lambda_1}, ..., \sqrt{\lambda_k}) = 
      diag(\sigma_1, ..., \sigma_k) = \Sigma$
  \item $V = A U \Sigma^{-1}$
\end{enumerate}
    
\subsection{Pseudoinverse }
$A^+ = U \Sigma^{-1} V^T$ ; ist A regulär dann gilt $A^{-1} = A^+$

\subsection{Normalengleichung}
$|Ax-b|_2=Min!$ durch $x = A^+b$ gelöst

\end{multicols}

\section{Hessenbergform (rechte-obere Dreiecksmatrix ab der unterren Nebendiagonale)}

\subsection{Tridiagonal (Nur Haupt- und Nebendiagonale)}

\begin{align*}
  \text{TeilmatrixA }&{A'}^{(j-1)} \\
  w^{(j)} &= {a'}_{I}^{(j-1)} + sign({a'}_{Ii}^{(j-1)}) \cdot \|{a'}_{I}^{(j-1)}\|_2 \cdot e_I \\
  {Q'}^{(j-1)} &= I - \frac {2 w^{j} w^{(j)T}} {w^{(j)T} w^{(j)}} \\
  Q^{(j)} &= \begin{pmatrix} 1 & 0 \\ 0 && {Q'}^{(j-1)} \end{pmatrix} \\
    H^{(j)} &= Q^{T(j)} A^{(j-1)} Q^{(j)}
\end{align*}

\subsection{Jacobi-Verfahren (Lösung von Ax =b) / Gesamtschrittverfahren}
\begin{align*}
  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$} \\
  x^{k+1} &= x^k + D^{-1} (b - Ax^k) & A = D + (L + U) \\ 
  & &\text{(diagonal + (strikte linke untere / rechte obere))}
\end{align*}

\subsection{Gauß-Seidel-verfahren / Einzelschrittverfahren}
\begin{align*}
  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) \\
  x^{k+1} &= x^k + (D + L)^{-1} (b - Ax^k)
\end{align*}

\subsection{CG-Verfahren}
\begin{align*}
  a
\end{align*}

\subsection{GMRES}
\begin{align*}
  a
\end{align*}

Energienorm $\|x\|_A = \sqrt{x^TAx}$

SKP $<x,y> = x^TAy$

\subsection{Krylov-Raum}

\section{Spline Interpolation}

\begin{align*}
  & s'(a) = v_0 \text{ und } s'(b) = v_N & \text{hermitisch} \\
  & s''(a) = s''(b) = 0 & \text{natürlich} \\
  & s'(a) = s'(b) \text{ und } s''(a) = s''(b) & \text{periodisch}
\end{align*}

\section{Newton-Verfahren}
\[
  x^{n+1} = x^n - \frac {f(x^n)} {f'(x^n)}
\]

\section{Quadraturformel}

Gewichte $b_k \in [0,1]$, Knoten $c_k \in [0,1]$, Stützstelle $a + c_k (b-a)$

\[
  \int_a^b f(x)dx \approx (b - a) \Sigma_{k=1}^s b_k f(a+c_k (b-a))
\]

\begin{tabular}{llll}
  Rechteckregel & $s=1$ & $b_1=1$ & $c_1=0$ \\
  Mittelpunktregel & $s=1$ & $b_1=1$ & $c_1 = \frac12$ \\
  Trapezregel & $s=2$ & $b_1 = b_2 = \frac12$ & $c_1 = 0, c_2 = 1$ \\
  Simpsonregel & $s=3$ & $b_1 = b_3 = \frac16, b_2 = \frac46$ & $c_1 = 0, c_2 = \frac12, c_3 = 1$
\end{tabular}

Symmetrische Quadraturformel $c_k = 1 - c_{s+1-k}$, $b_k = b_{s+1-k}$

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

\section{Polynom-Interpolation}

\subsection{Lagrange}

\begin{align*}
  & p(x) = \Sigma_{n=0}^N f_n L_n(x) & 
  L_n(x) = \Pi_{j=0, j \neq n}^N \frac{x - x_j}{x_n - x_j}
\end{align*}

Lebesque-Konstante
\[
  \Lambda_N := \max_{x \in [a,b]} \Sigma_{n=0}^{N} |L_n(x)|
\]

\subsection{Newton-Darstellung}

\begin{tabular}{c|c|c|c|c}
  $f_n$ & 1 & 6 & -3 & 3 \\
  \hline
  $x_n$ & -1 & 0 & 1 & 3
\end{tabular}

\[
\begin{NiceArray}{c|cccc}
  x_0 = -1 & f_0 = 1 & & & \\
  x_1 = 0 &  f_1 = 6 & \frac{1-6}{-1-0} = 5 & & \\
  x_2 = 1 & f_2 = -3 & \frac{6+3}{0-1} = -9 & \frac{5+9}{-1-1} = -7 & \\
  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}
\end{NiceArray}
\]

\begin{align*}
  p(x) &= 1 + 5(x-(-1)) -7(x-(-1))(x-0) + \frac{11}4 (x-(-1))(x-0)(x-1) \\
  p(x) &= f_{0,0} + f_{0,1}(x-x_0) + ... + f_{0,N}(x-x_0) \cdot ... \cdot (x-x_{N-1})
\end{align*}

\end{document}