% !TeX root = main.tex
\newcommand{\norm}[1]{\Vert #1 \Vert}
\newcommand{\abs}[1]{| #1 |}
\newcommand{\M}{\mathbb{M}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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!60!black}#1}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Maschinenzahlen}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%###################################################################
\begin{frame}[fragile]{Maschinenzahlen}
\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]{Maschinenzahlen}

\metroset{block=fill}
\begin{Definition}[Maschinenzahlen]
Die \alert{Menge aller Maschinenzahlen in normalisierter Gleitpunktdarstellung}
mit Basis $\r{p}$, Mantissenlänge \b{$m$} und Exponentenlänge \g{$e$} ist
{\footnotesize  \begin{align*}
    \M(\r{p},\b{m},\g{e}) =\{\pm  & (z_1 p^{-1} + z_2 p^{-2}+ \dots + z_{\b{m}}p^{-\b{m}})
      p^{\pm(\beta_1 p^{\g{e}-1} + \beta_2 p^{-2}+ \dots + \beta_{\g{e}}p^{0})} \mid \\
                                   &z_j\in\{0,1,\dots,p-1\}, z_1\ne0\} \cup \{0\}
  \end{align*}}

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


%###################################################################
\begin{frame}[fragile]{Aufgabe 1}
  \begin{enumerate}
     \item Betrachten Sie die Maschinenzahlen $\mathbb{M}(2,4,2)$. 
      Wie lauten hier \texttt{eps}, \texttt{xmin}, \texttt{xmax}?
\end{enumerate}
\begin{equation*}
  x\in\mathbb{M}(2,4,2)\Rightarrow x=\pm (0.z_1z_2 z_3 z_4)_2* 2^{\pm(e_1 e_2)_2} 
  \end{equation*}
  
\end{frame}

\begin{frame}[fragile]{Lösung 1}
%  \textbf{Definition:} \texttt{eps} ist der Abstand der Zahl 1 zur nächst größeren Maschinenzahl!\\

  \begin{equation*}
  x\in\mathbb{M}(2,4,2)\Rightarrow x=\pm (0.z_1z_2 z_3 z_4)_2* 2^{\pm(e_1 e_2)_2} 
  \end{equation*}
  \textbf{Mögliche Mantissen:} $\pm 0.1000, \pm0.1001, \pm0.1010, \ldots, \pm0.1111$\\

$\to$ d.h. von $\pm 2^{-1}=\pm 1/2$ bis $\pm(2^{-1}+2^{-2}+2^{-3}+2^{-4})=\pm 15/16$.\\
\vspace{0.3cm}
\textbf{Mögliche Exponenten:} $\pm 00,\pm 01, \pm 10, \pm 11$\\
$\to$ d.h. von $\pm(0*2^{0}+ 0* 2^1)=0$ bis $\pm(1*2^{0}+1*2^{1})=\pm 3$.\\

\vspace{0.3cm}
 \texttt{xmin}=1/2 $\cdot 2^{-3}= 2^{-4}$,\\ \texttt{xmax}=15/16 $\cdot 2^{3}= 15/2=7.5$,\\
\texttt{eps}$\coloneqq\frac{p}{2}p^{-m}= \frac{2}{2}2^{-4}=2^{-4}$
\end{frame}
%###################################################################



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Rechenoperationen}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%###################################################################
%###################################################################
\setbeamersize{description width=0.57cm}
\begin{frame}[fragile]{Aufgabe 2}
            Die Maschinenoperation $\oplus$ können wir durch die Gleichung
      \[x\oplus y= (x+y)(1 +\epsilon) \]
      mit der gewöhnlichen Addition in Beziehung setzen. 
      Handelsübliche Prozessoren sorgen dafür das der relative Rundungsfehler $\epsilon$ 
      unabhängig von $x$ und $y$ mit $\epsilon^*$ beschränkt bleibt:  $|\epsilon|\leq\epsilon^*$. 
      %(Wie  groß  dieses  ist,  wird  in  der  ersten  Programmieraufgabe  bestimmt.  Siehe  auch  ... Das Doppelte, also $2\epsilon^*$ wird übrigens als Rechnergenauigkeit oder Maschinenepsilonbezeichnet.)
      Wir wollen nun $x_1,\ldots,x_n$ summieren gegeben und sei durch
      \[\tilde{s}_1=x_1, \quad \tilde{s}_n=\tilde{s}_{n-1}\oplus x_n\]
       ein Algorithmus zur Berechnung der Summe $s_n=\sum^n_{i=1} x_i$ definiert.
       Wir  wollen in dieser Aufgabe den Fehler exakt  abgeschätzten.
      $\epsilon^2$ darf  deshalb nicht gekürzt werden! Benutze keine $\mathcal{O}$-Notation.
      \begin{description}
        \item[a)] Berechnen Sie für $n= 1,...,4$ den absoluten Fehler $f_n\equiv \tilde{s}_n-s_n$.
      \end{description}
\end{frame}
%
%###################################################################
%###################################################################
\begin{frame}[fragile]{Lösung Teilaufgabe a)}
      \[
        \boxed{\tilde{s}_1=x_1, \quad \tilde{s}_n=\tilde{s}_{n-1}\oplus x_n = (s_{n-1}+x_n)(1 +\epsilon_n) }
    \]
  \begin{align*}
    \tilde{s}_1 &=\only<2>{ x_1}\only<1>{\alert{\dots ? \dots}}\\
    {f}_1 &=\only<2>{ x_1-x_1=0}\only<1>{\alert{\dots ? \dots}}\\
    \tilde{s}_2 &=\only<2>{(x_1+x_2)(1+\epsilon_2)= s_2 + s_2 \epsilon_2}\only<1>{\alert{\dots ? \dots}}\\
        {f}_2 &=\only<2>{ s_2\epsilon_2}\only<1>{\alert{\dots ? \dots}}\\
        \tilde{s}_3 &=\only<2>{ (s_2+f_2 + x_3)(1+\epsilon_3)= s_3 + s_3\epsilon_3+(1+\epsilon_3)f_2}\only<1>{\alert{\dots ? \dots}}\\
        {f}_3 &=\only<2>{s_3\epsilon_3+(1+\epsilon_3)f_2}\only<1>{\alert{\dots ? \dots}}\\
        \tilde{s}_4 &=\only<2>{(s_3+f_3+ x_4)(1+\epsilon_4)
        =s_4+  s_4\epsilon_4+f_3(1+\epsilon_4)}\only<1>{\alert{\dots ? \dots}}\\
          {f}_4 &=\only<2>{ s_4 \epsilon_4 +f_3(1+\epsilon_4)=s_4 \epsilon + (s_3 \epsilon_3 +f_2(1+\epsilon_3))(1+\epsilon_4)}\only<1>{\alert{\dots ? \dots}}\\
                &=\only<2>{ s_4 \epsilon_4 + (s_3 \epsilon_3 +s_2\epsilon_2(1+\epsilon_3))(1+\epsilon_4)}\only<1>{\alert{\dots ? \dots}}\\
                &\vdots\\
          \tilde{s}_k&= \only<2>{s_k+\underbrace{s_k\epsilon_k +f_{k-1}(1-\epsilon_k)}_{=f_k}}
  \end{align*}
\end{frame}
%###################################################################


%#####
\begin{frame}[fragile]{Aufgabe 2}
  \begin{itemize}
  \item
    $x\oplus y= (x+y)(1 +\epsilon)$ 
  \item
      $\epsilon$ ist beschränkt durch:  $|\epsilon|\leq\epsilon^*$. 
      %(Wie  groß  dieses  ist,  wird  in  der  ersten  Programmieraufgabe  bestimmt.  Siehe  auch  ... Das Doppelte, also $2\epsilon^*$ wird übrigens als Rechnergenauigkeit oder Maschinenepsilonbezeichnet.)
    \item  Algorithmus:
      $\tilde{s}_1=x_1, \quad \tilde{s}_n= \tilde{s}_{n-1}\oplus x_n $
    \item $s_n\equiv\sum^n_{i=1} x_i$.
   \end{itemize}
      \begin{description}
        \item[b)] Zeigen Sie: Zerlegt man $\tilde{s}_n=s_n+f_n$, so gilt für den absoluten Fehler
      \[|f_n|\leq [(1+\epsilon^*)^n-1]\sum_{i=1}^n |x_i|.\]
      Diskutieren Sie den relativen Fehler von $\tilde{s}_n$.
    \item[c)] Zeige, dass die berechnete Lösung gleich der exakten Lösung von leichtgestörten Eingabedaten $x_i(1 +\delta_i)$ ist:
      \[
      \tilde{s}_n=\sum^n_{i=1} x_i(1+\delta_i) \quad \text{ mit } \quad (1-\epsilon^*)^n-1\leq \delta_i\leq(1 +\epsilon^*)^n-1
      \]
      und dass falls $n\epsilon^*<1$ ist, die Abschätzung
      \[
      |\delta_i|\leq \frac{n\epsilon^*}{1-n\epsilon^*}, \quad  i= 1,\ldots,n
      \]
      gilt.
      \end{description}
\end{frame}
%
%###################################################################
%###################################################################
\begin{frame}[fragile]{Lösung Teilaufgabe b)}
  \begin{center}
\textbf{z.Z:} für $\tilde{s}_k = s_k + f_k $ gilt $|f_k|\le [(1+\epsilon^*)^k-1] \sum_{i=1}^k |x_i|$
\end{center}
\textbf{Hilfe:} Benutzt: $f_k = s_k\epsilon_k + f_{k-1} (1+\epsilon_k)$ zusammen mit $\abs{\epsilon_k}\le\epsilon^*$
  \begin{align*}
    \abs{f_k }&=\abs{s_k \epsilon_k +f_{k-1} (1-\epsilon_k)}\le\abs{s_k}\abs{\epsilon_k}+\abs{f_{k-1}} (1+\abs{\epsilon_k})\\
              &\le\abs{s_k}\epsilon^*+\abs{f_{k-1}} (1+\epsilon^*)\le\abs{s_k}\epsilon^*+(\abs{s_{k-1}}\epsilon^*+\abs{f_{k-2}} (1+\epsilon^*)) (1+\epsilon^*)\\
              &\le\dots\le\abs{s_k}\epsilon^*+\abs{s_{k-1}}\epsilon^*(1+\epsilon^*)\dots+\abs{s_1}\epsilon^*(1+\epsilon^*)^{k-1}\\
              &= \epsilon^* \sum_{j=0}^{k-1} \abs{s_{k-j}}(1+\epsilon^*)^j\le\epsilon^*\b{\sum_{i=1}^{k} \abs{x_i}}\g{\sum_{j=0}^{k-1}(1+\epsilon^*)^j} 
            =\epsilon^*\b{\sum_{i=1}^k \abs{x_i}}\g{\frac{1-(1+\epsilon^*)^k}{1-(1+\epsilon^*)}} \\
              &= \epsilon^*{\sum_{i=1}^k \abs{x_i}}{\frac{1-(1+\epsilon^*)^k}{-\epsilon^*}} 
              = [(1+\epsilon^*)^k-1] \sum_{i=1}^k |x_i|
  \end{align*}
  wobei $\b{\abs{s_{k-j}}\le\sum_{i=1}^{k-j}\abs{x_i}\le \sum_{i=1}^{k}\abs{x_i}}$\\
  und die Partialsumme $\g{\sum_{j=0}^k q^k =\frac{ 1-q^{k+1}}{1-q}}$
\end{frame}
%###################################################################
%###################################################################
\begin{frame}[fragile]{Lösung Teilaufgabe b)}
  \textbf{Relativer Fehler:}
  \begin{align*}
    \frac{ \abs{f_k }}{\abs{s_k}}&\le 
    \frac{  [(1+\epsilon^*)^k-1] \sum_{i=1}^k |x_i|}{\abs{\sum_{i=1}^k x_i}}
  =[(1+\epsilon^*)^k-1]\frac{\sum_{i=1}^k \abs{x_i}}{\abs{\sum_{i=1}^k x_i}}
  \end{align*}
\end{frame}
%###################################################################



%#####
\begin{frame}[fragile]{Aufgabe 2}
  \begin{itemize}
  \item
    $x\oplus y= (x+y)(1 +\epsilon)$ 
  \item
      $\epsilon$ ist beschränkt durch:  $|\epsilon|\leq\epsilon^*$. 
      %(Wie  groß  dieses  ist,  wird  in  der  ersten  Programmieraufgabe  bestimmt.  Siehe  auch  ... Das Doppelte, also $2\epsilon^*$ wird übrigens als Rechnergenauigkeit oder Maschinenepsilonbezeichnet.)
    \item  Algorithmus:
      $\tilde{s}_1=x_1, \quad \tilde{s}_n= \tilde{s}_{n-1}\oplus x_n $
    \item $s_n\equiv\sum^n_{i=1} x_i$.
   \end{itemize}
      \begin{description}
        \item[b)] Zeigen Sie: Zerlegt man $\tilde{s}_n=s_n+f_n$, so gilt für den absoluten Fehler
      \[|f_n|\leq [(1+\epsilon^*)^n-1]\sum_{i=1}^n |x_i|.\]
      Diskutieren Sie den relativen Fehler von $\tilde{s}_n$.
    \item[c)] Zeige, dass die berechnete Lösung gleich der exakten Lösung von leichtgestörten Eingabedaten $x_i(1 +\delta_i)$ ist:
      \[
      \tilde{s}_n=\sum^n_{i=1} x_i(1+\delta_i) \quad \text{ mit } \quad (1-\epsilon^*)^n-1\leq \delta_i\leq(1 +\epsilon^*)^n-1
      \]
      und dass falls $n\epsilon^*<1$ ist, die Abschätzung
      \[
      |\delta_i|\leq \frac{n\epsilon^*}{1-n\epsilon^*}, \quad  i= 1,\ldots,n
      \]
      gilt.
      \end{description}
\end{frame}
%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[fragile]{Lösung Teilaufgabe c)}
siehe Tafel
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



%###################################################################
%###################################################################
