{%hackmd @themes/dracula %}

# Motivation
- ich finde es großartig wie die Informatiker hier gerade mit Lagrange Gleichungen verstört werden
- die armen kinder

# Inhalt
1. Einführung, Motivation
2. Rechnerarithmetik, Fehleranalyse & Konditionierung
3. Interpolation & Approximation
4. Numerische Integration
5. LGS & Ausgleichsprobleme (direkte Verfahren)
6. Nichtlineare Gleichungssysteme
7. LGS (iterative Verfahren)
8. Eigenwertaufgaben

# Literatur
- [Numerische Mathematik 1](https://link.springer.com/book/10.1007/978-3-540-45390-1)
- Deuflhard, Hohmann: Numerische Mathematik 1
- R. Rannacher Numerik 0: Einführung in die numerische Mathematik
- Skript R. Scheichl
- Skript P. Bastian
- Kostina Notizen

# Kapitel 2 - Fehleranalyse
## 2.1) Fehlertypen
#### Beispiel:
Wir werfen einen Stein vom schiefen Turm von Pisa (44,12m) .

<img src="https://hackmd.io/_uploads/HJraG90gC.png" scale />

Frage: Wann schlägt er auf dem Boden auf?

- Modellbildung:
- Annahmen:
- Reibungsfreier Fall
- Stein ist eine Punktmasse
- wie in Theo 1, xD
- <font color="red">=> im Vergleich zur Wirklichkeit: **Modellierungsfehler** </font>
- Höhe $h(t)$
- Geschwindigkeit des Steines $v(t) =\frac{dh}{dt}(t)$
- Beschleunigung $a(t)=\frac{d^2h}{dt^2} (t)$
- Newton: $\vec{F}=m\vec{a}=\vec{g}$
- Annahme: $g=9.81\frac{m}{s^2}$ (Konstante) => <font color="red">weiterer Modellierungsfehler/Fehler in Daten, denn $\vec{g}$ hängt von der Höhe $h$ ab</font>
- $\implies$ Modell: $a(t)= -9.81$
- Berechnung:
- $v(t) = \int \vec{a(t)} dt= -\vec{g}t+ \vec{v_0}$
- $h(t)= \int v(t) dt= - g\frac{t^2}{2} + c_1 t+ c_2$
- $v(0) = 0 \implies c_1 = 0$
- $h(0)= 44.12 \implies c_2 = 44.12$
- $h(t) = \frac{-g}{2}t^2 + 44.12$
- **Gesucht:**
- $t$ s.d. $h(t) = 0 \implies t = \pm \sqrt{\frac{2c_2}{g}}$
- Alg: $t=\sqrt{\frac{2*44.12}{9.81}}$
- <font color ="red"> Verfahrensfehler Rundungsfehler</font>

- Rechner: $t= 3.00 s$ (3 Stellen genau)

| Anwendungsproblem | Bsp.Freier Fall | Fehler |
|---|---|---|
| Modellbildung - Math. Problem | $\frac{d^2h}{dt^2}= -9.81$| Modellierungsfehler, Datenfehler|
|Math. Analyse - Numerische Methode|| |
|analytische Lösung - numerische Lösung| Lösung: $t=3.00$| Verfahrensfehler (z.B. Diskretisierungsfehler), Rundungsfehler, Abbruchsfehler, ...|
| exakte Lösung - Näherung | |Gesamtfehler|

#### Bemerkung:
2 Phänomene bei Fehleranalyse zu unterscheiden:
1) Fehlerentstehung
2) Fehlerfortpflanzung

## 2.2 Floatingpoint arithmetics
- IEEE 754: [Definition auf Wikipedia](https://en.wikipedia.org/wiki/IEEE_754)
- hi

#### Definition - Gleitpunktzahl

1. Eine (normalisierte) Gleitpunktzahl zur <font color = "red">Basis B</font> $\in \mathbb{N}, ~b \geq 2$ ist eine Zahl dargestellt in der Form
$x = \pm m \times b^{\pm e}$ mit der <font color = "green"> Mantisse </font> $m=m_1 b^{-1}+ m_2b^{-2} + ...+ m_r b^{-r} + ... \in \mathbb{R}$
und dem <font color = "lightblue"> Exponenten </font> $e = e_0b^0+ e_1b^1+...+ e_{S-1}b^{S-1}+... \in \mathbb{N}$ wobei $m_1, e_i \in \{0,...,b-1\} \forall x \in \mathbb{R}$ können als Gleitpunktzahl dargestellt werden.

2. Mit $mk= 0 ~\forall k> r$ und $e_k= 0~ \forall k \geq s$ erhält man einen **endlichen** Unterraum der reellen Zahlen mit endlicher Gleitpunktdarstellung$\mathbb{F} := \mathbb{F}(b,r,s) \subset \mathbb{R}$

3. $\forall x \neq 0$ ist eindeutig bestimmt durch $m_1 \neq 0 m = 0. m_1m_2...m_r$ (falls $b=2 \implies m_1 =1$)

4. Für $x=0$ setzen wir $m=0$ und $e=0$

- Auf Computer endlicher Speicher $\implies \text{in } \; \mathbb{F}(b,r,s)$ muss man für jede Zahl
- $r$ Ziffern $+ 1$ Vorzeichen für die Mantisse
- $s$ Ziffern $+ 1$ Vorzeichen für den Exponenten
speichern,
- d.h. gesamt $r+s+2$ Bits
- Alternativ könnte man mit Festpunktzahlen arbeiten, d.h. $x = \pm \sum\limits_{i= - R}^{l} m_i b^i$
- <font color = "red"> Achtung: </font> Für wissentschaftliche Anwendungen ist das ineffizient( aufgrund der zum Teil sehr unterschiedlichen Größenordnungen verschiedener Zahlen). Gegebenenfalls wählt man andere Abbildungen der Reellen Zahlen in einen Unterraum
- $\mathbb{F}(r,b,s)$ endlich ist $\implies \exists$ eine größte/kleinste Zahl. Setze
- $m_i = (b-1),~e_i=(b-1)$, pos. Vorzeichen bei Exponent
- $X_{max}^{+} = \underbrace{(b-1)(b^{-1}+ ... + b^{-r})}_m \times b^{\underbrace{(b-1)(b^0+...+b^{S-1})}_e}$
- $= (b-1) b^{-1} \frac{b^{-r}-1}{b^{-1}-1}\times b^{(b-1)}\frac{b^s-1}{b-1}$
- $=(1-b^{-r}) \times b^{b^s-1}$
- $X_{min}^{-} = -(1-b^{-r}) \times b^{b^s-1}$

=> Nahe Null gibt es eine kleinste postive/größte negative darstellbare Zahl.
- Setze
- $m_1$, $m_i=0$ $\; \forall i > 1$
- $e_i= (b-1)$
- negative Vorzeichen in Exponenten
- $X_{min}⁺= b^{-1} \times b^{-(b-1)(b^0+...+ b^{S-1})}=b^{-b^s}$
- $X_{max}^-=-b^{-b^s}$

#### IEEE 754

Auf modernen Rechnern:
- $b=2$
- IEEE 754 double precision standard (standard in Matlab, python, C++, (siehe Definition weiter oben)) werden 8 Bytes = 64 bits zum Speichern einer Floatingpoint Zahl benutzt.
- Statt Exponenten $\pm e \in \mathbb{Z}$ wird sog. Charakteristika $c\in \mathbb{N}_0$ verwendet$x= \pm m \times 2^{c+e_{min+1}}$
- $c=c_02^0+c_12^1+...+c_S2^S$
- $\implies$ entfällt: Speicherung des Vorzeichens im Exponent:
- $b=2$ => $m_1=1$ (muss nicht gespeichert werden)
- 64 Bit für Zahlspeicherung:
- 1 Bit für Vorzeichen
- 52 bit für $m_2, ..., m_r \in \{ 0,1\}$ => $r=53$
- 11 Bit für Charakteristik => $s=10$
- $\implies x = \pm m \times 2 ^{c-1022}$
- $\implies c \in \{1,...,2046\}$ für normalisierte Zahl $c=0$ und $c=2047$ zusätzlich
- $\implies X_{max}^+\approx 2^{1024}\approx 1.8 \times 10^{308}$
- $\implies X_{min}^+ = 2^{-1022}\approx 2.2 \cdot 10^{-308}$
- Ähnlich für negative Bereiche
- $c=0$, $m=0 \equiv$ Null
- $c=0~ m\neq 0~ \text{denormalisierte Darstellung}$
- $c=2047$, $m\neq 0 \equiv$ NAN (not a number)
- $c=2047~ m\neq 0 \equiv$ NaN(not a number) (z.B. Division durch Null)

<!--- 23.04 ---->

## 2.3 Runden und Rundungsfehleranalyse

Zu $x\in \mathbb{R}$ definiere <font color=green>Rundungsoperation. </font>

$rd: \mathbb{R} \rightarrow \mathbb{F}$ mit $| x-rd(x)|= \min\limits_{y\in \mathbb{F}} |x-y|$ (Bestapproximation).

#### Natürliche Rundung
$rd(x)= sgn(x) \begin{cases} (m_1b^{-1} +.. + m_rb^{-r} ) \times b^l \texttt{ falls } m_{r+1}< \frac{b}{2}\\ m_1b^{-1}+...+(m_r+1)b^{-r}) \times b^l \texttt{ falls } m_{r+1}\geq \frac{b}{2} \end{cases}$

Beispiel im Zahlenformat IEEE:
- $rd(x)=sgn(x)*\begin{cases} (0.m_1...m_{53}*2^l \texttt{ falls } m_{54}=0)\\(0.m_1...m_{53}+2^{-53})*2^l \texttt{ falls } m_{54}=1 \end{cases}$

Der absolute Rundungsfehler für Natürliche Rundung (NR) erfüllt

$|x-rd(x)|\leq \frac 1 2 b^{-r} b^l =\frac 1 2 b^{l-r}$

Bild einfügen! - Hilfe

$|r(x)-l(x)|\leq b^{l-r}$

$|x-rd(x)|\leq\left|\frac{l(x)+r(x)}{2}-l(x) \right|=\frac 1 2 |l(x)-r(x)|\leq \frac 1 2 b^{l-r}$

#### Der relative Rundungsfehler
$|\frac{x-rd(x)}{x} | \leq \frac{\frac{1}{2}b^{l-r}}{|m|b^l}\leq \frac12 b^{-r+1}=: eps$

$x = \pm (0.\underbrace{m_1 ...m_rm_{r+1}}_m+...)\cdot b^l=: eps$

$|m|\geq \frac{1}{b}$ (wegen Normierung $m_1 \neq 0$)

$eps=\frac{1}{2}b^{-r+1}$ heißt <font color=red>Maschinengenauigkeit</font> (engl. machine precision)

Mit eps:
$rd(x)=x(1+\epsilon)\quad |\epsilon | \leq eps$

##### Bsp: IEEE double precision
$eps=\frac{1}{2}2^{-52} \approx10^{-16}$

#### Rundungsfehler elementarer Operationen

$+,-,\times,/$ werden ersetzt durch Maschinenoperationen $\oplus,\ominus,\otimes,\oslash$

z.B. $x\oplus y = rd(x+y) = (x+y)\cdot (1+ \varepsilon)$ mit $|\varepsilon| \leq eps$

<font color=red> ACHTUNG:</font>
Assoziativ und Distributivgesetze gelten nicht für Maschinenoperationen!(Intern gibt es kleine unterschiede einmal bedingt durch die floating point Darstellung und Rundungsfehler beim rechnen)

z.B.
$a=0.23371258\cdot 10^{-4}$
$b=0.33678429\cdot 10^2$
$c=-0.33677811\cdot 10^2$

Exakt: $a+b+c=0.641371258 \cdot 10^{-3}$

Rundung:

- $rd(rd{(a+b)}+c) \neq rd(a+rd(b+c))$

- $~~~~~~~~~(a\oplus b)\oplus c ~~\neq ~~~~~a \oplus (b \oplus c)$ <font color= green> Assoziativgesetz</font>

- $rd(a+b) =0.33678452 \cdot 10^2$

- $rd(rd(a+b)+c)= 0.0000641\cdot 10^2$

Normalisiert: $0.\underbrace{641}_{\text{3 Stellen in Ergebnis}}\text{xxxxx} \cdot 10^{-3}$

$rd(b+c)=0.00000618 \cdot 10^2$

Normalisiert: $0.618 \text{yyyyy}\cdot 10^{-3}$

$rd(a+rd(b+c))=0.641\text{zzzzz}\cdot 10^{-3}$

## Fehlerfortpflanzung (nicht dass noch jemand denkt wir seien hier in Biologie) bei elementaren Operationen

Eingangsdaten: $x,y$ sind gestört durch Rundungsfehler

$\overset{\sim}x=x(1+\epsilon_x)$, $\tilde y=y(1+\epsilon_y)$, $|\epsilon_x|\ll1$, $|\epsilon_y|\ll1$

Betrachten : $rd(\overset{\sim}{x}\circ \overset{\sim}{y})-x\circ y,~\circ\in \{+,-,\times, /\}$

Multiplikation:
$\overset{\sim}z=rd(\overset{\sim}x * \overset{\sim}y)= rd(x(1+\varepsilon_x) y(1+\varepsilon y))$

$=x\cdot(1+\varepsilon_x)\cdot y\cdot (1+\varepsilon_y)\cdot (1+\varepsilon_{mult})$

$=x\cdot y \cdot (1+\varepsilon_x+\varepsilon_y+ \varepsilon_{mult} + \text{gemischte terme})$

$\dot{=} ~x\cdot y(1+\epsilon_x+\epsilon_y+\epsilon_\text{mult.})$

Gleichheit in 1. Ordnung

Für relative Fehler:

$| \frac{\overset{\sim}{ z}-xy}{xy} | \leq |\varepsilon_x| + |\varepsilon_y|+|\varepsilon_{mult}|$

Keine Verstärkung von Eingangsfehler

Division: $y,\tilde y\neq 0$

$\tilde{z} =rd\left(\frac {\overset{\sim}{x}}{\overset{\sim}{y}} \right)=\frac{x(1+\epsilon_x)}{y(1+\epsilon_y)}(1+\epsilon_\text{div})$

$\left[ \frac{1}{1+\varepsilon}=\frac{1}{1+\varepsilon}|_{\varepsilon=0} + (\frac{1}{1+\varepsilon})'|_{\varepsilon=0} \varepsilon+... = 1- \varepsilon +...\right ]$

$\begin{split}\tilde z&\dot=\frac{x}{y}(1+\varepsilon_x)(1 - \varepsilon_y)(1 + \varepsilon_{div})\\
&\dot = \frac{x}{y} (1+\varepsilon_x-\varepsilon_y+\varepsilon_{div})\end{split}$

$\implies$ Auch hier keine Verstärkung vom Eingangsfehler

Addition/Substraktion

$\tilde z=rd(\tilde x+\tilde y)=(x(1+\varepsilon_x)+y(1+\varepsilon_y))(1+\varepsilon_{add})$

$\dot=(x+y)(1+\frac{x}{x+y}\varepsilon_x+\frac{y}{x+y}\varepsilon_y+\varepsilon_{add})$

2 Fälle:
1) $x$ und $y$ haven gleiches Vorzeichen

$\Rightarrow K_x:=\mid \frac{x}{x+y}\mid < 1~~ K_y = | \frac{y}{x+y}|< 1~~ |K_x|+|K_y|=1$

$\implies$Keine Verstärkung von Eingangsfehler

2. $x$ und $y$ haben unterschiedliche Vorzeichen:

Annahme: $x>0,~ y<0 \Rightarrow K_x$ oder $K_y > 1$
$\Rightarrow$ Verstärkung von Fehler

Schlimmster Fall: $|x| \approx |y|$
$\implies K_x \text{ oder } K_y >> 1$

##### Bsp

Normalisiert: $0.00002222\cdot 10^{-4}$

Eingaben: 8 Stellen exakt
Ergebnis: 4 Stellen korrekt

$\implies$ Fehlerverstärkung um Faktor $10^4$

##### <font color=green> Bemerkung: </font>

- Stimmen $l$ Dezimalstellen überein, so ergibt sich eine Verstärkung von mindestens $10^{l-1}$. Dieser Effekt heißt <font color=red>Auslöschung </font>führender Stellen.

- Auslöschung ist ein Phänomen der Fortpflanzung von Eingangsfehlern.

## 2.4 Kondition von Aufgaben, Stabilität von Algorithmen
Aufgaben:
- Eingangsdaten $p\in\mathbb{R}^{n_{p}}$
- Aufgabe:
- $x=f(p), x\in \mathbb{R}^n$
- $f:D\subset \mathbb{R}^{n_p} \rightarrow \mathbb{R}^n$ 2mal stetig diff'bar

### Hilfsmittel für die Fehleranalyse
Frage: $\overset{\sim}{p}= p+ \Delta p$ (gestörte Daten mit $\Delta p$ Fehler)

Auswirkung von $\Delta p$ auf $\Delta x= f\cdot (p+\Delta p)-f(p)$

Hilfsmittel für die Fehleranalyse:

Taylor: $\Delta x = \frac{\partial f}{\partial p}(p)\Delta p+R(p,\Delta p)~\forall x \in \mathbb{R}^n$

Restglied:

$R(p, \Delta p)=O(||\Delta p||^2)$

Komponentenweise:
$\underbrace{f_j(p+\Delta p)-f_j(p)}_{\Delta x_j}=\frac{\partial f_j}{\partial p}(p)\Delta p+\underbrace{\frac12 \Delta p^T\frac{\partial f_j(p+\tau_j\Delta p)}{\partial p}\Delta p}_{R_j(p,\Delta p)=O(||\Delta p||^2)},~\tau_j\in[0,1]$

#### <font color=red> Def Landau Symbole </font>

Funktionen $g(t),h(t), t\in \mathbb{R}^t$

1. $g(t)=O(h(t)) \text{ für } t\to 0$ bedeutet für kleine $t\in [0,t.] \text{ gilt } |g(t)|\leq c\cdot |h(t)| \text { mit } c \geq 0$
2. $g(t)=o(h(t)) \text{ für } t\to 0$ falls für kleine $t\in[0,t]$ und eine Funktion $c(t)\to 0$, $t\to 0$ gilt: $|g(t)|~\leq~|c(t)h(t)|$

Analog für $t\to\infty$

#### Taylorreihe und Fehlerfortpflanzung
Der Absolute Fehler:
$\Delta x= f(p+\Delta p)-f(p)\dot= \frac{\partial f}{\partial p}p\Delta p,~\forall x\in \mathbb{R}^n$

$\Delta x_j\dot= \sum\limits_{i=1}^{k} \frac{\partial f_j}{\partial p_i}(p)\Delta p_i$ Komponentenweise

Relativer Fehler in Daten: $\frac{\Delta p_i}{p_i}$

Relativer Fehler im Ergebnis: $\frac{\Delta x_j}{x_j}\dot= \sum_{i=1}^k\frac{\partial f_j}{\partial p_i}(p)\frac{p_i}{x_j}\frac{\Delta p_i}{p_i}$

$\implies |\underbrace{\frac{\Delta x_j}{x_j}}_{\text{relativer Fehler in Ergebnis}}| \dot\leq \sum\limits_{i=1}^{k} |\underbrace{\frac{\partial f_j(p)}{\partial p_i}\cdot \frac{p_i}{x_j}}_\text{Faktoren}|\cdot |\underbrace{\frac{\Delta p_i}{p_i}}_\text{rel. Fehler in Daten}|$

### Definition Konditionszahlen
Die großen $\kappa_{ji}(p)=\frac{\partial f_j(p)}{\partial p_i}- \frac{p_j}{\underbrace{x_j}_{=f_j(p)}}$ heißen relative Kondidtionszahlen der Aufgabe f im Punkt $p$.

Die Aufgabe $x=f(p)$ heißt **schlecht konditioniert** falls eine der $\mid \kappa_{ji}(p))|>>1$ ist. Andernfalls heißen sie **gut konditioniert**.

Im Falle von $|\kappa _{ji}|<1$ spricht man über Fehlerdämpfung, im Fall von $>1$ von Fehlerverstärkung.

Bsp. Konditionszahlen von elementaren Operationen

1. **Multiplikation**:

Aufgabe:

$x= f(p) = p_1 \cdot p_2, p \in \mathbb{R}^2$

Fehler im Ergebnis:
$\Delta x = \frac{\partial f}{\partial p} \cdot \Delta p= (p_2 ; p_1) \cdot \begin{pmatrix}\Delta p_1\\ \Delta p_2\end{pmatrix}= p_2 \Delta p_1 + p_1 \Delta p_2$

Relativer Fehler:

$\frac{\Delta x}{x} = \frac{p_2\cdot p_1}{\underbrace{x}_1}\cdot \frac{\Delta p_1}{p_1} + \frac{p_1 \cdot p_2}{\underbrace{x}_1} \cdot \frac{\Delta p_2}{p_2}$

$\implies$ Die Multiplikation ist gut konditioniert!

2. **Addition**:

Aufgabe:

$x=f(p)=p_1+p_2$

Fehler:

$\Delta x = \frac{\partial f}{\partial p}\Delta p=(1;1) \begin{pmatrix}\Delta p_1\\ \Delta p_2\end{pmatrix}=\Delta p_1 +\Delta p_2$

Relativer Fehler:

$\frac{\Delta x}{x}=\frac{p_1}{x}\frac{\Delta p_1}{p_2}+\frac{p_2}{x}\frac{\Delta p_2}{p_2}$

$\implies \frac{p_1}{p_1+p_2}= \frac{1}{1+\frac{p_2}{p_1}}$ Analog für $\frac{p_2}{p_1+p_2}$

$\implies$ Die Addition ist schlecht konditioniert falls $p_1 \approx -p2$

Bsp. LGS $Ax=b$

$\begin{pmatrix} 1 & 10^6\\ 0 & 1 \end{pmatrix} \cdot \begin{pmatrix}x_1\\ x_2\end{pmatrix}= \begin{pmatrix} b_1 \\ b_2 \end{pmatrix}$

Lösung

$\begin{pmatrix} x_1 \\ x_2 \end{pmatrix} = \begin{pmatrix} 1 & -10^6 \\ 0 & 1 \end{pmatrix} \cdot \begin{pmatrix} b_1 \\ b_2 \end{pmatrix}$

Sei $b=\begin{pmatrix} 1\\0\end{pmatrix}\implies x=\begin{pmatrix}1\\0\end{pmatrix}$

$b=\begin{pmatrix} 1\\10^{-3}\end{pmatrix}\implies x=\begin{pmatrix}-999\\10^{-3}\end{pmatrix}\neq\begin{pmatrix}1\\0\end{pmatrix}$
Ist schlecht konditioniert!

### Stabilität von Algorithmen

Sei $f: p \overset{f}\longmapsto x$ ein Algorithmus.

Frage: $\Delta p \mapsto \Delta x$?

Algorithmus hat Zwischenschritte $\varphi _i$ und Zwischenergebnisse $z_i$ mit Fehler:

$p := z_0 \overset{\varphi_0}{\to} z_1 \overset{\varphi_1}{\to} z_2 \to ... \overset{\varphi_{m-1}}{\to} z_m \overset{rd}{\to} x$

$\Delta p_i := \Delta z_0 \overset{\varphi_0}{\to} \Delta z_1 \overset{\varphi_1}{\to} \Delta z_2 \to ... \overset{\varphi_{m-1}}{\to} \Delta z_m \overset{rd}{\to} \Delta x$

Alle Zwischenschritte $\varphi _i$ sind mit Fehlerentstehung und Fehlerfortplanzung behaftet

$\Delta z_i=\underbrace{\Delta z_i^\text{neu}}_{\text{neue Fehler des Schrittes }\varphi_{i-1}} + \underbrace{\varphi_{i-1}(z_{i-1}+\Delta z_{i-1})-\varphi_{i-1}(z_{i-1})}_{\text{Fehlerfortpflanzung von alten Fehlern }\Delta z_{i-1}}$

$~~~~~~~\overset{\circ}{=}\Delta z_i^{\text{neu}}+\frac{\partial \varphi_{i-1}(z_{i-1})}{\partial z_{i-1}}\Delta z_{i-1}$

Restabbildung $\overset{\sim}{\varphi_i} := \varphi_m \circ \varphi_{m-1} \circ ... \circ ~\varphi_i$ pflanzt Fehler im Schritt $\varphi_i$ auf $x$ fort.

Für den gesamten Fehler gilt:

$\Delta x^\text{ges}\dot= \underbrace{\frac{\partial f}{\partial p}(p)\Delta p}_{{\Delta x^E}\text{ Fortpflanzung des Eingangsfehlers}}$

$+\underbrace{\sum_{i=1}^m \frac{\partial \tilde\phi _{i+1}}{\partial z_i}\Delta z_i^{\text{neu}}}_{\Delta x^A \text{ Fortpflanzung des Algorithmusfehler}} + \underbrace{rd(z_m)-z_m}_{\text{Fehler des letzten Schritts}}$

#### Definition Stabilität von Algorithmen
Ein Algorithmus heißt stabil (oder instabil), wenn der vom Algorithmus verursachte Fehler $\Delta x^A$ klein oder nur moderat (groß) gegenüber dem unvermeidbaren, fortgeplanzten Eingangsfehler $\Delta x^E$ ist.


Aufgabe gut/schlecht konditioniert


Falls der Algorithmus stabil ist, dann ist $\tilde p \approx p$.

<span style="background-color:green">Mrs. Robinson</span>,

### Beispiel: Lösung von quadratischen Gleichungen

$y^2-py+q=0$, mit $p,q\in \mathbb{R}$ and $q \neq 0$

$\implies y_{1,2}= \frac{p}{2} \pm \sqrt{\frac{p^2}{4}-q}=: f_{1,2}(p,q)$

Wurzel $y_1$ und $y_2$ erfüllen:

$\underbrace{p=y_1+y_2}$, $\underbrace{q=y_1\cdot y_2}$

$\begin{matrix}
\frac{dp}{dp} = 1 = \frac{\partial y_1}{\partial p}+\frac{\partial y_2}{\partial p} & \frac{dq}{dp} = 0 = \frac{\partial y_1}{\partial q}+\frac{\partial y_2}{\partial q} \\
\frac{dp}{dq} = 0 = \frac{\partial y_1}{\partial p}+\frac{\partial y_2}{\partial p} & \frac{dq}{dq} = 1 = \frac{\partial y_1}{\partial q}+\frac{\partial y_2}{\partial q} \end{matrix}$

Lösung für $\frac{\partial y_1}{\partial p}$, $\frac{\partial y_2}{\partial p}$ (1. Zeile von der Matrix)
Lösung für $\frac{\partial y_1}{\partial q}$, $\frac{\partial y_2}{\partial q}$ (2. Zeile von der Matrix)

Lösung:

$\begin{matrix}\frac{\partial y_1}{\partial p} = \frac{y_1}{y_1-y_2}& \frac{\partial y_2}{\partial p}=\frac{y_2}{y_2-y_1}\\ \frac{\partial y_1}{\partial q}= \frac{1}{y_2-y_1} & \frac{\partial y_2}{\partial q}=\frac{-1}{y_2-y_1}\end{matrix}$

Konditionszahlen:
$\kappa_{11}(p,q)=\frac{\partial f_1}{\partial p} \cdot \frac{p}{y_1}= \frac{y_1}{y_1-y_2}\cdot \frac{p}{y_1}=\frac{y_1+y_2}{y_1-y_2}=\frac{1+\frac{y_2}{y_1}}{1-\frac{y_2}{y_1}}$

$\kappa_{12}(p,q)=\frac{\partial f_1}{\partial q} \cdot \frac{q}{y_2}= \frac{1}{y_2-y_1}\cdot \frac{y_1\cdot y_2}{y_1}=\frac{1}{1-\frac{y_1}{y_2}}$

$\implies$ $\kappa_{11}(p,q)$ und $\kappa_{12}(p,q)$ sind groß, falls $y_1 \approx y_2 \implies$ schlecht konditioniert, falls $y_1\approx y_2$

- Betrachten wir gut konditionierte Aufgaben:
- $y^2-py+q=0$ mit $p<0$ und $0\neq q \ll \frac{p^2}{4}$, d.h. $|\frac{y_1}{y_2}| \gg 1$
- Algorithmus: $u= \frac{p^2}{4}$, $v=u-q$, $w=\sqrt{v}$

Fehlerfortpflanzung:

$\frac{\Delta u}{u}\overset{\cdot}{=}\frac{2p}{4} \cdot \frac{p}{u}\cdot \frac{\Delta p}{p}= \frac{\Delta p}{p}$

$[u=f(p)]$

$\frac{\Delta v}{v} \overset{\cdot}{=} \frac{1\cdot u}{v} \cdot \frac{\Delta u}{u} +\frac{-1 \cdot q \cdot \Delta q}{v\cdot q}$

$[v=f(u,g)]$

$\frac{u}{v}= \frac{\frac{p^2}{4}}{\frac{p^2}{4}-q}=\frac{1}{1-\underbrace{ \frac{q\cdot 4 }{p^2}}_{q \ll \frac{p^2}{4}}}\approx 1$

$\frac{q}{v}= \frac{q}{u-q}= \frac{1}{\frac{u}{q}-1}\ll 1$

$\frac{u}{q}= \frac{p^2}{4} \cdot \frac{1}{q} \gg 1$

Analog für den Rest.

$\implies \frac{\Delta w} w \dot = \frac 1 2 \frac{\Delta v}{v}$

Um Auslöschung zu vermeiden, berechnen wir zuerst

$\tilde y_2 = \frac p 2 - w$

Relativer Fehler:

Für $\frac{\Delta y_2}{y_2} \dot = \underbrace{\frac12 \frac{p}{y^2}}_{\underbrace{=\frac{p}{p-2w}}_{\underbrace{\approx \frac12}_{\text{weil } w \approx -\frac{p}{2}}}} \frac{\Delta p}{p} - \underbrace{\frac{w}{y_2}}_{\frac{2w}{p-2w}\approx \frac{1}{2}}\cdot \frac{\Delta w}{w}$:

Berechnung von Wurzel $y_2$

$[y_2=f(p,w)]$

Variante A
$\tilde y_1=\frac p 2 + w$

Variante B
$\tilde y_1=\frac q {\tilde{y}_2}$

Wegen $w \approx \frac{-p}{2}$ tritt bei Variante A zwangläufig eine Auslöschung ein.

$|\frac{y_1}{y_1}| \dot= |\frac{p}{p+2w}||\frac{\Delta p}{p}|+|\frac{2w}{p+2w}||\frac{\Delta w}{w}|$

Fazit: Variante A instabil, Variante B stabil!

Schauen Sie hier nach:
https://entwickler.de/programmierung/top-10-der-software-katastrophen

oder

https://www.uni-frankfurt.de/63789753/numerik.pdf

<!---30.04--->

# Einschub: Grundbegriffe der linearen Algebra und Analysis 2
## Vektorraum
Definition

Eine Menge $V$ mit einer Verkönüpfung "Addition"
$$+: V\times V \to V, (v,w)\mapsto v+w$$

und einer Verknüpfung "Multiplikation mit Skalaren"
$$\cdot: \mathbb{R} \times V\to V, (\lambda,v)\mapsto \lambda \cdot v$$

heißt Vektorraum (über $\mathbb{R}$) wenn
- $V1$ $(V,+) ist eine abel'sche Gruppe (d.h. kommutativ)

$$\begin{split} (\lambda+\mu) \cdot v&=\lambda \cdot v +\lambda \cdot w \\ \lambda \cdot (v+w) \end{split}
$$

## Lineare Hülle

> Einschub nach vl ergänzen my brain is not braining this fast - agree

# Noch VL vom 2.5 Ergänzen

.

.

### Satz 3.4.1

<!--- Nachtragen --->

#### Beweis

Notation: $p_{i,j}\in P_k$ mit Grad $k:=j-i$ des Polynoms, das die Punkte $(x_iy_i) ... (x_j,y_j)$ interpoliert. Dann $p_{o,n}$ des gas gesuchte Polynom.

Wir zeigen dass
$p_{i,j}(x)=y[x_i] +y[x_i, x_{i+1}] (x-x_i)+..+y[x_i,...,x_j](x-x_i)$:

(woraus mit $i=0$, $j=n$ die Aussage von Satz 3.4.1 folgt)

Induktion bzgl. $k$

$k=0:~~p_{i,j}(x)\equiv y_i=y[x_i]~~\checkmark$

Übergang von $k-1\implies k$: Seien $i< j, k = j-i$

Aus Induktionsannahme $\implies$ für $(k-1)$ Aussage des Satzes

$p_{i,j}(x)=\underbrace{p_{i,j-1}(x)}_{grad(k-1)}+a_k(x-x_i)...(x-x_{j-1})$

z.zg: $a_k=y[x_i,\dots,x_j]$

Es ist leicht zu erkennen, dass $a_k$ ist der Koeffizient zu $x^k$ ist.

(weil $p_{i,j-1}(x)$ von $grad(k-1)$)

$a_k$ ist der Koeffizient zu $x^k$ in $p_{i,j}(x)$ (weil $p_{i,j-1}(x)$ von $grad(k-1)$)

Betrachte

$q(x):=\frac{(x-x_i)p_{i-1,j}-(x-x_j)p_{i,j-1}}{x_j-x_i}\in P_k$

:::info
$p_{i-1,j}$ und $p_{i,j-1}\in P_{k-1}$
:::

- $q(x)\in P_k$
- interpoliert $(x_i,y_i)...(x_j,y_j)$
- überprüfen:
- $x=x_l, ~~~ i<l<j$
- $p_{i,j-1}(x_l)=y_l$
- $q(x_l)=\frac{x_l-x_i-x_l+x_j}{x_j-x_i}y_e=y_e$
- analog für $x=x_i$ und $x=x_j$

Polynomaufgabe eindeutig lösbar
$\implies$
$q(x)=p_{i,j}(x)$

Koeffizienten zu $x^{k-1}$ in $p_{i+1,j}$ und $p_{i,j-1}$ sind $y[x_{i+1},\dots,x_j]$ resp. $y[x_i,\dots,x_{j-1}]$

$\implies$ Koef zu $x^k$ in $q(x)$ is

$\frac{y[x_{i+1}\dots x_j]-y[x_i\dots x_{j-1}]}{(x_j-x_i)}$

$=\underbrace{y[x_i,...,x_j]}_{=a_k\text{ q e d}}$

Bemerkungen:

- Eindeutigkeit des **Interpolationspolynoms** + **Unabhängigkeit** von $a_n$ von der Numerierung von Stützstellen.
- $\implies y[x_{i_0}, ..., x_{x_n}]=y[x_0,...,x_n]$
- hier ist $(i_b,...,i_n)$ eine beliebige Permutation von $(0,...,n)$
- Tabelle: Dividierte Differenzen

| i | $x_i$ | $y_[x_i]$ | $y_[x_i,x_{i+1}$ | ... | $y[0\dots n]$ |
|:---: | :---:| :---: | :---: | :---: | :---: |
| 0 | $x_0$ | $y_0$ | $\frac{y[x_1]-y[x_0]}{x_1-x_0}$ | ... | |
| 1 | $x_1$ | $y_1$ | $\frac{y[x_2]-y[x_1]}{x_2-x_1}$ | ... | |
| 2 | $x_2$ | $y_2$ | $\frac{y[x_3]-y[x_2]}{x_3-x_2}$ | ... | |
| ... | ... | ... | ... | ... | |
| n-1 | $x_{n-1}$ | $y_{n-1}$ | $\frac{y[x_n]-y[x_{n-1}]}{x_{n}-x_{n-1}}$ | | |
| n | $x_n$ | $y_n$ | | | |

yeah okay, no
just imagine the lines, i dunno

- Mit Hilfe von (NS)(Neville-Schema) berechnet man die Polynome $p_{i,j}(x)$
- Diese bodenlosen Pfeile werden auch als Neville-Schema oder Neville Darstellung bezeichnet
<!--- later --->
>boooooooooooooooooooooodenlose pfeile
>[name=olga]
> xDDDDD
> [name=felix]
> very pain
> [name=xel]

- ! Annahme: alle Stützstellen paarweise verschieden
- **Algorithmus**: Neville Schema/Auswertung von Polynomen an einer Stelle $\xi \in \mathbb{R}$


- Die Idee ist, dass wir ausgehend von einer Menge an Datenpunkten ein Polynom finden, dass diese Werte bestmöglich beschreibt, sodass wir im Nachhinein für einen Wert $\xi$ der nicht in unseren ursprünglichen Datenpunkten liegt vorhesagen können welchen Wert er annimt. Dafür nehmen wir an, dass unser Polynom $f(\xi)\approx p(\xi)$. Falls wir genügend Datenpunkte(Stützstellen) haben, sollte dies auch genügend gut funktionieren

Gegeben:
$(x_0,y_0)...(x_n,y_n),\xi$

Gesucht:

$p(\xi)=p_{0,n}(\xi)$
für $k=0,...,n$ setze $P_{k,k}=y_k$
für $l=1,...,n$ und

fpr $k=0,...n-l$ berehcne

$p_{k,k+l}=p_{k,k+l-1}+(\xi-x_k)\frac{p_{k+1,k+l}+aaaaaaaa}{x_{k+l}aaa}$

$\implies$ Mit Neville Schema kann man $p(\xi), \xi \neq x_i$ auswerten

- Auswertung von Polynomen mit Horner Schema

Gegeben:

$p(x)=a_0+a_1x+...+a_nx^n,\xi \neq x_i$

Horner Schema:

Berechne $b_k=\begin{cases} a_n, ~ n=k \\ a_k + b_{k+1}, k=n-1,...,0\end{cases}$

$\implies p(\xi) = b_0$

Gegeben: $p(x) = a_0 +a_1(x-x_0) + ...+ a_n(x-x_0)...(x-x_{n-1})$

Verallgemeinertes Horner Schema:

$b_k= \begin{cases} a_n, n= k \\ a_k +( \xi - x_k) b_{k+1}, k= n-1,...,0\end{cases}$

$\implies p(\xi)=b_0$

##### Beispiel
Stützstellen:
- $(x_0,y_0) = (0,1)$
- $(x_1,y_1) = (1,4)$
- $(x_2,y_2) = (2,3)$

Gesucht ist: $p\in P_2$ (Polynom vom Grad 2)

###### (a) Monombasis $\{ 1,x,x^2\}$
$\begin{pmatrix}
1, 0, 0\\
1, 1, 1\\
1,2,4
\end{pmatrix} \cdot \begin{pmatrix}
a_0\\a_1\\a_2\end{pmatrix}
= \begin{pmatrix}1\\4\\3\end{pmatrix}$
$\implies \begin{pmatrix}
a_0\\a_1\\a_2\end{pmatrix}
= \begin{pmatrix}1 \\5 \\ -2\end{pmatrix}$

###### (b) Lagrange-Darstellung

$\begin{split}p(x)&= \underbrace{1\cdot L_0^{(2)}(x)}_{y_0}+\underbrace{4\cdot L_1^{(2)}(x)}_{y_1}+\underbrace{3 \cdot L_2^{(2)}(x)}_{y_2}\\ &= 1 \cdot \frac{(x-1)(x-2)}{(0-1)(0-2=)}+4\frac{(x-0)(x-2)}{(1-0)(1-2)}+3 \frac{(x-0)(x-1)}{(2-0)(2-1)}\\ &=\frac12 (x-1) (x-2)-4x(x-2)+\frac32 x(x-1) \end{split}$

###### (c) Newton-Darstellung

TODO: TABELLE MIT PFEILEN EINFÜGEN

> there is no such thing as too many arrows.... right?
> [name=xel]
> definetly not
> [name=olga]
> i mean the arrows and the concept overall are quite straigthforward. I am howewer utterly clueless as to how to make them in Tex/markdown
> [name=felix]
> possible (in tex), but too much work for during a lecture
> [name=xel]
> yeaah think with tikz or smthg meybe
> [name=olga]
> there was other stuff here too that we forgot
> [name=olga]

## 3.5 Interpolation von Funktionen und Interpolationsfehler

gegeben: Stützpunkte $y_i=f(x_i), ~~ x_i \in[a,b], ~~ i=0,...,n$
Knotenwerte $y_i$ sind Funktionswerte von $y:[a,b] \longrightarrow \mathbb{R}$

Frage: Wie gut approximiert das zugehörige Interpolationsoolynom $p\in P_n$ die Funktion $f$ auf $[a,b]$?

**Notation**:
- $I(x_0,...,x_n)$ ist das kleinste Intervall, das die Punkte $x_0,...,x_n$ enthält.
- $C[a,b]$ Vektorraum der stetigen Funktionen über $[a,b]$
- $C^k[a,b]$ - Vektorraum von k-mal stetig diff.baren Funktionen

### Satz 3.5.1 (Interpolationsfehler)
Sei $\in C^{n+1}[a,b]$. Dann gilt:

$~~~~~\forall x\in[a,b] \exists \xi_x \in I(x_0,...,x_n,x):$

$~~~~~f(x)-p(x)= \frac{f^{(n+1)}(\xi)}{(n+1)!}\prod\limits_{j=0}^n (x-x_j)$

**Beweiß** wird in den Notizen provided, alternativ im scheichl skript nachschauen

### Korollar 3.5.2
Unter Vorraussetzung von Satz 3.5.1 mit $a=x_0 < x_1 < ... < x_n=b$ gilt:

$||f-p||_{\infty,[a,b]} \leq \frac{|x_n-x_0|^{n+1}}{(n+1)!}||f^{(n+1)}||_{\infty,[a,b]}$

#### Beispiel:
Interpoliere $sin(x)$ durch kubische Polynome auf $x_{i-1},xt_i,x_{i+1},x_{i+2}$ auf $[x_i, x_{i+1}]$ so dass:
$|\text{Fehler}(x)| < \text{Toleranz(TOL)}, ~~~~ x\in [x_i, x_{i+1}]$.

Aus Satz 3.5.1 folgt:

$\begin{split}|\text{Fehler}(x)| &= \mid \frac{sin^4(\xi)}{4!} \mid \cdot \mid (x-x_{x-1}(x-x_i)(x-x_{i+1})(x-x_{i+2}) \mid\\
&\leq \frac{1}{4!} \frac32 h \cdot \frac12 h \cdot \frac12 h \cdot \frac32 h= \frac{3}{128}h^4 \leq TOL\end{split}$

z.B $TOL = 10^{-6}\implies h \leq 0.8 \cdot 10^{-1}$

#### Bemerkung (Diskussion)
z.B. für $x_i=ih$, $h=\frac{1}{h}$ auf $[0,1]$
$||f-p||_{\infty,[a,b]} \leq \frac{||f^{n+1}||_{\infty,[0,1]}}{{2^n(n+1)!}}$

$\implies$ falls $||f^{(n+1)}||_{\infty,[0,1]}$ beschränkt, dann wird Fehler reduziert mit $O(\frac{2-n}{(n+1)!}$ für $n \ti \infty$

Aber: meistens die Ableitungen von $f$ haben ein zu starkes Wachstum für $n \to \infty$, z.B. "Runge Funktion"

$f(x) = \frac{1}{1+25x^2}\implies f^{(n)}(x) \approx 2^n n! O(|5x|^{-(n+2)})$

> Frage: Hat die Runge Funktion einen bezug zu Runge-Kutta?
> [name=felix]

.