[WS] Lineare Gleichungssysteme 2 - Beispiele

08.08.2007, 21:27	tigerbine	Auf diesen Beitrag antworten »
[WS] Lineare Gleichungssysteme 2 - Beispiele Gliederung Berechnung von LR-Zerlegungen und deren Speicherungen LR-Zerlegung mit dem Gauß-Algorithmus LR- Zerlegung mit dem Verfahren von Crout LDL^T - Zerlegung Cholesky-Zerlegung Lösen des Linearen Gleichungssystems Ax=b Mit den obigen Verfahren
08.08.2007, 21:32	tigerbine	Auf diesen Beitrag antworten »
Die Matrix Anhand der Matrix $\begin{eqnarray} A = \begin{pmatrix}9 & -36 & 30 \\ -36 & 192 & -180 \\ 30 & -180 & 180 \end{pmatrix} \end{eqnarray}$ sollen die im Workshop angesprochenen Zerlegungen berechnet werden. Es ist A eine SPD-Matrix. Somit können wir alle angesprochenen Verfahren durchführen. Die Symmetrie ist dabei offensichtlich. Mit dem Satz von Hurwitz folgt aufgrund von $\begin{eqnarray} a_{11} = 9 > 0 \end{eqnarray}$ $\begin{eqnarray} a_{11}a_{22} - a_{21}a_{12} = 432 > 0 \end{eqnarray}$ $\begin{eqnarray} a_{11}a_{22}a_{33} + a_{12}a_{23}a_{31} + a_{13}a_{21}a_{32} - a_{31}a_{22}a_{13} - a_{32}a_{23}a_{11} - a_{33}a_{21}a_{12} =2160 > 0 \end{eqnarray}$ auch die positive Definitheit.
08.08.2007, 23:35	tigerbine	Auf diesen Beitrag antworten »
1. LR-Zerlegung mit dem Gauß-Algorithmus Gesucht ist also eine Zerlegung PA=LR. Wir beginnen "stur", die Frobenius und Permutationsmatrizen zu bestimmen. D.h. Pivotelement ist immer das "nächst Beste". $\begin{eqnarray} a_{11}^{(1)} = 9 \neq 0 \end{eqnarray}$ $\begin{eqnarray} \Rightarrow P_1 = \begin{pmatrix} 1 & 0&0\\ 0&1&0 \\ 0&0&1 \end{pmatrix} \end{eqnarray}$ $\begin{eqnarray} \Rightarrow L_1 = \begin{pmatrix} 1&0&0 \\ 4&1&0 \\ -\frac{10}{3}&0&1\end{pmatrix} \end{eqnarray}$ $\begin{eqnarray} A^{(2)} = \begin{pmatrix} 9&-36&30 \\ 0&48&-60 \\ 0&-60&80 \end{pmatrix} \end{eqnarray}$ $\begin{eqnarray} a_{22}^{(2)} = 48 \neq 0 \end{eqnarray}$ $\begin{eqnarray} \Rightarrow P_2 = \begin{pmatrix} 1 & 0&0\\ 0&1&0 \\ 0&0&1 \end{pmatrix} \end{eqnarray}$ $\begin{eqnarray} \Rightarrow L_2 = \begin{pmatrix} 1&0&0 \\ 0&1&0 \\ 0&\frac{5}{4}&1\end{pmatrix} \end{eqnarray}$ $\begin{eqnarray} A^{(3)} = \begin{pmatrix} 9&-36&30 \\ 0&48&-60 \\ 0&0&5 \end{pmatrix} \end{eqnarray}$ Und somit erhalten wir die LR-Zerlegung (Zum Vergleich möge man das Verfahren von Doolittle verwenden und sich von der Eindeutigkeit überzeugen der LR-Zerlegung überzeugen). $\begin{eqnarray} \begin{pmatrix}9 & -36 & 30 \\ -36 & 192 & -180 \\ 30 & -180 & 180 \end{pmatrix} =\begin{pmatrix} 1&0&0 \\ -4&1&0 \\ \frac{10}{3}&-\frac{5}{4}&1\end{pmatrix} \begin{pmatrix} 9&-36&30 \\ 0&48&-60 \\ 0&0&5 \end{pmatrix} \end{eqnarray}$ So werden die Daten dann z.B. in einem Programm gespeichert: Es wäre auch eine LR-Zerlegung mit vordefinierten Einsen auf der Diagonale von R denkbar:
09.08.2007, 02:40	tigerbine	Auf diesen Beitrag antworten »
2. LR- Zerlegung mit dem Verfahren von Crout Wir legen hier nun die Diagonelemente von R mit 1 fest. K=1 $\begin{eqnarray} l_{11} = \frac{a_{11}}{r_{11}} = \frac{9}{1} = 9 \end{eqnarray}$ $\begin{eqnarray} l_{21} = \frac{a_{21}}{r_{11}} = \frac{-36}{1} = -36 \end{eqnarray}$ $\begin{eqnarray} l_{31} = \frac{a_{31}}{r_{11}} = \frac{30}{1} = 30 \end{eqnarray}$ $\begin{eqnarray} r_{12} = \frac{a_{12}}{l_{11}} = \frac{-36}{9} = -4 \end{eqnarray}$ $\begin{eqnarray} r_{13} = \frac{a_{13}}{l_{11}} = \frac{30}{9} = \frac{10}{3} \end{eqnarray}$ K=2 $\begin{eqnarray} l_{22} = \frac{a_{22} - l_{21}r_{12} }{r_{22}} = \frac{192 - (-36) \cdot (-4)}{1} = 48 \end{eqnarray}$ $\begin{eqnarray} l_{32} = \frac{a_{32} - l_{31} \cdot r_{12} }{r_{22}} = \frac{-180 - 30 \cdot (-4)}{1} =-60 \end{eqnarray}$ $\begin{eqnarray} r_{23} = \frac{a_{23} - l_{21} \cdot r_{13}}{l_{22}} = \frac{-180 - (-36) \cdot \frac{10}{3}}{48} = - \frac{5}{4} \end{eqnarray}$ k=3 $\begin{eqnarray} l_{33} = \frac{a_{33} - l_{31}\cdot r_{13} - l_{32} \cdot r_{23}}{r_{33}} = \frac{180 - 30 \cdot \frac{10}{3} -(-60) \cdot (-\frac{5}{4}) }{1} =5 \end{eqnarray}$ Somit erhalten wir: $\begin{eqnarray} \begin{pmatrix}9 & -36 & 30 \\ -36 & 192 & -180 \\ 30 & -180 & 180 \end{pmatrix} =\begin{pmatrix} 9&0& 0\\ -36 & 48 & 0 \\ 30 & -60 & 5\end{pmatrix} \begin{pmatrix} 1&-4 & \frac{10}{3} \\ 0&1&-\frac{5}{4} \\ 0&0&1 \end{pmatrix} \end{eqnarray}$ Aus dieses Verfahren wäre mit Permutation durchführbar. Im Theorie Teil wurde angenommen, dass die Matrix A schon entsprechend geordnet ist.
09.08.2007, 02:58	tigerbine	Auf diesen Beitrag antworten »
3. LDL^T - Zerlegung Die Diagonalelemente von L sind Einsen. K=1 $\begin{eqnarray} d_{11} = a_{11}= 9 \end{eqnarray}$ $\begin{eqnarray} l_{21} = \frac{a_{21}}{d_{11}} = \frac{-36}{9} = -4 \end{eqnarray}$ $\begin{eqnarray} l_{31} = \frac{a_{31}}{d_{11}} = \frac{30}{9} = \frac{10}{3} \end{eqnarray}$ K=2 $\begin{eqnarray} d_{22}=a_{22} - d_{11}\cdot l_{21}^2 = 192 - 9 \cdot (-4)^2 = 48 \end{eqnarray}$ $\begin{eqnarray} l_{32} = \frac{a_{32} - d_{11}\cdot l_{31} \cdot l_{21}}{d_{22}} = \frac{-180 - 9 \cdot \frac{10}{3}\cdot (-4)}{48}= -\frac{5}{4} \end{eqnarray}$ K=3 $\begin{eqnarray} d_{33} = a_{33} - d_{11}\cdot l_{31}^2 - d_{22} \cdot l_{32}^2 = 180 - 9 \cdot (\frac{10}{3})^2 - 48 \cdot (-\frac{5}{4})^2= 5 \end{eqnarray}$ Somit erhält man die LDL^T-Zerlegung: $\begin{eqnarray} \begin{pmatrix}9 & -36 & 30 \\ -36 & 192 & -180 \\ 30 & -180 & 180 \end{pmatrix} =\begin{pmatrix} 1&0&0 \\ -4&1&0 \\ \frac{10}{3}&-\frac{5}{4}&1\end{pmatrix} \begin{pmatrix} 9&0&0 \\ 0&48&0 \\ 0&0&5 \end{pmatrix}\begin{pmatrix} 1&-4 & \frac{10}{3} \\ 0&1&-\frac{5}{4} \\ 0&0&1 \end{pmatrix} \end{eqnarray}$ So könnte eine Speicherung erfolgen:
10.08.2007, 14:02	tigerbine	Auf diesen Beitrag antworten »
4. Cholesky-Zerlegung zunächst müssen wir nun die Wurzeln aus den Eintragen der vorherigen Diagonalmatrix ziehen $\begin{eqnarray} \hat l_{11} =\sqrt{9} = 3 \end{eqnarray}$ $\begin{eqnarray} \hat l_{22} = \sqrt{48} = 4\sqrt{3} \end{eqnarray}$ $\begin{eqnarray} \hat l_{33} = \sqrt{5} \end{eqnarray}$ Danach muss da Produkt $\begin{eqnarray} LD^{\frac{1}{2}} \end{eqnarray}$ gebildet werden. $\begin{eqnarray} \hat l_{21} =l_{21} \cdot \hat l_{11} = -4 \cdot 3 = -12 \end{eqnarray}$ $\begin{eqnarray} \hat l_{31} =l_{31} \cdot \hat l_{11} = \frac{10}{3} \cdot 3 = 10 \end{eqnarray}$ $\begin{eqnarray} \hat l_{32} = l_{32} \cdot \hat l_{22} = - \frac{5}{4} \cdot 4\cdot{3} = - 5 \sqrt{3} \end{eqnarray}$ Somit lautet die Cholesky-Zerlegung: $\begin{eqnarray} \begin{pmatrix}9 & -36 & 30 \\ -36 & 192 & -180 \\ 30 & -180 & 180 \end{pmatrix} =\begin{pmatrix} 3&0&0 \\ -12&4\sqrt{3}&0 \\ 10&- 5 \sqrt{3}&\sqrt{5}\end{pmatrix} \begin{pmatrix} 3&-12 & 10 \\ 0& 4 \sqrt{3}&-5 \sqrt{3} \\ 0&0&\sqrt{5} \end{pmatrix} \end{eqnarray}$ Wieder ein Blick in die Speicherung:
Anzeige

16.08.2007, 14:06	tigerbine	Auf diesen Beitrag antworten »
Lösen des Linearen Gleichungssystems Ax=b Hauptziel der Zerlegung der Matrix A war die Bestimmung der Lösung des LGS Ax = b. Mit den hier bestimmten Zerlegungen erhält man also: $\begin{eqnarray} A = LR:~Ax = b \Leftrightarrow LRx = b \end{eqnarray}$ D.h. mittels der gespeicherten Daten kann man durch Rückwärts- und Vowärtssubstitution die Lösung x* bestimmen. $\begin{eqnarray} A = LDL^T:~Ax=b \Leftrightarrow LDL^Tx = b \end{eqnarray}$ D.h. mittels der gespeicherten Daten kann man durch Rückwärts-, Direkt,- Vorwärtssubstitution die lösung x* bestimmen. $\begin{eqnarray} A=LL^T:~Ax=b \Leftrightarrow LL^Tx = b \end{eqnarray}$ D.h. mittels der gespeicherten Daten kann man durch Rückwärts- und Vowärtssubstitution die Lösung x* bestimmen.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »