QR-Algorithmus,Givens-Rotation Hessenberg Matrizen

Neue Frage »

brunsi Auf diesen Beitrag antworten »
QR-Algorithmus,Givens-Rotation Hessenberg Matrizen
Hallo zusammen,

nun wo mir die Transformation einer symmetrischen -Matrix, auf Hessenberg-Gestalt mittels Householdermatrizen gelungen ist, möchte ich nun die QR-Zerlegung der Hessenberg Matrix vornehmen.

Im Forum habe ich gelesen, dass dies mit Givens-Rotation geschehen soll. Ist dies richtig oder kann man noch einmal Householder-Verfahren darauf anwenden?


Ausgangsmatrix:


Hessenberg-Form der Ausgangsmatrix:


Nun möchte ich die Hessenberg-Form mittels Givens-Rotation QR-zerlegen. dabei soll allerdings die Symmetrie erhalten bleiben.

In wiefern ändert sich der Algorithmus dieses Beispiels?:

http://www.matheboard.de/archive/389900/thread.html

Wäre schön wenn ihr euch dazu äußern könntet. Denn sonst kann ich die Eigenwerte nicht bestimmen.

edit: ich habe folgendes Verständnisproblem:

Sei die matrix A auf Hessenberg-Gestalt, dann bestimme ich mittels Givens-Rotation die erste Orthogonale Matrix
und berechne die Spektralzerlegung

hier wird ein Element in der 1.Spalte unterhalb der Hauptdiagonalen ungleich 0. Somit ist die Hessenberg-Struktut der Matrix nicht mehr erfüllt.
Dann bilde ich und multipliziere von links an das Produkt
[/latex] Q^{T}_{1}*A*Q_{1}[/latex], so dass dieses Element wieder null wird.
Meine Frage nun: Berechne ich die neue orthogonale Matrix aus dem Produkt
oder nur aus der Matrix A?
frank09 Auf diesen Beitrag antworten »

Zitat:
In wiefern ändert sich der Algorithmus dieses Beispiels?:

http://www.matheboard.de/archive/389900/thread.html


Gar nicht: ( sei deine Hessenberg-Matrix)



usw.
Du führst den QR-Algorithmus wie üblich weiter bis du die Schur-Form erreichst.

Zitat:
Meine Frage nun: Berechne ich die neue orthogonale Matrix aus dem Produkt
oder nur aus der Matrix A?


Man kann auch sagen:
brunsi Auf diesen Beitrag antworten »

also ich möchte gerne einmal alle Iterationen hintereinander hier auflisten und gerne ein Feedback über deren Richtigkeit haben. Könnte dies jmd. überprüfen?

Also meine Ausgangsmatrix für die QR-Zerlegung ist die Hessenbergmatrix im ersten Post!!!
Die dezimalzahlen sind mit excel berechnet und einfach bestimmter länge hier zur besseren lesbarkeit abgekappt.

Nun berechne ich die beiden Elemente auf der Hauptdiagonalen, die sich verändern und nenne sie


Für das zu verändernde Element wähle ich die Variable


Damit ergibt sich die erste Givens-Rotationsmatrix(deren Werte sind auf 3 Kommastellen durch Excel gerundet

Die sich so ergebende neue obere Rechtsdreiecksmatrix sei und enthält folgende werte



Die zweite GivensRotationsmatrix wird nun durch folgende Elemente bestimmt:









Ich kann doch hier zunächst die 1. Spalte der Hessenberg-Matrix abarbeiten? Wenn die Elemente sind, so verändert sich die Rechtsdreiekcsmatrix durch Givens-Rotationen nicht?!

Wenn ihr diese Ergebnisse für den 1. QR-Schritt und dort für die ersten beiden Elemente bestätigen könnt, würde ich mich über eine Antwort freuen, um dann die nächsten Schritte posten zu können.

edit: die unitäre Matrix verliert doch im Gegensatz zum Householder-Verfahren ihre symmetrie-eigenschaft?!
frank09 Auf diesen Beitrag antworten »
RE: QR-Algorithmus,Givens-Rotation Hessenberg Matrizen
Die erste Rotationsmatrix scheint in Ordnung zu sein.
Die zweite ist überflüssig, weil es die Einheitsmatrix ist und nichts ändert.
Du hast die erste Spalte mit schon "abgearbeitet" und nur noch das Diagonalelement übrig.
Was mich etwas stört sind die Bezeichnungen etc., weil es sich noch nicht um Rechtsdreiecksmatrizen handelt. Das werden sie erst nach Abschluss aller G-Rotationen des ersten Durchlaufs (alle Elemente unterhalb der Diagonalen müssen null sein.)
brunsi Auf diesen Beitrag antworten »
RE: QR-Algorithmus,Givens-Rotation Hessenberg Matrizen
da hast du Recht, die Bezeichnung ist irreführend, aber für die Excel-Programmierung durchaus sinnvoll, um zu wissen, wo ich die Matrix immer hinspeichere.

nun reduziere ich die zweite Spalte unterhalbd er Hauptdiagonalen:

wähle dafür:




die Neue Givens-Rotationsmatrix lautet:



und folglich ist die modifizierte Matrix :




und nun die Endmatrix=Obere Rechtsdreiecksmatrix für die erste Iteration:



so und nun müsste ich ja multiplizieren: ??

es ist doch für das Endresultat, die Eigenwerte auf der Hauptdiagonalen direkt ablesen zu können unerheblich, ob ich nach jeder GivensRotation die so entstandene unitäre Matrix direkt von rechts an das Produkt heranmultipliziere oder zunächst die komplette unitäre Matrix bilde?
brunsi Auf diesen Beitrag antworten »
RE: QR-Algorithmus,Givens-Rotation Hessenberg Matrizen
die unitäre inverse GesamtGivensRotationsmatrix ist bei mir gleich:



Hast du die Möglichkeit die oigen Hessenberg-Matrix über ein JAVA-Applet laufen zu lassen??

Denn ich weiß langsam nicht mehr, wo dieser Fehler versteckt sein könnte!!
 
 
frank09 Auf diesen Beitrag antworten »

Zitat:
und nun die Endmatrix=Obere Rechtsdreiecksmatrix für die erste Iteration


Endmatrix der ersten und zugleich Anfangsmatrix der zweiten Iteration ist wiederum eine Hessenberg-Matrix, und zwar

Zitat:
so und nun müsste ich ja multiplizieren: ??


Ja, müsstest du, tust du offenbar aber nicht. Um die nächsten G-Rotationen durchzuführen brauchst du die neue H-Matrix , denn nur aus dieser kannst du Rotationswinkel, etc. ablesen. Du musst ja wieder wie beim ersten Durchlauf auf Rechtsdreicksform bringen. Mir ist auch nicht ganz klar, was ist.
Wenn sein soll, also das Produkt aller G-Rotationen, um auf R-Form zu bringen, stimmt die Gleichung nicht.
Es gilt:



Du erhälst dann eine Folge symmetrischer H_Matrizen, deren Einträge ober- und unterhalb der Diagonalen immer kleiner werden und die gegen eine Diagonalmatrix konvergiert.
Du musst also mit dem Inversen der G-Rotationen die eben entstandene Rechtsdreiecks-M. von rechts multiplizieren.
brunsi Auf diesen Beitrag antworten »

ja genau, soll die Inverse der GivensRotationsmatrizen sein.

Aber Muss ich nach jeder neuen GivensRotationsmatrix sowhol von links als auch dann von Rechts multiplizikeren oder kann ich zunächst wie oben dargestellt die Rechtsdreiecksmatrix (die hoffentlich richtig ist??) zunächst bestimmen und anschließend mit der inversen gesamtunitärmatrix, die die inversen einzelnen Givensrotationen beinhaltet, multiplizieren??

edit: ergibt denn die obere Rechtsdreiecksmatrix multipliziert mit der inversen Gesamtgivensmatrix von rechts genau wieder eine Hessenberg-Matrix oder gibt es eine nicht symmetrische Matrix,deren Elemente alle von null verschieden sind???

Hast du rein zufällig ein Beispiel für eine Transformation einer symmetrischen Matrix auf Hessenberg.Form und anschließend mittels Givesn-Rotation auf Diagonalmatrix??

EIn einfaches Beispiel würde mir schon ausreichen.
Könnte ich dir ggf. auch einmal meine Excel-VBA-Programmierung senden??
frank09 Auf diesen Beitrag antworten »

Da du die Hessenberg-Form und die erste Rechtsdreiecks-Matrix schon hergeleitet hast, mache ich einfach mal da weiter:



Nun bilde ich für den nächsten Durchlauf :

Wieder mit G-Rotationen zerlegt:

Nächste Hessenbergmatrix bilden:
und so weiter:


Es ist nicht möglich zu bilden ohne voher die entsprechende Hessenbergmatrix durch Inversmultiplikation zu erzeugen.
brunsi Auf diesen Beitrag antworten »

Danke dir vielmals.

aber einen kleinen Kniff habe ich freitag noch gefunden, ich weiß allerdings nicht, ob er matehmatisch korrekt ist.

es erhalte allerdings auch die gleichen eigenwerte:

also zunächst habe ich ja die Matrix erzeugt und habe jeweils die aktuelle Givensrotationsmatrix invertiert und mit den vorangegangenen multipliziert. das Gesamtprodukt der invertierten Givensrotationsmatrizen habe ich dann zum Schluss mit der Matrix multipliziert.

Wenn es gewünscht ist, so bin ich gerne bereit, das Tool jmd. zuzusenden, der es hier hereinstellt.

Eine universelle Nutzung ist nicht möglich, sondern nur bis zu einer nxn=13x13 Matrix. Anpassen müsste ich es dann noch, falls jmd höhere Matrizen nehmen möchte?!

So ich eröffne nun noch einen neuen Beitrag zur Bestimmung der Faktorrenditen, die in Marktrenditen enthalten sind und aus denen man mittels Eigenwertbestimmung die Faktorrenditen ableiten soll.


vielen dank schon einmal hierfür frank09
brunsi Auf diesen Beitrag antworten »

achso eine Frage hätte ich allerdings vorerst noch:

ich suche jetzt die zu den Eigenwerten gehörenden Eigenvektoren. Diese Löse ich über die Gleichung:

Normalerweise wird dies über die Bestimmung des charakteristischen Polynoms gemacht, nur bei höheren Matrizen größer 3 ist das nicht mehr möglich so (Satz von Schur).

Als Nebenprodukt wurden bei einer symmetrischen Matrix mittels Householder-Transformation und Givens-Rotation die Diagonalform erstellt.

http://itp.tugraz.at/LV/sormann/NumPhysi...um/kapitel7.pdf

Aus obigem Link wird deutlich, dass die unitäre Matrix die Einheitsvektoren zu den Eigenwerten enthält.

Meine Frage: Ist die unitäre Matrix lediglich durch die Givens-Rotationsmatrizen definiert oder gehören auch noch die Householder-Matrizen dazu??

Ist für mich wichtig, um das Speicherproblem zu minimieren.
frank09 Auf diesen Beitrag antworten »


Sei nun



dann gilt für große n annähernd:

für symmetrische Matrizen

Du kannst in die Eigenvektoren für ablesen. Nimmst du die Householder-Spiegelungen dazu:



findest du in die EVs von .
brunsi Auf diesen Beitrag antworten »

ok, vielen dank. werde morgen noch einmal die lösung zu den eigenvektoren posten.
brunsi Auf diesen Beitrag antworten »

So nun einmal meine Lösung zur unitären Gesamtmatrix (Householedrmatrizen und GivensRotationsmatrizen zusammengefasst)




ist das denn so richtig??
frank09 Auf diesen Beitrag antworten »

Zeilen von sind annähernd EVs von A. Wenn du es noch genauer möchtest, einfach Zahl der Iterationen erhöhen.
brunsi Auf diesen Beitrag antworten »

Guten Morgen,

die Anzahl der Iterationen ist auf 100 gesetzt für die Givens-Rotationen. Ich könnte die Konvergenzgeschwindigkeit allerdings noch erhöhen indem ich einen Shift einbaue. ist dieses überhaupt sinnvoll?


Ich benötige die Eigenvektoren nämlich nur, um mir für ein ökonometrisches Modell die Faktorrenditen zurecht zu basteln.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »