Cholesky oder QR -Zerlegung? < Lin. Gleich.-systeme < Numerik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Hallo, ich habe wieder mal eine Frage: |
wenn ich von einer Matrix [mm] (A=B^T*B,A [/mm] also symmetrisch positiv semidefinit) die Cholesky Zerlegung berechne dann [mm] A=C^T*C, [/mm] C oebere Dreiecksmatrix. Ist es dasselbe wenn ich von B die QR-Zerlegung B=Q*R bestimme? R ist dann doch auch die obere Dreiecksmatrix mit [mm] (Q*R)^T*Q*R=R^T*Q^T*Q*R=R^T*R?
[/mm]
Wenn es dasselbe sein sollte dann bitte noch eine Frage: was ist sparsamer zu berechnen, Cholesky oder die QR-Zerlegung? Man sollte dabei auch die Bestimmung von [mm] B^T*B [/mm] beachten. Oder könnte man die Cholesky von A auch nur mit B bestimmen?
Danke an alle
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:37 So 25.03.2007 | | Autor: | viktory_hh |
Über ide erstee min ich mir mehr oder weniger doch noch sicher? oder gilt das nicht?
Zu zwei: kann man die Choleski von [mm] A^T*A [/mm] ohne das Produkt auszurechnen bestimmen?
Danke
|
|
|
| |
|
Hallo victory_hh,
> Hallo, ich habe wieder mal eine Frage:
> wenn ich von einer Matrix [mm](A=B^T*B,A[/mm] also symmetrisch
> positiv semidefinit) die Cholesky Zerlegung berechne dann
> [mm]A=C^T*C,[/mm] C oebere Dreiecksmatrix. Ist es dasselbe wenn ich
> von B die QR-Zerlegung B=Q*R bestimme? R ist dann doch auch
> die obere Dreiecksmatrix mit
> [mm](Q*R)^T*Q*R=R^T*Q^T*Q*R=R^T*R?[/mm]
Und was macht man jetzt damit?
> Wenn es dasselbe sein sollte dann bitte noch eine Frage:
> was ist sparsamer zu berechnen, Cholesky oder die
> QR-Zerlegung?
Cholesky
> Man sollte dabei auch die Bestimmung von
> [mm]B^T*B[/mm] beachten. Oder könnte man die Cholesky von A auch nur
> mit B bestimmen?
Wenn B symm. pos. def. sicher i.A. imho nein.
gruß
mathemaduenn
P.S.: Wenn es um die Lösung linearer Quadratmittelprobleme gehen soll mußt du das vllt. dazusagen.
|
|
|
| |
|
| Aufgabe | Also habe ich aus deiner Antwort verstanden, dass aus QR --> die Matrix R und aus Cholesky --> die Matrix C dasselbe sind wenn die Matrix pos. def. ist.
Nochmal: ich betrachte Cholesky von [mm] A=B^T*B [/mm] und QR-Zerlegung von B.
Auch wenn B nicht pos. def. ist A pos. def. wenn B regulär.
Leider bekomme ich auf der Diagonalen von R negative Elemente, noch schlimmer dass die Matrizen R und C doch noch relativ unterschiedlich sind, d.h. ein relativer Fehler von 10^-9. Das ist ja auch nicht gut. |
Eine etwas abgeänderte Frage: kann man die Cholesky Zerlegung durchführen, und dabei wegen Speicherknappheit nicht ständig die ganze Matrix R im Speicher halten müssen?
Danke
|
|
|
| |
|
Hallo,
> Eine etwas abgeänderte Frage: kann man die Cholesky
> Zerlegung durchführen, und dabei wegen Speicherknappheit
> nicht ständig die ganze Matrix R im Speicher halten müssen?
Also die Antwort ist natürlich ja, aber ich nehme an, dass war nicht genau Deine Frage. Ich habe leider das nicht mehr genau im Kopf, aber ich meine man braucht bei der Cholesky-Zerlegung immer wieder die gleichen Elemente. Man braucht, wenn ich mich nicht irre, immer zwei volständige Zeilen. Falls beide in den Speicher passen, ist es natürlich extrem Vorteilhaft. Ansonsten muss man wohl oder übel in den saueren Apfel beißen und Laufzeit durch Sekundärspeicherzugriffe opfern.
Mit freundlichen Grüßen
Matthias Kretschmer
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:12 Mo 26.03.2007 | | Autor: | viktory_hh |
erstmal vielen dank, das macht mir zunächst Mut mich weiter mit Cholesky in diese Richtung zu beschäftigen. Vielen Dank
|
|
|
| |
|
> Also habe ich aus deiner Antwort verstanden, dass aus QR
> --> die Matrix R und aus Cholesky --> die Matrix C dasselbe
> sind wenn die Matrix pos. def. ist.
Wenn Du wissen willst ob C=R gelten muß. Wolltest Du das wissen? Das gilt nicht Warum?
Multipliziere z.b. C mit einer Diagonalmatrix die 1 oder -1 auf der Diagonale hat. Dann ist immer noch
[mm] C^TC=(DC)^T(DC)=C^TD^TDC
[/mm]
aber es gilt offenbar nicht DC=C .
Dies ist eine mögliche Erklärung der neg. Diagonaleinträge. Ich nehme an die restliche Matrix stimmt auch nur bis aufs Vorzeichen.
> Leider bekomme ich auf der Diagonalen von R negative
> Elemente, noch schlimmer dass die Matrizen R und C doch
> noch relativ unterschiedlich sind, d.h. ein relativer
> Fehler von 10^-9. Das ist ja auch nicht gut.
Die Konditionszahl von B ist i.A. kleiner als die von A und QR-Zerlegung ist wohl das stabilste was man machen kann.( genauer [mm] cond_2(A)=cond_2(B)^2 [/mm] für invertierbares B)
> Eine etwas abgeänderte Frage: kann man die Cholesky
> Zerlegung durchführen, und dabei wegen Speicherknappheit
> nicht ständig die ganze Matrix R im Speicher halten müssen?
Ja. Die Choleskyzerlegung kann man auf dem Speicher von A durchführen. Für die QR-Zerlegung braucht man imho auch nur einen zusätzlichen Vektor.
viele Grüße
mathemaduenn
![[guckstduhier]](/images/smileys/guckstduhier.gif "[guckstduhier]")
![[]](/images/popup.gif) http://de.wikipedia.org/wiki/Cholesky-Zerlegung
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:01 Mo 26.03.2007 | | Autor: | viktory_hh |
O.K. alles klar, vielen Dank
|
|
|
|
