% Dies ist Teil der Vorlesung Physik auf dem Computer, SS 2013
% Axel Arnold und Tobias Richter,  Universitaet Stuttgart.
% 
% Dieses Werk ist unter einer Creative Commons-Lizenz vom Typ
% Namensnennung-Weitergabe unter gleichen Bedingungen 3.0 Deutschland
% zugänglich. Um eine Kopie dieser Lizenz einzusehen, konsultieren Sie
% http://creativecommons.org/licenses/by-sa/3.0/de/ oder wenden Sie sich
% schriftlich an Creative Commons, 444 Castro Street, Suite 900, Mountain
% View, California, 94041, USA.
\documentclass[a4paper,fontsize=8pt,headsepline=true]{scrartcl}

% Font setup
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{icomma}
\usepackage{nicefrac}
\usepackage[final]{hyperref}
\usepackage[ngerman]{babel}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{longtable}
\usepackage{xspace}
\usepackage{color}
\usepackage{ifthen}
\usepackage{framed}
\usepackage{setspace}
% Contains the comment environment
\usepackage{verbatim}
\usepackage[left=1.0cm, right=1.0cm, top=1.5cm, bottom=1.5cm]{geometry}

\renewcommand{\arraystretch}{1.8}

\newcommand{\compressmatrix}{%
\renewcommand{\arraystretch}{1.0}}

\begin{document}
\pagestyle{empty}


\begin{longtable}{l|l}
		Gausselemination:	 &
  $\begin{array}{rcll}
    a_{ik}^{(r)} &=& a_{ik}^{(r-1)} -  l_{i}^{(r)}a_{r,k}^{(r-1)}
    & \quad\text{für}\; i=r+1(1)n, k=r(1)m\\[0.3em]
    b_{i}^{(r)} &=& b_{i}^{(r-1)} - l_{i}^{(r)} b_{r}^{(r-1)}
    & \quad\text{für}\; i=r+1(1)n \\[0.3em]
    a_{ik}^{(r)} &=& a_{ik}^{(r-1)},\quad b_{i}^{(r)} = b_{i}^{(r-1)}
    & \quad\text{sonst}
  \end{array}$
  mit $l_{i}^{(r)} = \frac{a_{ir}^{(r-1)}}{a_{rr}^{(r-1)}}.$ \\
  LU-Zerlegung: & $A = L\cdot R$ mit $r_{ij} = a_{ij}^{(r)}$ und
   $l_{ij} = \begin{cases}
   			l_j^{(i)} & \text{~für~} i \ge j\\
   			1         & \text{~für~} i = j
  \end{cases}$\\
		Lösung per LU Zerlegung:		 & $Ly=b\,,Ux=y\, \rightarrow Ax = LUx = Ly =b$\\\hline
		Cholesky: & Zerlege positiv semidefinites $A=R^TR$ \\
	&  $r_{11} = \sqrt{a_{11}} \text{
		und } r_{1k}=\frac{a_{1k}}{r_{11}}\,~\text{für}~ k>1$\\
							 & $ r_{ii} = \sqrt{a_{ii} - \sum_{l=1}^{i-1}r_{li}^2},\quad
							   r_{ik}=\frac{1}{r_{ii}}\left(a_{ik}-\sum_{l=1}^{i-1}r_{li}r_{lk}\right),~\text{für}~
							   k>i$\\\hline
		Horner Schema:		 & Auswerten eines Polynoms: $\sum_{i=0}^n c_i x^i = c_0 + x(c_1 + x(c_2 +
							   x(\ldots(c_{n-1} +xc_n)))) $ \\\hline
		Linearer Spline:	& $P_1(x)=\frac{(x_{i+1} - x)y_i+(x-x_i)y_{i+1}}{x_{i+1}
							   -x_i}\quad x_i\leq x < x_{i+1} $ \\\hline
		Kubischer Spline:	 & $P_3(x) = y_i + m(x-x_i) + \frac{1}{2}M_i(x-x_i)^2 +
							   \frac{1}{6} \alpha_i(x-x_i)^3 $ ~\text{für}~ $x_i\leq x<x_{i+1} $\\
							  & $\alpha_i = \frac{M_{i+1} - M_i}{x_{i+1} - x_i}$ für $i = 0(1)n-2$\\
							  & $m_i = \frac{y_{i+1} - y_i}{x_{i+1}-x_i} -
  \frac{1}{6}(x_{i+1}-x_i)(2M_i + M_{i+1})$ für $i = 0(1)n-2$\\
  & natürlich: {\small\compressmatrix $
  \begin{pmatrix}
    1      & 0         &           &           &           &         0 \\
    \mu_1  & 2         & \lambda_1 \\
           &           & \ddots    & \ddots    & \ddots \\
           &           &           & \mu_{n-2}  & 2         & \lambda_{n-2} \\
    0      &           &           &           & 0         & 1         \\
  \end{pmatrix}
  \begin{pmatrix}
    M_0\\
    M_1\\
    \vdots\\
    M_{n-2}\\
    M_{n-1}
  \end{pmatrix} \,=\,
  \begin{pmatrix}
    P_3''(x_0)\\
    6S_1\\
    \vdots\\
    6S_{n-2} \\
    P_3''(x_{n-1})
  \end{pmatrix}$}\\
	& mit
  $\lambda_i = \frac{x_{i+1}-x_i}{x_{i+1} - x_{i-1}}$,
  $\mu_i = \frac{x_i - x_{i-1}}{x_{i+1} - x_{i-1}}$ und
  $S_i = \frac{\frac{y_{i+1}-y_i}{x_{i+1} -
      x_i} - \frac{y_i-y_{i-1}}{x_i - x_{i-1}}}{x_{i+1}-x_{i-1}}.$
                        \\
	& periodisch: die inneren Zeilen periodisch fortsetzen\\\hline
		Nevill-Aitken-Schema:& Auswerten des interpolierenden Polynoms $P_{0,n}(x)$ durch $(x_i,\,y_i)$ an der Stelle $x$\\
	                    & $P_{i, 1}(x) = y_i,~i=0(1)n-1,\quad P_{i,k}(x) = \frac{P_{i, k-1}(x)(x_{i+k-1} - x) +
							   P_{i+1,k-1}(x)(x-x_i)}{x_{i+k-1} - x_i} $. \\\hline

		Chebyshev-Stützstellen & $ x_{k,n} = \cos{\frac{2k+1}{2n}\pi} $ \\\hline
		Fourierreihe:		 & $ f(t) = \sum_{n\in \mathbb{Z}} \hat{f}_n \exp{(\imath n
							   \omega t)}\quad$ mit
							   $\hat{f}_n=\frac{1}{T}\int_0^Tf(t)\exp{(-\imath n \omega
							   t)} \mathrm{d}t$, $\omega=\frac{2\pi}{T} $\\
							 & $\widehat{\left(\frac{df}{dt}\right)}_n =
								 \imath n\omega \hat{f}_n$ \\
		DFT:				 & $ \text{DFT}(f_k)_n = g_n = \sum_{k=0}^{N-1} f_k
							   \exp{( -\imath \frac{2\pi}{N} n k)},$ \\
							 & $\text{iDFT}(g_n)_k = f(t_k) =
							   \sum_{n=0}^{N-1} \frac{g_n}{N} \exp{(\imath \frac{2\pi}{N} n k )} $ \\\hline
		Faltung:			 & $ (f \star g)(t) := \int_{-\infty}^{\infty}
							   f(\tau)g(t-\tau) \textrm{d}\tau $ oder \\
& im Fourierraum $\widehat{(f\star g)}_k = \sqrt{2\pi}\hat{f}_k\hat{g}_k$
\\\hline
		Sch\"atzer & Mittelwert: $ \bar{x} = \frac{1}{N}\sum_{i=1}^N x_i $, Varianz
		$ \sigma^2 \approx \frac{N}{N-1}(\overline{x^2} -
							   {\bar{x}}^2) $ \\
	& quadratischer Fehler: $\sigma^2/N$, bzw. $2\tau_\text{int}\sigma^2/N$ bei korrelierten Daten \\\hline
		Autokorrelation:	 & normiert: $C_f(t)=\frac{\langle (f(t) - \langle f \rangle) (f(0) - \langle f \rangle) \rangle}{ \langle (f - \langle f \rangle)^2 \rangle}$,  diskret und unnormiert: $  C_f(k\Delta) \approx
  \frac{1}{N-k}\sum_{l=0}^{N-k}f(l\Delta)f\left((l+k)\Delta\right)$\\\hline
		Newtonverfahren:	 & Approximation durch Tangente $ x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} $, lokal quadratisch konvergent \\\hline
		Sekantenverfahren:	 & Approximation durch Sekante $ x_{n+1} = x_n - f(x_n) \frac{x_n - x_{n-1}}{f(x_n) -
							   f(x_{n-1})} $ \\\hline
		Bisektion:			 & $ f \in C([a,b]) \text{ und } f(a)f(b)<0 \rightarrow
							   m_n = \frac{a_n+b_n}{2}\quad$ \\
							 & wenn $ \begin{cases} 
								f(m_n)f(a_n) < 0 &\rightarrow b_{n+1} = m_n \\
								f(m_n)f(b_n) < 0 &\rightarrow a_{n+1} = m_n \\
							   \end{cases} $ bis $b_{n+1} - a_{n+1} < $ Toleranz \\
				& linear konvergent\\\hline
		MC Integration:		 & $\int_{x \in V} f(x) \textrm{d}x \approx \frac{|V|}N
							   \sum_{i=1}^Nf(\xi_i) \quad \text{mit } \xi_i \text{
							   gleichverteilte Zufallsvektoren in } V $ \\\hline
		zus. Trapezregel:	 & $ \int_a^b f(x)\textrm{d}x \approx \sum_{i=0}^{N-1}
							   \frac{x_{i+1} - x_i}{2} \left(f(x_i) + f(x_{i+1})\right) $ \\
	& $ = h\left(\frac{f(x_0)}{2} + \sum_{i=1}^{N-1} f(x_i) +
    \frac{f(x_N)}{2}\right)$ äquidistant, also mit $h=\frac{b-a}{N}$ und $x_i =
							   a+ h\cdot i$ \\\hline
		zus. Mittelpunktsregel: & $ \int_a^b f(x)\textrm{d}x \approx h
							   \sum_{i=0}^{N-1} f(x_i)$ äquidistant, also mit $h=\frac{b-a}{N}\text{ und } x_i =
							   a+ h(i+\frac{1}{2}) $ \\\hline
		finite Differenzen:  & $ f'(x_i) \approx \begin{cases} 
							   \frac{f(x_{i+1}) - f(x_{i-1})}{2h} = f'(x_i) +
							   \mathcal{O}(h^2)\text{ zentrale Differenz}\\
							   \frac{f(x_{i+1}) - f(x_{i})}{h} = f'(x_i) +
							   \mathcal{O}(h)\text{ linke Differenz} \\ \frac{f(x_i)
							   - f(x_{i-1})}{h} =f'(x_i)+ \mathcal{O}(h)\text{
							   rechte Differenz} \end{cases} $ \\
							 & $ f''(x_i) \approx \frac{f(x_{i+1} - 2f(x_i) +
							   f(x_{i-1}}{h^2} $ \\\hline
		Zufallsgenerator LCG & $ x_{i+1}=(ax_i+b) \mod m $ \\
		c rand:				 & $m=2^{31}$ $a=1.103.515.245$ und $b=12.345$ bzw.
						$m=2^{48}$, $a=25.214.903.917$ und $b=11$ \\
		MinStd:				 & $m=2^{31} - 1\quad a=16807\quad b=0$\\\hline
		Verz\"ogerter Fibonacci: & $ x_n=(x_{n-a}+x_{n-b}) \mod m, $ \\
							 & $ a=250\;b=103\;\text{ (Stoll Kirkpatrick), }a=521\;b=168\;$\\\hline
		Verwerfungsmethode:	 & Ziehen von ZZ gemäß einer beliebigen beschränkten Verteilung $\rho(p)\leq \rho_{\textrm{max}}$ auf $V$:\\[-0.5em]
						     & ziehe $p$ gleichverteilt aus $V$ und 
							    $u$ gleichverteilt auf $[0, \rho_{\textrm{max}}] $\\[-0.5em] 
							  & akzeptiere $p$, wenn $u\leq\rho(p) $\\\hline
		Box-Muller-Verfahren:& Erzeugen von normalverteilten Zufallszahlen $z, z'$ aus Standardzufallszahlen durch Inversion\\
	& ziehe $u\text{ und }u'$ gleichverteilt auf $[0,1]$
							   $\implies$ $\begin{cases} z=\sqrt{-2\ln(u)}\cos(2\pi u')\\
							   z'=\sqrt{-2\ln(u)}\sin(2\pi u')\end{cases}$ \\\hline
		Qualit\"atsanalyse	
	& Mittelwerttest: $B$ Blöcke der Größe $k$: $X_i := \frac{1}{k}\sum_{j=1}^k x_{j + (i-1)k}$ $\implies$ $\langle X_i\rangle = \frac{1}{2}$ bzw. $X_i \approx \frac{1}{2}$ für große $k$\\[-0.5em]
	& $\chi^2$-Test: Binnen der Daten in $M$ Bins mit Grenzen $b_i$ $\implies$ W-keit aus Bin $i$ zu ziehen ist $P_i = b_{i+1} - b_i$\\
	& $\implies$ $\chi^2 = \sum_{i=1}^M\frac{(N_i - N P_i)^2}{N P_i}$ misst, ob wirklich gleichverteilt in $[0,1]$\\
	& Varianztest: $  \frac{B}{B-1}\left(\overline{(X_i - \bar{X_i})^2}\right) \stackrel{!}{\approx} \frac{1}{12 k}$\\[-0.5em]
	& Poinc\'are-Schnitte: Auftragen von $x_i$, $x_{i+1}$, $x_{i+2}$ in Würfel, um Korrelationen an Ebenenbildung zu erkennen \\[-0.5em]
	& Fouriertest: 0-Amplitude der Fouriertransformierten $\approx N/2$, alle anderen $\approx 0$\\[-0.5em]
	& Autokorrelationstest: Eine Zufallsreihe ist $\delta$-korreliert \\\hline
		Random Walk			 & Zufällige Schritte $\pm 1$ $\implies$ Verteilung nach $t$ Schritten $   \rho(x, t) = \rho(x_t) \approx \frac{1}{\sqrt{2\pi t}}
  \exp\left(-\frac{x^2}{2t}\right) $\\\hline
		Jacobi-Verfahren	 & LDU-Zerlegung: $ x^{(i+1)} = (I-D^{-1}A)x^{(i)} +
							   D^{-1}b = -D^{-1}(L+U)x^{(i)} + D^{-1}b, $ \\
							 & $x_j^{(i+1)} =
							   \frac{1}{a_{jj}}\left(b_j - \sum_{k\neq j}a_{jk}x_k^{(i)}\right)$ \\\hline
		Gau\ss-Seidel-Verfahren /
		SOR					 & $ x_j^{(i+1)} =
							   \frac{\omega}{a_{jj}}\left(b_j -
							   \sum_{k=1}^{j-1}a_{jk}x_k^{(i+1)}
							   -\sum_{k=j+1}^{n}a_{jk}x_k^{(i)}\right) +
							   (1-\omega)x_j^{(i)}$,\quad $\omega=1$ ist Gauß-Seidel\\\hline
		Gram-Schmidt-Verfahren: & $A=QR$ mit $ q_1 = \frac{a_1}{||a_1||},\quad q_k = \frac{a_k -
								 \sum_{i=1}^{k-1}(a_k, q_i)q_i}{||a_k - \sum_{i=1}^{k-1}(a_k,
								 q_i)q_i||},$
							  \quad $r_{ik}=\begin{cases} (a_k,q_i)\text{ falls } i<k\\
								  ||a_k - \sum_{i=1}^{k-1}(a_k,q_i)q_i||\text{ falls } i=k\\
								  0\text{ sonst } \end{cases}$ \\\hline
	   Givensrotation: & Drehen eines Matrixelements auf Null durch 
			{\small\compressmatrix $G_{i,k,\phi} = \begin{pmatrix}
    I      & 0 & \ldots& 0&0\\
    0      & c & 0 & s & 0 \\
    \vdots & 0 & I & 0 & \vdots\\
    0      & -s & 0 & c & 0 \\
    0      & 0 & \ldots& 0 &I
  \end{pmatrix}$} mit $\begin{matrix}
	r'=\sqrt{1 + \left(\nicefrac{y}{x}\right)^2}\\
	c =\text{sgn}(x)\frac{1}{r'},\text{~und~}s = \frac{y}{|x|r'}\end{matrix}$
				\\\hline
		QR-Algorithmus:		& $A^{(k)} = Q^{(k)} R^{(k)}, \quad A^{(k+1)} =
							   R^{(k)}Q^{(k)}=\left(Q^{(k)}\right)^H A^{(k)}Q^{(k)} $
							   konvergiert, Eigenwerte von $A^{(0)}$ auf der Diagonalen\\\hline
		Inverse Iteration:	 & Eigenvektor zu approx. Eigenwert $\lambda$: $ \left(A-\lambda I\right) \tilde{x}^{(i+1)}=x^{(i)}, \quad
							   x^{(i+1)}=\frac{\tilde{x}^{(i+1)}}{||\tilde{x}^{(i+1)}||_2} $\\\hline
		Steepest descent:	 & Minimieren durch $x^{(k+1)} = x^{(k)} - \lambda \nabla f(x^{(k)}), \quad
							   \lambda>0$, aber klein\\\hline
		Armijo-Schrittweiten:& Gesicherter Abstieg durch $f(x+\lambda d) \leq f(x) + \alpha \lambda \nabla
							   f(x)^T d, \quad 0<\alpha<\frac{1}{2} $ \\\hline
		Simplex-Normalform	 & $ \min(c^Tx)\quad\text{unter NB~} x\geq 0,\quad Ax=b $
							   \\\hline
		Runge-Kutta:		 & Numerische Lösung von DGL 1. Ordnung $ \frac{dy}{dt}(t) =  F(t, y(t)),$ \\
							 & $\quad y_{n+1} = y_n + h\sum_{j=1}^s b_jk_j,$\\
							 & $ \quad\text{mit } k_j=F\left(t+h c_j, y_n + h \sum_{k=1}^s a_{jk}k_k\right)$. Explizit Verfahren, wenn $k_j$ aus $k_k$, $k<j$ zu berechnen\\\hline
		Butcher-Tableaus:	 & Allgemein \compressmatrix 
							   $\begin{array}{c|c} c & A \\\hline & b \end{array}$,
			                   Euler explizit \compressmatrix 
							   $\begin{array}{c|c} 0 & \\\hline & 1 \end{array}$,
							  Euler implizit 
							   $\begin{array}{c|c} 1 & 1 \\\hline & 1\end{array}$,
							  Runge-Kutta
							   $\begin{array}{c|cccc} 
							  	0 & & & & \\
							  	\nicefrac{1}{2} & \nicefrac{1}{2} & & & \\
							  	\nicefrac{1}{2} & 0 &  \nicefrac{1}{2} & & \\
							  	1 & 0 & 0 & 1 &\\\hline
							  	  & \nicefrac{1}{6} & \nicefrac{1}{3} &
							  	  \nicefrac{1}{3} & \nicefrac{1}{6}
							   \end{array}$
							   \\\hline
		Velocity-Verlet:	 & $\ddot x(t) = F[t, x(t)], \quad x_n \approx x(t_n),$ \\
							 & \"aquidistant mit Schrittweite h\\[-0.5em]
							 & $v_{n+\nicefrac{1}{2}} = v_n + \frac{h}{2}F(t_n, x_n) $\\[-0.5em]
							 & $x_{n+1}=x_n + hv_{n+\nicefrac{1}{2}} $ \\[-0.5em]
							 & $v_{n+1}=v_{n+\nicefrac{1}{2}} + \frac{h}{2}F(t_{n+1},
							 x_{n+1})$ \\\hline
\end{longtable}




\end{document}

