QR-Zerlegung mit Nullzeile (Householder)

24.06.2011, 18:30

Tom9876

QR-Zerlegung mit Nullzeile (Householder)

Meine Frage:
Hallo,
bei einer QR-Zerlegung nach dem Householder-Verfahren
mit der Matrix (4x3)
A = (1,2,3 ; 0,0,0 ; 1,2,1 ; 3,2,1)
bekomme ich

R = (-3.74,-2.67,-2.67 ; 0,0,0 ; 0,-1.09,-2.61 ; 0,0.81,0)

(R ist nicht in (zeilen-)Stufenform.)

Nach welchen Regeln muß ich eine Matrix manipulieren, welche
mindestens eine Nullzeile enthält,bevor ich
das Verfahren der QR-Zerlegung speziell nach Householder
anwenden kann, um dennoch ein korrektes Ergebnis zu bekommen ?

Meine Ideen:
Mein Ansatz für die Lösung ist bis jetzt:

wenn ich im o.a. Beispiel vor der QR-Zerlegung
in A die Nullzeile streiche und alle anderen nach oben rücke und
die Nullzeile am Ende einfüge, dann bekomme ich für R ein korrektes Ergebnis. In Q muß ich zusätzlich noch die Zeilen in umgekehrter
Reihenfolge zurückvertauschen.

Am Bsp. Oben bekomme ich nach folgenden Zeilenvertauschungen:
1) Z2,Z3
2) Z3,Z4

A´=(1,2,3 ; 1,2,1 ; 3,2,1 ; 0,0,0)

und damit R´= (-3.74,-2.67,-2.67 ; 0,1.36,2.09 ; 0,0,1.56 ; 0,0,0)

wenn ich bei Q´ die Zeilenvertauschungen von oben in
umgekehrter Reihenfolge durchführe, bekomme ich
ein korrektes Q .

24.06.2011, 18:37

tigerbine

Auf diesen Beitrag antworten »

RE: QR-Zerlegung mit Nullzeile (Householder)
[WS] Lineare Ausgleichprobleme ff.
[WS] Lineare Ausgleichsprobleme - Beispiele

Komme da eigentlich durch...

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:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:
129:
130:
131:
132:
133:
134:

>> QRmitH
Es wird eine QR-Zerlegung mit Householder berechnet.
====================================================
---------------------------
| H=I-ß*uu^T              |
| u=x+sign(x1)*||x||_2*e1 |
| ß=2/(u^Tu)              |
---------------------------
 
Matrix A eingeben: [1,2,3;0,0,0;1,2,1;3,2,1]
A0 =
     1     2     3
     0     0     0
     1     2     1
     3     2     1
 
Durchgang 1 
================
x =
     1
     0
     1
     3
signx =
     1
e1 =
     1
     0
     0
     0
u =
    4.3166
         0
    1.0000
    3.0000
beta =
    0.0698
 
H =
   -0.3015         0   -0.3015   -0.9045
         0    1.0000         0         0
   -0.3015         0    0.9302   -0.2095
   -0.9045         0   -0.2095    0.3714
Qk =
   -0.3015         0   -0.3015   -0.9045
         0    1.0000         0         0
   -0.3015         0    0.9302   -0.2095
   -0.9045         0   -0.2095    0.3714
Ak =
   -3.3166   -3.0151   -2.1106
         0         0         0
    0.0000    0.8382   -0.1839
    0.0000   -1.4854   -2.5518
 
Durchgang 2 
================
x =
         0
    0.8382
   -1.4854
e1 =
     1
     0
     0
u =
    1.7056
    0.8382
   -1.4854
beta =
    0.3438
 
H =
         0   -0.4914    0.8709
   -0.4914    0.7585    0.4280
    0.8709    0.4280    0.2415
Qk =
    1.0000         0         0         0
         0         0   -0.4914    0.8709
         0   -0.4914    0.7585    0.4280
         0    0.8709    0.4280    0.2415
Ak =
   -3.3166   -3.0151   -2.1106
    0.0000   -1.7056   -2.1320
    0.0000   -0.0000   -1.2317
    0.0000    0.0000   -0.6950
 
Durchgang 3 
================
x =
   -1.2317
   -0.6950
signx =
    -1
e1 =
     1
     0
u =
   -2.6459
   -0.6950
beta =
    0.2672
 
H =
   -0.8709   -0.4914
   -0.4914    0.8709
Qk =
    1.0000         0         0         0
         0    1.0000         0         0
         0         0   -0.8709   -0.4914
         0         0   -0.4914    0.8709
Ak =
   -3.3166   -3.0151   -2.1106
    0.0000   -1.7056   -2.1320
   -0.0000    0.0000    1.4142
         0    0.0000    0.0000
 
 
Die QR-Zerlegung mit Householder
--------------------------------
A =
     1     2     3
     0     0     0
     1     2     1
     3     2     1
Q =
   -0.3015   -0.6396    0.7071    0.0000
         0         0    0.0000    1.0000
   -0.3015   -0.6396   -0.7071    0.0000
   -0.9045    0.4264   -0.0000   -0.0000
R =
   -3.3166   -3.0151   -2.1106
    0.0000   -1.7056   -2.1320
   -0.0000    0.0000    1.4142
         0    0.0000    0.0000

24.06.2011, 19:43

Tom9876

Auf diesen Beitrag antworten »

Ok, hab den Fehler gefunden:
Ich hatte beim 2. Durchgang für sign(x1)=sign(0)=0 eingesetzt,
damit war sign(x1)*||x|| = 0 .

Also nehme ich für den Sonderfall x1=0

u=x+||x||*e1

oder ?

danke,
Thomas

24.06.2011, 19:45

tigerbine

Auf diesen Beitrag antworten »

Also im code sieht das so aus