numerische Mathematik

% Numerische Mathematik
% Kompilieren: xelatex -interaction=nonstopmode %.tex
\documentclass[a4paper,10pt]{scrartcl}
%XeLaTeX spezifisch
%\usepackage{sfmath}
\usepackage{amsmath, amsfonts} % ,amssymb, sfmath
\usepackage{mathspec} % Mathepaket fuer eigenen Font im Mathemodus
\setmathfont(Digits,Latin,Greek){Linux Libertine O} % ,Latin,Greek; \setmathsfont
%\usepackage[cm-default]{fontspec}
\usepackage{xunicode}
\usepackage{xltxtra}
% --------------------
\setromanfont[Mapping=tex-text]{Linux Libertine O} %serife Schrift; Numbers=OldStyle
\setsansfont[Mapping=tex−text]{Myriad Pro} %serifenlose Schrift
\setmonofont[Mapping=tex-text]{Droid Sans Mono} % monospace Schriftart
% --------------------
\usepackage{wrapfig} % umflossene Graphiken im Fliesstext
\usepackage[utf8]{inputenc} % UTF8-Kodierung
\usepackage{polyglossia} % Rechtschreibung; Ersatz fuer Babel
\setmainlanguage{german} % Option zu polyglossia
%\usepackage[ngerman]{babel}
\usepackage{latexsym}
\usepackage{array}          % wird von colortbl benoetigt
\usepackage{setspace}
\usepackage{graphicx}       % Einbindung von Grafiken
\usepackage{color}          % Vorder- und Hintergrundfarben
\usepackage{colortbl}       % ermoeglicht farbig hinterlegte Tabellen
\usepackage{float}
\setlength{\parindent}{0em}
\usepackage{tikz}                       % tikz-Grafikpackage
\usepackage[paper=a4paper,inner=20mm,outer=20mm,top=30mm,bottom=25mm, headheight=0mm, headsep=26mm]{geometry}
\usepackage{ulem}
\usepackage{booktabs}
\deffootnote{1em}{1em}{\textsuperscript{\thefootnotemark\ }}
\usepackage[pdfborder={0 0 0}]{hyperref}
\hypersetup
{%
pdftitle = {Numerische Mathematik},
pdfsubject = {Script},
pdfauthor = {knox},
pdfkeywords = {Numerische Mathematik, Mathe},
colorlinks = {false}
}
\usepackage{multicol}       % ermoeglicht 3 und mehr Spalten
\setcounter{tocdepth}{3}
\setcounter{secnumdepth}{3}
\usepackage{fancyhdr}       % eigenes Layout einbinden
\definecolor{dgreen}{rgb}{0.42,0.66,0.0}
\usetikzlibrary{shapes,arrows} % fuer Rete-Flussdiagramme
\usepackage{verbatim}            % fuer Rete-Flussdiagramme
\usetikzlibrary{mindmap,trees} % fuer mindmaps
\usepackage{trfsigns}            % for laplace symbole

%\usepackage{bbm}            % LaTeX support fuer fette cm fonts.
%\usepackage{textcomp}       % spezielle Zeichen im Text
%\usepackage{eurosym}        % Euro-Symbol
%\usepackage{ifthen}         % ifthen-Konstrukt für Schleifen-Befehl
%\usepackage{pifont}         % Sonderzeichen über \ding{nummer} und \Pisymbol{fontname}{nummer}
%\usepackage{calc}           % Berechnen von Laengen und Werten
%\usepackage{wrapfig}        % mehrspaltige Bilder
%\usepackage{listings}           % für Listings
%\usepackage[hyphens]{url}   % Urls anzeigen und trennen
%\usepackage[scaled]{helvet} % Helvetica, \sf-Schriftart
%\usepackage{lettrine}       % fuer Initiale
%\usepackage{titlesec}       % Anpassung der Ueberschriften
%\usepackage{framed}         % spezielle Rahmen (framed, shaded, leftbar)
%\usepackage{enumitem}       % Aufzaehlung ohne Einrueckung
%-------------------


\begin{document}


\definecolor{dgray}{rgb}{0.224,0.224,0.224}
\pagestyle{fancy}

\fancyhf{}
\renewcommand{\headrulewidth}{0.1pt}
\fancyhead[L]{\rmfamily \begin{huge}\textsc{\color{dgreen}{Numerische Mathematik}}\end{huge}\\
\vspace{5mm}
%\begin{tikzpicture} \begin{scope}[thick]
%       \draw[shift={(100:1cm)},xshift=10cm]node [right,text width=23cm,fill=orange!80,inner sep=0.5ex]{
\begin{scriptsize} \color{dgray}{version 2011.10.01} \end{scriptsize}   }
%};     \end{scope} \end{tikzpicture}}
\fancyhead[C]{\sffamily \begin{footnotesize} \color{dgray}{Lernhilfe} \end{footnotesize}}
\fancyhead[R]{\sffamily \begin{scriptsize}\color{dgray}{Seite \thepage} \end{scriptsize}}
\fancyfoot[c]{\color{gray}{ \sffamily \begin{scriptsize}License: GNU Free Documentation License\end{scriptsize} }}
\renewcommand\footrulewidth{0.1pt}


\newcommand{\eqhat}{\ensuremath{\widehat{=}}}


\section{Allgemeines}
\begin{itemize}
\item \textbf{Hauptsatz der Differential- und Integralrechnung:} Ist $ f: [a,b] \Rightarrow \mathrm{R} $ integrierbar, dann gilt $ \int \limits_{a}^{b} f(x) dx = F(b)-F(a) $, wobei F(x) eine Funktion $ F: [a,b] \Rightarrow \mathrm{R} $ ist, mit $ F'(x) = f(x) $.
\item \textbf{Terminiert:} Algorithmus bricht nach endlicher Zeit ab. Braucht geeignete Abbruchbedingungen.
\item \textbf{Determiniert:} Gleiche Eingaben f\"uhren zu gleichen Ausgaben.
\item \textbf{Deterministisch:} F\"ur jeden Schritt gibt es genau einen m\"oglichen Folgeschritt.
\item \textbf{Probabilistisch:} nicht deterministisch.
\end{itemize}

\subsection{Gleitkommazahlen}
\begin{itemize}
\item kleinste positive Gleitkommazahl: $ 1.000...0 \cdot 2^{-126}$
\item kleinste pos. Gleitkommazahl bei double: $ \varepsilon = 1.00...0 \cdot 2^{-52} \, \rightarrow \, 1+ \varepsilon = 1.00...1\cdot 2^{0} \neq 1$
\item float: $ x_{31} \eqhat $ Vorzeichenbit, 8 Bit Exponent, 23 Bit Mantisse; somit 24 bin\"are signifikante Stellen;
\end{itemize}

\subsection{Fehlerrechnung}

\begin{itemize}
\item absoluter Fehler: $ F_{\mathrm{a}} (x, fl(x)) = |x - fl(x)| $
\item relativer Fehler: $ F_{\mathrm{r}}(x, fl(x)) = \frac{|x - fl(x)|}{|x|} \hspace{1cm} \mathrm{mit} \, x\neq 0$
\item Max. relativer Fehler h\"angt nur von Basis B und Pr\"azision p ab.
\end{itemize}

\section{L\"osen von Gleichungen einer Variablen}
\subsection{Bisektionsverfahren}

\begin{itemize}
\item langsamstes Verfahren; Fehler: O($ 2^{-n} $)

        \textbf{\underline{Zwischenwertsatz:} \\
        Es sei $ f: \left[ a, b \right] \, \rightarrow \, \mathrm{R} $ stetig mit $ f(a) \cdot f(b) < 0 $, dann gibt es ein $ x_{0} \in \, ] a, b [ $ mit $ f(x_{0})=0 $.}
\end{itemize}

\subsection{Sekantenverfahren (Regula falsi)}
\begin{itemize}
\item schnelleres Verfahren als Bisektion, langsamer als Newtonverfahren; Variante des Newton-Raphson-Verfahrens\\
 \begin{center}
$x_{n+1} = x_{n} - \frac{f(x_{n})\cdot (x_{n}- x_{n-1})}{f(x_{n}) - f(x_{n-1})} \hspace{1cm} n=1,2,... $
\end{center}
\textbf{Regula-Falsi:} \\
-- Variante des Sekantenverfahrens mit $ f(x_{n-1}) \cdot f(x_{n}) \leq 0 $, NST zwischen $ x_{n} $ und $ x_{n-1} $.
\item \textbf{Aufgabe:} Beschreibe Iterationsformel des Sekantenverfahrens und gib Vor- und Nachteil gegen\"uber des Newtonverfahrens an.\\
In der Newtonformel approximiert man f\"ur $n \geq 2$ \\
$ f'(x_{n-1}) = \lim\limits_{x \rightarrow x_{n-1}} \cdot \frac{f(x) - f(x_{n-1})}{x-x_{n-1}} \approx \frac{f(x_{n-2})-f(x_{n-1})}{x_{n-2}-x_{n-1}} $.\\
Diesen Ausdruck setzt man in die Newtongleichung ein und erh\"alt $ x_{n} = x_{n-1} - \frac{f(x_{n-1}) \cdot (x_{n-2}-x_{n-1})}{f(x_{n-2})-f(x_{n-1})} $.\\
Vorteil: Diese Formel ist auch f\"ur stetige, aber nicht differenzierbare Funktionen anwendbar.\\
Nachteil: Konvergenzgeschwindigkeit geringer als beim Newtonverfahren.
\end{itemize}

\subsection{Newton-Raphson-Verfahren}

\begin{itemize}
\item schnellstes Verfahren\\
\item $ x_{1}= x_{0} - \frac{f(x_{0})}{f'(x_{0})} $ \hspace{2cm} $ x_{n} = x_{n-1} -  \frac{f(x_{n-1})}{f'(x_{n-1})} $ \\
\item Nachteile: Anzahl Schritte, um $ \mid x_{n} - x_{N} \mid < \varepsilon $ zu erreichen, nicht vorhersagbar; \\
f muss differenzierbar sein; \\
Bei Abbruchkriterium $ \mid x_{n} - x_{n-1} \mid < \varepsilon $ keine Sicherheit, dass  $ \mid x_{n} - x_{N} \mid < \varepsilon $ gilt.
\end{itemize}


\section{Numerische L\"osung linearer Gleichungssysteme}
\subsection{Allgemeines}

\begin{itemize}
\item Lineare Gleichung: $ a_{1}x_{1} + a_{2}x_{2}+ ... + a_{n}x_{n} = C_{1} $\\
        $ a_{11}x_{1} + a_{22}x_{2}+ ... + a_{nn}x_{n} = C_{2} $\\
homogene L\"osung: $ c=0 $.\\
inhomogene L\"osung: $ c\neq 0$.
\item  \textbf{Normen:} \\
\hspace*{2 cm}\begin{tabular}{lllll}
 1-Norm:& $ ||x||_{1}$ & = & $ |x_{1}| + |x_{2}|+ ... + |x_{n}|$ & (Spalte betrachten) $ \diamondsuit $\\
 Euklidische Norm:& $ ||x||_{2}$ & = & $\sqrt{x_{1}^{2} + x_{2}^{2}+...+x_{n}^{2}}$ &(Spalte betrachten) $ \bigcirc $ \\
 Maximumnorm: & $ ||x||_{\infty}$ & = & $\quad \mathrm{max}{\left\lbrace |x_{i}|; \, 1 \le i \le n\right\rbrace }$ &(Zeile betrachten) (Quadrat) \\
\end{tabular}
\\
Jede Norm ist \"aquivalent.
\end{itemize}

\subsection{Spaltenpivotisierung}
-- dient zur Fehlervermeidung;\\
Versucht, Zahlen in Matrix betragsm\"assig klein zu halten.\\
$ \Big| \frac{a_{i+1,i}}{a_{ii}} \Big| \le 1, \, \Big| \frac{a_{i+2,i}}{a_{ii}} \Big| \le 1, \, ... $\\

Skalierte Spaltenpivotisierung:\\
-- bei Versagen der Spaltenpivotisierung vorher skalieren;\\
-- Koordinaten des St\"orvektors bleiben beim Skalieren unber\"ucksichtigt.\\
-- Bsp.: $ a_{11} \eqhat \frac{|a_{11}|}{|a_{12}|} $, dann ggf. Zeilen tauschen.\\
-- Matrix allgemein: $ \left( \begin{array}{cc} a_{11} & a_{12} \\ a_{21} & a_{22}
\end{array}  \right)  $
\subsection{Jacobi-Verfahren (Gesamtschrittverfahren)}
-- iteratives Verfahren;\\
-- statt $ A \cdot x = b \, \Rightarrow \, x= M_{x} + d$\\
-- Startvektor $ x_{0} \, \Rightarrow \, x_{n+1} = M_{xn} +d $\\
-- erfolgreich, wenn Vektoren $ (x_{n})_{n \in \mathrm{N}} $ gegen Fixpunkt konvergieren.\\
\begin{center}
$  x_{i}^{(\mu + 1)} = \frac{b_{i}}{a_{ii}} - \sum_{k=1, k \neq i}^{n} \frac{a_{ik}}{a_{ii}} \cdot x_{k}^{(\mu)} \hspace{1cm} (i = 1, 2, ..., n) $
\end{center}

\subsection{Gauss-Seidel-Verfahren (Einzelschrittverfahren)}
\begin{itemize}
\item $ x_{i}^{(\mu +1)} = \frac{b_{i}}{a_{ii}} - \sum_{k=1}^{i-1} \frac{a_{ik}}{a_{ii}} x_{k}^{(\mu +1)} - \sum_{k=i+1}^{n} \frac{a_{ik}}{a_{ii}} x_{k}^{(\mu)} $\\
$ (i=1,2,...,n; \, x_{1}^{(0)}, x_{2}^{(0)},...,x_{n}^{(0)} \, \mathrm{gegebene \, Startwerte}; \, \mu = 0,1,2,...) $
\end{itemize}

\subsection{Interpolation und Approximation von Funktionen}
\subsubsection{Lagrange-Form des Interpolationspolynoms}
\begin{itemize}

\item $ L_{n} (x) := \sum \limits^{n}_{i=0} f(x_{i}) \cdot L_{n,i}(x) $
\item $ L_{n,i} = \prod^{n}_{k=o; k \neq i}  \frac{x - x_{k}}{x_{i}-x_{k}} $ \\
\item $ L_{n, i} (x) \,\qquad (0 \leq i \leq n) $ \hspace{2cm} mit $ n \eqhat $ Anzahl der Punkte/NST; $ i \eqhat $ Laufindex
\\
Grad 0, wenn alle y-Werte gleich sind; z.B. (1;2), (3;2), ...\\
Grad 1, wenn alle Punkte auf Gerade;
\item Grad = n-1, d.h. Polynom vom Grad n hat n+1 Koeffizienten, also n+1 Freiheitsgrade.
\end{itemize}

$\begin{array}{l|lllll}
x_{i} & f_{i} &  &  &  &  \\
\hline
x_{0} & P_{0} &  &  &  &  \\
x_{1} & P_{1} &  {\overset{\searrow}{\rightarrow}} P_{0,1} & \rightarrow L_{1} &  &  \\
x_{2} & P_{2} & {\overset{\searrow}{\rightarrow}}P_{1,2} & {\overset{\searrow}{\rightarrow}} P_{0,1,2} & \rightarrow L_{2} &  \\
x_{3} & P_{3} & {\overset{\searrow}{\rightarrow}}P_{2,3} & {\overset{\searrow}{\rightarrow}}P_{1,2,3} & {\overset{\searrow}{\rightarrow}} P_{0,1,2,3} & \rightarrow L_{3}
\end{array} $ \hspace{1cm}
wobei z.B. $ P_{0,1}: \frac{f(x_{1}) - f(x_{0})}{x_{1} - x_{0}}  $ ist.

Fehlerterm: $ f(x) - p(x) = \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod \limits^{n}_{i=0}(x-x_{i}) $\\
\\
Berechnung mit dividierten Differenzen:\\
 $ f[x_{i}, ..., x_{i+k}] = \frac{f[x_{i+1}, ..., x_{i+k}] - f[x_{i}, ..., x_{i+k-1}]}{x_{i+k}-x_{i}} $

\subsubsection{Neville}

\begin{tikzpicture}
        \begin{scope}[thick]
        \draw[shift={(60:1cm)},xshift=5cm]
                node [right,text width=17cm,fill=gray!20,inner sep=2ex]
        {
Gegeben seien Wertepaare $(x_{i}, f_{i}) $ f\"ur $ i=0,...,n $. Man definiert eine Folge von Polynomen rekursiv wie folgt:\\
$\qquad p_{i0}(x) := f_{i}, $ f\"ur $ i=0,...,n $\\

f\"ur $ k=1,...,n $ und $ i=0,...,n: $\\

$ \qquad p_{ik}(x):= p_{i+1,k-1}(x)+\frac{x_{i+k}-x}{x_{i+k}-x_{i}(p_{i,k-1}(x)-p_{i+1,k-1}(x))} $\\

Dann gilt: \\
$ p_{0n} $ ist das Interpolationspolynom zu den gegebenen Wertepaaren.\\
        };
        \end{scope}
        \end{tikzpicture}

\begin{itemize}
\item bietet sich an, wenn man ein Interpolationspolynom nur an einer Stelle auswerten will;
\item Aufwand f\"ur n+1 St\"utzstellen ist n(n+1) Punktoperationen;
\end{itemize}

\subsubsection{Newton-Cotes-Formeln}
\begin{itemize}
\item Fehler: $O(n^2)$
\item $ p(x) = \sum \limits_{i=0}^{n}f[x_{0},...,x_{i}] \cdot \prod \limits_{j=0}^{i-1}(x-x_{j}) $
\item Interpolation, rekursiv, Koeffizienten sind dividierte Differenzen
\end{itemize}

\section{Numerische Integration und Differentation}
\subsection{Newton-Cotes-Formel}
$ \int \limits_{a}^{b} f(x) dx = \int \limits_{a}^{b} L_{n} (x) dx + $ Fehlerterm \hspace{1cm} // Schrittweite $ h=\frac{b-a}{N} $\\
Fehlerterm: $ \int \limits_{a}^{b} \frac{f^{(n+1)}(\xi(x))}{(n+1)!} \cdot \prod \limits_{i=0}^{n}(x-x_{i}) dx $

\subsection{Sehnentrapezformel}
Fehler: $O (h^{3}) $\\
f\"ur n=1 (1. Grad): $ \int \limits_{a}^{b} f(x) dx \approx \frac{h}{2} (f(a) +2f(a+h) + f(b)) - \underbrace{\frac{1}{12} \cdot f'' (\xi) \cdot h^{3}}_{\mathrm{Fehlerterm}} $ \hspace{1cm} //  Schrittweite $ h=\frac{b-a}{N} $\\

\subsection{Simpsonformel}
entspricht Newton-Cotes-Formel f\"ur n=2 (Grad 2)\\
Fehler: $ O(h^{5}) $\\
$ \int \limits_{a}^{b} f(x) dx = \frac{h}{3} (f(a) + 4f(a+h) +f(b)) $ \hspace{1cm} //  Schrittweite $ h=\frac{b-a}{2} $\\
Fehlerterm: $ -\frac{f^{(4)} (\xi)\cdot h^{(5)}}{90} $ \hspace{1cm} // $ a<\xi < b $\\
Idee der Simpsonformel: Funktion f auf Intervall [a,b] durch $ L_{2} $ zu interpolieren, wenn man St\"utzstellen a, a+h und b ausw\"ahlt.

\section{Differentialgleichungen}
\subsection{Eulerverfahren}
Fehler: $ O(h) $ \hspace{2 cm} $ h := \frac{t_{1}-t_{0}}{N} $ \hspace{2 cm} $ y_{i+1} = y_{i} + h\cdot f(\tau_{i}, y_{i}) $\\
\\
Eulerverfahren muss N-mal angewandt werden.\\
\\
\definecolor{hgrau}{gray}{0.9}
\begin{tabular}{>{\columncolor{hgrau}}llllll}
\toprule
$\mathbf{i}$ & 0 & 1 & 2 & 3 & 4 \\
\midrule
$\mathbf{\tau_{i}}$  & $ t+ih $ & $ t+(i+1)h $ & ... & ... & ... \\
$\mathbf{k=f(\tau_{i},y_{i})}$ & \begin{footnotesize}aus Richtungsfeld\end{footnotesize} & $ (\tau_{i}, \mathrm{voriges} \, y_{i+1} )$ & ... & ... & ... \\
$\mathbf{y_{i+1}}$ & $y_{i} + h \cdot f (\tau_{i}, y_{i}) $ & \begin{footnotesize}voriges \end{footnotesize}$y_{i+1} + h\cdot $\begin{footnotesize}oberes \end{footnotesize}$ f(\tau_{i}, y_{i}) $ & ... & ... & \cellcolor[gray]{0.9}{{\begin{footnotesize}Ergebnis $(y1) \approx$...\end{footnotesize}}} \\
\bottomrule
\end{tabular}


\subsection{Runge-Kutta-Verfahren}
Fehler: $ O(h^{4}) $, d.h. bei Halbierung der Schrittweite nur ca. 1/16 Fehler (Fehler proportional zu $ h^{4} $);\\
\\
Schritt 1:\\
$\begin{array}{llll}
x & y & k=h\cdot f(x,y) \\
\hline
x_{0} & y_{0} & k_{1} & \\
x_{0}+h/2 & y_{0}+k_{1}/2 & k_{2} &  x_{1} = x_{0}+h  \\
x_{0} + h/2 & y_{0}+k_{2}/2 & k_{3} &  \\
x_{0} +h & y_{0}+k_{3} & k_{4} & \\
\end{array} $
\\
\bigskip
\\
Schritt 2:\\
$y_{1} = y_{0} + \frac{1}{6} \cdot h \cdot (k_{1}+2k_{2}+2k_{3}+k_{4}) $\\

\end{document}