Permutationsmatrix und LU-Zerl < Lin. Gleich.-systeme < Numerik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 10:56 So 08.01.2006 | | Autor: | apanachi |
| Aufgabe | | Wie beweise ich, dass es zu einer quadratischen Matrix A eine Permutationsmatrix gibt, so dass PA gleich der LU zerlegung von A ist? |
Wenn ich den Beweis mit Induktion über n versuche, muss ich dann die Anzahl der Zeilen als n betrachten?
Aber eigentlich habe ich gar keine Ahnung, wie ich das wirklich machen soll.
Es wäre super, wenn mir jemand helfen könnte.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 12:26 So 08.01.2006 | | Autor: | DaMenge |
Hi,
angenommen du hast eine quadratische Matrix A mit n Zeilen, wobei n beliebig ist.
weisst du denn, warum es nicht immer klappt einfach die LU-Zerlegung ohne irgendwelche Zeilenpermutationen durchzuführen?
Wenn du nun also Gauss-Verfahren machen würdest - was kann dabei passieren?
Wie hilft dir dann eine Permutationsmatrix weiter?
Und wenn du dies in verschiedenen Schritten des Gauss-Algo's machen müsstest - wie kann man dann die verschiedenen Permutationsmatrizen der einzelnen Schritte zu einer zusammen fassen ?
Schreib mal formal auf, wie weit du kommst - nur so sehen wir ja, wieviel Hilfe du tatsächlich noch brauchst.
Ach so, per Induktion würde es bestimmt auch gehen - wenn du nämlich den Gauss-algo dann evtl. mit Permutation in der ersten Zeile gemacht hast, kannst du dann die Induktionsvorraussetzung für den Rest der Matrix benutzen - wie setzt sich dann die neue gesamt-Permutationsmatrix zusammen?
viele Grüße
DaMenge
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:39 So 08.01.2006 | | Autor: | apanachi |
Hallo DaMenge,
die Permutationsmatrix bewirkt ja, dass die Zeilen der Matrix A vertauscht werden, damit ich dann später diese Matrix ohne Zeilenvertauschen mit Gauß Algo auf eine obere Dreiecksmatrix bringen kann.
Wenn ich mehrere Zeilen vertauschen muss multipliziere ich mehrere Permutationsmatrizen von links mit A. Ist das so richtig?
[mm]\pmat{ 0 & 1 \\ 1 & 0 }[/mm]*[mm]\pmat{ a & b \\ c & d }[/mm]=[mm]\pmat{ c & d \\ a & b }[/mm]
Dann könnte man das Ergebnis als LU zerlegung schreiben, aber wie muss ich denn bei einer Induktion anfangen und woher weiß ich dann (bei Variablen, dass diese Matrix jetzt zerlegt werden kann und die andere nicht?
|
|
|
| |
|
Hallo apanachi,
> die Permutationsmatrix bewirkt ja, dass die Zeilen der
> Matrix A vertauscht werden, damit ich dann später diese
> Matrix ohne Zeilenvertauschen mit Gauß Algo auf eine obere
> Dreiecksmatrix bringen kann.
![[daumenhoch]](/images/smileys/daumenhoch.gif "[daumenhoch]")
> Wenn ich mehrere Zeilen vertauschen muss multipliziere ich
> mehrere Permutationsmatrizen von links mit A. Ist das so
> richtig?
> Dann könnte man das Ergebnis als LU zerlegung schreiben,
> aber wie muss ich denn bei einer Induktion anfangen und
> woher weiß ich dann (bei Variablen, dass diese Matrix jetzt
> zerlegt werden kann und die andere nicht?
Die Möglichkeiten durchgehen.
1. in Spalte i gibt's ein Eintrag ungleich Null -> man kann durch Zeilenvertauschen einen Gaußschritt durchführen.
2. es gibt nur Nullen in der entsprechenden Spalte -> Übergang zur nächsten Spalte i+1
viele Grüße
mathemaduenn
|
|
|
| |
|
> Wie beweise ich, dass es zu einer quadratischen Matrix A
Sei [mm]A := \begin{pmatrix}0&0\\0&0\end{pmatrix} \in \mathbb{R}^{2\times 2}[/mm].
> eine Permutationsmatrix gibt, so dass PA gleich der LU
> zerlegung von A ist?
Zum obigen [mm]A[/mm] gibt es keine solche Permutationsmatrix, oder? Stimmt den die Aufgabenstellung so wie sie da steht?
Obwohl man vielleicht sagen könnte, daß
[mm]A = \underbrace{\begin{pmatrix}1&0\\0&1\end{pmatrix}}_{=:L}\underbrace{\begin{pmatrix}0&0\\0&0\end{pmatrix}}_{=:R}[/mm]
eine solche Zerlegung ist. Allerdings wüßte ich nicht, ob man mit dem Gauss-Algorithmus darauf kommen könnte... ![[kopfkratz3]](/images/smileys/kopfkratz3.gif "[kopfkratz3]")
[Oder was wäre, wenn ich als [mm]A[/mm] die "Telefonmatrix" wähle?]
Viele Grüße
Karl
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:57 Mo 09.01.2006 | | Autor: | Stefan |
Hallo Karl!
Man muss i.A. die Regularität von $A$ voraussetzen, um ganz sicher eine Zerlegung der Form $PA=LR$ erhalten zu können.
Edit: Okay, wenn $R$ nicht regulär sein muss, dann geht es natürlich immer.
Den Beweis für die Aussage findet man (zum Beispiel) in Hämmerlin/Hoffmann: Numerische Mathematik, Satz zur Dreieckszerlegung, Seite 58, aber -ich denke mal- auch in fast jedem Numerik-Skript.
Liebe Grüße
Stefan
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:00 Mo 09.01.2006 | | Autor: | DaMenge |
Hi,
ich würde sagen, das hängt davon ab, wie man das Format von L und R gewählt hat...
eine Möglichkeit : man könnte erlauben, dass sowohl bei L aber auch bei R Einträge auf der Diagonalen stehen können (wobei nur die in L immer ungleich 0 sein müssen / oder immer Diagonaleinträge in L alle gleich 1)
> [Oder was wäre, wenn ich als [mm]A[/mm] die "Telefonmatrix" wähle?]
[mm] $\pmat{1&0&0\\4&1&0\\7&2&1}*\pmat{1&2&3\\0&-3&-6\\0&0&0}=\pmat{1&2&3\\4&5&6\\7&8&9}$
[/mm]
viele Grüße
DaMenge
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:13 Mo 09.01.2006 | | Autor: | moudi |
Hallo zusammen
Da man durch den Gaussalgorithmus (mit vertauschen der Zeilen) immer erreichen kann, dass R in Zeilenstufenform ist, gibt es daher eine Permutationsmatrix P so, dass
PA=LR, wobei L auf den Diagonalen nur 1 hat und R in Zeilenstufenform ist.
mfG Moudi
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:06 Mo 09.01.2006 | | Autor: | Karl_Pech |
Hallo Zusammen!
Danke für eure zahlreichen Antworten! Also kann man für jede quadratische Matrix mit dem Pivot-Gauss-Algorithmus eine LR-Zerlegung bestimmen. Meine Verwirrung rührte wohl daher, daß ich über Matrizen gesprochen, aber lineare Gleichungssysteme im Kopf hatte... ![[bonk]](/images/smileys/bonk.gif "[bonk]")
Ich versuche mal den Beweis im Hämmerlin/Hoffmann nachzuvollziehen.
Liebe Grüße
Karl
|
|
|
|
