Numerik: Spaltenpivotsuche bei LR Zerlegung.

26.08.2005, 18:03

Protector1982

Numerik: Spaltenpivotsuche bei LR Zerlegung.

Ich habe das Prinzip der normalen LR Zerlegung um ein Gleichungssystem zu lösen verstanden.
Was ändert sich an dem Verfahren, wenn man es mit einer Spaltenpivotsuche verwenden soll, oder allgemein eine Pivotsuche benutzen soll?

Nehmen wir als Beispiel:
$\begin{eqnarray*} A=\begin{pmatrix}-1&2&3\\-2&7&4\\1&4&-2\end{pmatrix} \end{eqnarray*}$
und die Gleichung soll lauten:
$\begin{eqnarray*} Ax=\begin{pmatrix}12\\24\\3\end{pmatrix} \end{eqnarray*}$

$\begin{eqnarray*} A&=\begin{pmatrix}-1&2&3\\-2&7&4\\1&4&-2\end{pmatrix}\to \begin{pmatrix}-1&2&3\\0&3&-2\\1&4&-2\end{pmatrix}\to \begin{pmatrix}-1&2&3\\0&3&-2\\0&6&1\end{pmatrix}\to \begin{pmatrix}-1&2&3\\0&3&-2\\0&0&5\end{pmatrix} \end{eqnarray*}$
$\begin{eqnarray*} \Rightarrow R=\begin{pmatrix}-1&2&3\\0&3&-2\\0&0&5\end{pmatrix} \end{eqnarray*}$
L Bestimmen
$\begin{eqnarray*} \begin{pmatrix}-1&2&3\\-2&7&4\\1&4&-2\end{pmatrix}=\begin{pmatrix}1&0&0\\L_{21}&1&0\\L_{31}&_{32}&1\end{pmatrix}\cdot \begin{pmatrix}-1&2&3\\0&3&-2\\0&0&5\end{pmatrix} \end{eqnarray*}$
$\begin{eqnarray*} \begin{pmatrix}-1&2&3\\-2&7&4\\1&4&-2\end{pmatrix}=\begin{pmatrix}-1&2&3\\-L_{21}&2L_{21}+3&-3L_{21}-2\\-L_{31}&2L_{31}+3L_{32}&3L_{31}-2L_{32}+5\end{pmatrix} \end{eqnarray*}$
$\begin{eqnarray*} \Rightarrow L=\begin{pmatrix}1&0&0\\2&1&0\\-1&2&1\end{pmatrix} \end{eqnarray*}$
Gleichung lösen:
$\begin{eqnarray*} Ax=b \Rightarrow L\cdot R\cdot x=b \end{eqnarray*}$
$\begin{eqnarray*} y=R\cdot x\Rightarrow L\cdot y=b \end{eqnarray*}$
$\begin{eqnarray*} \begin{pmatrix}1&0&0\\2&1&0\\-1&2&1\end{pmatrix}\cdot \begin{pmatrix}y_1\\y_2\\y_3\end{pmatrix}=\begin{pmatrix}12\\24\\3\end{pmatrix}<br /> \Rightarrow y=\begin{pmatrix}12\\0\\15\end{pmatrix} \end{eqnarray*}$
Jetzt nur noch das x bestimmen:
$\begin{eqnarray*} y=R\cdot x \end{eqnarray*}$
$\begin{eqnarray*} \begin{pmatrix}12\\0\\15\end{pmatrix}=\begin{pmatrix}-1&2&3\\0&3&-2\\0&0&5\end{pmatrix}\cdot \begin{pmatrix}x_1\\x_2\\x_3\end{pmatrix} \end{eqnarray*}$
$\begin{eqnarray*} \Rightarrow x=\begin{pmatrix}1\\2\\3\end{pmatrix} \end{eqnarray*}$

Wie funktioniert das nun mit der Piviotsuche?

27.08.2005, 09:35

Auf diesen Beitrag antworten »

So wie ich den Begriff Pivot-Suche kenne, bezieht er sich ausschließlich auf numerische Matrix-Verfahren (sei es nun Gauß-Algorithmus, LR-Zerlegung usw.), und dort zum Zwecke der Reduzierung der numerischen Fehler.

Nur als Beispiel den Anfang, das Eliminationsverfahren und dort nur die erste Spalte. Da hast du die erste Zeile, also die Position (1,1) mit Wert -1 als Bezugspunkt genommen:

Zitat:

Original von Protector1982
$\begin{eqnarray*} A&=\begin{pmatrix}-1&2&3\\-2&7&4\\1&4&-2\end{pmatrix}\to \begin{pmatrix}-1&2&3\\0&3&-2\\1&4&-2\end{pmatrix}\to \begin{pmatrix}-1&2&3\\0&3&-2\\0&6&1\end{pmatrix} \end{eqnarray*}$

Beim Pivot-Verfahren sucht man aber in dieser ersten Spalte das betragsmäßig maximale Element - das ist hier die (-2) an Position (2,1), und richtet danach die Elimination aus:

$\begin{eqnarray*} A&=\begin{pmatrix}-1&2&3\\-2&7&4\\1&4&-2\end{pmatrix}\to \begin{pmatrix}0&-3/2&1\\-2&7&4\\1&4&-2\end{pmatrix}\to \begin{pmatrix}0&-3/2&1\\-2&7&4\\0&15/2&0\end{pmatrix} \end{eqnarray*}$

Bezugselement in der zweiten Spalte wären anschließend die 15/2 an Position (3,2) .

Wie man am vermehrten Auftauchen von Brüchen deutlich sieht, ist das bei ganzen Zahlen und schriftlicher Rechnung eher nicht so günstig - es handelt sich aber wie gesagt um ein numerisches Verfahren.

Außerdem ergibt sich so am Ende nur dann eine "echte" R-Matrix, wenn man noch die Zeilen permutiert - man muss also über den Verlauf der Rechnung einen Permutationsvektor (Pivotvektor) mitführen, der dies protokolliert. Aber das ist ja mitunter auch beim "normalen" Verfahren unumgänglich, wenn an "unpassender Stelle" in der Matrix eine Null auftaucht und dort das "normale" Verfahren zu Fall bringt...

27.08.2005, 16:56

Protector1982

Auf diesen Beitrag antworten »

Hm, genau im Buch steht, dass der Piviot Verktor mitgeführt werden muss.
Wie würde ich dass denn weiterrechnen? Ist mir noch nicht so wirklich klar, vor allem was genau schreibe ich in den Vektor rein?

Wenn ich dich richtig verstehe würde das Verfahren also so gehen?
Wenn b= $\begin{eqnarray*} \begin{pmatrix}0\\4\\15\end{pmatrix} \end{eqnarray*}$ wäre und $\begin{eqnarray*} A=\begin{pmatrix}4&1&0\\1&4&1\\0&5&4\end{pmatrix} \end{eqnarray*}$

$\begin{eqnarray*} \begin{pmatrix}4&1&0&\mid&1&0&0\\1&4&1&\mid&0&1&0\\0&5&4&\mid&0&0&1\end{pmatrix} \end{eqnarray*}$

$\begin{eqnarray*} \Rightarrow \begin{pmatrix}4&1&0&\mid&1&0&0\\0&\frac{15}{4}&1&\mid&\frac{1}{4}&1&0\\0&5&4&\mid&0&0&1\end{pmatrix} \end{eqnarray*}$

Da $\begin{eqnarray*} \frac{15}{4}<5 \end{eqnarray*}$ muss 2 und 3 getauscht werden:
$\begin{eqnarray*} \begin{pmatrix}4&1&0&\mid&1&0&0\\0&5&4&\mid&0&0&1\\0&\frac{15}{4}&1&\mid&\frac{1}{4}&1&0\end{pmatrix} \end{eqnarray*}$
$\begin{eqnarray*} \rightarrow \begin{pmatrix}4&1&0&\mid&1&0&0\\0&5&4&\mid&0&0&1\\0&0&-2&\mid&\frac{1}{4}&1&-\frac{3}{4}\end{pmatrix} \end{eqnarray*}$

Wie rechne ich jetzt weiter?

edit: Doppelpost zusammengefügt, bitte benutze die edit-Funktion! (MSS)

29.08.2005, 16:47

Auf diesen Beitrag antworten »

Hmmm, da gibt es wohl unterschiedliche Darstellungen, was man wie als Pivotvektor bezeichnet. Ich versuch's mal nur prinzipiell zu klären, dazu greife ich auf meinen letzten Beitrag zurück (um den letzten Schritt ergänzt):

$\begin{eqnarray*} \begin{pmatrix}-1&2&3\\-2&7&4\\1&4&-2\end{pmatrix}\to \begin{pmatrix}0&-3/2&1\\-2&7&4\\1&4&-2\end{pmatrix}\to \begin{pmatrix}0&-3/2&1\\-2&7&4\\0&15/2&0\end{pmatrix} \to \begin{pmatrix}0&0&1\\-2&7&4\\0&15/2&0\end{pmatrix}=R \end{eqnarray*}$

Die Pivotelemente lagen in der 1.Spalte in der 2.Zeile, in der 2.Spalte in der 3.Zeile und in der 3.Spalte in der 1.Zeile (bei letzterem ist dann aber nichts mehr zu rechnen), das bezeichne ich mal mit $\begin{eqnarray*} \pi=(2,3,1) \end{eqnarray*}$ . ( $\begin{eqnarray*} \pi \end{eqnarray*}$ = Permutation)
Diesem $\begin{eqnarray*} \pi \end{eqnarray*}$ isomorph zugeordnet ist eine Permutationsmatrix $\begin{eqnarray*} \Pi=\begin{pmatrix}0&0&1\\1&0&0\\0&1&0\end{pmatrix} \end{eqnarray*}$ in folgendem Sinne:

$\begin{eqnarray*} \begin{pmatrix}0&0&1\\-2&7&4\\0&15/2&0\end{pmatrix} = \begin{pmatrix}0&0&1\\1&0&0\\0&1&0\end{pmatrix} \cdot \begin{pmatrix}-2&7&4\\0&15/2&0\\0&0&1\end{pmatrix} = \Pi\cdot R \end{eqnarray*}$

"Isomorphie" deswegen, weil die Hintereinanderausführung von Permutationen einer Matrizenmultiplikation der zugehörigen Permutationsmatrizen entspricht. Dieses $\begin{eqnarray*} R \end{eqnarray*}$ hat jetzt die "normale", d.h. gewohnte Dreiecksgestalt, und da Permutationsmatrizen im besonderen auch Orthogonalmatrizen sind, gilt $\begin{eqnarray*} \Pi^T\Pi=E \end{eqnarray*}$ und wir können bezugnehmend auf die normale LR-Zerlegung (also ohne Pivotisierung) im R-Teil folgern:

$\begin{eqnarray*} \Pi^T \cdot A = \begin{pmatrix}0&1&0\\0&0&1\\1&0&0\end{pmatrix} \cdot \begin{pmatrix}-1&2&3\\-2&7&4\\1&4&-2\end{pmatrix} = \begin{pmatrix}-2&7&4\\1&4&-2\\-1&2&3\end{pmatrix} \to \cdots \to \begin{pmatrix}-2&7&4\\0&15/2&0\\0&0&1\end{pmatrix} = R \end{eqnarray*}$

D.h., für $\begin{eqnarray*} \Pi^TA \end{eqnarray*}$ führst du jetzt eine gewöhnliche LR-Zerlegung durch - R hast du ja bereits.

Siehe auch http://de.wikipedia.org/wiki/LR-Zerlegung ; das $\begin{eqnarray*} P \end{eqnarray*}$ dort entspricht dem $\begin{eqnarray*} \Pi^T \end{eqnarray*}$ hier.

18.09.2005, 15:50

Log

Auf diesen Beitrag antworten »

Hallo Leute,

ich rechne gerade eine alte Klausur Höhere Mathematik. Und hier ist bei LR-Zerlegung gefragt und nacher ob man aus L und R die Eigenwerte und/oder die Determinante ablesen kann. Gefunden habe ich bis jetzt das die Hauptachse der U-Matrix die Determinante ergibt. Aber mit den Eigenwerten habe ich bisher nichts. Weiß jemand Bescheid? Danke.

18.09.2005, 16:09

Log

Auf diesen Beitrag antworten »

Ist aufgeklärt. Man kann die Eigenwerte aus der Hauptdiagonalen der U Matrix ablesen und die Determinante ist logischerweise immer noch die HAuptachse der U Matrix multipliziert Augenzwinkern

26.09.2005, 19:59

Protector1982

Auf diesen Beitrag antworten »

So hier mal für alle ein ausführliches Beispiel für Pivot! Auf das es jemand vielleicht hilft...
$\begin{eqnarray*} \begin{pmatrix}4&1&0&\mid&1&0&0\\1&4&1&\mid&0&1&0\\0&5&4&\mid&0&0&1\end{pmatrix}\rightarrow \begin{pmatrix}4&1&0&\mid&1&0&0\\0&\frac{15}{4}&1&\mid&\frac{1}{4}&1&0\\0&5&4&\mid&0&0&1\end{pmatrix} \end{eqnarray*}$
2 und 3 muss getauscht werden
$\begin{eqnarray*} \begin{pmatrix}4&1&0&\mid&1&0&0\\0&5&4&\mid&0&1&1\\0&\frac{15}{4}&1&\mid&\frac{1}{4}&0&1\end{pmatrix}\rightarrow \begin{pmatrix}4&1&0&\mid&1&0&0\\0&5&4&\mid&0&1&0\\0&0&-2&\mid&\frac{1}{4}&\frac{3}{4}&1\end{pmatrix} \end{eqnarray*}$
$\begin{eqnarray*} Ly=\tilde{b} \end{eqnarray*}$ da das b ja nicht vertauscht wurde oder:
$\begin{eqnarray*} Ly=\tilde{b}=Pb \end{eqnarray*}$ mit P entspricht der Vertauschung also:
$\begin{eqnarray*} P=\begin{pmatrix}1&0&0\\0&0&1\\0&1&0\end{pmatrix} \end{eqnarray*}$
$\begin{eqnarray*} \begin{pmatrix}1&0&0&\mid&0\\0&1&0&\mid&4\\\frac{1}{4}&\frac{3}{4}&1&\mid&15\end{pmatrix}\Leftrightarrow y=\begin{pmatrix}0&4&12\end{pmatrix} \end{eqnarray*}$
$\begin{eqnarray*} R\cdot x=y \end{eqnarray*}$ hier darf nichts mehr getauscht werden, da im vorherigen die Vertauschung rückgänig gemacht wurde.
$\begin{eqnarray*} \begin{pmatrix}4&1&0&\mid&0\\0&5&4&\mid&4\\0&0&-2&\mid&12\end{pmatrix} \end{eqnarray*}$
$\begin{eqnarray*} x=\begin{pmatrix}-\frac{7}{5}\\\frac{28}{5}\\-6\end{pmatrix} \end{eqnarray*}$

Neue Frage »

Antworten »

Numerik: Spaltenpivotsuche bei LR Zerlegung.

Verwandte Themen