Pivoting bei QR-Zerlegung

otze

Mein Leute,

ich komme gerade nicht drauf. Vielleicht sollte ich einfach 8h pennen und morgen drauf schauen um mir sofort den m) am Frühstückstisch zu geben. Ich bin gerne bereit, diese Schmach jetzt auf mich zu nehmen

Also, ich habe die RQ-zerlegung implementiert(also umgekehrtes QR weil meine Matrizen Row-Major sind). Die Version ohne Pivoting funktioniert ziemlich gut.

Der Algorithmus ist auch nicht mehr als:

//berechnet A = RQ
R<-A
Q<-I
for i = 1,...n
  Berechne Householderreflektion H so dass H*row(R,i)=(c,0,...,0)
  R<-R*H
  Q<-H*Q

Nun wollte ich Pivoting einbauen. So wie ich das verstanden habe, ist das dann eine Zerlegung P*A=RQ wobei P eine Permutationsmatrix ist.

In meinem Algorithmus ist die Anpassung momentan nicht mehr als:

P<-I
for i = 1,...n
  k<-Pivot(R,i)
  swap(row(R,i),row(R,k))
  swap(row(P,i),row(P,k))
  Berechne Householderreflektion H so dass H*row(R,i)=(c,0,...,0)
  R<-R*H
  Q<-H*Q

Nur funktioniert das so überhaupt nicht.
Ich dachte zuerst, ich würde die Rekonstruktion falsch erzeugen - und das kann sicherlich auch sein - aber in meinen Testmatrizen sehen die Ergebnisse nicht so aus, dass ich glaube, sie mit einer Permutation wieder in den Griff zu kriegen:

Eingabe:
(
  (1.1008,0.35008,0.343653,-0.746309),
  (0.35008,0.373544,-0.062034,-0.186705),
  (0.343653,-0.062034,0.66776,-0.703222),
  (-0.746309,-0.186705,-0.703222,0.941805)
)
Rekonstruktion Q*R nach 2 Schritten des Algorithmus und 1 Permutation von Zeile 2+4:

(
  (1.1008,0.35008,0.343653,-0.746309),
  (0.604414,0.242857,-0.281547,0.0260547),
  (0.343653,-0.062034,0.66776,-0.703222),
  (-1.00064,-0.0560171,-0.483709,0.729046)
)

Zeile 1 +3 sind korrekt - sie wurden auch nicht permutiert. Aber Zeile 2 und 4 haben keinerlei Ähnlichkeit mit der Eingabe. Das Paper das ich hier rum liegen hab schweigt sich leider generell zur Matrix Q aus. Aber ich vermute, dass dort der Fehler passiert.

Irgendjemand nen Tipp?

otze

Hab die Lösung...ahem. Der Hauptfehler war, dass ich versucht habe, in jeder Iteration nur auf der unteren rechten Submatrix von R zu arbeiten...ohne pivoting klappt das toll, mit pivoting werden ein paar Elemente nicht getauscht...oh mann.