diff options
| -rw-r--r-- | .gitignore | 301 | ||||
| -rw-r--r-- | LICENSE | 14 | ||||
| -rw-r--r-- | Makefile | 10 | ||||
| -rw-r--r-- | sheet.tex | 406 |
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 @@ -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} |