[Numerik I] - Übung 13 *

20.01.2009, 16:18	tigerbine	Auf diesen Beitrag antworten »
[Numerik I] - Übung 13 * Frobeniusnorm wird durch keine Norm induziert Numerische Integration Cholesky-Zerlegung Lineare Spline-Interpolation
20.01.2009, 16:18	tigerbine	Auf diesen Beitrag antworten »
13.1 Frobeniusnorm Aufgabenteil a Wenn man zeigen will, dass die Frobeniusnorm nicht durch eine Matrixnorm induziert ist, könnte man das doch wie folgt tun. Für eine induzierte Norm gilt: $\begin{eqnarray} \\|A\\|_{V \to V}:=\sup_{x \neq 0} \frac{\\|Ax\\|_V}{\\|x\\|_V} \end{eqnarray}$ Wählt man nun die Einheitsmatrix I, so folgt (): $\begin{eqnarray} \\|I\\|_{V \to V}:=\sup_{x \neq 0} \frac{\\|Ix\\|_V}{\\|x\\|_V} = 1 \end{eqnarray}$ Nehmen wir nun die Frobeniusnorm in der Spurdefinition: $\begin{eqnarray} \\|A\\|_F := \sqrt{\text{tr}(A^HA)} \end{eqnarray}$ so folgt: $\begin{eqnarray} \\|I\\|_F := \sqrt{\text{tr}(I)} = \sqrt{n} \end{eqnarray}$ Was im Widerspruch zu () steht (n>1) , und somit kann die Frobeniusnorm nicht durch eine Vektornorm induziert sein. Aufgabenteil b Eine Induzierte Norm muss mit ihrer Vektornorm verträglich sein. Es muss dann für alle Vektoren gelten: $\begin{eqnarray} \\|Ax\\|_V \leq \\|A\\|_M \\|x\\|_V \end{eqnarray}$ (*) Wenn ich nun die Matrix so wähle, dass nur der Eintrag A(1,1) =1 von Null verschieden ist. Dann besitzt die Matrix den Eigenwert 1 und einen vom Nullvektor verschiedenen Eigenvektor x. Damit folgt dann: $\begin{eqnarray} \\|1\cdot x\\|_V \leq \\|A\\|_M \\|x\\|_V \end{eqnarray}$ $\begin{eqnarray} \\| x\\|_V \leq \\|A\\|_M \\|x\\|_V \end{eqnarray}$ $\begin{eqnarray} 1 \leq \\|A\\|_M \end{eqnarray}$ Für die Matrixnorm ergibt sich: $\begin{eqnarray} \\|A\\|_M=\frac{1}{\sqrt{n}} \sqrt{\text{tr}(AA^H)}=\frac{1}{\sqrt{n}} \sqrt{\text{tr}(A)} = \frac{1}{\sqrt{n}} \end{eqnarray}$ Und somit wäre () nicht erfüllt, M also nicht induziert. Was passiert, wenn man die bekannten induzierten Normen nimmt? $\begin{eqnarray} \\|A\\|_1=1,~\\|A\\|_p = 1,~\\|A\\|_{\infty}=1 \end{eqnarray*}$
20.01.2009, 16:18	tigerbine	Auf diesen Beitrag antworten »
13.2 Integration mit Simpson Betrachten wir die Funktion $\begin{eqnarray} f(x)=u(x)v'(x)=x\cdot \exp(x) \end{eqnarray}$ die wir über [0,1] integrieren wollen. Zur exakten Berechnung verwendet man die partielle Integration und erhält: $\begin{eqnarray} \int_{0}^{1} x\cdot \exp(x)~dx &&= [x\cdot \exp(x)]_0^1-\int_{0}^{1}1\cdot \exp(x)~dx \\&& = \exp(1) - \exp(1) + 1 = 1 \end{eqnarray}$ Verwendet man die Simpson-Regel, so ergibt sich die Näherung: $\begin{eqnarray} \tilde I(f) &&= \frac{1-0}{6}\Bigl(f(0) + 4f(0.5) + f(1) \Bigr) = \frac{1}{6} \Bigl(0 + 2 \exp(0.5) + \exp(1) \Bigr) \\&&=\frac{1}{6} \Bigl(2 \exp(0.5) + \exp(1) \Bigr) \end{eqnarray}$ Wie gut ist nun diese Näherung? Die Simpson-Regel ist eine Newton-Coates-Formel für gerades n (n=2), somit integriert sie so gar für n=3 exakt. (Ordnung 4!) wonach wir den Fehler wie folgt abschätzen können (Integration des Interpolationsfehlers) (): $\begin{eqnarray} I(f)-I_2(f) && = \int_a^b~\frac{f^{(4)}(\xi_x)}{4!} \cdot (x-a)(x-\frac{(b-a)}{2})^2(x-b)~dx \\&& \stackrel{(1),(2)} = \frac{f^{(4)}(\xi)}{24} \cdot (b-a)^5 \cdot \int_0^1~(t-0)(t-0.5)^2(t-1)~dt \\&& = -\frac{f^{(4)}(\xi)}{2880} \cdot (b-a)^5 \end{eqnarray}$ Um nun eine obere Schranke angeben zu können, müssen wir die Ableitungen von f berechnen. $\begin{eqnarray} f(x)=x\cdot \exp(x) \end{eqnarray}$ $\begin{eqnarray} f^{(1)}(x)=1\cdot \exp(x) + x \cdot \exp(x) = (1+x)\exp(x) \end{eqnarray}$ Wiederholen liefert dann: $\begin{eqnarray} f^{(4)}(x)=(4+x)\exp(x) \end{eqnarray}$ $\begin{eqnarray} f^{(5)}(x)=(5+x)\exp(x) \end{eqnarray}$ Auf dem Intervall [0,1] ist $\begin{eqnarray} f^{(5)} >0 \end{eqnarray}$ , somit ist die vierte Ableitung von f dort streng monoton steigend. Da auch sie strikt positiv ist, folgt die Abschätzung: $\begin{eqnarray} f^{(4)}(x)=(4+x)\exp(x) \leq 5 \cdot \exp(1) \end{eqnarray}$ Es ergibt sich somit mit () $\begin{eqnarray} \|I(f)-I_2(f)\| = \|\frac{f^{(4)}(\xi)}{2880} \cdot (1-0)^5\| \leq \frac{5}{2880} \cdot \exp(1) \end{eqnarray}$ Die relativen Fehler Er ergibt sich aufgrund des Wertes des exakten Integrals: $\begin{eqnarray} \frac{\|\tilde I(f)-I(f)\|}{\|I(f)\|} =\|\tilde I(f)-I(f)\| = \|\frac{1}{6} \Bigl(2 \exp(0.5) + \exp(1) \Bigr) -1\| \end{eqnarray}$ $\begin{eqnarray} \frac{\|R(f)\|}{\|I(f)\|} =\|R(f)\| = \| \frac{5}{2880} \cdot \exp(1)\| =\|\frac{1}{576}\cdot \exp(1)\| \end{eqnarray}$ Mit dem Peanoschen Fehlerdarstellung ergibt sich für die Simpsonregel (s.o. mit n=3) $\begin{eqnarray} R(f):=\tilde I(f) - \int_{0}^{1}f(x)dx \end{eqnarray}$ $\begin{eqnarray} R(f):=\int_0^1f^{4}(t)K(t)~dt \end{eqnarray}$ Mit dem Peano-Kern: $\begin{eqnarray} K(t):=\frac{1}{3!} R_x\Bigl( (x-t)_+^3 \Bigr),~(x-t)_+^3 = \begin{cases} (x-t)^3 & x\geq t \\ 0& x < t \end{cases} \end{eqnarray}$ $\begin{eqnarray} K(t)=\frac{1}{6} \Bigl(\frac{1}{6}(0-t)_+^3 + \frac{4}{6}(0.5-t)_+^3 + \frac{1}{6}(1-t)_+^3 - \int_0^1(x-t)_+^3~dx \Bigr) \end{eqnarray}$ Es ergibt sich für $\begin{eqnarray} 0 \leq t \leq 1 \end{eqnarray}$ $\begin{eqnarray} \int_0^1(x-t)_+^3~dx=\int_t^1(x-t)^3~dx = [\frac{1}{4}(x-t)^4]_t^1 =\frac{1}{4}(1-t)^4 \end{eqnarray}$ $\begin{eqnarray} (0-t)_+^3 = 0,~ (1-t)_+^3 =(1-t)^3,~ (0.5-t)_+^3 =\begin{cases}0 & t \geq 0.5 \\ (0.5-t)^3 & t<0.5 \end{cases} \end{eqnarray}$ Es ergibt sich also für den Peano Kern $\begin{eqnarray} K(t)=\begin{cases} \frac{1}{6}\Bigl(\frac{1}{6}(1-t)^3- \frac{1}{4}(1-t)^4\Bigl)& 0.5 \leq t \leq 1 \\ \frac{1}{6}\Bigl(\frac{4}{6}(0.5-t)^3 + \frac{1}{6}(1-t)^3- \frac{1}{4}(1-t)^4\Bigl) & 0 \leq t \leq 0.5\end{cases} \end{eqnarray}$ $\begin{eqnarray} K(t)=\begin{cases} \frac{1}{6}\Bigl((1-t)^3(\frac{1}{6}-\frac{1}{4}(1-t))\Bigl)& 0.5 \leq t \leq 1 \\ \frac{1}{6}\Bigl(\frac{4}{6}(0.5-t)^3 + \frac{1}{6}(1-t)^3- \frac{1}{4}(1-t)^4\Bigl) & 0 \leq t \leq 0.5\end{cases} \end{eqnarray}$ Der Kern ändert sein Vorzeichen nicht - das ist bei allen NC-Formeln so - damit kann man den Mittelwertsatz der Integeralrechnung anwenden. Die Berechnung des Fehlers vereinfacht sich - Ordnung der Quadraturformel beachten - zu $\begin{eqnarray} R(f)&&=\frac{R(x^{3+1})}{(3+1)!}f^{(3+1)}(\xi) \\&&=\frac{1}{24}\Bigl(\frac{1-0}{6}(1\cdot 0^4+4\cdot(0.5)^4+1\cdot 1^4) - \int_0^1x^4 \Bigr) \cdot f^{(4)}(\xi) \\ && =\frac{1}{24}\Bigl(\frac{1}{6}\cdot 1.25-0.2\Bigl)\cdot f^{(4)}(\xi)\\&& = \frac{1}{2880} \cdot f^{(4)}(\xi) \end{eqnarray}$ Ab nun gleiche Argumentation wie oben.
20.01.2009, 16:34	tigerbine	Auf diesen Beitrag antworten »
13.3 Cholesky-Zerlegung Sollte man den Algorithmus nicht "im Kopf" haben, so kann man bei kleinen Dimensionen sich einfach mit folgender Vorgabe behelfen. $\begin{eqnarray} \begin{pmatrix}l_{11} & 0 & 0 \\ l_{21} & l_{22} & 0 \\ l_{31} & l_{32} & l_{33} \end{pmatrix}\begin{pmatrix}l_{11} & l_{21} & l_{31} \\ 0 & l_{22} & l_{32} \\ 0 & 0 & l_{33} \end{pmatrix} = \begin{pmatrix} 4 & 1 & -1 \\ 1 & 4 & 1 \\ -1 & 1 & 4 \end{pmatrix} \end{eqnarray}$ Somit ergibt sich nach und nach: $\begin{eqnarray} l_{11}^2 = 4 \Rightarrow l_{11} = 2 \end{eqnarray}$ $\begin{eqnarray} l_{11} \cdot l_{21} = 1 \Rightarrow l_{21} = 0.5 \end{eqnarray}$ $\begin{eqnarray} l_{11} \cdot l_{31} = -1 \Rightarrow l_{21} = -0.5 \end{eqnarray}$ Nun die zweite Spalte: $\begin{eqnarray} l_{21}^2+l_{22}^2=4 \Rightarrow l_{22} = \sqrt{4-\frac{1}{4}} = \sqrt{\frac{15}{4}} \end{eqnarray}$ $\begin{eqnarray} l_{21}l_{31}+\l_{22}l_{32}=1 \Rightarrow l_{32} = (\sqrt{1+\frac{1}{4}}) \sqrt{\frac{4}{15}} = \frac{5}{12} \end{eqnarray}$ Und die letzte Spalte: $\begin{eqnarray} l_{31}^2+l_{32}^2 + l_{33}^2=4 \Rightarrow l_{33} = \sqrt{4-\frac{1}{4} - \frac{5}{12}} = \sqrt{\frac{40}{12}} \end{eqnarray}$ Damit lautet die Cholesky-Zerlegung: $\begin{eqnarray} \begin{pmatrix} 2 & 0 & 0 \\ \frac{1}{2} & \sqrt{\frac{15}{4}} & 0 \\ -\frac{1}{2}&\sqrt{\frac{5}{12}} & \sqrt{\frac{40}{12}} \end{pmatrix} \begin{pmatrix} 2 & 0 & 0 \\ \frac{1}{2} & \sqrt{\frac{15}{4}} & 0 \\ -\frac{1}{2}&\sqrt{\frac{5}{12}} & \sqrt{\frac{40}{12}} \end{pmatrix}^T = \begin{pmatrix} 4 & 1 & -1 \\ 1 & 4 & 1 \\ -1 & 1 & 4 \end{pmatrix} \end{eqnarray}$
20.01.2009, 16:34	tigerbine	Auf diesen Beitrag antworten »
13.4 lineare Splineinterpolation Betrachten wir zunächst eine Restriktion $\begin{eqnarray} R_i \end{eqnarray}$ auf dem Intervall $\begin{eqnarray} [x_i,x_{i+1}] \end{eqnarray}$ . Auf diesem Intervall ist f zweimal stetig differenzierbar und die Restriktion ist als Polynomfunktion vom Grad 1 aus $\begin{eqnarray} C^{\infty}([x_i,x_{i+1}]) \end{eqnarray}$ . Aus der interpolierenden Eigenschaft des Splines folgt für die Differenzenfunktion: $\begin{eqnarray} G(x):=f(x)-R_j(x) \end{eqnarray}$ $\begin{eqnarray} G(x_i)=G(x_{i+1}) =0 \end{eqnarray}$ Somit gilt nach dem Satz von Rolle, dass die Funktion g auf dem Intervall mind. eine Nullstelle hat. $\begin{eqnarray} g(x):=f'(x)-R_j'(x) \end{eqnarray}$ Wie kann man nun die Funktionswerte von g abschätzen? Da f zweimal stetig diff'bar ist, nimmt die zweite Ableitung auf dem Kompaktum ein Maximum und ein Minimum an. Somit können wir aus dem Mittelwertsatz der Differentialrechnung folgern, dass man die Funktionswerte von g wie folgt abschätzen können: $\begin{eqnarray} g'(x)=f''(x) \end{eqnarray}$ $\begin{eqnarray} \\|g\\|_{\infty} \leq h \cdot \\|f''\\|_{\infty} \end{eqnarray}$ Diese Abschätzungen können wir auf jedem Teilintervall für jede Restriktion machen. Somit können wir über dem gesamten Intervall (Verwendung der Maximumsnorm) schreiben: $\begin{eqnarray} \\|f'-s'_h\\|_{\infty} \leq h \cdot \\|f''\\|_{\infty} \end{eqnarray}$

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »