QR-Zerlegung mittels HH-Transformation

30.04.2010, 18:31

ThTs

QR-Zerlegung mittels HH-Transformation

Ich rechne für eine baldige Numerik-Prüfung gerade alte Klausuraufgaben durch. Bei der QR-Zerlegung versage ich noch etwas. Eventuell liegt es nur daran, dass ich der hohen Verlockung für Folgefehler zum Opfer falle, vielleicht hab ich aber auch einen richtigen Denkfehler dabei.

Hier mal die konkrete Aufgabe und meine Rechenweise:

$\begin{eqnarray*} A=\begin{pmatrix} -10 & -16 & 29 \\ 11 & -7 & 14 \\ 2 & 2 & 4,25 \end{pmatrix} \end{eqnarray*}$

1. Schritt

$\begin{eqnarray*} v_1 = \begin{pmatrix} -10 \\ 11 \\ 2 \end{pmatrix} \end{eqnarray*}$
$\begin{eqnarray*} ||v_1|| = 15 \end{eqnarray*}$
$\begin{eqnarray*} u_1 = \begin{pmatrix} -10 \\ 11 \\ 2 \end{pmatrix} + 15 \cdot \begin{pmatrix} 1 \\ 0 \\ 0 \end{pmatrix} = \begin{pmatrix} 5 \\ 11 \\ 2 \end{pmatrix} \end{eqnarray*}$
$\begin{eqnarray*} \beta_1 = \frac{2}{||u_1||} = \frac{2}{150} = \frac{1}{75} \end{eqnarray*}$
$\begin{eqnarray*} U_1 = \begin{pmatrix} 5 \\ 11 \\ 2 \end{pmatrix} \cdot \begin{pmatrix} 5 & 11 & 2 \end{pmatrix} = \begin{pmatrix} 25 & 55 & 10 \\ 55 & 121 & 22 \\ 10 & 22 & 4 \end{pmatrix} \end{eqnarray*}$
$\begin{eqnarray*} Q_1 = E_3 - \frac{1}{75} \cdot \begin{pmatrix} 25 & 55 & 10 \\ 55 & 121 & 22 \\ 10 & 22 & 4 \end{pmatrix} = \begin{pmatrix} \frac{2}{3} & -\frac{11}{15} & -\frac{2}{15} \\ -\frac{11}{15} & -\frac{46}{75} & -\frac{22}{75} \\ -\frac{2}{15} & -\frac{22}{75} & \frac{71}{75} \end{pmatrix} \end{eqnarray*}$
$\begin{eqnarray*} R_1 = Q_1 \cdot A = \begin{pmatrix} -15 & -9 & -30,1667 \\ 0 & 8,4 & 11,4333 \\ 0 & 28,8 & 3,7833 \end{pmatrix} \end{eqnarray*}$

2. Schritt:

$\begin{eqnarray*} v_2 = \begin{pmatrix} 0 \\ 8,4 \\ 11,4333 \end{pmatrix} \end{eqnarray*}$
$\begin{eqnarray*} ||v_2|| = 14,1873 \end{eqnarray*}$
$\begin{eqnarray*} u_2 = \begin{pmatrix} 0 \\ 8,4 \\ 11,4333 \end{pmatrix} + 14,1873 \cdot \begin{pmatrix} 0 \\ 1 \\ 0 \end{pmatrix} = \begin{pmatrix} 0 \\ 22,5873 \\ 11,4333 \end{pmatrix} \end{eqnarray*}$
$\begin{eqnarray*} \beta_2 = \frac{2}{||u_2||} = \frac{2}{25,3163} = 0,0790 \end{eqnarray*}$
$\begin{eqnarray*} U_2 = \begin{pmatrix} 0 \\ 22,5873 \\ 11,4333 \end{pmatrix} \cdot \begin{pmatrix} 0 & 22,5873 & 11,4333 \end{pmatrix} = \begin{pmatrix} 0 & 0 & 0 \\ 0 & 510,1861 & 258.2474 \\ 0 & 258,2474 & 130,7203 \end{pmatrix} \end{eqnarray*}$
$\begin{eqnarray*} Q_2 = E_3 - 0,0790 \cdot \begin{pmatrix} 0 & 0 & 0 \\ 0 & 510,1861 & 258.2474 \\ 0 & 258,2474 & 130,7203 \end{pmatrix} = \begin{pmatrix} 1 & 0 & 0 \\ 0 & -39,3047 & -20,4015 \\ 0 & -20,4015 & -9,327 \end{pmatrix} \end{eqnarray*}$

$\begin{eqnarray*} R_2 \end{eqnarray*}$ ergibt dann kein vernünftiges Ergebnis mehr.
Mein Taschenrechner (TI-89 Titanium) gibt während dessen ein Ergebnis für die QR-Zerlegung aus, dass mich denken lässt, das oben dann doch ein bischen mehr falsch ist, einfach schon, weil die Zahlen "hübscher" sind. Leider gibt er mir dabei keine Zwischenwerte aus, sondern nur Q und R. Hier die Ergebnisse meines Taschenrechners:

$\begin{eqnarray*} R = \begin{pmatrix} 15 & 9 & -\frac{17}{2} \\ 0 & 30 & -\frac{25}{2} \\ 0 & 0 & \frac{115}{4} \end{pmatrix} \end{eqnarray*}$
$\begin{eqnarray*} Q = \begin{pmatrix} -\frac{2}{3} & -\frac{1}{3} & \frac{2}{3} \\ \frac{11}{15} & -\frac{34}{75} & \frac{38}{75} \\ \frac{2}{15} & \frac{62}{75} & \frac{41}{75} \end{pmatrix} \end{eqnarray*}$

Kann das jemand nachvollziehen und mir eventuell sagen, was ich oben falsch gemacht habe?

30.04.2010, 19:20

tigerbine

Auf diesen Beitrag antworten »

RE: QR-Zerlegung mittels HH-Transformation
Hallo,

zum Nachrechnen habe ich leider keine Zeit. Vielleicht findest du so selbst deinen Fehler. Wink

Theorie:

[WS] Lineare Ausgleichprobleme und ff.

Programm:
[WS] - Programmsammlung Numerik

Lösung mir Rechenschritten:

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:
135:
136:
137:
138:
139:
140:
141:
142:
143:
144:
145:
146:
147:
148:
149:
150:
151:
152:
153:
154:
155:
156:
157:
158:
159:
160:
161:
162:
163:
164:
165:
166:
167:
168:
169:
170:
171:
172:
173:
174:
175:
176:
177:
178:
179:
180:
181:
182:
183:
184:
185:
186:
187:
188:
189:
190:
191:
192:
193:
194:
195:
196:
197:
198:
199:
200:
201:
202:
203:
204:
205:
206:
207:
208:
209:
210:
211:
212:
213:
214:
215:
216:
217:
218:
219:
220:
221:
222:
223:
224:

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: [-10,-16,29;11,-7,14;2,2,4.25]

A0 =

  Columns 1 through 2 

 -10.00000000000000 -16.00000000000000
  11.00000000000000  -7.00000000000000
   2.00000000000000   2.00000000000000

  Column 3 

  29.00000000000000
  14.00000000000000
   4.25000000000000

 
Durchgang 1 
================

x =

   -10
    11
     2


signx =

    -1


e1 =

     1
     0
     0


u =

   -25
    11
     2


beta =

   0.00266666666667

 

H =

  Columns 1 through 2 

  -0.66666666666667   0.73333333333333
   0.73333333333333   0.67733333333333
   0.13333333333333  -0.05866666666667

  Column 3 

   0.13333333333333
  -0.05866666666667
   0.98933333333333


Qk =

  Columns 1 through 2 

  -0.66666666666667   0.73333333333333
   0.73333333333333   0.67733333333333
   0.13333333333333  -0.05866666666667

  Column 3 

   0.13333333333333
  -0.05866666666667
   0.98933333333333


Ak =

  Columns 1 through 2 

  15.00000000000000   5.80000000000000
   0.00000000000000 -16.59200000000000
                  0   0.25600000000000

  Column 3 

  -8.50000000000000
  30.50000000000000
   7.25000000000000

 
Durchgang 2 
================

x =

 -16.59200000000000
   0.25600000000000


signx =

    -1


e1 =

     1
     0


u =

 -33.18597481015323
   0.25600000000000


beta =

   0.00181591281844

 

H =

  -0.99988099233753   0.01542728628486
   0.01542728628486   0.99988099233753


Qk =

  Columns 1 through 2 

   1.00000000000000                  0
                  0  -0.99988099233753
                  0   0.01542728628486

  Column 3 

                  0
   0.01542728628486
   0.99988099233753


Ak =

  Columns 1 through 2 

  15.00000000000000   5.80000000000000
  -0.00000000000000  16.59397481015323
   0.00000000000000  -0.00000000000000

  Column 3 

  -8.50000000000000
 -30.38452244072944
   7.71966942613535

 
 
Die QR-Zerlegung mit Householder
--------------------------------

A =

  Columns 1 through 2 

 -10.00000000000000 -16.00000000000000
  11.00000000000000  -7.00000000000000
   2.00000000000000   2.00000000000000

  Column 3 

  29.00000000000000
  14.00000000000000
   4.25000000000000


Q =

  Columns 1 through 2 

  -0.66666666666667  -0.73118908954287
   0.73333333333333  -0.67815779293867
   0.13333333333333   0.07392241344829

  Column 3 

   0.14463080892057
  -0.04821026964019
   0.98831052762389


R =

  Columns 1 through 2 

  15.00000000000000   5.80000000000000
  -0.00000000000000  16.59397481015323
   0.00000000000000  -0.00000000000000

  Column 3 

  -8.50000000000000
 -30.38452244072944
   7.71966942613535

Lösung durch matlab

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:

[Q,R]=qr(A)

Q =

  Columns 1 through 2 

  -0.66666666666667  -0.73118908954287
   0.73333333333333  -0.67815779293867
   0.13333333333333   0.07392241344829

  Column 3 

   0.14463080892057
  -0.04821026964019
   0.98831052762389


R =

  Columns 1 through 2 

  15.00000000000000   5.80000000000000
                  0  16.59397481015324
                  0                  0

  Column 3 

  -8.50000000000001
 -30.38452244072946
   7.71966942613535

>>

30.04.2010, 21:38

ThTs

Auf diesen Beitrag antworten »

Besten Dank :-) Leider habe ich gerade festgestellt, dass ich mich ganz oben bei der Matrix A vertippt habe. Die sollte eigentlich so aussehen:

$\begin{eqnarray*} A=\begin{pmatrix} -10 & -16 & 29 \\ 11 & -7 & 14 \\ 2 & 26 & 4,25 \end{pmatrix} \end{eqnarray*}$

Ich habe kein matlab, aber habe mir den Quellcode mal angesehen und denke ich weiß wo mein Fehler war. Ich versuche das ganze nochmal Schritt für Schritt anhand des Quellcodes durchzurechnen und hoffe das ich dann auf das Ergebnis meines TI komme :-/

30.04.2010, 21:47

tigerbine

Auf diesen Beitrag antworten »

Bei mir kommt da nicht das Gleiche raus.

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:

Q=[-2/3,-1/3,2/3;11/15,-34/75,38/75; 2/15, 62/75, 41/75]

Q =

  Columns 1 through 2 

  -0.66666666666667  -0.33333333333333
   0.73333333333333  -0.45333333333333
   0.13333333333333   0.82666666666667

  Column 3 

   0.66666666666667
   0.50666666666667
   0.54666666666667

>> R=[15,9,-17/2;0,30,-25/2;0,0,115/4]

R =

  Columns 1 through 2 

  15.00000000000000   9.00000000000000
                  0  30.00000000000000
                  0                  0

  Column 3 

  -8.50000000000000
 -12.50000000000000
  28.75000000000000

>> Q*Q'

ans =

  Columns 1 through 2 

   1.00000000000000   0.00000000000000
   0.00000000000000   1.00000000000000
  -0.00000000000000                  0

  Column 3 

  -0.00000000000000
                  0
   1.00000000000000

>> Q*R

ans =

  Columns 1 through 2 

 -10.00000000000000 -16.00000000000000
  11.00000000000000  -7.00000000000000
   2.00000000000000  26.00000000000000

  Column 3 

  29.00000000000000
  14.00000000000000
   4.25000000000000

>>

30.04.2010, 21:53

ThTs

Auf diesen Beitrag antworten »

Da habe ich wohl den Beitrag direkt darüber zu schnell editiert. Tut mir leid für die Verwirrung.

Ich rechne es jetzt nochmal richtig durch. Wenn ich dann immer noch nicht auf das richtige Ergebnis komme, melde ich mich noch einmal.

30.04.2010, 22:07

tigerbine

Auf diesen Beitrag antworten »

Alles klar.

30.04.2010, 22:43

ThTs

Auf diesen Beitrag antworten »

Der erste Schritt stimmt jetzt, beim zweiten muss ich mich aber irgendwo noch verhaspeln. Kannst du mir bitte noch den Matlab-Rechenweg für die korrigierte Matrix posten?

$\begin{eqnarray*} A=\begin{pmatrix} -10 & -16 & 29 \\ 11 & -7 & 14 \\ 2 & 26 & 4,25 \end{pmatrix} \end{eqnarray*}$

30.04.2010, 22:52

tigerbine

Auf diesen Beitrag antworten »

Wenn du matlab hast, kannst du dir auch QRmitH.m herunterladen.

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:
135:
136:
137:
138:
139:
140:
141:
142:
143:
144:
145:
146:
147:
148:
149:
150:
151:
152:
153:
154:
155:
156:
157:
158:
159:
160:
161:
162:
163:
164:
165:
166:
167:
168:
169:
170:
171:
172:
173:
174:
175:
176:
177:
178:
179:
180:
181:
182:
183:
184:
185:
186:
187:
188:
189:
190:
191:
192:
193:
194:
195:
196:
197:
198:
199:
200:
201:
202:
203:
204:
205:
206:
207:
208:
209:
210:
211:
212:
213:
214:
215:
216:
217:
218:
219:
220:
221:
222:
223:
224:
225:
226:
227:
228:
229:
230:
231:
232:
233:
234:
235:
236:
237:
238:
239:
240:
241:
242:
243:
244:
245:
246:
247:
248:
249:
250:
251:
252:
253:
254:
255:
256:
257:
258:
259:
260:
261:
262:
263:
264:
265:
266:
267:
268:
269:
270:
271:
272:
273:


>> 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: [-10,-16,29;11,-7,14;2,26,4.25]

A0 =

  Columns 1 through 2 

 -10.00000000000000 -16.00000000000000
  11.00000000000000  -7.00000000000000
   2.00000000000000  26.00000000000000

  Column 3 

  29.00000000000000
  14.00000000000000
   4.25000000000000

 
Durchgang 1 
================

x =

   -10
    11
     2


signx =

    -1


e1 =

     1
     0
     0


u =

   -25
    11
     2


beta =

   0.00266666666667

 

H =

  Columns 1 through 2 

  -0.66666666666667   0.73333333333333
   0.73333333333333   0.67733333333333
   0.13333333333333  -0.05866666666667

  Column 3 

   0.13333333333333
  -0.05866666666667
   0.98933333333333


Qk =

  Columns 1 through 2 

  -0.66666666666667   0.73333333333333
   0.73333333333333   0.67733333333333
   0.13333333333333  -0.05866666666667

  Column 3 

   0.13333333333333
  -0.05866666666667
   0.98933333333333


Ak =

  Columns 1 through 2 

  15.00000000000000   9.00000000000000
   0.00000000000000 -18.00000000000000
                  0  24.00000000000000

  Column 3 

  -8.50000000000000
  30.50000000000000
   7.25000000000000

 
Durchgang 2 
================

x =

 -18.00000000000000
  24.00000000000000


signx =

    -1


e1 =

     1
     0


u =

   -48
    24


beta =

    6.944444444444445e-004

 

H =

  -0.60000000000000   0.80000000000000
   0.80000000000000   0.60000000000000


Qk =

  Columns 1 through 2 

   1.00000000000000                  0
                  0  -0.60000000000000
                  0   0.80000000000000

  Column 3 

                  0
   0.80000000000000
   0.60000000000000


Ak =

  Columns 1 through 2 

  15.00000000000000   9.00000000000000
  -0.00000000000000  30.00000000000000
   0.00000000000000                  0

  Column 3 

  -8.50000000000000
 -12.50000000000000
  28.75000000000000

 
 
Die QR-Zerlegung mit Householder
--------------------------------

A =

  Columns 1 through 2 

 -10.00000000000000 -16.00000000000000
  11.00000000000000  -7.00000000000000
   2.00000000000000  26.00000000000000

  Column 3 

  29.00000000000000
  14.00000000000000
   4.25000000000000


Q =

  Columns 1 through 2 

  -0.66666666666667  -0.33333333333333
   0.73333333333333  -0.45333333333333
   0.13333333333333   0.82666666666667

  Column 3 

   0.66666666666667
   0.50666666666667
   0.54666666666667


R =

  Columns 1 through 2 

  15.00000000000000   9.00000000000000
  -0.00000000000000  30.00000000000000
   0.00000000000000                  0

  Column 3 

  -8.50000000000000
 -12.50000000000000
  28.75000000000000

 
Soll noch ein LGS gelöst werden? 0-nein, 1-ja: 0
>> A=[-10,-16,29;11,-7,14;2,26,4.25]

A =

  Columns 1 through 2 

 -10.00000000000000 -16.00000000000000
  11.00000000000000  -7.00000000000000
   2.00000000000000  26.00000000000000

  Column 3 

  29.00000000000000
  14.00000000000000
   4.25000000000000

>> [Q,R]=qr(A)

Q =

  Columns 1 through 2 

  -0.66666666666667  -0.33333333333333
   0.73333333333333  -0.45333333333333
   0.13333333333333   0.82666666666667

  Column 3 

   0.66666666666667
   0.50666666666667
   0.54666666666667


R =

  Columns 1 through 2 

  15.00000000000000   9.00000000000000
                  0  30.00000000000000
                  0                  0

  Column 3 

  -8.50000000000001
 -12.50000000000000
  28.75000000000000

30.04.2010, 23:22

ThTs

Auf diesen Beitrag antworten »

Besten dank, jetzt hat alles gepasst :-)

Matlab hab ich leider nicht. In der Uni läuft auf den Rechnern nur Mathematica, aber damit konnte ich mich nie so richtig anfreunden. Wenn es nötig wurde, habe ich mir Programme dieser Art und Weise meist in Java geschrieben, aber in diesem Fall wäre die Gefahr, dass es in die Hose geht recht groß, wenn ich schon bei der manuellen Rechnung so große Probleme habe.

30.04.2010, 23:28

tigerbine

Auf diesen Beitrag antworten »

Gut, dann: Problem gelöst! Auf zum nächsten Augenzwinkern

Neue Frage »

Antworten »

QR-Zerlegung mittels HH-Transformation

Verwandte Themen