---
# System prepended metadata

title: 1 Computerarithmetik
tags: [num0]

---

{%hackmd @themes/dracula %}
!!! [RICHTLINIEN](/GhohNZ9wTUecB5MSC9b2Rg)  !!!

---

# 1.0 Einführung

## Beispiel 1.1
Die folgende Darstellung der Euler'schen Zahl $e$ ist aus der Analysis bekannt: 

$$e = \lim\limits_{n\to\infty} (1+\frac{1}{n})$$

## Beispiel 1.2
Die Potenzreihe der Exponentialfunktion konvergiert für jedes $x\in\mathbb{R}$

$$e^x=\sum\limits_{k=0}^\infty \frac{x^k}{k!}=1+x+\frac{x^2}{2}+\frac{x^3}{6}+\frac{x^4}{24}+...$$

## Satz 1.3
Jede reele von Null verschiedene Zahl $x\in\mathbb{R}$ lässt sich in der Form 
$$x = \pm \beta^e (\frac{d_1}{\beta}+\frac{d_2}{\beta^2}+ \frac{d_3}{\beta^3}+...)$$
darstellen, mit der **Basis** $2\leq \beta \in \mathbb{N}$, den Ziffern (engl. "digits") $d_1,d_2,...\in \{0,1,2,...,\beta -1\}$, wobei $d_1 \neq 0$, und dem **Exponenten** $e\in\mathbb{Z}$.


## Beispiel 1.4 
**(Basen)**

| System      | $\beta$ | Zifferndarstellung      |
| ----------- | ------- | ----------------------- |
| Dezimal     | 10      | 0, 1, 2, ..., 9             |
| Binär       | 2       | 0, 1                     |
| Oktal       | 8       | 0, 1, 2, ..., 7             |
| Hexadezimal | 16      | 0, 1, 2, ..., 9, A, B, C, D, E, F |


## Definition 1.5
**(Gleitkommazahlen $\mathbb{F}(\beta,t,e_{min},e_{max}$)**

Sei $\beta\in\mathbb{N},~\beta \geq 2$ (**Basis**) und $t\in\mathbb{N}$ (**Mantissenlänge**), sowie $e_{min} < 0 < e_{max}\in\mathbb{Z}$ (**Exponentenschranken**). 
Dann ist die Menge $\mathbb{F}=\mathbb{F}(\beta, t,e_{min},e_{max})$ wie folgt definiert:

$$\mathbb{F}:= \pm \beta^e (\frac{d_1}{\beta}+\frac{d_2}{\beta^2}+...+\frac{d_t}{\beta^t}):~~  \{0\} \cup 
\begin{cases}
d_1,...,d_t \in\{0,...,\beta -1\},\\
d_1\neq 0,\\
e\in\mathbb{Z}, e_{min}\leq e\leq e_{max}   \end{cases}$$

Offensichtlich ist $\mathbb{F}$ eine endliche Teilmenge von $\mathbb{Q}$ (und damit von $\mathbb{R}$). Es ist wichtig zu bedenken, dass die Elemente von $\mathbb{F}$ nicht gleichmäßg verteilt sind.

## Beispiel 1.6
Nichtnegative Gleitkommazahlen für $\beta=2,~t=3,~e_{min}=-1,~e_{max}=3$ 

![](https://s3.hedgedoc.org/demo/uploads/5ad4a8cd-4259-4c36-8881-7e43e120d37a.png)

## Bemerkung 1.7
Alternativ könnte man mit **Festkommazahlen** arbeiten, d.h. $$\begin{equation} \left\{ \begin{aligned} \pm \sum\limits_{i= e_{min}}^{e_{max}} d_i\beta^i: d_1,...,d_t \in\{0,...,\beta - 1\end{aligned} \right\} \end{equation}$$

## Lemma 1.8
In $\mathbb{F}:=\mathbb{F}(\beta,t,e_{min},e_{max})$ gilt 

$$x_{min}(\mathbb{F}):=\min\{x\in\mathbb{F}:x>0\}=\beta^{e_{min}-1},$$ 

$$x_{max}(\mathbb{F}):=\max\{x\in\mathbb{F}\}=\beta^{e_{max}}(1-\beta^{-t})$$

<font color="red">Bereich($\mathbb{F}$)$:=[-X_{max},-X_{min}],[X_{min},X_{max}]$</font>

### Beweis a)
Betrachtet man [Def 1.5](#Definition-15) Gleitkommazahlen $\mathbb{F}( beta,t,e_{min},e_{max})$, so besteht die einzige Schwierigkeit im Beweis von (1.2.1)-(1.2.2) darin, den minimalen und maximal möglichen Wert der Mantisse $m=\sum\limits_{k=1}^{t}= d_k\beta^{-k}$ zu bestimmen. Es gilt wegen $d_1\neq0$ $$\beta^{-1} \leq m \leq\sum\limits_{k=1}^{t}\beta^{-k}(\beta-1)=1-\beta^t$$
und beide Werte können angenommen werden.

### Beweis b)

$\to x_{min} = \beta^{e_{min}}(\frac{1}{\beta}+\frac{0}{\beta^2}+...+\frac{0}{\beta^t} =\beta^{e_{min}-1}$
$\to x_{max} = \beta_0^{e_{max}}(\frac{\beta-1}{\beta}+\dots+\frac{\beta-1}{\beta^n})$
$=\beta^{e_{max}}(\sum\limits_{j=1}^t\beta^-j)\cdot(\beta-1)=\beta^{e_{max}}(1-\beta^t)$
$\beta(\sum\limits_{j=1}^t\beta^{-j})=(\sum\limits^t_{j=1}\beta^{-j})+1-\beta^{-t}$
$\Rightarrow (\sum)=\frac{1+\beta^{-t}}{\beta-1}$ 
$\square$


## Lemma 1.9

Der Abstand zwischen einer Gleitkommazahl $x\neq 0$ und der nächstgelegenen Gleitkommazahl ist mindestens $\beta^{-1}\epsilon_{_M}|x|$ und höchstens $\epsilon_{_M} |x|$, wobei $\epsilon_M = \beta^{1-t}$ der Abstand von 1 zur nächstgrößeren Gleitkommazahl ist.

**Beweis in Übung**
<img src = "https://s3.hedgedoc.org/demo/uploads/d1b3add4-8354-4c91-974d-86b9f3a94007.png" width="60%">

> Aus Lemma 1.9 folgt, dass für eine feste Basis $\beta$ die relative Genauigkeit von $\mathbb{F}$ lediglich von der Mantissenlänge $t$ abhängt: $e_{min},e_{max}$ bestimmen **nur den Bereich** von $\mathbb{F}$, nicht aber die **Genauigkeit** von $\mathbb{F}$.

**Bemerkung**
Um die Lücke zu 0 zu schließen betrachtet man auch denormalisierte GLZs
$$\hat{\mathbb{F}} = \mathbb{F}\cup \{\pm \beta^e(\frac{d_0}{\beta^2}+...+\frac{d_t}{\beta^t}) | d_j\in{0,...\beta-1}, e\in \mathbb{Z}  \cap [e_{min},e_{max}]$$

(HIER STEHT TECHNICALLY NOCH MEHR IM SKRIPT aber ne)

## Beispiel 1.10
$\mathbb{\hat{F}}$ für $\beta=2,~t=3,e_{min}=-1,e_{max}=3$:
![](https://hackmd.io/_uploads/S1vEsbFMa.png)


> Es ist zu beachten, dass für denormalisiserte Zahlen das [Lemma 1.9](#Lemma-19) nicht gilt.
> Der denormalisierte Bereich hat niedrigere relative Genauigkeit.

Die zwei im IEEE-Standard von 1955  festegelegten Grundformate zur Basis $\beta = 2$ sind

| Typ    | Größe   | Mantisse  | Exponent | $x_{min}$   | $x_{max}$   |
| ------ | ------- | --------- | -------- | ----------- | ----------- |
| Single | 32 bits | 23+1 bits | 8 bits   | $10^{-38}$  | $10^{+38}$  |
| Double | 64 bits | 52+1 bits | 11 bits  | $10^{-308}$ | $10^{+308}$ |



> 24.10.2023

# 1.3 Runden
Wir führen eine Rundungsfunktion 
$$rd:Bereich(\mathbb{F})\to\mathbb{F}$$
und bildet $x\in Bereich(\mathbb{F})$ auf *eine* höchstgelegene Zahl in $\mathbb{F}$ ab.

IEEE 754 vermeidet die "symmetrische" Rundung, falls zwei nächstgelegene Zahlen suchst, wird auf die Gleitkommazahl (GKZ) gerundet, falls wieder die letzte Ziffer eine gerade Zahl ist.


## Beispiel 1.12
Sei $\Omega =10,~t=3$
Mit Rundung gilt 

$$\begin{split}
rd(0.9994)&=0.999 \\
rd(0.3345)&=0.334\\
rd(0.3355)&=0.336\\
\end{split}$$

Bemerkung: bei letzter Ziffer 5 wird auf die nächste gerade Ziffer gerundet, also $0.3345$ $\to 0.33$<font color="red"> $4$</font>, nicht $0.3345\to 0.33$<font color="red"> $5$</font>
% Aber warum dann letztes Beispiel?

## Satz 1.13
Für alle $x\in$ Bereich$(\mathbb{F})$ existiert ein $\delta\in\mathbb{R}$, sodass $$rd(x)=x(1+\delta),~|\delta|\leq u$$ 
wobei $u:=\frac{1}{2}\beta^{1-t}$ die Runduungseinheit (engl. unit roundoff) des GKZ-Systems bezeichnet

Daraus folgt $$\frac{|x-rd(x)|}{|x|}=\frac{|\delta x|}{|x|}=|\delta|\leq u=\frac{1}{2}\Omega^{1-t}$$

### Beweis
Seien $y_1,y_2\in\mathbb{F}$ zwei benachbarte GKZ, sodass $y_1\leq x\leq y_2$.
Dann ist $rd(x)\in\{y_1,y_2\}$. Nach [Lemma 1.9] gilt $|y_1-y_2|\leq \beta^{1-t}$.
$\Rightarrow |x-rd(x)|\leq \frac{|y_1-y_2|}{2}\leq \frac{1}{2}\beta^{1-t}=u$.
$\square$

## Satz 1.15
Für alle $x\in Bereich(\mathbb{F})$ $\exists \delta$, sodass $|\delta|\leq u$ und $$rd(x)=\frac{x}{1-\delta}$$

**Beweis in Übung**

----
Für die vier Grundrechenarten $\circ \in\{+,-,\cdot,/\}$ gilt (bis $0/0$)

$$\circ :\mathbb{R}\times\mathbb{R}\to \mathbb{R} \cup \{0,\pm \infty\}$$

allerdings gilt **nicht**:

$$\circ :\mathbb{F}\times\mathbb{F}\to\mathbb{F}\cup\{\pm\infty\}$$

## Definition 1.16 (Mathematisches Standardmodell der Rundung)

Die Abbildung $rd:$ Bereich$(\mathbb{F})\to\mathbb{F}$, sei derart, dass $\forall ~\circ \in\{+,-,\cdot,/\}$ gilt

$$rd(x \circ y)=(x\circ y)(1+\delta), ~|\delta|\leq u$$

**Bemerkung**
$\to$ Kommutativität und Assoziativität gelten nicht, z.B.
$$x+y\neq y+x$$

## Beispiel 1.17
Für $\beta=10, t=2$ 
$$rd((rd(74+70)+74)=rd(140+74)=210$$
$$rd(70+rd(74+74))=rd(70+150)=220$$

---

lol, bis hier hin skript, dann anarchie
if someone hits him hard enough, a mandatory break would happen
murder anyone?

schreiben wir die beisp mit? -> Ja 
KRISE 
GROSSE KRISE 
MIESE KRISE
FIESE KRISE
![](https://s3.hedgedoc.org/demo/uploads/6464c3e0-23c2-41f1-9d82-117006a26109.png)

Nemo is a vile scoundrel!

---

# 1.4 Rundungsfehleranalyse


Das Standardmodell der Rundung erlaubt es uns, auf einfache Weise die *Fortpflanzung von Rundungsfehlern in einer Gleitkommarechnung* mathematisch abzuschätzen. 
Als wichtiges Beispiel betrachten wir den Rundungsfehler beim "berechnen" des euklidischen Skalarprodukts $\underline{x},\underline{y}\in\mathbb{R}^n$ :
$$\underline{x}^T\underline{y}=\sum\limits_{i=1}^nx_iy_i\in \mathbb{R}$$

$$\begin{split}
\hat{s}_1&=rd(x_1y_1)=x_1y_1(1+\delta_1) \\
\hat{s}_2 &= rd(\hat{s}_1+x_2y_2) \\
&=(\hat{s}_1+x_2y_2(1+\delta_2))(1+\delta_3) \\
&= x_1y_1(1+\delta_1)(1+\delta_3)+x_2y_2(1+\delta_2)(1+\delta_3)
\end{split}$$

Wir schreiben kürzer: 

$$\hat{s}_2= x_1y_1(1+\delta)^2+x_2y_2(1+\delta)^3$$
da der konkrete Wert von $\delta_i$ zwar von $\underline{x}$ und $\underline{y}$ abhängig sind, aber für alle $i$ gilt $|\delta_i|\leq u(\mathbb{F})$. Wir nehmen also $\delta$ als beliebige reelle Zahl mit $|\delta|\leq u(\mathbb{F})$.

$$\to 
\begin{split}
\hat{s}_3 &= rd(\hat{s}_2+x_3y_3)\\
&=(\hat{s}+ x_3y_3(1+\delta))(1+\delta)\\
&= x_1y_1(1+\delta)^3+x_2y_2(1+\delta)^3+x_3y_3(1+\delta_3)^2\\
\end{split}$$

Induktiv:

$$\hat{s}_n=x_1y_1(1+\delta)^n+x_2y_2(1+\delta)^n+x_3y_3(1+\delta)^{n-1}+\dots+x_ny_n(1+\delta)^2$$

$\Rightarrow$ Fehler pflanzt sich exponentiell in $n$ fort.


## Lemma 1.18

Für $|\delta|\leq u(\mathbb{F})$, $i=1,\dots,n$ und $n<\frac{1}{u(\mathbb{F})}=:\gamma_n$ 

$\exists~\theta_n\in\mathbb{R}$, sodass

$$\prod\limits^n_{i=1}(1+\delta_i)\leq1+\theta_n$$ wobei $$|\theta_n|\leq\frac{nu(\mathbb{F})}{1-nu(\mathbb{F})}$$

### Beweis
$\underline{n=1}$,$1+\delta_i$: 
$|\delta_1|\leq u\leq \frac{u}{1-u}$.

$\underline{n-1\mapsto n}$: 

$$\begin{split}
\prod\limits^n_{i=1}(1+\delta_i)&=(1+\theta_{n-1})(1+\delta_n)\\
&=:1+\theta_n,~~~~\theta_n:=\delta_n+(1+\delta_n)\theta_{n-1} \\
~\\
~\\
|\theta_n|&\leq u+(1+u)\Theta_{n-1} \\
&\leq u+(1+u)\frac{n-1)u}{1-(n-1)u} \\
&=\frac{\underline{u}[1-(n-1)n]+(1+u)(n-1)u}{1-(n-1)u}\\
&=\frac{u+(n-1)n}{1-n-1)u} \\
&=\frac{nu}{1-(n-1)u} \\
&\leq\frac{nu}{1-nu}
\end{split}$$


z.B. für $n\leq\frac{1}{2u(\mathbb{F})}$ gilt $|\theta_n|\leq 2n\cdot u(\mathbb{F})$.

Als Rückwärtsfehler bezeichnen wir die Störung in den Eingabedaten, die das exakte Ergebnis zu den mit den gestörten Daten berechneten Ergebnis liefert.

$$\hat{s}_n=(x_1y_1)(1+\theta_n)+x_2y_2(1+\theta_n^{\prime})+x_3y_3(1+\theta_{n-1})+\dots+x_ny_n(1+\theta_2)$$

$\Rightarrow rd(\underline{x}^T \underline{y})=(x+\Delta y)^T\underline{y}$ wobei $|\Delta \underline{x}|\leq\gamma_n|\underline{x}|$ korrespondierend

$\Rightarrow rd(\underline{x}^T\underline{y})=(\underline{x}^T(\underline{y}+\underline{\Delta y}))$ 
wobei $|\Delta\underline{y}|\leq\gamma_n|\underline{y}|$.

$\to$ Der tatsächliche Fehler wird als Vorwärtsfehler bezeichnet. 
Für das Skalarprodukt (SKP):

$$|\underline{x}^T\underline{y}-rd(\underline{x}^T\underline{y})|\leq \gamma_n\cdot\sum\limits_{i=1}^{n}|x_iy_i|=\gamma_n|\underline{x}|^T|\underline{y}|$$

Falls $|\underline{x}^T\underline{y}|\cong|\underline{x}|^T|\underline{y}|$ $\Rightarrow$ dann verhält sich der relative Fehler wie $\gamma_n$

> SKRIPT GIBT ALTERNATIVE ABSCHÄTZUNG

$\Rightarrow$ so ist der relative Fehler klein. 
Gilt jedoch $|\underline{x}^T\underline{y}| \ll |\underline{x}|^T|\underline{y}|$, so ist kein kleiner relativer Fehler zu erwarten.

<u>Matrix-Vektor Produkt</u>

$\underline{y}=A\underline{x}$, wobei $A\in\mathbb{R}^{m\times n}$, $\underline{x}\in\mathbb{R}^n$,$\underline{y}\in\mathbb{R}^m$.
$A=\begin{pmatrix}a_1^T\\ \dots \\a_n^T\end{pmatrix}$

$y_i=\underline{a}_i^T\underline{x}$
$\hat{y}_i=(\underline{a}_i+\underline{\Delta a_i})^T\underline{x}$
$<|\Delta\underline{a}_i|$
$\Rightarrow\underline{y}=(A+\Delta A)\underline{x}$, $|\Delta A|\leq \gamma_n|A|\leftarrow$ Matrix mit Einträgen $(|A_{ij}|)_{ij}$

$\overset{\texttt{Vorwärtsfehler}}\Rightarrow  |\hat{y}-y|\leq \gamma_n|A||\underline{x}|$

Insb. 
$||\hat{y}-\underline{y}||_{\infty} =\underset{i=1,\dots,n}{\max}|\hat{y}_i-y_i|=\underset{i=1,\dots,n}{\max}|\underline{a}_i|^t|\underline{x}|\leq \gamma_n||A\underline{x}||_\infty\leq\gamma_n||A||_\infty||x||_\infty$
w
> $|\underline{a}_i|^t|\underline{x}|\Leftrightarrow|\underline{a}_i^t\underline{x}|$


> 26.10.2023

# 1.5 Auslöschung

Numerische Auslöschung tritt beim Subtrahieren von 2 fast gleichen **bereits rundungsfehlerbehafteten** Zahlen in GK-Arithmetik auf

## Beispiel 1.19

Sei 

$$f(x):=\frac{1-\cos{x}}{x^2}$$

<img src = "https://s3.mathphys.info/hedgedoc/uploads/0a840528-11ab-441f-82e5-317d97649873.png" width="30%">

Für $x=1,2\cdot 10^{-5}$, dann ist $\cos{x}$ auf $10$ Dezimalen gerundet.

$$C:=0,9999~9999~99$$

Dann ist $1-c=0,0000~0000~01$

Dann ist 

$$\frac{1-c}{x^2}=0.6944\neq \frac{1-\cos{x}}{x^2}=0.499...$$

z.B. $f^{-1}(x)\simeq\frac{f(x+h)-f(x)}{h}$.

---

Sei $a,b\in\mathbb{R}$, und $\hat{a}=a(1+\delta_a),\hat{b}=b(1+\delta_b)$, wobei $|\delta_a|, |\delta_b|\leq u(\mathbb{F})$.
$x=a-b$, $\hat{x}=\hat{a}-\hat{b}$
$\Rightarrow \frac{|x-\hat{x}|}{|x|}=\frac{|\delta_aa+\delta_bb|}{|a-b|}\leq u\frac{|a|+|b|}{|a-b|}$


Keine Aussage über Vorzeichen oder Wert von $\delta_a,\delta_b$, deshalb muss die Abschätzung von beiden abhängig sein. 

Relativer Fehler in Berechnung $x=a-b$ ist groß, falls $|a|+|b|>>|a-b|$ gilt.

## Beispiel 1.20
$$f(x)=\frac{e^x+1}{x} = \sum_{i=0}^{\infty} \frac{x^i}{(i+1)!}$$
<img src="https://s3.mathphys.info/hedgedoc/uploads/7c8539be-849d-40e2-8a2f-9f15496b214e.png" width="50%">
<img src="https://s3.mathphys.info/hedgedoc/uploads/0d64fff0-4173-4629-bc90-95659df7bcbf.png" width=50%>

Falls $\underline{\hat{y}=1} \to f=1$

$$\begin{split}
\hat{y}&=y(1+\delta_y),~~ |\delta|| \\
&= e^x(1+\delta)\\
&\Rightarrow x=-\log(1+\delta) \\
&=-\delta+\frac{\delta^2}{2}-\frac{\delta^3}{3}+\dots\\
\Rightarrow x&=-\delta+O(\delta^2)
\end{split}$$

Falls $\underline{\hat{y} \neq 1:}$ 

$$\begin{split}
\hat{f}&=rd(\frac{\hat{y}-1}{\log(\hat{y})} \\
&=\frac{(\hat{y}-1)(1+\delta_1)}{\log{\hat{y}(1+\delta_2)}}(1+\delta_3),~~|\delta_i|\leq u
\end{split}$$

Sei jetzt $v=\hat{y}-1$ und 

$$\begin{split}
g(v) :&=\frac{v}{\log(v+1)}\\
\implies g(v) &= \frac{v}{v+\frac{v^2}{2}+\frac{v^3}{3}+...} \\
&=\frac{1}{1-\frac{v}{2}+\frac{v^2}{3}-\dots} \\
&=1+\frac{v}{2}+O(v^2)
\end{split}$$

$\frac{1}{1+x}=1-x+O(x^2)$

Somit gilt für $\hat{y}=y(1+\delta)$

$$g(\hat{y})-g(y)=\delta\cdot \frac{y}{2}+O(\delta^2)$$

**Insgesamt:**

$$\begin{split}
\frac{|\hat{f}-f|}{|f|} &=g(\hat{y})\frac{(1+\delta_1)}{(1+\delta_2)}\cdot (1+\delta_3)) \\
&= g(y)(1+\frac{d_y}{2}+o(\delta^2))(1+\delta_1)(1-\delta_2+O(\delta_2^2))(1+\delta_3) \\
&=f(1+(\delta_1+\delta_2+\delta_3+\frac{\delta_y}{2})+O(u^2))\\
&=f(1+(3+\frac{u}{2}\overset{\sim}{\delta}+ O(u^2))\implies \hat{f}
\end{split}$$