\documentclass[a4paper]{article}

\usepackage{ngerman}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{moreverb}
\usepackage{latexsym}

\title{3. "Ubungsblatt Numerik}
\date{Version vom \today}
\author{B"uch, Lutz (Gruppe 7)\\Rieck, Bastian (Gruppe 1)}

%
%\renewcommand{\familydefault}{\sfdefault}
%

\begin{document}

\maketitle

\section*{Aufgabe 1}

Die Vorw"artsanalyse betrachtet einen Algorithmus als gut beziehunsweise
stabil, wenn eine berechnete L"osung $\tilde{l}$ m"oglichst nahe an der
exakten L"osung $l$ liegt. Hierbei kommt es allerdings bei schlecht
konditionierten Problemen zum Versagen der Fehlerabsch"atzung. Denn
selbst bei einem sehr guten Algorithmus wird die Abweichung eines
schlecht konditionierten Problems zur exakten L"osung signifikant sein. 

Bei der R"uckw"artsanalyse wird die berechnete L"osung $\tilde{l}$ als
exakte L"osung zu gest"orten Ausgangswerten $\tilde{x_i}$ betrachtet.
Ergo werden durch Operationen entstehende Fehler zur"uckverfolgt und als
St"orungen der Eingabedaten interpretiert. Ein Algorithmus, der stabil
im Sinne der R"uckw"artsanalyse ist, weist somit bei der Approximation der
L"osung eines Problems nur eine geringe Abweichung vom Originalproblem
auf, selbst wenn dieses schlecht konditioniert sein sollte.

\section*{Aufgabe 2}

Zun"achst wird nachgewiesen, dass die L"osung eindeutig ist. Mit der
Basis $\{f_0(x) = 1,f_1(x) = x,f_2(x) = x^2\} \in P[x]_{ \leq 2}$ kann die folgende Matrix
aufgestellt werden:

\begin{align*}
A & = 
\begin{pmatrix}
f_0( x_0 ) & f_1( x_0 ) & f_2( x_0 )\\
f_0( x_1 ) & f_1( x_1 ) & f_2( x_1 )\\
f_0( x_2 ) & f_1( x_2 ) & f_2( x_2 ) 
\end{pmatrix}\\
& =
\begin{pmatrix}
1 & 0 & 0\\
1 & 2 & 4\\
1 & 3 & 9
\end{pmatrix}
\end{align*}

Es gilt $\det{A} = 6 (\neq 0)$. Damit ist das Interpolationspolynom
eindeutig bestimmt. Zur Berechnung werden die einzelnen
Lagrangepolynome $l_i(x)$ aufgestellt:

\begin{align*}
l_0(x) = \frac{( x - 2 )( x - 3 )}{ 6 } & = \frac{ x^2 - 5x }{6 } + 1\\ 
l_1(x) = \frac{( x - 0 )( x - 3 )}{ -2 } & = \frac{ 3x - x^2 }{2}\\
l_2(x) = \frac{( x - 0 )( x - 2 )}{ 3 } & = \frac{x^2 - 2x}{3}
\end{align*}

F"ur das Lagrangepolynom $P(x)$, welches die Bedingungen an den
St"utzstellen erf"ullt, gilt somit:

\begin{displaymath}
P(x) = \sum_{i = 0}^2 y_i l_i( x ) = - \frac{2}{3}x^2 + \frac{4}{3} x + 3
\end{displaymath}

\hfill $\Box$

\section*{Aufgabe 3}

\paragraph{1.:}

Durch partielle Integration, kann man beweisen, dass f"ur die
Vorw"artsrekursion folgende Beziehung zwischen $I_{n-1}$ und $I_n$ gilt:

\begin{align*}
I_n & = 1 - n I_{n-1}\\
I_0 & = 1 - \frac{1}{e} \approx 0.63212
\end{align*}

$\hfill \Box$

Berechnet man die Werte mit einem rekursiven Algorithmus, der durch
Gleitkommaoperationen einen bereits fehlerbehafteten Anfangswert hat, so
ergibt sich:

\begin{align*}
I_{10} & = 0.083773439833891\\
I_{20} & = -69478144.4601392
\end{align*}

Der relative Fehler ist f"ur $I_{20}$ also astronomisch gro"s.
 
\paragraph{2.:}

Der Fehler pflanzt sich nicht linear fort, sondern w"achst "uber alle
Schranken, genauer gesagt w"achst der Fehler so schnell wie die
Fakult"atsfunktion.

Sei $I_0$ der Startwert und $\tilde{I}_0$ der fehlerbehaftete Wert. Dann
gilt:

\begin{align*}
I_n & = 1 - n ( 1 - ( n - 1 )( 1 - ( n - 2 ) ) \dots ( 1 - I_0 )) \dots
)\\
\tilde{I}_n & = 1 - n ( 1 - ( n - 1 )( 1 - ( n - 2 ) ) \dots ( 1 -
\tilde{I}_0 )) \dots )
\end{align*}

Durch mehrfache Anwendung des Distributivgesetzes sieht man, dass sich
f"ur den Betrag des absoluten Fehlers Folgendes ergibt: 

\begin{displaymath}
\vert I_n - \tilde{I}_n \vert = n! \vert I_0 - \tilde{I}_0 \vert
\end{displaymath}

Damit gilt die Behauptung.

$\hfill \Box$

\section*{Aufgabe 4}

\end{document}