QR-Zerlegung mittels Householder-Transf.

16.11.2006, 16:07

Paul_H

QR-Zerlegung mittels Householder-Transf.

So, ich habe jetzt echt die Schnauze voll. LOL Hammer

Ich sitze nun schon so lange an der Aufgabe, und doch scheine ich irgendetwas falsch zu machen, irgendwo sitzt ein kleiner Fehler, der mir immer alles kaputt macht.
Bitte, schaut euch meine Rechnungen an und findet meinen Fehler.

Also, gegeben:

$\begin{eqnarray*} A_1 = \begin{pmatrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} & \sqrt{2} \\ \frac{1}{ \sqrt{2}} & \frac{1}{\sqrt{2}} & 0 \\ 0 & 1 & 1 \end{pmatrix} \end{eqnarray*}$

Berechnet habe ich nun:

$\begin{eqnarray*} v = \vec{a_1} + sgn( a_{11} ) || \vec{a_1} ||_2 e_1 = \frac{1}{\sqrt{2}} \begin{pmatrix} \sqrt{2} + 1 \\ 1 \\ 0 \end{pmatrix} \end{eqnarray*}$

$\begin{eqnarray*} \beta = \frac{1}{||\vec{a_1}||_2^2 + |a_1| ||\vec{a_1}||_2 } = \frac{\sqrt{2}}{1 + \sqrt{2}} \end{eqnarray*}$
$\begin{eqnarray*} w = \begin{pmatrix} 1 \\ 0 \end{pmatrix} \end{eqnarray*}$

$\begin{eqnarray*} w = \beta A_1^T v = \begin{pmatrix} 1 \\ 1 \\ \sqrt{2} \end{pmatrix} \end{eqnarray*}$

$\begin{eqnarray*} Q_1A_1 = A_1 - vw^T \end{eqnarray*}$

$\begin{eqnarray*} . \end{eqnarray*}$

$\begin{eqnarray*} . \end{eqnarray*}$

$\begin{eqnarray*} . \end{eqnarray*}$

$\begin{eqnarray*} = \begin{pmatrix} -1 & -1 & -1 \\ 0 & 0 & -1 \\ 0 & 1 & 1 \end{pmatrix} \end{eqnarray*}$

Bis hierhin gefallen mir meine Zwischenergebnisse recht gut.

$\begin{eqnarray*} Q_1 = E_3 \cdot \beta \cdot v v^T \end{eqnarray*}$

$\begin{eqnarray*} = \frac{1}{ 2 + \sqrt{2}} \cdot \begin{pmatrix} -(1+ \sqrt{2}) & -(1+ \sqrt{2}) & 0 \\ -(1+ \sqrt{2}) & 1+ \sqrt{2} & 0 \\ 0 & 0 & 2 + \sqrt{2} \end{pmatrix} \end{eqnarray*}$

Aber ab spätestens jetzt (der eigentlich viel einfachere Teil) geht alles schief:

Nun ist $\begin{eqnarray*} A_2 = \begin{pmatrix} 0 & -1 \\ 1 & 1 \end{pmatrix} \end{eqnarray*}$

$\begin{eqnarray*} \beta = 1 \end{eqnarray*}$
$\begin{eqnarray*} v = \begin{pmatrix} 1 \\ 1 \end{pmatrix} \end{eqnarray*}$
$\begin{eqnarray*} w = \begin{pmatrix} 1 \\ 0 \end{pmatrix} \end{eqnarray*}$

$\begin{eqnarray*} \tilde{Q_2} = \begin{pmatrix} -1 & 0 \\ 2 & 0 \end{pmatrix} \end{eqnarray*}$

So, wenn ich nun diese Matrix später in meine rechte untere Dreiecksmatrix R einbaue, kommt natürlich keine rechte untere Dreiecksmatrix raus.

18.11.2006, 10:43

mathemaduenn

Auf diesen Beitrag antworten »

RE: QR-Zerlegung mittels Householder-Transf.
Hallo Paul,
Deinen Algo kann ich ehrlich gesagt nicht ganz nachvollziehen. Insbesondere die Berechnung von $\begin{eqnarray*} Q_1 \end{eqnarray*}$ scheint mir falsch zu sein. Einen funktionierenden Algo findest Du z.B. hier Wenn Du mit Programmiersprachen kein Problem hast auch bei Numerical Recipes in C.
viele Grüße
mathemaduenn

02.01.2009, 14:32

tigerbine

Auf diesen Beitrag antworten »

Nachtrag
Hier steht der Algorithmus: QR mit Householder

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:

>> QRmitH
Es wird eine QR-Zerlegung mit Householder berechnet.
====================================================
---------------------------
| H=I-ß*uu^T              |
| u=x+sign(x1)*||x||_2*e1 |
| ß=2/(u^Tu)              |
---------------------------
 
A0 =
    0.7071    0.7071    1.4142
    0.7071    0.7071         0
         0    1.0000    1.0000
 
Durchgang 1 
================
x =
    0.7071
    0.7071
         0
signx =
     1
e1 =
     1
     0
     0
u =
    1.7071
    0.7071
         0
beta =
    0.5858
 
H =
   -0.7071   -0.7071         0
   -0.7071    0.7071         0
         0         0    1.0000
Qk =
   -0.7071   -0.7071         0
   -0.7071    0.7071         0
         0         0    1.0000
Ak =
   -1.0000   -1.0000   -1.0000
    0.0000    0.0000   -1.0000
         0    1.0000    1.0000
 
Durchgang 2 
================
x =
    0.0000
    1.0000
signx =
     1
e1 =
     1
     0
u =
     1
     1
beta =
     1
 
H =
     0    -1
    -1     0
Qk =
     1     0     0
     0     0    -1
     0    -1     0
Ak =
   -1.0000   -1.0000   -1.0000
         0   -1.0000   -1.0000
   -0.0000   -0.0000    1.0000
 
 
Die QR-Zerlegung mit Householder
--------------------------------
A =
    0.7071    0.7071    1.4142
    0.7071    0.7071         0
         0    1.0000    1.0000
Q =
   -0.7071         0    0.7071
   -0.7071         0   -0.7071
         0   -1.0000         0
R =
   -1.0000   -1.0000   -1.0000
         0   -1.0000   -1.0000
   -0.0000   -0.0000    1.0000

Neue Frage »

Antworten »

QR-Zerlegung mittels Householder-Transf.

Verwandte Themen