QR-Zerlegung

06.01.2009, 18:20

Die_Kroete

QR-Zerlegung

Hallo Leute,

Ich hab da eine Matrix $\begin{eqnarray*} M = \begin{pmatrix} 2 & 1 \\ 2 & 2 \\ 1 & 0 \end{pmatrix} \end{eqnarray*}$ bekommen, die QR-zerlegt werden muss. Q hab ich nun wie folgt bestimmt:

$\begin{eqnarray*} a_1=\begin{pmatrix} 2 \\ 2 \\ 1 \end{pmatrix}, a_2=\begin{pmatrix} 1 \\ 2 \\ 0 \end{pmatrix} \end{eqnarray*}$

$\begin{eqnarray*} q_1 = \frac{1}{||a_1||}*a_1 \end{eqnarray*}$
$\begin{eqnarray*} q_1 = \frac{1}{3}*\begin{pmatrix} 2 \\ 2 \\ 1 \end{pmatrix} \end{eqnarray*}$

---

$\begin{eqnarray*} u_2=a_2-<a_2,q_1>*q_1 \end{eqnarray*}$

$\begin{eqnarray*} u_2=\begin{pmatrix} 1 \\ 2 \\ 0 \end{pmatrix}-<\begin{pmatrix} 1 \\ 2 \\ 0 \end{pmatrix},\begin{pmatrix} 2/3 \\ 2/3 \\ 1/3 \end{pmatrix}>*\begin{pmatrix} 2/3 \\ 2/3 \\ 1/3 \end{pmatrix} \end{eqnarray*}$

$\begin{eqnarray*} q_2 = \frac{1}{||u_2||}*u_2 \end{eqnarray*}$
$\begin{eqnarray*} q_2 = \frac{1}{1}*\begin{pmatrix} -1/3 \\ 2/3 \\ -2/3 \end{pmatrix} \end{eqnarray*}$

$\begin{eqnarray*} Q=\begin{pmatrix} 2/3 & -1/3 \\ 2/3 & 2/3 \\ 1/3 & -2/3 \end{pmatrix} \end{eqnarray*}$

Vielleicht hab ich da irgendwas falsch gemacht oder falsch angefangen, aber ich frag mich nun:
Wie komme ich auf R? Ist diese R-Matrix eigentlich nicht die selbe wie jene bei der LR-Zerlegung? Glaub das wäre etwas umständlich von A eine LR-Zerlegung zu machen, da muss es doch noch einen kürzeren Weg geben. Auf Google bzw. Wiki hab ich leider nichts näheres dazu gefunden und in meinem Skript steht auch nichts was mir weiterhilft...

Hiiilfe....

mit besten grüßen
Die Kröte

06.01.2009, 18:24

tigerbine

Auf diesen Beitrag antworten »

RE: QR-Zerlegung
[WS] Lineare Gleichungssysteme 2 - direkte Verfahren

06.01.2009, 18:37

Die_Kroete

Auf diesen Beitrag antworten »

Thx, das ging ja schnell... ^^

Also wenn ich das richtig verstanden hab kann man auf folgender Beziehung auf R kommen:
$\begin{eqnarray*} Q^{-1}A = R \Leftrightarrow Q^{T}A = R \Leftrightarrow A = QR \end{eqnarray*}$

Das heißt ich muss eine Matrizenmultiplikation zwischen der transponierten von Q und A machen um auf R zu kommen. Da $\begin{eqnarray*} (Q^T*Q) ( = I) * R = R \end{eqnarray*}$ ergibt.

Mein Ansatz mit Q war also vollkommen richtig? Jetzt muss ich mit $\begin{eqnarray*} Q^T \end{eqnarray*}$ also nur mehr R bestimmen und das wars?

06.01.2009, 18:40

tigerbine

Auf diesen Beitrag antworten »

Nein, du sollst den Algorithmus, hier eben QR mit Gram Schmidt machen. Dann bekommst du Q und R raus.

06.01.2009, 18:49

Die_Kroete

Auf diesen Beitrag antworten »

hm, wie meinst du das?
Q ist eh bereits nach Gram-Schmidt-Verfahren orthonormiert, hab statt $\begin{eqnarray*} v_1, v_2 \end{eqnarray*}$ nur $\begin{eqnarray*} q_2 \end{eqnarray*}$ als Bezeichnung gewählt. In meinem Skript wurde es so gemacht. Nur bei R wusste ich nicht wie das geht.

06.01.2009, 18:57

tigerbine

Auf diesen Beitrag antworten »

Steht doch in meinem Link. Das wird parallel berechnet.... Hier mal ein Beispiel:

Zitat:

$\begin{eqnarray*} A = \begin{pmatrix}1 & 5 & 4 \\ -2 & 1 & 3 \\ 2 & 0 &-2 \end{pmatrix} =\begin{pmatrix}q_{11} & q_{12} & q_{13} \\ q_{21} & q_{22} & q_{23} \\ q_{31} & q_{32} & q_{33} \end{pmatrix}\begin{pmatrix} r_{11} & r_{12} & r_{13} \\ 0 & r_{22} & r_{23} \\ 0&0& r_{33}\end{pmatrix} \end{eqnarray*}$

Wir wählen die Diagonalelemente von R nicht negativ. Somit ergibt sich:

$\begin{eqnarray*} r_{11} = ||a^1||_2 = \sqrt{1^2+(-2)^2+2^2} = 3 \end{eqnarray*}$

$\begin{eqnarray*} q^1 = \begin{pmatrix}\frac{1}{3} \\ -\frac{2}{3} \\ \frac{2}{3} \end{pmatrix} \end{eqnarray*}$

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

Nun rechnen wir das Gram Schmidt Verfahren (nicht das modifizierte!) einmal weiter durch:

j=2

$\begin{eqnarray*} q^2:=a^2 = \begin{pmatrix} 5 \\ 1 \\ 0 \end{pmatrix} \end{eqnarray*}$

$\begin{eqnarray*} r_{12}:=(q^1)^Ta^2 = (\frac{1}{3},-\frac{2}{3},\frac{2}{3}) \begin{pmatrix}5\\1\\0 \end{pmatrix}= 1 \end{eqnarray*}$

$\begin{eqnarray*} q^2:=q^2-r_{12} \cdot q^1=\begin{pmatrix} 5 \\ 1 \\ 0 \end{pmatrix}-1\cdot \begin{pmatrix}\frac{1}{3} \\ -\frac{2}{3} \\ \frac{2}{3} \end{pmatrix}=\begin{pmatrix} \frac{14}{3} \\ \frac{5}{3} \\-\frac{2}{3} \end{pmatrix} \end{eqnarray*}$

$\begin{eqnarray*} r_{22}:= ||q^2||_2 = \sqrt{\frac{196}{9} + \frac{25}{9} + \frac{4}{9}} = \frac{15}{3} = 5 \end{eqnarray*}$

$\begin{eqnarray*} q^2:=\begin{pmatrix} \frac{14}{15} \\ \frac{1}{3} \\-\frac{2}{15} \end{pmatrix} \end{eqnarray*}$

q=3

$\begin{eqnarray*} q^3=\begin{pmatrix} 4 \\ 3 \\ -2\end{pmatrix} \end{eqnarray*}$

$\begin{eqnarray*} r_{13}:= (q^1)^Ta^3 =(\frac{1}{3},~ -\frac{2}{3},~ \frac{2}{3} ) \begin{pmatrix} 4 \\ 3 \\ -2\end{pmatrix} = -2 \end{eqnarray*}$

$\begin{eqnarray*} q^3:=q^3 +2 \cdot q^1 =\begin{pmatrix} 4 \\ 3 \\ -2\end{pmatrix} + 2\cdot \begin{pmatrix}\frac{1}{3} \\ -\frac{2}{3} \\ \frac{2}{3} \end{pmatrix} = \begin{pmatrix}\frac{14}{3} \\ \frac{5}{3} \\- \frac{2}{3} \end{pmatrix} \end{eqnarray*}$

$\begin{eqnarray*} r_{23}:=(q^2)^Ta^3 =(\frac{14}{15},~\frac{1}{3},~-\frac{2}{15}) \begin{pmatrix} 4 \\ 3 \\ -2\end{pmatrix} = 5 \end{eqnarray*}$

$\begin{eqnarray*} q^3:=q^3-5\cdot q^2 = \begin{pmatrix}\frac{14}{3} \\ \frac{5}{3} \\- \frac{2}{3} \end{pmatrix} - 5\cdot \begin{pmatrix} \frac{14}{15} \\ \frac{1}{3} \\-\frac{2}{15} \end{pmatrix} = \begin{pmatrix} 0 \\ 0\\ 0\end{pmatrix} \end{eqnarray*}$

$\begin{eqnarray*} r_{33} = 0 \end{eqnarray*}$

Lehrer

Hier bricht das Verfahren nun ab. Denn die Matrix A hat nur den Rang 2 (n=3). Eine QR-Zerlegung ist in diesem Fall mit dem Gram-Schmidt-Verfahren nicht möglich. Dennoch sollen die bisherigen Resultat einmal notiert werden. In den nächsten beiden Absätzen werden wir sehen, dass man auch im Falle Rang(A) < n eine QR-Zerlegung bestimmen kann und was das für die Lösungsmenge des Linearen Ausgleichsproblems bedeutet.

$\begin{eqnarray*} A = QR \Leftrightarrow A = \begin{pmatrix}1 & 5 & 4 \\ -2 & 1 & 3 \\ 2 & 0 &-2 \end{pmatrix} = \begin{pmatrix} \frac{1}{3} & \frac{14}{15} & ? \\ -\frac{2}{3} & \frac{1}{3} & ? \\\frac{2}{3} & -\frac{2}{15}&? \end{pmatrix} \begin{pmatrix} 3&1&-2 \\ 0 & 5 & 5 \\ 0 &0&0\end{pmatrix} \end{eqnarray*}$

06.01.2009, 19:24

Die_Kroete

Auf diesen Beitrag antworten »

danke!

ja, meine variante war aber auch richtig. hab meine Variante an dein Beispiel da angewendet und komme auch auf die selbe QR-Zerlegung.

06.01.2009, 19:36

tigerbine

Auf diesen Beitrag antworten »

Sicher kommt man, mit Q und A auf R. Nur der "Algo" geht eben anders. Das meinte ich damit. Augenzwinkern

06.01.2009, 19:38

Die_Kroete

Auf diesen Beitrag antworten »

Falls dich interessiert was ich meine:

$\begin{eqnarray*} q^2:=a^2 = \begin{pmatrix} 5 \\ 1 \\ 0 \end{pmatrix} \end{eqnarray*}$

$\begin{eqnarray*} r_{12}:=(q^1)^Ta^2 = (\frac{1}{3},-\frac{2}{3},\frac{2}{3}) \begin{pmatrix}5\\1\\0 \end{pmatrix}= 1 \end{eqnarray*}$ <= das ist das Skalarprodukt also dasselbe wie $\begin{eqnarray*} <a_2,q_1> \end{eqnarray*}$ bei mir

$\begin{eqnarray*} q^2:=q^2-r_{12} \cdot q^1=\begin{pmatrix} 5 \\ 1 \\ 0 \end{pmatrix}-1\cdot \begin{pmatrix}\frac{1}{3} \\ -\frac{2}{3} \\ \frac{2}{3} \end{pmatrix}=\begin{pmatrix} \frac{14}{3} \\ \frac{5}{3} \\-\frac{2}{3} \end{pmatrix} \end{eqnarray*}$ <= $\begin{eqnarray*} u_2=a_2-<SKALARPRODUKT von OBEN>*q_1 \end{eqnarray*}$
Vergleich mit Formel aus meinem Skript:
$\begin{eqnarray*} u_2=a_2-<a_2,q_1>*q_1 \end{eqnarray*}$

Jetzt normierst du noch:

$\begin{eqnarray*} r_{22}:= ||q^2||_2 = \sqrt{\frac{196}{9} + \frac{25}{9} + \frac{4}{9}} = \frac{15}{3} = 5 \end{eqnarray*}$

$\begin{eqnarray*} q^2:=\begin{pmatrix} \frac{14}{15} \\ \frac{1}{3} \\-\frac{2}{15} \end{pmatrix} \end{eqnarray*}$

das entspricht dann $\begin{eqnarray*} q_2=\frac{1}{||u_2||}*u_2 \end{eqnarray*}$

Was aber für mich interessant ist an deiner Variante, dass man auf R auch direkt kommt.

lg
Die Kröte

06.01.2009, 19:42

Die_Kroete

Auf diesen Beitrag antworten »

ok. vielen dank nochmal für deine Hilfe. smile

06.01.2009, 19:43

tigerbine

Auf diesen Beitrag antworten »

"Du" machst einfach nur das Gram Schmidt verfahren zur Orthogonalisierung von Vektoren.

Bindet man in diesem Verfahren das Vorhaben ein, eine QR-Zerlegung zu bestimmen, so berechnet man eben noch r gleich mit. Deswegen heißt es ja QR nach Gram Schmidt. Augenzwinkern

28.07.2013, 18:30

der_frosch

Auf diesen Beitrag antworten »

Der Thread ist uralt, ich hoffe, er wird noch gelesen =)

Tigerbine schreibt, dass das die QR Zerlegung mit Gram-Schmidt nur bei Rang = n geht.
Über Spaltenpivotisierung sollte es aber doch auch für Rang<n gehen, oder?

Neue Frage »

Antworten »

QR-Zerlegung

Verwandte Themen