Givens Rotation -Lineares Ausgleich Problem m x n Matrix

07.07.2014, 14:19

Oran

Givens Rotation -Lineares Ausgleich Problem m x n Matrix

Hallo,

ich stehe vor folgendem Problem:

Ich bekomme es einfach nicht hin diese Ausgabe zulösen.

Gegeben sind :

$\begin{eqnarray*} A = \begin{pmatrix} 3 & 7 & -2 \\ 4 & 5 & -10 \\ 0 & -2 & 3 \\ 0 & 0 & 8 \end{pmatrix} und b = \begin{pmatrix} 12 \\ 7 \\ 5 \\ -2 \end{pmatrix} \end{eqnarray*}$

Ich soll nun mittels der QR Zerlegung das Ausgleichs Problem lösen
Wobei

$\begin{eqnarray*} Ax = b \end{eqnarray*}$

Eine QR Zerlegung mit einer 3x3 Matrix bekomme ich hin.
Aber ich scheitere schon daran R zu bestimmen.

In diese Workshop finde ich zwar Formeln
[WS] Lineare Ausgleichprobleme

kann aber diese nur schwer nach vollziehen:

Wie kommt er auf
$\begin{eqnarray*} R = \begin{pmatrix} R Dach \\ 0 \end{pmatrix} \end{eqnarray*}$

Und wozu das c ?

Könnte mir jemand helfen ein Beispiel durchzurechnen, ich steige da irgendiwe überhaupt nicht durch.

Gruß und Danke im Vorraus

09.07.2014, 15:11

Oran

Auf diesen Beitrag antworten »

Ich hoffe jemand kann mir dabei helfen.

Bei der Householder zerlegung geht es mir ähnlich.

Sobald eine nicht quadratische MAtrix zum einsatzkommt bin ich raus.

Falls jemand ansonsten Links (gerne auch für Youtube) für mich hat wäre ich auch glücklich.

Danke im vorraus

24.07.2014, 19:38

Oran

Auf diesen Beitrag antworten »

Kann mir denn hierbei niemand helfen ?

25.07.2014, 02:28

frank09

Auf diesen Beitrag antworten »

RE: Givens Rotation -Lineares Ausgleich Problem m x n Matrix
Sinn ist es zunächst, durch Drehungen die Matrix A auf die Form

$\begin{eqnarray*} R=\begin{pmatrix} * & * &* \\ 0 & * & * \\ 0 & 0 & *\\ 0 & 0 & 0 \end{pmatrix} \end{eqnarray*}$ zu bekommen.

Genaue Vorgehensweise findest du hier:
http://de.wikipedia.org/wiki/Givens-Rotation

Zitat:

Eine QR Zerlegung mit einer 3x3 Matrix bekomme ich hin.

Dann weißt du ja, wie man einen bestimmten Eintrag $\begin{eqnarray*} a_{ij} \end{eqnarray*}$ durch Drehung auf null bringt?

Im obigen Beispiel wird $\begin{eqnarray*} A=\begin{bmatrix} 3 & 5\\ 0 & 2\\ 0 & 0\\ 4 & 5 \end{bmatrix} \end{eqnarray*}$ durch zwei Rotationen auf $\begin{eqnarray*} R = \begin{bmatrix} 5 & 7\\ 0 & \sqrt{5}\\ 0 & 0\\ 0 & 0 \end{bmatrix} \end{eqnarray*}$ gebracht.

$\begin{eqnarray*} \hat R \end{eqnarray*}$ ist die obere Dreiecksmatrix, es werden also alle Nullzeilen weggelassen:
$\begin{eqnarray*} \hat R= \begin{bmatrix} 5 & 7\\ 0 & \sqrt{5}\end{bmatrix} \end{eqnarray*}$

Mithilfe der beiden Givensrotationen G1 und G2 lässt sich A wie folgt darstellen
$\begin{eqnarray*} G_2G_1A=R \end{eqnarray*}$

Setzt man $\begin{eqnarray*} Q^T=G_2G_1 \end{eqnarray*}$ bzw. $\begin{eqnarray*} Q=(G_2G_1)^T=G_1^TG_2^T \end{eqnarray*}$ gilt
$\begin{eqnarray*} A=QR \end{eqnarray*}$

Zu minimieren ist
$\begin{eqnarray*} ||Ax-b||_2 && = ||QRx - b||_2 =||Q^TQRx -Q^T b||_2=||Rx -Q^T b||_2 \end{eqnarray*}$
Nun sei
$\begin{eqnarray*} Q^Tb=G_2G_1b=\begin{pmatrix}c_1 \\c_2 \\ c_3 \\ c_4 \end{pmatrix} \end{eqnarray*}$

$\begin{eqnarray*} ||\begin{bmatrix} 5 & 7\\ 0 & \sqrt{5}\\ 0 & 0\\ 0 & 0 \end{bmatrix}\begin{pmatrix}x_1 \\x_2 \end{pmatrix}-\begin{pmatrix}c_1 \\c_2 \\ c_3 \\ c_4 \end{pmatrix}||_2 \end{eqnarray*}$

$\begin{eqnarray*} ||\begin{pmatrix}5x_1+7x_2-c_1 \\\sqrt{5}x_2-c_2 \\ -c_3 \\ -c_4 \end{pmatrix}||_2 \end{eqnarray*}$

Die oberen beiden Zeilen kann ich auf null bekommen, indem ich folgendes GLS löse

$\begin{eqnarray*} \begin{bmatrix} 5 & 7\\ 0 & \sqrt{5}\end{bmatrix} \begin{pmatrix}x_1 \\x_2 \end{pmatrix}=\begin{pmatrix}c_1 \\c_2 \end{pmatrix} \end{eqnarray*}$
Sei nun
$\begin{eqnarray*} \begin{pmatrix}c_1 \\c_2 \end{pmatrix}= \hat c \end{eqnarray*}$ , dann ist zu lösen

$\begin{eqnarray*} \hat Rx = \hat c \end{eqnarray*}$

26.07.2014, 04:17

Oran

Auf diesen Beitrag antworten »

Danke sehr.

Ich glaube das hilft mir ganz gut weiter.

Ich habe mir zu folgender Frage noch etwas aufgeschrieben und kann das jetzt nicht ganz nachvollziehen.
Ich hatte mir aufgeschrieben, dass das Gleichungssystem nur dann eindeutig lösbar sei, wenn man das Vorzeichen der Diagonalelemente von R bzw R~ vorgibt und folgendes gilt:

$\begin{eqnarray*} A^{m x n} mit m \geq n und Rang(A)=n \end{eqnarray*}$

bringe ich da irgendwas durcheinander?
Oder wo wird hier vorgegeben, das die Diegonaleelemente von R positiv sind?

Zudem sehe ich das richtig, das G immer quadratisch ist und immer die Größe entsprechend A hat.

Also:

Dimension von G = max{n,m) von A.

oder gilt G m x m da m>= n ?

26.07.2014, 16:48

Oran

Auf diesen Beitrag antworten »

Desweiteren sehe ich das richtig , dass folgendes gilt:

$\begin{eqnarray*} G_{i,j} = G_{j,i} mit c_{1} \neq c_{2} und s_{1} \neq s_{2} \end{eqnarray*}$

Also der aufbau der Givens Matrizen gleich ist und sich nur deren s bzw c elemente unterscheidet?

27.07.2014, 00:34

frank09

Auf diesen Beitrag antworten »

Zitat:

Ich hatte mir aufgeschrieben, dass das Gleichungssystem nur dann eindeutig lösbar sei, wenn man das Vorzeichen der Diagonalelemente von R bzw R~ vorgibt...

Es gibt nur eine QR-Zerlegung, bei der z.B. alle Vz positiv sind. Wenn man z.B. spiegelt statt dreht, können sich bei R die Vz unterscheiden. Das sagt aber nichts über die Lösbarkeit aus. Dazu muss R Dach vollen Rang haben, was ja klar ist. G ist auch immer quadratisch mit m x m Elementen.

Zitat:

Desweiteren sehe ich das richtig , dass folgendes gilt:...

Ja.

27.07.2014, 00:39

Oran

Auf diesen Beitrag antworten »

Danke sehr.

Wie kann ich den erkennen wann das Gleichunssystem eindeutig lösbar ist?
NUR dadruch, dass R bzw R Dach vollen Rang hat?

27.07.2014, 23:26

frank09

Auf diesen Beitrag antworten »

RE: Givens Rotation -Lineares Ausgleich Problem m x n Matrix
Ja, wenn R (Dach) und A den Rang n haben, ist das Ausgleichsproblem eindeutig lösbar, ansonsten nicht.

27.07.2014, 23:30

Oran

Auf diesen Beitrag antworten »

RE: Givens Rotation -Lineares Ausgleich Problem m x n Matrix

Zitat:

Original von frank09
Ja, wenn R (Dach) und A den Rang n haben, ist das Ausgleichsproblem eindeutig lösbar, ansonsten nicht.

Danke sehr!
Dann bin ich ja beruhigt und dieses mit positiven Elementen auf der Diagona festlegen ist Mumpitz?

28.07.2014, 00:34

Oran

Auf diesen Beitrag antworten »

Gibt es eigentlich eine Strategie, nach der man am "besten" die Reihenfolge der ai,j wählen sollte?

Also welche Stelle man zuerst zu 0 machen sollte oder ist das eigentlich egal?

28.07.2014, 02:29

Oran

Auf diesen Beitrag antworten »

Ich habe jedoch immer folgendes Problem mit der Aufgabe.

Laut dieses Online Tools komme ich auf ein falsches ergebniss bezüglich einiger Vorzeichen, auch mit nachrechnen finde ich meinen Fehler nicht.

$\begin{eqnarray*} A = \begin{pmatrix} 3 & 7 & -2 \\ 4 & 5 & -10 \\ 0 & -2 & 3 \\ 0 & 0 & 8 \end{pmatrix} b = \begin{pmatrix} 12 \\ 7 \\ 5 \\ -2 \end{pmatrix} \end{eqnarray*}$

Ich komme dabei auf :

$\begin{eqnarray*} R = \begin{pmatrix} 5 & 8.2 & -9.2 \\ 0 & -3.2802 & -1.6583 \\ 0 & 0 & 9.4661 \\ 0 & 0 & 0 \end{pmatrix} \end{eqnarray*}$

Angeblich stimmen die Vorzeichen in der zweiten Zeile von R nicht

Gibt es hier doch irgendeine Vorraussetzung

Hier wären meine A und G Matrizen:

$\begin{eqnarray*} A_{1} = \begin{pmatrix} 5 & 8.2 & -9.2 \\ 0 & -2.6 & -4.4\\ 0 & -2 & 3 \\ 0 & 0 & 8 \end{pmatrix} A_{2} = \begin{pmatrix} 5 & 8.2 & -9.2 \\ 0 & -3.2802 & -1.6583 \\ 0 & 0 & 5.0605 \\ 0 & 0 & 8 \end{pmatrix} G_{2,1} = \begin{pmatrix} 3/5 & 4/5 & 0 & 0 \\ -4/5 & 3/5 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix} G_{3,2} = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 0.7926 & 0.6097 & 0 \\ 0 & -0.6097 & 0.7926 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix} G_{4,3} = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0.5346 & 0.8451 \\ 0 & 0 & -0.8451 & 0.5346 \end{pmatrix} \end{eqnarray*}$

Ich sollte hierbei immer mit Nachkommastellen rechnen.

Könnte ihr mir sagen wo der Fehler liegt?

Ich habe mit meinem "fehlerhaftem" R mal weitergerechnet

$\begin{eqnarray*} Q = \begin{pmatrix} 0.6 & 0.8 & 0 & 0 \\ -0.6341 & 0.4756 & 0.6097 & 0 \\ 0.7608 & -0.1956 & 0.4237 & 0.8451 \\ -0.4122 & 0.3091 & -0.6698 & 0.5346 \end{pmatrix} \end{eqnarray*}$

Dann habe ich Q transponiert und von links auf b multipliziert

$\begin{eqnarray*} Q^{T}*b = \begin{pmatrix} 7.2897 \\ 11.333 \\ 7.726 \\ 3.1563 \end{pmatrix} \end{eqnarray*}$

Damit komme ich dann auf

$\begin{eqnarray*} \vec{x} = \begin{pmatrix} 9.3026 \\ -3.8676 \\ 0.8162 \end{pmatrix} \end{eqnarray*}$

Laut dieses online Tools wäre das falsch, allerdings weichen meine Vorzeichen auch ab.
Es könnten natürlich auch Rechenfehler unterlaufen sein aber ist das Vorgehen richtig so?

29.07.2014, 17:56

Oran

Auf diesen Beitrag antworten »

Hallo

ok ich hatte das Q transponiert falsch. weill das Produkt der einzelnen Rotations Matrizen ja bereits Qt ergibt.

Zwar unterscheiden sich meine Vorzeichen, aber es kommt letzlich das selbe für x heraus smile

Neue Frage »

Antworten »

Givens Rotation -Lineares Ausgleich Problem m x n Matrix

Verwandte Themen