Cholesky- / LR-Zerlegung < Lin. Gleich.-systeme < Numerik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:19 Sa 17.01.2009 | | Autor: | Pacapear |
Hallo zusammen.
Ich verstehe irgendwie den Sinn bzw. den Nutzen der Cholesky-Zerlegung nicht so ganz.
Was bringt es mir, bei spd-Matrizen ausgerechnet dieses Verfahren und nicht bloß die LR-Zerlegung anzuwenden?
Eigentlich ist es doch viel mehr Aufwand, weil zum Berechnen der Colesky-Zerlegung muss ich ja überhaupt erstmal die LR-Zerlegung bilden.
Und dann am Ende, wenn ich ein LGS [mm]\ Ax=b[/mm] lösen will.
Bei LR nehme ich dann einfach meine R-Matrix und mein verändertes [mm]\ b[/mm] und mache Rückwärts-Einsetzen.
Hab ich mehrere [mm]\ b[/mm], dann rechne ich einmal LR (ohne [mm]\ b[/mm] zu verändern), und berechne dann [mm]\ Lz=b[/mm] für alle [mm]\ b[/mm] durch Vorwärts-Einsetzen und danach [mm]\ Rx=z[/mm] für alle [mm]\ z[/mm] durch Rückwärts-Einsetzen.
Aber wie löse ich das LGS bei Cholesky?
Ich habe ja dann [mm]\ L'[/mm] und [mm]\ (L')^T[/mm] , also [mm] A=L'*(L')^T [/mm] , aber wie erhalte ich dann mein [mm]\ x[/mm]?
Wahrscheinlich auch irgendwie durch Vorwärts-Einsetzen oder Rückwärts-Einsetzen, aber wie?
Wir haben keine Gleichungen aufgeschrieben...
Nehme ich dann mein [mm]\ (L')^T[/mm] zum Rückwärts-Einsetzen?
Aber wenn ja, was hätte das für einen Sinn?
Bis ich [mm]\ (L')^T[/mm] erstmal ausgerechnet habe, hätte ich mein [mm]\ x[/mm] schon längst über [mm]\ LR[/mm] erhalten
Irgendwie versteh ich das nicht...
LG, Nadine
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 12:26 So 18.01.2009 | | Autor: | max3000 |
Hallo,
also das Lösen der Gleichungssysteme geht bei Cholesky genau so.
L ist eine untere Dreiecksmatrix, also lösbar mit Vorwärtselimination und [mm] L^T [/mm] folglich eine obere Dreiecksmatrix, also Rückwärtselimination.
Die Choleskyzerlegung geht immer schneller als LR, darum wird diese auch für spd-Matrizen angewendet.
Ein Vorteil ist, dass diese immer ohne Pivotisierung (im Gegensatz zur LR-Zerlegung) durchführbar ist.
Wenn dann D die Diagonale von A ist, so gilt:
[mm] DL^T=R,
[/mm]
wenn man die LR-Zerlegung durchführen würde.
Der unterschied bei der Choleskyzerlegung ist nun, dass man D auf R und L gleich verteilt. Aus diesem Grund reicht es auch nur eine der Beiden Dreiecksmatrizen zu berechnen. Darum kommt die Choleskyzerlegung mit nur der Hälfte der Rechenoperationen aus ( [mm] O(n^2/3) [/mm] statt [mm] O(2n^2/3) [/mm] ).
Also wie gesagt, die Ideen sind die gleichen, nur mit dem Unterschied, dass man nur eine Dreiecksmatrix berechnen muss und damit nur halb so viel Aufwand besteht.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:59 So 18.01.2009 | | Autor: | Pacapear |
Hallo!
> Die Choleskyzerlegung geht immer schneller als LR, darum
> wird diese auch für spd-Matrizen angewendet.
Das verstehe ich nicht.
Warum geht die Choleskyzerlegung schneller als LR?
Um die Choleskyzerlegung zu erhalten, muss ich doch erstmal LR machen, oder nicht?
> Ein Vorteil ist, dass diese immer ohne Pivotisierung (im
> Gegensatz zur LR-Zerlegung) durchführbar ist.
Ja, das weiß ich.
Liegt doch daran, dass die Matrix spd ist, oder?
> Wenn dann D die Diagonale von A ist, so gilt:
> [mm]DL^T=R,[/mm]
> wenn man die LR-Zerlegung durchführen würde.
Das habe ich anders gelernt...
Also ich meine, dass [mm]DL^T=R[/mm] hatte ich auch.
Aber D ist bei uns nicht die Diagonale von A, sondern von R, besteht also aus den jeweiligen Pivotelementen von A.
[Diesen Fehler hatte ich in einem Thema vorher auch gemacht, da hat mich ein MR-Mitglied darauf aufmerksam gemacht, dass D eben nicht die Diagonale von A ist. Und genauso steht es auch in meinem Skript, hatte nur falsch gelesen  ]
> Der unterschied bei der Choleskyzerlegung ist nun, dass man
> D auf R und L gleich verteilt.
Was meinst du damit?
> Aus diesem Grund reicht es
> auch nur eine der Beiden Dreiecksmatrizen zu berechnen.
Wenn ich nur ein b habe, dann muss ich doch bei LR auch nur eine Dreiecksmatrix berechen, nämlich R. Die L-Matrix brauch ich doch zur Berechnung des x in [mm]Ax=b[/mm] dann eigentlich garnicht.
Ich bereche einfach R mit Gauß, verändere b direkt mit und kann dann x über Rückwärtseinsetzen lösen.
Welche Dreiecksmatrix würde ich denn dann bei Cholesky berechnen?
Und komme ich da auch ohne LR hin?
Weil ich kenne nur Cholesky mittels LR.
LG, Nadine
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:14 Di 20.01.2009 | | Autor: | alex42 |
Hallo Nadine,
ich versuche mal, einigermaßen strukturiert zu erzählen:
Zuerst einmal: Wie du wahrscheinlich weißt, kann man jede spd-Matrix A schreiben als [mm]A = L D L^T[/mm], wobei L eine untere Dreiecksmatrix mit Einsen auf der Diagonalen und D eine Diagonalmatrix mit positiven Einträgen ist. Wenn man jetzt $R := D [mm] L^T$ [/mm] setzt, bekommt man die LR-Zerlegung von A. Man kann aber auch die "Wurzel" von D betrachten: $D = [mm] D^{\frac{1}{2}}D^{\frac{1}{2}}$. [/mm] Dann bekommt man mit der Definition [mm] $\overline{L} [/mm] := L [mm] D^{\frac{1}{2}}$ [/mm] die Zerlegung
$A = [mm] \overline{L} *\overline{L}^T$
[/mm]
Ich denke, das war damit gemeint, D zu "verteilen". Geht man jetzt die Einträge von A sukzessive durch und schaut, welche Einträge von [mm] $\overline{L}$ [/mm] man für die Berechnung benötigt (z.B. ist [mm] $a_{1 1} [/mm] = [mm] l_{1 1}^2$) [/mm] bekommt man den Cholesky-Algorithmus.
Das ist die Herleitung, wie ich sie kenne, also komplett ohne LR. Ich weiß nicht, wie ihr das aufgebaut habt, aber man muss definitiv nur das [mm] $\overline{L}$ [/mm] berechnen, egal wie viele rechte Seiten b man hat. Damit kommt man etwa auf den halben Aufwand vom Gauß-Algorithmus, Cholesky ist also immer schneller - vorausgesetzt er ist anwendbar. Dazu muss die Matrix halt spd sein. Andererseits gilt aber auch, dass, falls Cholesky anwendbar ist, die Matrix positiv definit sein muss! D.h., wenn man eine Matrix auf positive Definitheit testen will, kann man probieren, ob eine Cholesky-Zerlegung möglich ist. Auch wenn es vielleicht blöd klingt: So weit ich weiß gibt es derzeit keinen schnelleren Weg, das zu testen - was ein großer Nutzen der Zerlegung ist, auch wenn man gar kein Gleichungssystem lösen will.
Gruß,
Alex
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:55 Di 20.01.2009 | | Autor: | Pacapear |
Hallo Alex.
Danke für deine Antwort.
Ich denke, ich habe es jetzt verstanden
LG, Nadine
|
|
|
|
