Givens < Lin. Gleich.-systeme < Numerik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:39 Sa 07.05.2011 | | Autor: | wieschoo |
Hi,
die "normale Givensoperation" kenne ich.
In diesem Buch wird die "fast givens" besprochen:
Ich habe auch einen Algorithmus gefunden, der mir
die obere Dreickesmatrix und die Diagonalmatrix ausrechnet.
Wenn ich jetzt Ax=b lösen möchte, dann bin der Meinung, dass noch etwas fehlt. Oder kann ich damit das LGS lösen:
In dem paper steht:
In this section we briefly discuss the two different QR decomposition algorithms and report on
computation times that were obtained using the algorithms. The input for both of the algorithms
is an m × n matrix A, with m > n. The output for the Givens algorithm is an n x n upper
triangular matrix R, with $R = Q^TA$ and Q m x m orthogonal. The output for the Fast Givens
algorithm is an n x n upper triangular matrix T with $T = M^TA$ and $M^TM = diag(d1, .... [mm] ,d_m)$.
[/mm]
Wie kann ich damit das LGS lösen.
bei der normalen QR- zerlegung kann ich es ja einfach durch vorwärst und Rückwärst substitution lösen.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:57 Sa 07.05.2011 | | Autor: | felixf |
Moin wieschoo!
> die "normale Givensoperation" kenne ich.
>
> In diesem Buch wird die "fast
> givens" besprochen:
Der Link ist nutzlos.
> Ich habe auch einen Algorithmus gefunden, der mir
> die obere Dreickesmatrix und die Diagonalmatrix
> ausrechnet.
>
> Wenn ich jetzt Ax=b lösen möchte, dann bin der Meinung,
> dass noch etwas fehlt. Oder kann ich damit das LGS lösen:
>
> In dem paper steht:
> In this section we briefly discuss the two different QR
> decomposition algorithms and report on
> computation times that were obtained using the algorithms.
> The input for both of the algorithms
> is an m × n matrix A, with m > n. The output for the
> Givens algorithm is an n x n upper
> triangular matrix R, with [mm]R = Q^TA[/mm] and Q m x m orthogonal.
Bist du sicher, dass $R$ das Format $n [mm] \times [/mm] n$ hat?! [mm] $Q^T [/mm] A$ hat doch das Format $m [mm] \times [/mm] n$.
> The output for the Fast Givens
> algorithm is an n x n upper triangular matrix T with [mm]T = M^TA[/mm]
> and [mm]M^TM = diag(d1, .... ,d_m)[/mm].
(Hier das gleiche.)
Die [mm] $d_1, \dots, d_m$ [/mm] sind nicht 0, oder?
> Wie kann ich damit das LGS lösen.
>
> bei der normalen QR- zerlegung kann ich es ja einfach durch
> vorwärst und Rückwärst substitution lösen.
Macht man mit der Fast Givens Rotation genauso: aus $A x = b$ folgt doch nach Multiplikation mit [mm] $M^T$, [/mm] dass $R x = [mm] M^T [/mm] A x = [mm] M^T [/mm] b$ ist. Das LGS $R x = [mm] M^T [/mm] b$ kannst du schoen einfach loesen (durch Rueckwaertseinsetzen), und das dafuer benoetigte [mm] $M^T [/mm] b$ erhaelst du durch eine Matrix-Vektor-Multiplikation.
Edit: es soll $T x = [mm] M^T [/mm] A x = [mm] M^T [/mm] b$ heissen, und dann das LGS $T x = [mm] M^T [/mm] b$.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:03 Sa 07.05.2011 | | Autor: | wieschoo |
Das Problem ist, dass der Algorithmus nicht dieses M liefert.
http://files.wieschoo.com/algo.txt
Das ist der Algorithmus. Den habe ich nicht geschrieben. Er liefert jedoch nur diese Dieagonalmatrix
und ich kann [mm] $R=D^{-1/2}*fgivQRo(A)$ [/mm] berechnen. Habe aber kein Q.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:11 Sa 07.05.2011 | | Autor: | felixf |
Moin!
> Das Problem ist, dass der Algorithmus nicht dieses M
> liefert.
Du kannst den Algo entsprechend abaendern 
Oder besser: du aenderst den Algo so ab, dass er auch den Vektor $b$ erhaelt, und genauso wie er Schritt fuer Schritt $A$ transformiert, die gleichen Transformationen auch auf $b$ anwendet, um schliesslich [mm] $M^T [/mm] b$ zu erhalten (neben [mm] $M^T [/mm] A$).
> http://files.wieschoo.com/algo.txt
>
> Das ist der Algorithmus. Den habe ich nicht geschrieben. Er
> liefert jedoch nur diese Dieagonalmatrix
>
> und ich kann [mm]R=D^{-1/2}*fgivQRo(A)[/mm] berechnen. Habe aber
> kein Q.
Das $R$ brauchst du auch nicht, das $T = fgivQRo(A)$ reicht voellig, wenn du fgivQRo aenderst dass es $[T, [mm] \hat{b}] [/mm] = fgivQRo(A, b)$ lautet mit $T = [mm] M^T [/mm] A$ und [mm] $\hat{b} [/mm] = [mm] M^T [/mm] b$.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:31 Sa 07.05.2011 | | Autor: | wieschoo |
Ich sehe den Sinn dann nicht die Diagonalmatrix noch mit zurückzugeben. Hat das einen Sinn?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:21 Sa 07.05.2011 | | Autor: | felixf |
Moin!
> Ich sehe den Sinn dann nicht die Diagonalmatrix noch mit
> zurückzugeben. Hat das einen Sinn?
Bei dieser Anwendung? Nein.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:23 Sa 07.05.2011 | | Autor: | wieschoo |
Danke dir.
Vielleicht ist ja der Sinn die "Verwirrung" gewesen. Trotzdem danke.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:32 So 08.05.2011 | | Autor: | wieschoo |
Ich bin ja auch doof. Warum bin ich da nicht gleich darauf gekommen.![[heul]](/images/smileys/heul.gif "[heul]")
Der Algorithmus muss ja nicht geändert werden, sonder nur die Eingabegröße.
|
|
|
|
