[Numerik I] - Übung 3 *

11.01.2009, 12:38	tigerbine	Auf diesen Beitrag antworten »
[Numerik I] - Übung 3 * Aufgaben - Teil 3 Operatornorm QR-Zerlegung als stetige Abbildung Fehler beim Orthogonalisieren (Cauchy Schwarze Ungleichung) Kondition und Fehler beim Lösen von LGS
11.01.2009, 13:19	tigerbine	Auf diesen Beitrag antworten »
3.1 Operatornorm Sei nun M eine reguläre komplexe Matrix. Zum Nachweis der Normeigenschaft gilt es die Axiome zu überprüfen. Dabei gilt hier die Definition $\begin{eqnarray} \\|x\\|_M:=\\|Mx\\| \end{eqnarray}$ für eine beliebige Norm des $\begin{eqnarray} \mathbb C^n \end{eqnarray}$ $\begin{eqnarray} \\|x\\|_M =0 \Leftrightarrow \\|Mx\\| =0 \Leftrightarrow x = 0 \end{eqnarray}$ Die ist durch die Regularität von M erfüllt und auch nur so möglich. Durch eine beliebige Matrix kann also auf diese Weise keine Norm erzeugen. $\begin{eqnarray} \\|\alpha \cdot x \\|_M = \\|\alpha Mx\\| = \alpha \cdot \\|Mx\\|,~\alpha \in \mathbb C \end{eqnarray}$ Hierbei dürfen wir einfach auf die Normeigenschaften von \|\|.\|\| zurückgreifen. $\begin{eqnarray} \\|x+y\|\|_M = \\|M(x+y)\\| = \\|Mx+My\\| \leq \\|Mx\\|+\\|My\\| \end{eqnarray}$ Hierbei dürfen wir einfach auf die Normeigenschaften von \|\|.\|\| zurückgreifen. Wie lautet nun die induzierte Matrixnorm? $\begin{eqnarray} \\|A\\|_M = \sup_{\\|x\\|_M=1}~\\|Ax\\|_M =\sup_{\\|Mx\\|=1}~\\|MAx\\| =\sup_{\\|Mx\\|=1}~\\|MAM^{-1}Mx\\| =\\|MAM^{-1}\\| \end{eqnarray}$
11.01.2009, 19:04	tigerbine	Auf diesen Beitrag antworten »
3.2 QR-Zerlegung als stetige Abbildung Man untersuche die QR-Zerlegungen mittel Gram-Schmidt. Sie besteht aus lauter stetigen Zwischenschritten und somit folgt auch, dass die QR-Zerlegung stetig ist. Es bleibt zu erwähnen, dass man diese Argumentation nicht mit Givens-Rotationen oder Housholderspiegelungen durchführen kann, da diese Schritte nicht stetig sind. Auch wenn die Komposition der Abbildungen am Ende stetig ist.
11.01.2009, 19:04	tigerbine	Auf diesen Beitrag antworten »
3.3 Fehler beim Orthogonalisieren Aufgabenteil a Hierzu benutzen wir die Cauchy-Schwarze-Ungleichung, von der hier ein Speziallfall dargestellt ist. An diesem machen wir uns klar, dass im Falle der Linearen Abhängigkeit von a und q die Gleichheit gilt: $\begin{eqnarray} \|<a,q>\|^2 ~\leq ~<a,a>~<q,q> \end{eqnarray}$ Hier vereinfacht sich das zu: $\begin{eqnarray} \|<a,q>\|^2 \leq 1 \end{eqnarray}$ Wir wollen die Behauptung durch die Äquivalenz der negierten Aussagen zeigen. Sei $\begin{eqnarray} \|a^Tq\| =1 \end{eqnarray}$ . Kombinieren wir nun a und q linear, so ergibt sich: $\begin{eqnarray} <a-(a^Tq)q,a-(a^Tq)q> &&= <a,a> - 2<a,(a^Tq)q> + <(a^Tq)q, (a^Tq)q> \\&&= 1 - 2(a^Tq)<a,q> + (a^Tq)^2<q,q> \\&& = 1-2(a^Tq)^2+1 \\&& = 0 \end{eqnarray}$ Der einzige Vektor für den dies gilt ist der Nullvektor und somit sind a und q linear abhängig. Anderseits, nehmen wir an, dass a und q l.a. sind, so folgt für einen Skalar k $\begin{eqnarray} q=ka \end{eqnarray}$ $\begin{eqnarray} \|<a,q>\|^2 = \|<a,ka>\|^2 = \|k\|^2 \cdot \|<a,a>\|^2 \leq ^{\text{CSU}} <a,a><q,q> \end{eqnarray}$ $\begin{eqnarray} \|k\|^2 \leq 1 \end{eqnarray}$ andereseits gilt auch $\begin{eqnarray} \frac{1}{k}q=a \end{eqnarray}$ $\begin{eqnarray} \|<a,q>\|^2 = \|<\frac{1}{k}q,q>\|^2 = \|\frac{1}{k}\|^2 \cdot \|<q,q>\|^2 \leq ^{\text{CSU}} <a,a><q,q> \end{eqnarray}$ $\begin{eqnarray} \|\frac{1}{k}\|^2 \leq 1 \end{eqnarray}$ Somit muss gelten \|k\|=1 und es folgt a=q und damit gilt: $\begin{eqnarray} \|<a,q>\|=1 \end{eqnarray}$ Somit folgt dann auch die Behauptung. Aufgabenteil b Hierzu vergleiche man, mit entsprechender Umbezeichnung das Gram-Schmidt-Verfahren. Wr wollen also testen, wie anfällig das Verfahren auf Rundungsfehler im ersten Schritt ist. Theoretisch sollten die neuen Vektoren ja orthogonal sein, ihr Zwischenwinkel sollte also $\begin{eqnarray} \frac{\pi}{2} \end{eqnarray}$ betragen. $\begin{eqnarray} \alpha(p_0)=\arccos\Bigl( \frac{\langle q, a-p_0q\rangle}{\langle a-p_0q,a-p_0q\rangle}\Bigr) \end{eqnarray}$ Betrachten wir den Zähler, so ergibt sich: $\begin{eqnarray} \langle q, a-p_0q\rangle =\langle q, a\rangle - p_0 \langle q,q\rangle = \langle q, a\rangle - \langle q, a\rangle \cdot 1 = 0 \end{eqnarray}$ Somit ergibt sich: $\begin{eqnarray} \alpha(p_0)=\arccos \Bigl(0\Bigr) = \frac{\pi}{2} \end{eqnarray}$ Nun schauen wir uns die Funktion an, und bilden ihre erste Ableitung, die wir für die Taylorentwicklung benötigen. $\begin{eqnarray} \alpha(p) &&= \arccos (\frac{q^t(a-pq)}{\sqrt{\langle a-pq,a-pq \rangle}}) \\&& = \arccos (\frac{q^ta-pq^tq}{\sqrt{\langle a,a \rangle -2p \langle a,q \rangle + p^2 \langle q,q \rangle}}) \\&& = \arccos (\frac{p_0-p}{\sqrt{1-2p_0p+p^2}}) \end{eqnarray}$ $\begin{eqnarray} \alpha'(p) && = -\frac{1}{\sqrt{1-\frac{(p_0-p)^2}{1-2p_0p+p^2}}} \cdot \frac{-(\sqrt{1-2p_0p+p^2} - (p_0-p)\frac{1}{2\sqrt{1-2p_0p+p^2}}(-2p_0+2p)}{1-2p_0p+p^2} \end{eqnarray}$ $\begin{eqnarray} \alpha'(p_0) && = -\frac{1}{\sqrt{1-p_0^2}} \end{eqnarray}$ Somit ergibt sich mit Taylor entwickelt um $\begin{eqnarray} p_0 \end{eqnarray}$ $\begin{eqnarray} \alpha(p_0 + \triangle p_0) && \approx \alpha(p_0) + \alpha'(p_0) (p_0+\triangle p_0 - p0) \\&&= \frac{\pi}{2} - \frac{\triangle p_0}{\sqrt{1-p_0^2}} \end{eqnarray}$ Somit ergibt sich für den relativen Fehler: $\begin{eqnarray} \frac{\alpha(p_0)-\alpha(p_0+\triangle p_0)}{\alpha(p_0)} =\frac{\frac{\triangle p_0}{\sqrt{1-p_0^2}}}{ \frac{\pi}{2}} \end{eqnarray}$
11.01.2009, 19:09	tigerbine	Auf diesen Beitrag antworten »
3.4 Kondition und Fehler beim Lösen von LGS Hier betrachten wir 2 Gleichungssysteme mit regulären Matrizen. Das zweite entsteht zum Beispiel durch die Eingabe der Daten in ein Programm. $\begin{eqnarray} Ax=b,~\hat{A}\hat{x} = \hat{b} \end{eqnarray}$ Interessiert sind wir an der Lösung x und folglich an dem relativen Fehler, den wir bei der Lösungsausgabe des zweiten Systems erhalten. Im [Workshop - Lineare Gleichungssysteme 1] hatten wir die Frage gestellt, ob es LGS gibt, die von vorneherein schlecht zur Eingabe geeignet sind. Nun gehen wir noch einen Schritt weiter. Vorab: $\begin{eqnarray} \\|b\\| = \\|Ax\\| \leq \\|A\\|\\|x\\| \end{eqnarray}$ für $\begin{eqnarray} x\neq 0: \frac{1}{\\|x\\|} \leq \frac{\\|A\\|}{\\|b\\|} \end{eqnarray}$ () $\begin{eqnarray} \frac{\\|\hat x - x\\|}{\\|x\\|} &&= \frac{\\|\hat x -\hat{A}^{-1}b+\hat{A}^{-1}b - x\\|}{\\|x\\|} \\ &&\leq \frac{\\|\hat x -\hat{A}^{-1}b\\|}{\\|x\\|} + \frac{\\|\hat{A}^{-1}b - x\\|}{\\|x\\|} \\&& = \frac{\\|\hat{A}^{-1}\hat{b} -\hat{A}^{-1}b\\|}{\\|x\\|} + \frac{\\|\hat{A}^{-1}Ax - \hat{A}^{-1}\hat{A}x\\|}{\\|x\\|} \\ &&= \frac{\\|\hat{A}^{-1}(\hat{b} -b)\\|}{\\|x\\|} + \frac{\\|\hat{A}^{-1}(A- \hat{A})x\\|}{\\|x\\|} \\ && \leq \frac{\\|\hat{A}^{-1}\\|\\|\hat{b} -b\\|}{\\|x\\|} + \frac{\\|\hat{A}^{-1}\\|\\|A- \hat{A}\\|\\|x\\|}{\\|x\\|} \\ && \leq \frac{\\|A\\|\\|\hat{A}^{-1}\\|\\|\hat{b} -b\\|}{\\|b\\|} + \\|\hat{A}^{-1}\\|\\|A- \hat{A}\\| \\&& = \\|A\\|\\|\hat{A}^{-1}\\| \Bigl(\frac{\\|\hat{b}-b\\|}{\\|b\\|}+\frac{\\|\hat{A}-A\\|}{\\|A\\|} \Bigr) \end{eqnarray*}$
31.01.2009, 00:23	tigerbine	Auf diesen Beitrag antworten »
RE: 3.4 Kondition und Fehler beim Lösen von LGS Hier geht es weiter: [Numerik I] - Übung 4 *
Anzeige

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »