Permutation und eindeutige LR-Zerlegung

Neue Frage »

Dunkit Auf diesen Beitrag antworten »
Permutation und eindeutige LR-Zerlegung
So, ich mal wieder mit einer numerischen Frage...

Ich habe eine reguläre Matrix A. Zu zeigen ist, dass es eine Permutationsmatrix P gibt, so dass A eine eindeutige LR-Zerlegung besitzt, also .

Der Satz leuchtet ja irgendwie ein. Eine reguläre Matrix kann man schließlich auf jeden Fall zerlegen, wenn man Zeilenvertauschungen zulässt und nichts anderes bedeutet ja die Multiplikation mit P von links.

Es reicht doch eigentlich schon, das zu zeigen, oder? Also dass Zeilenvertauschungen ausreichen, um eine LR-Zerlegung anzugeben. Dann braucht man ja nurnoch zu sagen, dass alle diese Zeilenvertauschungen sich in einer Matrix P darstellen lassen, richtig?!

Meine Idee wäre folgende: Wenn ich irgendwann im k-ten Eliminationsschritt (Gauss) einen diagonaleintrag erwische, der 0 ist, muss sich wegen der Regularität irgendwo in dieser Spalte unterhalb dieses Diagonalelements noch ein Eintrag ungleich 0 befinden, sonst wären mindestens zwei Zeilen linear abhängig und damit A nicht regulär.

Kann ich diese Idee weiter verfolgen? bzw. wie zeige ich das?!
tigerbine Auf diesen Beitrag antworten »
Workshop Auszug
Mal wieder was zum Lesen. Augenzwinkern

Zitat:
I IdeeOriginal von tigerbine
In der Praxis wird jedoch häufiger der Fall einer LR-Zerlegung mit Pivotisierung auftreten, d.h. die Matrix A muss erst noch "aufbereitet werden. Man schreibt die Zerlegung dann in der Form , wobei P eine Permutationsmatrix ist.


Selbst wenn eine Pivotisierung nicht nötig ist, ist es am Ende günstiger die Matrix gleich durch diesen Algorithmus zu schicken. Denn bei der LR-Zerlegung ohne Pivotisierung muss man ja noch den Aufwand hinzunehmen, nachzuprüfen, ob diese Überhaupt möglich ist.

Ein weiterer Vorteil ist, dass man hier noch nicht einmal die Regularität von A prüfen muss. Bricht der Algorithmus ab, so ist A numerisch singulär.


Zitat:
II BerechnungOriginal von tigerbine
An einem Beispiel soll wieder die Idee verdeutlicht werden.







Darauf läßt sich nun ein Schritt der LR-Zerlegung (3a) durchführen.


mit



Im nächsten Schritt ist keine Vertauschung nötig. Dennoch schreibt man P=I hin. Warum werden wir später sehen.


mit



Im letzten Schritt ist nun wieder ein Vertauschen nötig.



Damit ist schon die gewünschte Dreiecksgestalt erreicht. Dennoch notiert man auch hier:


mit




Wie hängen nun die theoretisch existierende Darstellung PA=LR und die eben berechnete zusammen?
Dazu bedient man sich folgendes "Tricks", der am Beispiel illustriert werden soll:



Diese Matrizen haben sind wieder untere Dreiecksmatrizen mit der gleichen Struktur (Beweis unten). Die Permutationsmatrizen geben in ihrem Index hier nur an, welche Zeile getauscht werden soll. Den Tauschpartner läßt man hier nun einmal außen vor(siehe auch hier).


Somit ergibt sich:




Und damit die Zerlegung:




Dabei ist P wieder eine Permutationsmatrix und L wieder eine untere normierte Dreiecksmatrix. Im Beispiel also:










***********************************************************


Beweis:

Hier soll einmal die Struktur der konstruierten Matrizen betrachtet werden. Eine Permutationsmatrix ist zu sich selbst invers. Allgemein definiert ist nun:




Betrachten wir erstmal nur die Struktur von:




mit der Rechtsmultiplikation mit werden die Spalte (i+1) und eine Spalte vertauscht. Für diese gilt als Spaltenvektoren:






Nach dem ersten Tausch gilt also:




Nun werden die Zeilen (i+1) und j getauscht, somit ergibt sich:




Und somit ist die Struktur der Matrix erhalten geblieben, die Einträge sind jedoch vertauscht worden.


Zitat:
III - ExistenzOriginal von tigerbine
Jede reguläre Matrix besitzt eine Zerlegung in der Gestalt PA = LR mit mit einer(n x n) Permutationsmatrix P, einer (n x n) normierten unteren Dreiecksmatrix L sowie einer (n x n) oberen Dreiecksmatrix R.


Beweis:

Der Beweis wird durch Induktion geführt.




Zitat:
IV Eindeutigkeit und Pivotwahl.Original von tigerbine
In den Überlegungen von (4b) wurde bislang nur festgestellt, dass man bei einer regulären Matrix A immer einen "Tauschpartner" für den Fall einer Null auf der Diagonale findet.

Steht einem nicht nur ein "Tauschpartner" zur Verfügung, so stellt sich die Frage nach der "besten" Wahl. Den geringsten Aufwand wird wohl eine Suche nach dem ersten von 0 verschiedenen Eintrag in der betreffenden Spalte unterhalb der Diagonale machen. Ist diese "blinde" Wahl jedoch numerisch sinnvoll?


Durch die Implementierung erhält man eine Zerlegung und löst das LGS der Form:



mit einer unbekannten Matrix E, für die folgende Abschätzung gilt (Golub & VanLoan[1996, S. 106]):



m: Maschinengenauigkeit

n: Ordnung von A, also ist A eine (n x n) Matrix

|.|: Matrix der betragsmäßigen Einträgen


Somit ist es erstrebenswert die Einträge von möglichst klein zu halten.


2 LR-Zerlegungen:









Im ersten Fall treten also, im Gegensatz zum Zweiten, sehr große Werte auf. Man kann nun zeigen, dass allgemein für sehr kleine Diagonalelemente in der Matrix die Einträge in den Matrizen L und R sehr groß werden. Somit sollte man Kehrschluss die Diagonalelemente durch vertauschen möglichst groß wählen. Somit ergeben sich:



weitere Pivotsuchstrategien:

Spaltenpivotsuche
Unter den Elementen der j-ten Spalte wähle man ein dem Betrage nach größtes als neues Diagonalelement.
Suchaufwand:

Totale Pivotsuche
Unter den Elementen wähle man ein dem Betrag nach größtes als neues Diagonalelement aus. Hier müssen dann ggf. Zeilen und Spalten getauscht werden.
Suchaufwand:


Bei größeren Matrizen kann es sinnvoll sein, nur so lange zu suchen, bis ein Schwellenwert s überschritten wird.



Mit diesem Wissen kann man nun festhalten, dass auch im Falle der Existenz einer LR-Zerlegung ohne Pivotisierung es sinnvoll seien kann, selbige durchzuführen.


Hierzu ein Beispiel:




Exakte Lösung




Ohne Pivotisierung










Mit Spalten-Pivotisierung






Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »