[Numerik I] - Übung 2 *

10.01.2009, 22:54	tigerbine	Auf diesen Beitrag antworten »
[Numerik I] - Übung 2 * Aufgaben - Teil 2 Operatornorm Frobeniusnorm LR-Zerlegung ohne Pivotisierung LR-Zerlegung der Inversen Matrix
11.01.2009, 01:27	tigerbine	Auf diesen Beitrag antworten »
2.1 Operatornorm Hier ist nicht wie bei den anderen Aufgaben zu dem Thema klar, wie sie am Ende zu berechnen sein wird. Es ist nur bekannt, dass es einen Vektor x gibt, dessen Einträge betragsmäßig 1 sind, so dass Gleichheit mit einer Vektornorm (Betragssummennorm). Zunächst betrachtet man einmal die rechte Seite der Gleichung und definiert die Funktion $\begin{eqnarray} f:~[-1,1]^m \to \mathbb R,~\quad x \to \sum_{i=1}^n \begin{vmatrix}Ax \end{vmatrix} = \sum_{i=1}^n \begin{vmatrix} \sum_{k=1}^m a_{ik}x_k \end{vmatrix} \end{eqnarray}$ Nun betrachten wir eine weitere Funktion. Dazu seinen $\begin{eqnarray} x,y \in [-1,1]^m \end{eqnarray}$ . $\begin{eqnarray} \varphi: ~[0,1] \to \mathbb R,~\quad \lambda \to f\Bigl(\lambda x + (1-\lambda)y\Bigr) \end{eqnarray}$ Schauen wir uns diese Funktion etwas genauer an. Es ist $\begin{eqnarray} f\Bigl(\lambda x + (1-\lambda)y\Bigr) &&= \sum_{i=0}^n \begin{vmatrix} \sum_{k=1}^m a_{ik}(\lambda x_k + (1-\lambda)y_k) \end{vmatrix} \\&& = \sum_{i=0}^n \begin{vmatrix} \lambda \sum_{k=1}^m a_{ik}(x_k +y_k) + \sum_{k=1}^m a_{ik}x_k \end{vmatrix} \\&& = \sum_{i=0}^n \begin{vmatrix} \lambda a_i + b_i \end{vmatrix},~a_i,b_i \in \mathbb R \end{eqnarray}$ Somit handelt es sich um die Summe von "linearen" Funktionen auf dem kompakten Intervall [0,1]. Die Summe stetiger Funktionen ist stetig und es gibt ein globales Maximum für ein $\begin{eqnarray} \lambda ^ \in [0,1] \end{eqnarray}$ (). Nun nehmen wir an, dass gilt $\begin{eqnarray} \lambda ^ \in (0,1) \end{eqnarray}$ und führen dies zum Widerspruch. Aufgrund der "linearen" Gestalt ist $\begin{eqnarray} \varphi \end{eqnarray}$ im Maximum nicht differenzierbar. Somit existiert ein $\begin{eqnarray} I \subset \{1,,n\} \end{eqnarray}$ mit: $\begin{eqnarray} \|\lambda^a_k+b_k\| = 0,~a_k \neq 0,~\forall k \in I \end{eqnarray}$ $\begin{eqnarray} \varphi(x^) = \sum_{i \notin I} \|\lambda^a_i+b_i\| + \sum_{i \in I}\|\lambda^ a_i + b_i\| \end{eqnarray}$ Da $\begin{eqnarray} \sum_{i \notin I} \|\lambda^a_i+b_i\| \end{eqnarray}$ lokal affin in $\begin{eqnarray} \lambda^ \end{eqnarray}$ ist, existiert ein $\begin{eqnarray} \delta \end{eqnarray}$ mit $\begin{eqnarray} \sum_{i \notin I} \|(\lambda^+\delta )a_i+b_i\| \geq \sum_{i \notin I} \|\lambda^a_i+b_i\| \end{eqnarray}$ Daraus folgt: $\begin{eqnarray} \varphi(\lambda^* +\delta) &&=\sum_{i \notin I} \|(\lambda^* + \delta)a_i+b_i\| +\sum_{i \notin I} \|(\lambda^* + \delta)a_i+b_i\| \\&& \geq \sum_{i \notin I} \|\lambda^* a_i+b_i\| +\sum_{i \notin I} \|(\lambda^* + \delta) a_i+b_i\| \\ && > \varphi (\lambda^) \end{eqnarray}$ Dies steht im Widerspruch zu () und somit gilt $\begin{eqnarray} \varphi \end{eqnarray}$ wird maximal bei 0 der 1. Fazit: Sei $\begin{eqnarray} x \in [-1,1]^m \end{eqnarray}$ und es existiert ein $\begin{eqnarray} x_1 \neq x,~x_2 = x,~x_1,x_2 \in [-1,1]^m \end{eqnarray}$ mit $\begin{eqnarray} x \in \overline{x_1x_2} \Rightarrow f(x) \leq f(x_1) \text{ oder } f(x) \leq f(x_2) \end{eqnarray*}$ . f wird maximal an Punkten, die nicht in einer Verbindungslinie liegen.
11.01.2009, 01:34	tigerbine	Auf diesen Beitrag antworten »
2.2 Frobenius Norm $\begin{eqnarray} \\|A\\|_F:=\sqrt{\sum_{j,k=1^n}\|a_{jk}\|^2},\quad A \in \mathbb C^{n \times n} \end{eqnarray}$ Alternativ zur Summation der quadrierten betragsmäßigen Einträge der Matrix, kann man diese Norm auch wie folgt berechnen: $\begin{eqnarray} \\|A\\|_F^2=\text{tr}(AA^)=\text{tr}(A^A) \end{eqnarray}$ Zum Nachweis nutzt man die Darstellung komplexer Zahlen in der Form $\begin{eqnarray} z:=x+iy,~\overline{z}=x-iy \end{eqnarray}$ . Ferner gilt für den Betrag einer komplexen Zahl $\begin{eqnarray} \|z\|=\sqrt{x^2+y^2} \end{eqnarray}$ . Es ergeben sich dann durch Rechnung und Symmetrie die Behauptungen. $\begin{eqnarray} \text{tr}(AA^)= \sum_{k=1}^n~\sum_{j=1}^{n}a_{kj}\overline{a_{kj}} = \sum_{k=1}^n~\sum_{j=1}^{n}\|a_{kj}\|^2 \end{eqnarray}$ Der Nachweis, dass es sich um eine Norm handelt, soll nun geführt werden. $\begin{eqnarray} A=0 \Leftrightarrow \end{eqnarray}$ für alle Einträge der Matrix gilt $\begin{eqnarray} a_{ij}=0 \end{eqnarray}$ und somit auch $\begin{eqnarray} \sqrt{\sum_{j,k}^n\|a_{jk}\|^2}=0 \end{eqnarray}$ . Der Rückweg ergibt sich unmittelbar aus der Positivität der Summanden. $\begin{eqnarray} \\|\lambda A\\|_F=\sqrt{\sum_{j,k=1}^n\|\lambda\cdot a_{jk}\|^2} = \sqrt{\sum_{j,k=1}^n \|\lambda\|^2\cdot\| a_{jk}\|^2} =\sqrt{\|\lambda\|^2\cdot\sum_{j,k=1}^n \|a_{jk}\|^2} =\|\lambda\|\cdot \sqrt{\sum_{j,k=1}^n \|a_{jk}\|^2}=\|\lambda\|\cdot \\|A\\|_F \end{eqnarray}$ Hier betrachten wir die Quadrate: $\begin{eqnarray} \\|A+B\\|_F^2 && = \sum_{j,k}^n\|a_{j,k}+b_{j,k}\|^2 \\ && \stackrel{\triangle} \leq \sum_{j,k}^n(\|a_{j,k}\|+\|b_{j,k}\|)^2 =\sum_{j,k}^n\|a_{j,k}\|^2+2\sum_{j,k}^n \|a_{j,k}\|\|b_{j,k}\| +\sum_{j,k}^n\|b_{j,k}\|^2 \\&& \stackrel{\text{CSU}} =\sum_{j,k}^n\|a_{j,k}\|^2+2\sqrt{\sum_{j,k}^n \|a_{j,k}\|^2}\sqrt{\sum_{j,k}^n \|b_{j,k}\|^2} +\sum_{j,k}^n\|b_{j,k}\|^2 \\&& = (\sum_{j,k}^n\|a_{j,k}\| + \sum_{j,k}^n\|b_{j,k}\|)^2 \\&& =( \\|A\\|_F+\\|B\\|_F)^2 \end{eqnarray}$ Die Frobeniusnorm erfüllt eine weitere Eigenschaft, die auch typisch für Operatornormen ist. Sie ist submultiplikativ, denn es gilt $\begin{eqnarray} \\|AB\\|_F \leq \\|A\\|_F\\|B\\|_F \end{eqnarray}$ $\begin{eqnarray} \\|AB\\|_F= \sqrt{\sum_{j,k}^n\|a_{jk}\|^2}\cdot \sqrt{\sum_{j,k}^n\|b_{jk}\|^2}\leq \\|A\\|_F\\|B\\|_F \end{eqnarray}$ Für Operatornormen folgt diese Eigenschaft wie folgt: $\begin{eqnarray} \\|AB\\|_{\alpha \to \beta} \leq\\|A\\|_{\alpha \to \beta} \\|B\\|_{\alpha \to \beta} \end{eqnarray*}$
11.01.2009, 01:42	tigerbine	Auf diesen Beitrag antworten »
2.3 LR-Zerlegung ohne Pivotisierung Die reguläre Matrix A besitzt eine LR-Zerlegung ohne Pivotisierung $\begin{eqnarray} \Leftrightarrow \end{eqnarray}$ Alle Hauptabschnittsmatrizen $\begin{eqnarray} A[k] \end{eqnarray}$ regulär sind. Eine Hauptabschnittsmatrix ist genau dann regulär, wenn gilt $\begin{eqnarray} \det(A[k]) \neq 0 \end{eqnarray}$ . Beweis: $\begin{eqnarray} \Rightarrow \end{eqnarray}$ Besitze A eine LR-Zerlegung. Dann existiert eine normierte untere Dreiecksmatrix $\begin{eqnarray} L \in \mathbb R^{n \times n} \end{eqnarray}$ und eine obere Dreiecksmatrix $\begin{eqnarray} R \in \mathbb R^{n\times n} \end{eqnarray}$ mit $\begin{eqnarray} A=LR \end{eqnarray}$ . Aus $\begin{eqnarray} \det(A)=\det(L)\cdot \det(R) \end{eqnarray}$ und der Regularität von A folgt $\begin{eqnarray} \det(L)\neq 0,~\det(R) \neq 0 \end{eqnarray}$ . Da es sich um Dreiecksmatrizen handelt folgt sofort, dass auch alle ihre Hauptabschnittsmatrizen regulär sind. Durch "Nachrechnen" zeigt man die Gültigkeit von $\begin{eqnarray} (LA)[k] = L[k]A[k] \quad \forall~k=1,...,n~() \end{eqnarray}$ für jede (nicht notwendigerweise normierte) Dreiecksmatrix $\begin{eqnarray} L \in \mathbb R^{n \times n} \end{eqnarray}$ . Damit folgt: $\begin{eqnarray} \det(A[k]) &&= \det(LR[k]) = \det(L[k]R[k])= \\&&=\det(L[k])\cdot\det(R[k]) \neq 0\qquad \forall~k=1,...,n \end{eqnarray}$ $\begin{eqnarray} \Leftarrow \end{eqnarray}$ Seien alle Hauptabschnittsmatrizen positiv. Die Existenz der LR-Zerlegung weißt man durch die in diesem Falle Wohldefiniertheit des Algorithmus ihrer Berechnung nach. Es muss also gezeigt werden, dass alle Pivotelemente $\begin{eqnarray} a_{ii}^{(i)},~i = 1,...,n-1 \end{eqnarray}$ von Null verschieden sind. Der Beweis wird durch Induktion geführt: $\begin{eqnarray} \text{IA: }&& i=1,~a_{11}^{(1)} = \det(A[1]) \neq 0 \text{ nach Voraussetzung}\\\\\text{IV: } && \text{ Sei nun }a_{ii}^{i} \neq 0 \text{ für ein } 1 \leq i < n-1\\\\\text{IS: }&& \text{Aus der IV folgt die Existenz einer Matrix} \\ && A^{(i+1)} = L_i \cdot L_1 \cdot A \\\\&&\text{Durch sukzessive Anwendung von () folgt} \\&&A^{(i+1)}[i+1] = L_i[i+1]...L_1[i+1]A[i+1]\\\\&&\text{Mit der Determinantenmultiplikation folgt dann} \\&& \det(A^{(i+1)})[i+1]) = \det(L_i[i+1])\cdot ...\cdot \det(L_1[i+1]) \cdot \det(A[i+1]) \\\\ &&\text{Da } A^{(i+1)}[i+1] \text{offenbar eine obere Dreiecksmatrix darstellt mit} \\&& a_{i+1,i+1}^{(i+1)} \neq 0 \text{ als letzten Diagonalelement, folgt hieraus wegen } \\&& \det(A^{(i+1)}[i+1]) \neq 0 \text{ sofort } a_{i+1,i+1}^{(i+1)} \neq 0 \end{eqnarray}$
11.01.2009, 02:02	tigerbine	Auf diesen Beitrag antworten »
2.4 LR-Zerlegung der Inversen von X $\begin{eqnarray} \neg b \Rightarrow \neg a \end{eqnarray}$ *********** Nehmen wir also an, es gäbe einen Vektor $\begin{eqnarray} v \neq 0 \end{eqnarray}$ , der in beiden Erzeugnissen liegt. Es ist dann für $\begin{eqnarray} v \in \text{span}\{x_{k+1},...,x_m\} \end{eqnarray}$ : $\begin{eqnarray} w:=X^{-1}v \in \text{span}\{e_{k+1},...,e_n\} \end{eqnarray}$ Die ersten k Komponenten des Vektors w sind also 0. Nun ist gilt aber auch $\begin{eqnarray} v \in \text{span}\{e_1,...,e_k\} \end{eqnarray}$ . Das bedeutet, das w gerade eine nicht triviale LK der ersten k Spalten von $\begin{eqnarray} x^{-1} \end{eqnarray}$ ist. Die k-Nullen im Vektor w bedeuteten dann, dass die k-ten Hauptabschnitsmatrizen $\begin{eqnarray} X^{-1}[k] \end{eqnarray}$ von $\begin{eqnarray} X^{-1} \end{eqnarray}$ linear abhängig sind und somit die Hauptminoren gleich 0 sind. Somit kann $\begin{eqnarray} X^{-1} \end{eqnarray}$ keine LR-Zerlegung ohne Pivotisierung besitzen. $\begin{eqnarray} \neg a \Rightarrow \neg b \end{eqnarray}$ *********** Habe nun $\begin{eqnarray} X^{-1} \end{eqnarray}$ keine LR-Zerlegung ohne Pivotisierung. Da die Matrix aber regullär ist, gilt für die n-te k-ten Hauptabschnitsmatrix $\begin{eqnarray} X^{-1}[n] \end{eqnarray}$ , dass ihre Determinate von 0 verschieden ist. Es muss also mindestens für ein $\begin{eqnarray} k \in \{1,...,n-1\} \end{eqnarray}$ gelten: $\begin{eqnarray} \det(X^{-1}[k])=0 \end{eqnarray}$ Somit gibt es einen Vektor v ungleich 0 in $\begin{eqnarray} v \in \text{span}\{e_1,...,e_k\} \end{eqnarray}$ mit $\begin{eqnarray} w:=X^{-1}v \end{eqnarray}$ , wobei die ersten k Komponenten von w gleich 0 sind. Somit gilt: $\begin{eqnarray} w \in \text{span}\{e_{k+1},...,e_n\} \end{eqnarray}$ Somit gilt für $\begin{eqnarray} v=Xw \end{eqnarray}$ , dass es Element von $\begin{eqnarray} \text{span}\{x_{k+1},...,x_m\} \end{eqnarray}$ ist. Damit ist der Schnitt nicht leer: $\begin{eqnarray} \text{span}\{e_1,...,e_k\} \cap \text{span}\{x_{k+1},...,x_m\} \neq \{0\} \end{eqnarray}$
31.01.2009, 00:24	tigerbine	Auf diesen Beitrag antworten »
Weiter mit: [Numerik I] - Übung 3 *
Anzeige

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »