Initial commitHEADmain

4 files changed, 731 insertions, 0 deletions

diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..706a98f
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,301 @@
+## Core latex/pdflatex auxiliary files:
+*.aux
+*.lof
+*.log
+*.lot
+*.fls
+*.out
+*.toc
+*.fmt
+*.fot
+*.cb
+*.cb2
+.*.lb
+
+## Intermediate documents:
+*.dvi
+*.xdv
+*-converted-to.*
+# these rules might exclude image files for figures etc.
+*.ps
+*.eps
+*.pdf
+
+## Generated if empty string is given at "Please type another file name for output:"
+.pdf
+
+## Bibliography auxiliary files (bibtex/biblatex/biber):
+*.bbl
+*.bcf
+*.blg
+*-blx.aux
+*-blx.bib
+*.run.xml
+
+## Build tool auxiliary files:
+*.fdb_latexmk
+*.synctex
+*.synctex(busy)
+*.synctex.gz
+*.synctex.gz(busy)
+*.pdfsync
+
+## Build tool directories for auxiliary files
+# latexrun
+latex.out/
+
+## Auxiliary and intermediate files from other packages:
+# algorithms
+*.alg
+*.loa
+
+# achemso
+acs-*.bib
+
+# amsthm
+*.thm
+
+# beamer
+*.nav
+*.pre
+*.snm
+*.vrb
+
+# changes
+*.soc
+
+# comment
+*.cut
+
+# cprotect
+*.cpt
+
+# elsarticle (documentclass of Elsevier journals)
+*.spl
+
+# endnotes
+*.ent
+
+# fixme
+*.lox
+
+# feynmf/feynmp
+*.mf
+*.mp
+*.t[1-9]
+*.t[1-9][0-9]
+*.tfm
+
+#(r)(e)ledmac/(r)(e)ledpar
+*.end
+*.?end
+*.[1-9]
+*.[1-9][0-9]
+*.[1-9][0-9][0-9]
+*.[1-9]R
+*.[1-9][0-9]R
+*.[1-9][0-9][0-9]R
+*.eledsec[1-9]
+*.eledsec[1-9]R
+*.eledsec[1-9][0-9]
+*.eledsec[1-9][0-9]R
+*.eledsec[1-9][0-9][0-9]
+*.eledsec[1-9][0-9][0-9]R
+
+# glossaries
+*.acn
+*.acr
+*.glg
+*.glo
+*.gls
+*.glsdefs
+*.lzo
+*.lzs
+*.slg
+*.slo
+*.sls
+
+# uncomment this for glossaries-extra (will ignore makeindex's style files!)
+# *.ist
+
+# gnuplot
+*.gnuplot
+*.table
+
+# gnuplottex
+*-gnuplottex-*
+
+# gregoriotex
+*.gaux
+*.glog
+*.gtex
+
+# htlatex
+*.4ct
+*.4tc
+*.idv
+*.lg
+*.trc
+*.xref
+
+# hyperref
+*.brf
+
+# knitr
+*-concordance.tex
+# TODO Uncomment the next line if you use knitr and want to ignore its generated tikz files
+# *.tikz
+*-tikzDictionary
+
+# listings
+*.lol
+
+# luatexja-ruby
+*.ltjruby
+
+# makeidx
+*.idx
+*.ilg
+*.ind
+
+# minitoc
+*.maf
+*.mlf
+*.mlt
+*.mtc[0-9]*
+*.slf[0-9]*
+*.slt[0-9]*
+*.stc[0-9]*
+
+# minted
+_minted*
+*.pyg
+
+# morewrites
+*.mw
+
+# newpax
+*.newpax
+
+# nomencl
+*.nlg
+*.nlo
+*.nls
+
+# pax
+*.pax
+
+# pdfpcnotes
+*.pdfpc
+
+# sagetex
+*.sagetex.sage
+*.sagetex.py
+*.sagetex.scmd
+
+# scrwfile
+*.wrt
+
+# svg
+svg-inkscape/
+
+# sympy
+*.sout
+*.sympy
+sympy-plots-for-*.tex/
+
+# pdfcomment
+*.upa
+*.upb
+
+# pythontex
+*.pytxcode
+pythontex-files-*/
+
+# tcolorbox
+*.listing
+
+# thmtools
+*.loe
+
+# TikZ & PGF
+*.dpth
+*.md5
+*.auxlock
+
+# titletoc
+*.ptc
+
+# todonotes
+*.tdo
+
+# vhistory
+*.hst
+*.ver
+
+# easy-todo
+*.lod
+
+# xcolor
+*.xcp
+
+# xmpincl
+*.xmpi
+
+# xindy
+*.xdy
+
+# xypic precompiled matrices and outlines
+*.xyc
+*.xyd
+
+# endfloat
+*.ttt
+*.fff
+
+# Latexian
+TSWLatexianTemp*
+
+## Editors:
+# WinEdt
+*.bak
+*.sav
+
+# Texpad
+.texpadtmp
+
+# LyX
+*.lyx~
+
+# Kile
+*.backup
+
+# gummi
+.*.swp
+
+# KBibTeX
+*~[0-9]*
+
+# TeXnicCenter
+*.tps
+
+# auto folder when using emacs and auctex
+./auto/*
+*.el
+
+# expex forward references with \gathertags
+*-tags.tex
+
+# standalone packages
+*.sta
+
+# Makeindex log files
+*.lpz
+
+# xwatermark package
+*.xwm
+
+# REVTeX puts footnotes in the bibliography by default, unless the nofootinbib
+# option is specified. Footnotes are the stored in a file with suffix Notes.bib.
+# Uncomment the next line to have this generated file ignored.
+#*Notes.bib
diff --git a/LICENSE b/LICENSE
new file mode 100644
index 0000000..ee7d6a5
--- /dev/null
+++ b/LICENSE
@@ -0,0 +1,14 @@
+            DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE

+                    Version 2, December 2004

+

+ Copyright (C) 2004 Sam Hocevar <sam@hocevar.net>

+

+ Everyone is permitted to copy and distribute verbatim or modified

+ copies of this license document, and changing it is allowed as long

+ as the name is changed.

+

+            DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE

+   TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION

+

+  0. You just DO WHAT THE FUCK YOU WANT TO.

+

diff --git a/Makefile b/Makefile
new file mode 100644
index 0000000..9066144
--- /dev/null
+++ b/Makefile
@@ -0,0 +1,10 @@
+MAIN = sheet
+FLAGS = -pdf -lualatex
+
+all: 
+	latexmk $(FLAGS) $(MAIN)
+dev:
+	latexmk $(FLAGS) -pvc $(MAIN)
+clean: 
+	latexmk -C
+
diff --git a/sheet.tex b/sheet.tex
new file mode 100644
index 0000000..412ff23
--- /dev/null
+++ b/sheet.tex
@@ -0,0 +1,406 @@
+\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}