% !TeX root = main.tex
\newcommand{\norm}[1]{\Vert #1 \Vert}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Konsistenz und Konvergenz}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%###################################################################
\begin{frame}[fragile]{Konsistenz und Konvergenz}
Explizite Einschrittverfahren
\begin{align}
  \label{eq:einschritt}
  u_0    &= y_0\\
  u_{i+1}&= u_i + h_i \Phi(t_i,u_i,h_i) \qquad i = 0,1,2,\dots, n-1
\end{align}

\metroset{block=fill}
\begin{Definition}[Konsistenz]
  Das Einschrittverfahren \eqref{eq:einschritt} zur Lösung der DGL 
  $\dot{y} = f(t,y)$ mit hinreichend oft differenzierbarer Funktion $f$ heißt \alert{konsistent}, 
  wenn für alle $t\in[t_0,t_0+T]$ gilt, dass
  \begin{equation}
    \lim_{h\to 0 } \tau(t,h) = \lim_{h\to 0}\frac{y(t+h) - y(t)}{h} - \Phi(t,y(t),h) = 0\,.
  \end{equation}
  Das Verfahren heißt konsistent von der Ordnung $p\in \mathbb{N}$, falls
  \begin{equation}
    \tau(t,h) = \mathcal{O}(h^p)\,.
  \end{equation}
  \end{Definition}
\end{frame}
%###################################################################

%###################################################################
\begin{frame}[fragile]{Konsistenz und Konvergenz}
Explizite Einschrittverfahren
\begin{align}
  \label{eq:einschrittverfahren}
  u_0    &= y_0\\
  u_{i+1}&= u_i + h_i \Phi(t_i,u_i,h_i) \qquad i = 0,1,2,\dots, n-1
\end{align}

\metroset{block=fill}
\begin{Definition}[Konvergenz]
  Das Einschrittverfahren \eqref{eq:einschrittverfahren} zur Lösung der DGL 
  $\dot{y} = f(t,y)$ mit hinreichend oft differenzierbarer Funktion $f$ heißt \alert{konvergent}, 
  wenn für alle $t$ im Lösungsintervall gilt:
  \begin{equation}
    \lim_{h\to 0 } |e_h(t)| = \lim_{h\to 0}|y(t) - u_h(t)| = 0\,.
  \end{equation}
  Das Verfahren heißt konvergent von der Ordnung $p\in \mathbb{N}$, falls
  \begin{equation}
    e_h(t) = \mathcal{O}(h^p)\,
  \end{equation}
  für alle $t$ gilt. Hierbei ist $u_h(t)$ die numerische Lösung aus dem Einschrittverfahren \eqref{eq:einschrittverfahren}.
  \end{Definition}
\end{frame}
%###################################################################


%###################################################################
\begin{frame}[fragile]{Konsistenz und Konvergenz}

\metroset{block=fill}
\begin{Theorem}[Konvergenz des Einschrittverfahrens]
  Betrachte das Einschrittverfahren \eqref{eq:einschrittverfahren} zur Lösung des AWPs
  $\dot{y} = f(t,y), y(0) = y_0$.
  Die Verfahrensfunktion $\Phi(t,y,h)$ sei Lipschitzstetig in y, d.h.
  \begin{equation}
    \norm{\Phi(t,y_1,h)-\Phi(t,y_2,h)} \le L \norm{y_1-y_2}
  \end{equation}
  für eine beliebige Norm $\norm{\cdot}$ auf $\mathbb{R}^n$.
  Dann gilt:

\alert{Ist das Verfahren konsistent mit der Konsistenzordnung $p\in \mathbb{N}$, 
dann ist es auch  Konvergent mit Ordnung $p$}

Mit dem maximalen Diskretisierungsfehler $\tau_h = \max_{t\in[t_0,t_0+T]} |\tau(t,h)| $
gilt für den globalen Fehler die Abschätzung:
\begin{equation}
  \norm{e_h(t_i)} = \norm{y(t_i)-u_h(t_i)} \le (\norm{y(t_0) - u_h(t_0)} + (t_i - t_0)\tau_h) e^{L(t_i-t_0)}.
\end{equation}
  \end{Theorem}
\end{frame}
%###################################################################




%###################################################################
\begin{frame}[fragile]{Aufgabe 1}

Sei $h>0$ und $t_i = ih$, für $i=0, 1, 2, \ldots, N$.
 Das Verfahren von Heun angewendet auf die DGL
$\dot{y}(t) = f(t,y(t)), t>0$ mit AW $y(0)=y_0$
  liefert die Iteration
\begin{align*}
\tilde{u}_{i+1} &= u_i + h f(t_i, u_i)\\
u_{i+1} &= u_i + h\frac{f(t_i, u_i)+f(t_{i+1}, \tilde{u}_{i+1})}{2},
\end{align*}
wobei $u_0=y_0$.
\begin{enumerate}
\item Nehmen wir an, die Funktion $f:\mathbb{R}\times\mathbb{R}\to \mathbb{R}$ genüge einer Lipschitzbedingung im zweiten Argument mit  Lipschitzkonstante $L$.
Zeigen sie, dass dann  die Inkrementfunktion $\Phi(t, y, h)$ des Verfahrens von
Heun ebenfalls einer Lipschitzbedingung genügt und bestimmen Sie die 
dazugehörige Lipschitzkonstante.
\item Zeigen Sie, dass die Heun-Iteration des Anfangswertproblems \label{eq:Anfangswertproblem} mit $f(t,y(t))=2y(t)$,  $y_0 = 2$ gegen die L\"osung des Anfangswertproblems konvergiert.
\end{enumerate}

\end{frame}
%###################################################################

%###################################################################
\begin{frame}[fragile]{Lösung Teilaufgabe 1}
$\Phi(t,y,h)=\frac{1}{2}[f(t,y) + f(t+h, y+ hf(t,y)) ]$

 Lipschitzbedingung $|f(t,y_1)-f(t,y_2)| \leq L |y_1-y_2|$ für alle $t$, $h$.\\
%$\Phi(t,y,h)=\frac{1}{2}[f(t,y) + f(t+h, y+ hf(t,y)) ]$
\[
\begin{aligned}
 |&\Phi(t,y_1,h)-\Phi(t,y_2,h) |=
 \only<1>{&\alert{\dots\le \quad??\quad\le \dots\le} L |y_1-y_2|}
 \only<2>{\\
 &\frac{1}{2}|f(t,y_1) -f(t,y_2)  + f(t+h, y_1+ hf(t,y_1))- f(t+h, y_2+ hf(t,y_2)) |\\
 & \leq \frac{1}{2}\left(L|y_1 -y_2| + |f(t+h, y_1+ hf(t,y_1))- f(t+h, y_2+ hf(t,y_2)) |\right)\\
 &\leq \frac{1}{2}\left(L|y_1 -y_2| + L|y_1+ hf(t,y_1) -y_2+ hf(t,y_2) |\right)\\
  &\leq \frac{1}{2}\left(2L|y_1 -y_2| + Lh|f(t,y_1) -f(t,y_2) |\right)\\
  &\leq \frac{1}{2}\left(2L|y_1 -y_2| + L^2h|y_1 -y_2|\right) \\&\leq \frac{2L+L^2h}{2}|y_1 -y_2|}
\end{aligned}
\]
\only<1>{\begin{center}\alert{Your Turn !}\end{center}}
\end{frame}
%###################################################################


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[fragile]{Lösung Teilaufgabe 2}
Lösung des AWPs:
 \[
y(t)=2\exp(2t)
\]
\[
\begin{aligned}
 u_0&=2\\
 %\tilde{u}_1&=u_0+hf(u_0)=2+h f(2) = 2 +2\cdot 2h =u_0+h2u_0= u_0 (1+2h) \\
 \tilde{u}_1&=\visible<2>{u_0+hf(u_0)=u_0 (1+2h) }\only<1>{\alert{\dots ? \dots}}\\
 %u_1&=2+\frac{h}{2}\left(f(u_0) + f(\tilde{u}_1)\right)=2+\frac{h}{2}\left(4 + 4+8h)\right) = 2+h(4+4h)\\
 u_1&=\only<2>{u_0+\frac{h}{2}\left(2u_0 + 2\tilde{u}_1\right)=u_0+h(u_0 + u_0 (1+2h))=u_0(1+2h+2h^2)}
 \hspace{3.5cm}\only<1>{\alert{\dots ? \dots}}
 \\
% \tilde{u}_2&=u_1+hf(u_1)=2+4h+4h^2 + h \left(4+4h)+h f(2+h(4+4h)\right) = ...\\
 \tilde{u}_2&= \visible<2>{u_1+hf(u_1)=u_1(1+2h)=u_0(1+2h+2h^2)  (1+2h) } \\%
 %=u_1+hf(u_1)=2+4h+4h^2 + h \left(4+4h)+h f(2+h(4+4h)\right) = ...\\
 u_2&=\visible<2>{u_1+\frac{h}{2}\left(2u_1 + 2\tilde{u}_2\right)=u_1(1+2h+2h^2) = u_0(1+2h+2h^2)^2 } \\
 \vdots\\
 u_k& =\visible<2>{ u_0(1+2h+2h^2)^k } \\
\end{aligned}
\]
\only<1>{Wie verhält sich $u_h(\hat{t})$, wenn $h \to 0$ und $N\to \infty$, wobei $Nh=t$?}
\end{frame}
\begin{frame}[fragile]
We denote by $N(h)\in \mathbb{N}$ the number of steps that are necessary to attain 
or overtake a given (and fixed) time $\hat{t}$ with steps of size $h$,
i.e. $N(h)\equiv\ceil{\hat{t}/h}$.
It is clear that $N(h)\cdot h \to \hat{t}$ as $h\to 0$, and $N(h)\to \infty$ as $h\to 0$.
Therefore the numerical solution at the time 
$\tilde{t}(h)\equiv\ceil{\hat{t}/h} h \approx \hat{t}$ is given by
\[
u_h(\tilde{t})=u_{N} = u_0\left(1+2\frac{\tilde{t}}{N}+2\left(\frac{\tilde{t}}{N}\right)^2\right)^N 
\]
which tends to
\begin{equation}
  \label{eq:lim}
\lim\limits_{N\to \infty}u_0(1+2\frac{\hat{t}}{N}+2\left(\frac{\hat{t}}{N}\right)^2)^N = u_0\exp(2\hat{t}) =2\exp(2\hat{t})
\end{equation}
as $h\to 0$.
Since this is valid for any time $\hat{t}$, it follows that the numerical solution converges to the analytical one as $h\to 0$.
\end{frame}
\begin{frame}
To show \eqref{eq:lim} we use: $\log(\lim_{N\to \infty} a_N)=\lim_{N\to\infty} \log(a_N)$
if $\lim_{N\to\infty} a_N=a$ and $f$ continous at $a$. 
\begin{align}
  \lim_{N\to\infty}\log(u_h(t)/u_0)&=\lim_{N\to\infty}\log(1+2(t/N)+2(t/N)^2)^N)\\
                               &=\lim_{N\to \infty} \frac{ \log{(1+2(t/N)+2(t/N)^2)}}{1/N}\\ 
                   &\overset{\text{l'hospital}}{=}\lim_{N\to\infty}
                   \frac{2t + 4t/N}{1+2(t/N)+2(t/N)^2}=2t\\
                   \Rightarrow \log(\lim_{N\to\infty} u_h(t)/u_0 ) &= \lim_{N\to\infty}\log(u_h(t)/u_0)=2t\\
                   \Rightarrow \lim_{N\to\infty} u_h(t) & =u_0e^{2t}\\
\end{align}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Zahlendarstellung}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\renewcommand{\b}[1]{{\color{blue}#1}}
\renewcommand{\r}[1]{{\color{red}#1}}
\providecommand\g{} % to avoid error if \g is not yet defined 
\renewcommand{\g}[1]{{\color{green}#1}}
%###################################################################
\begin{frame}[fragile]{Aufgabe 2}
\metroset{block=fill}
\begin{Theorem}
  Sei $p\ge 2$  eine ganze Zahl und $r \in\mathbb{R},r\ge 0 $. Dann gibt es ein
  $k \in \mathbb{Z}$ und eine unendliche Folge $z_1, z_2, z_3,\dots \in{0,1,2,\dots,p-1}$
  mit $z_1\ne 0$, sodass
  \begin{align}
    r &= \b{z_1}*\r{p^{k-1}} + \b{z_2}*\r{p^{k-2}} + \b{z_3}*\r{p^{k-3}} + \dots\\
    r &= (\b{z_1}*\r{p^{-1}} + \b{z_2}*\r{p^{-2}} + \b{z_3}*\r{p^{-3}} + \dots) * \r{p^k}
  \end{align}
  Die Folge $\b{z_j}$ ist eindeutig, wenn man $\b{z_j}=\r{p}-1$ für alle $j\ge j_0$ ausschließt.
\end{Theorem}
\begin{table}[hp!]
  \centering
  \begin{tabular}{p{4cm} l}
    \textbf{Notation:}& $ r = (\b{z_1 z_2 \dots z_k.z_{k-1} z_{k-2}}\dots)_\r{p}$ , $k>0$\\
  \textbf{Normal. Gleitpktdarst.:}& $ r = (\underbrace{\b{0.z_1 z_2 z_3 \dots}} _{\text{Mantisse}})_\r{p}
  *\r{p^\g{k}}$ 
  \end{tabular}
\end{table}
\hspace{1cm}$\r{p} \widehat{=}$ Basis   \hspace{1cm}$\g{k}\widehat{=} exponent$\hspace{1cm}
  $\b{z} \widehat{=}$ Ziffer\\
  
  


\end{frame}
%###################################################################

%###################################################################
\begin{frame}[fragile]{Aufgabe 2}
\metroset{block=fill}
Transformieren Sie die folgenden Dezimalzahlen in ihre
Binär- bzw. Hexadezimaldarstellung (d.h. $p = 2, 16$)
\begin{enumerate}
\item $x = 12.125$
\item $x = 0.1$
\end{enumerate}
\begin{alertblock}{Frage}
  Warum ergibt $20\cdot({0.1+0.1+0.1-0.3})^{1/10} = 0.47..$ in Matlab ?
\end{alertblock}

\end{frame}
%###################################################################
\begin{frame}[fragile]{Lösung}
  \textbf{Darstellung zur Basis $p = 2 $.}

  Zuerst alle Stellen vor dem Komma:
  \begin{align}
    (12)_{10} : 2 &= (6)_{10} \text{ Rest } 0 \\
    (6)_{10} : 2 &= (3)_{10} \text{ Rest } 0 \\
    (3)_{10} : 2 & = (1)_{10} \text{ Rest } 1 \\
    (1)_{10} : 2 & = (0)_{10} \text{ Rest } 1
  \end{align}
   Ergebniss: $ (12)_{10} =1\cdot 2^3 + 1\cdot 2^2 +0\cdot 2^1 + 0\cdot 2^0 = (1100)_2$

  Nun die Nachkommastellen:
   \begin{align}
     (0.125)_{10} * 2 &= (0.25)_{10} \text{ Rest } 0 \\
    (0.25)_{10} * 2 &= (0.5)_{10} \text{ Rest } 0 \\
    (0.5)_{10} * 2 & = (1)_{10} \text{ Rest } 1 
  \end{align}
  Ergebniss: $ (0.125)_{10} = 0\cdot 2^{-1} + 0\cdot 2^{-2} +1\cdot 2^{-3}=(0.001)_2$

  \textbf{Damit ergibt sich $(12.125)_{10} = (1100.001)_2$}

\end{frame}
\begin{frame}[fragile]{Lösung}
  \textbf{Darstellung zur Basis $p = 16 $.}

  Hexadezimaldarstellung

%  $\{ $0,1,2,3,4,5,6,7,8,9,11,12,13,14,15$\}$\\
  $\{ $0,1,2,3,4,5,6,7,8,9,A, B, C, D, E, F$\}$

  Zuerst alle Stellen vor dem Komma:
  \begin{align}
    (12)_{10} : 16 &= (0)_{10} \text{ Rest } 12 \\
  \end{align}
  Ergebniss: $ (12)_{10} =C\cdot 16^0 = (C)_{16}$

  Nun die Nachkommastellen:
   \begin{align}
     (0.125)_{10} * 16 &= (2)_{10} \text{ Rest } 2 \\
  \end{align}
  Ergebniss: $ (0.125)_{10} = 2\cdot 16^{-1} =(0.2)_{16}$

  \textbf{Damit ergibt sich $(12.125)_{10} = (C.2)_{16}$}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[fragile]{Lösung}
  \textbf{Darstellung von $(0.1)_{10}$ zur Basis $p = 2 $.}
  \begin{align}
    (0.1)_{10} * 2 &= (0.2)_{10} \text{ Rest } 0 \\
    (0.2)_{10} * 2 &= (0.4)_{10} \text{ Rest } 0 \\
    (0.8)_{10} * 2 & = (0.8)_{10} \text{ Rest } 0 \\
    (1.6)_{10} * 2 & = (0.6)_{10} \text{ Rest } 1\\
    (0.6)_{10} * 2 & = (0.2)_{10} \text{ Rest } 1\\
  \text{Wiederho}&\text{lung on Zeile 2}
  \end{align}
  Ergebniss: $ (0.1)_{10} = (0.00011\overline{0011})_2$

\end{frame}
\begin{frame}[fragile]{Lösung}
  \textbf{Darstellung von $(0.1)_{10}$ zur Basis $p = 16 $.}

  Hexadezimaldarstellung

%  $\{ $0,1,2,3,4,5,6,7,8,9,11,12,13,14,15$\}$\\
  $\{ $0,1,2,3,4,5,6,7,8,9,A, B, C, D, E, F$\}$

  Zuerst alle Stellen vor dem Komma:
  \begin{align}
    (0.1)_{10} * 16 &= (0.6)_{10} \text{ Rest } 1 \\
    (0.6)_{10} * 16 &= (0.6)_{10} \text{ Rest } 9 \\
    \text{Wiederho}&\text{lung on Zeile 2}
  \end{align}
  Ergebniss: $ (12)_{10} = (0.1\overline{9})_{16}$
\end{frame}
%###################################################################




%###################################################################
%###################################################################
% Aufgabe 3
%###################################################################
\begin{frame}[fragile]{Aufgabe 3}
  Gegeben sei das sogenannte implizite Euler-Verfahren
\[
u_{i+1}=u_i+hf(t_{i+1}, u_{i+1})
\]
zur Lösung der DGL $\dot{y}=f(t,y)$, $y(t_0)=y_0$.
\begin{enumerate}
\item Welches praktisches Problem tritt hier auf?
\item Bestimmen Sie die Konsistenzordnung.
\item  Genüge $f$ bezüglich der zweiten Komponente einer Lipschitz-Bedingung, d.h.
\[
|f(t,y_1)-f(t,y_2)|\leq L|y_1-y_2|
\]
mit $L$ konstant für alle $t$ und alle $y_1, y_2$. 
Zeigen Sie, dass der globale Fehler $|e_h|$ der folgenden Ungleichung genügt:
\begin{equation}
\label{eq:globalenFehler}
|e_h(t_{i+1})|\coloneqq |y(t_{i+1})-u_{i+1}| \leq \frac{1}{1-Lh} (|e_h(t_i)|+h |\tau_h|)
\end{equation}
wobei
\[
\tau_h\coloneqq \frac{y(t_{i+1})-y(t_i)}{h}-f(t_{i+1}, y(t_{i+1})).
\]
\end{enumerate}
\end{frame}

%###################################################################
% Lösung
%###################################################################
\begin{frame}[fragile]{Lösung}
\begin{enumerate}
\item The method is not explicit, which means that one has to solve a nonlinear equation of the form
\[
g(u_{i+1})=u_{i+1}-u_i-hf(t_{i+1}, u_{i+1})=0
\] in order to find $u_{i+1}$.

\end{enumerate}
\end{frame}

\begin{frame}[fragile]{Lösung}
\begin{enumerate}
  \setcounter{enumi}{1}
\item Lokaler Abschneidefehler: \[\tau_h = \frac{y(t+h)-y(t)}{h}-f(t+h, y(t+h))
\]
Taylorentwicklung von $y(t+h)$:
\[
y(t+h)=y(t)+h\dot{y}(t)+\frac{h^2}{2}\ddot{y}(t)+\mathcal{O}(h^3)
\]
Taylor von  $f(t+h, y(t+h))=\dot{y}({t+h})$:
\[
\dot{y}(t+h)=\dot{y}(t)+h\ddot{y}(t)+\mathcal{O}(h^2)
\]
Daraus ergibt sich
\[
\tau_h=\dot{y}(t)+\frac{h}{2}\ddot{y}(t)+\mathcal{O}(h^2) - \dot{y}(t)-h\ddot{y}(t)+\mathcal{O}(h^2) = \mathcal{O}(h),
\]
 Konvergenzordnung $p=1$.
%\item $\to$ Aus \eqref{eq:globalenFehler} folgt dann, dass die Konvergenzordnung 1 ist. (Das braucht hier nicht bewiesen werden.)
\end{enumerate}
\end{frame}
\begin{frame}[fragile]{Lösung}
\begin{enumerate}
  \setcounter{enumi}{1}

\item Es gilt
\[
\begin{aligned}
y(t_{i+1})&=y(t_i)+hf(t_{i+1}, y(t_{i+1})) + h \tau_h\\
u_{i+1} &= u_i+hf(t_{i+1}, u_i+1),
\end{aligned}
\]
und deswegen
\[
\begin{aligned}
  |e_h(t_{i+1})|&=\only<1>{\alert{\dots \quad?\quad\dots}}\visible<2>{|y(t_i)+hf(t_{i+1}, y(t_{i+1})) + h \tau_h-u_i-hf(t_{i+1}, u_{i+1}) | \\
&= |e_h(t_i)+h\left[f(t_{i+1}, y(t_{i+1}))-f(t_{i+1}, u_{i+1}) \right]+h\tau_h|\\
&\leq |e_h(t_i)|+h|f(t_{i+1}, y(t_{i+1}))-f(t_{i+1}, u_{i+1})| +h|\tau_h|\\
&\leq |e_h(t_i)|+hL|y(t_{i+1})- u_{i+1}| +h|\tau_h|\\
&=|e_h(t_i)|+hL|e_h(t_{i+1})| +h|\tau_h|.}
\end{aligned}
\]
Daraus folgt die Ungleichung.

$\to$ Aus \eqref{eq:globalenFehler} folgt dann, dass die Konvergenzordnung 1 ist. (Das braucht hier nicht bewiesen werden.)
\end{enumerate}
\end{frame}
%###################################################################
%###################################################################
