# Lösungen Altklausur WS1920
###### tags: `Altklausuren`
## Aufgabe 1
### a)
A lässt sich folgendermaßen zerlegen: $A=QR$ mit $Q\in \mathbb{R}^{M\times M}$ orthogonal und $R=\begin{pmatrix}\tilde{R} \\ 0 \end{pmatrix} \in \mathbb{R}^{M\times N}$, wobei $\tilde{R} \in \mathbb{R}^{N\times N}$ eine obere Dreiecksmatrix ist.
Zur Lösung von $Ax=b$ :
1. Berechne QR-Zerlegung von A (durch Householder-Transformationen)
2. Löse $Qy=b$. $y$ kann so berechnet werden: $y=Q^\top b$
3. Löse $Rx=y$

Dann ist $x$ eine Lösung von $Ax=b$, denn $Ax=QRx=Qy=b$.
### b)
Die QR-Zerlegung ist stabiler zu berechnen, als die beiden anderen Zerlegungen.
* Aufwand QR-Zerlegung $\frac{2}{3} N^3$ Operationen
* Aufwand LR-Zerlegung $\frac{1}{3} N^3$ Operationen
* Aufwand Cholesky-Zerlegung $\frac{1}{6} N^3$ Operationen
### c)
### d)
Sei $v_w$ der Anteil von $v$, der orthogonal auf der Hyperebene steht, die durch $w$ als Normalenvektor definiert wird. ($v_w$ zeigt in die gleiche Richtung wie $w$).
Es gilt: $v_w=\frac{1}{2}w\,\begin{Vmatrix}v-u\end{Vmatrix}_2$ und $u_w=-\frac{1}{2}w\,\begin{Vmatrix}v-u\end{Vmatrix}_2$
sowie $w^\top(v-v_w)=0$ und $w^\top(u-u_w)=0$
Daraus folgt:
$Qv=(I_N-2ww^\top)v=v-2(w^\top v)w=v-2(w^\top v_w)w=v-2\frac{1}{2}\begin{Vmatrix}v-u\end{Vmatrix}_2(w^\top w)w\\=v-\begin{Vmatrix}v-u\end{Vmatrix}_2 w=u$
Und:
$Qu=(I_N-2ww^\top)u=u-2(w^\top u)w=u-2(w^\top u_w)w=u+2\frac{1}{2}\begin{Vmatrix}v-u\end{Vmatrix}_2(w^\top w)w\\=u+\begin{Vmatrix}v-u\end{Vmatrix}_2 w=v$
Bei den letzten Gleichheitszeichen ist beide Male die Definition von $w$ eingesetzt.
## Aufgabe 2
### a)
Siehe Übung
### b)
Siehe Übung
ODER:
Um $\underset{x\in\mathbb{R}^N}{min}\;f(x)$, $f(x):\mathbb{R}^N\rightarrow \mathbb{R}$ zu finden, ist die Nullstellengleichung $grad\;f(x)=\nabla f(x)=0_N^\top$ sowohl notwendig, als auch hinreichend, wenn der Startwert nahe genug an der Lösung ist. Entsprechend ergibt sich das Newton-Verfahren zu:
$x^{k+1}=x^k-H_f(x^k)^{-1}\nabla f(x^k)$
### c)
$x^0=(0\;\;0)^\top$
Lösung:
$x^1=(-1\;\;0)^\top$
Rechenweg:
$\nabla f(x^0)=\begin{pmatrix}1\\0\end{pmatrix}, H_f(x^0)=\begin{pmatrix}-1&1\\1&0\end{pmatrix}$
$H_f(x^0)d^0=-\nabla f(x^0)$
$x^1=x^0+d^0$

## Aufgabe 3
### a)
$p(x)=-2+2(x-1)-\frac{4}{3}(x-1)(x-2)$
### b)
$p(x)=-2+2(x-1)-\frac{4}{3}(x-1)(x-2)-\frac{1}{2}(x-1)(x-2)(x-4)$
### c)
siehe Übung 4 Aufgabe 3
### d)
Mit $f(x)=cos(x\pi)$:
$f(x)-p(x)=w_{N+1}(x)\;\cdot\;\frac{f^{(N+1)}(\xi)}{(N+1)!}\leq \frac{1}{2^N}\cdot\frac{f^{(N+1)}(\xi)}{(N+1)!}\leq\frac{\pi^{N+1}}{2^N (N+1)!}\stackrel{!}{\leq}10^{-10}$
Durch der $x\pi$ im Cosinus wird das Intervall $[-\pi, \pi]$ linear auf das Intervall $[-1, 1]$ abgebildet. Aufgrund der Symmetrie des Cosinus reicht es das Intervall $[0, \frac{\pi}{2}]$ als Grundlage zu verwenden und dann mit $f(x)=cos(\frac{\pi}{4}x+\frac{\pi}{4})$ zu rechnen.

Siehe auch Übung 4 Aufgabe 4
## Aufgabe 6
### a)
$L=\begin{pmatrix}3&0&0&0\\1&1&0&0\\0&2&2&0\\0&0&1&\sqrt{2}\end{pmatrix}$
### b)
Lineares Ausgleichsproblem:
Gegeben: $A\in \mathbb{R}^{M\times N}, b\in\mathbb{R}^M$
$\begin{Vmatrix}Ax-b\end{Vmatrix}_2=min!$
Anwendung: Falls $M>N\;(oft\;M>>N)$ und $Ax=b$ nicht lösbar.
### c)
### d)
Maschinengenauigkeit eps: $eps=\frac{B^{1-L_m}}{2}$
Kleinste positive Gleitpunktzahl: $min FL_+=B^{e_{min}-1}$
Größenordnungsmäßig:
$eps$ : $10^{-16}$
$min FL_+$: $10^{-308}$
### e)
$\frac{|(\tilde{x}+\tilde{y})-(x+y)|}{|x+y|}\leq\frac{|(1+\varepsilon)(x+y)-(x+y)|}{|x+y|}=\varepsilon\frac{|x+y|}{|x+y|}\leq\varepsilon\frac{|x|+|y|}{|x+y|}$
Haben $x$ und $y$ gleiche Vorzeichen, so ist der Bruch 1, in diesem Fall ist die Summe also gut konditioniert.
Haben $x$ und $y$ unterschiedliche Vorzeichen, so ist der Bruch möglicherweise sehr groß, in diesem Fall ist die Summe also schlecht konditioniert.