Householder

15.02.2011, 12:08

Manni2011

Householder

Meine Frage:
Von der LR-Zerlegung kenne ich es, dass man evtl. Pivoting durchführen muss.

Wie ist das bei der QR-Zerlegung via Householder?

Wenn ich z.B. folgende Matrix mittels Householder zerlegen soll:

$\begin{eqnarray*} \begin{pmatrix} 0 & 4 \\ 8 & -5 \\ -6 & 0 \end{pmatrix} \end{eqnarray*}$

Muss ich da jetzt irgendwas tauschen?

Meine Ideen:
Ich könnte mir vorstellen, dass dem so ist...

15.02.2011, 12:32

Math1986

Auf diesen Beitrag antworten »

RE: Householder
Bei der Householder-Zerlegung hast du keine Pivotierung, wie denn auch?
Es werden bei diesem Verfahren ja generell keine Umformungen durchgeführt, sondern es werden Spiegelungsmatrizen erzeugt..

Rechme mal vor wie du das rechnen würdest

15.02.2011, 12:36

Manni2011

Auf diesen Beitrag antworten »

RE: Householder
Bevor ich rechne:

Das heißt, ich kann jetzt einfach damit beginnen die erste Spalte zu eliminieren?

Da habe ich aber das Problem, dass ich ja schauen muss, ob der erste Eintrag größer oder kleiner 0 ist: Hier ist er aber gleich 0.

Welches Vorzeichen wählt man dann?

15.02.2011, 14:58

tigerbine

Auf diesen Beitrag antworten »

RE: Householder
Man setzt sign(0)=1. Das liefert:

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:

>> 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: [0,4;8,-5;-6,0]
A0 =
     0     4
     8    -5
    -6     0
 
Durchgang 1 
================
x =
     0
     8
    -6
e1 =
     1
     0
     0
u =
    10
     8
    -6
beta =
    0.0100
 
H =
         0   -0.8000    0.6000
   -0.8000    0.3600    0.4800
    0.6000    0.4800    0.6400
Qk =
         0   -0.8000    0.6000
   -0.8000    0.3600    0.4800
    0.6000    0.4800    0.6400
Ak =
   -10     4
     0    -5
     0     0
 
Durchgang 2 
================
x =
    -5
     0
signx =
    -1
e1 =
     1
     0
u =
   -10
     0
beta =
    0.0200
 
H =
    -1     0
     0     1
Qk =
     1     0     0
     0    -1     0
     0     0     1
Ak =
   -10     4
     0     5
     0     0
 
 
Die QR-Zerlegung mit Householder
--------------------------------
A =
     0     4
     8    -5
    -6     0
Q =
         0    0.8000    0.6000
   -0.8000   -0.3600    0.4800
    0.6000   -0.4800    0.6400
R =
   -10     4
     0     5
     0     0

15.02.2011, 15:53

Gast11022013

Auf diesen Beitrag antworten »

RE: Householder
Ich habe die Frage zwar nicht gestellt, aber trotzdem vielen Dank für die Antwort, diese Frage hatte ich mir nämlich auch schon mehrmals gestellt.
Nun weiß ich, dass man nicht zu schauen braucht, ob da jeweils eine Null oder eine andere Zahl in der jeweiligen gerade auszuräumenden Spalte steht.

Dennoch scheint der Begriff des Spaltentauschs nicht ganz irrelevant bei der Householder-Zerlegung zu sein, denn ich habe in manchen Erklärungen zur Householder-Zerlegung Folgendes gelesen:

"Eine $\begin{eqnarray*} m\times n \end{eqnarray*}$ -Matrix kann, gegebenenfalls nach einer Permutation der Spalten, als Produkt einer orthogonalen Matrix Q und einer oberen Dreiecksmatrix Rfaktorisiert werden."

Zum Beispiel hier: Seite 7/15:
http://www.mathematik.uni-stuttgart.de/s..._v3_handout.pdf

Und dann habe ich noch gelesen, dass in diesem Fall, weil ja eine Nullzeile bei der Prozedur entsteht, weil sich's um keine quadratische Matrix handelt, manchmal die Spalte mit der größten 2-Norm permutiert wird.

Also, ich hoffe ich stifte damit keine Verwirrung, aber vielleicht hast Du ja Ahnung davon, denn irgendwie scheint der Begriff der Permutation doch bei der Householder-Zerlegung eine (untergeordnete?) Rolle zu spielen.
Ich selbst hatte nie Beispiele, die diese Fragen erfordert hätten und auch für meine Klausur erhoffe ich mir eine schöne klassische Rechenaufgabe zum Thema Householder, aber wissenswert ist es ja vielleicht trotzdem!

Danke für das Durchlesen.

15.02.2011, 16:03

tigerbine

Auf diesen Beitrag antworten »

RE: Householder
Es ist hier wohl eine Konvention:

http://www.math.ubbcluj.ro/~tradu/nlalgs...HouseGivens.pdf Seite 7

Vielleicht trifft man die in dem anderen Paper nicht, und permutiert daher? Ferner scheint es auch um die Minimierung des Fehlers dort zu gehen, wie pivotisiert wird. Aber genau kann ich das nun nicht sagen. Da bin ich aktuell nicht genug drin. Tut mir Leid.

15.02.2011, 16:07

Gast11022013

Auf diesen Beitrag antworten »

RE: Householder
Nunja, ich hoffe einfach mal, dass ich dieses Wissen nicht benötige.

Eine Frage noch: Warum sind in dem Beispiel oben 2 Schritte nötig? Nach dem ersten Schritt hat man doch eigentlich schon die gewünschte Form, denn bei einer 3 x 2 - Matrix müsste es doch eigentlich 3-2=1 Nullzeile geben und ansonsten muss eine obere Dreiecksmatrix vorliegen, das ist doch der Fall.

15.02.2011, 16:10

tigerbine

Auf diesen Beitrag antworten »

RE: Householder
Weil der Algorithmus durchläuft (2 Spalten) und ich nicht nach jedem Schritt eine Gestaltabfrage gemacht habe. Augenzwinkern