Eigenwertproblem durch QR-Zerlegung lösen

Neue Frage »

SchrödingersKatze Auf diesen Beitrag antworten »
Eigenwertproblem durch QR-Zerlegung lösen
Meine Frage:
Hallo liebe Mathematiker,
ich bin gerade dabei ein Programm mit C++ zu schreiben das die Eigenwerte einer beliebigen Quadratischen Matrix berechnet.
Als ansatz dafür hab ich den QR-Algorithmus gewählt. Die QR-Zerlegung mittels Householdertransformation funktioniert soweit auch einwandfrei. Nur bei den ausgegeben Eigenwerten hakt es dann bei einigen Matritzen. z.B. bei der Matrix
3 1
4 -3
Da gibt mein Programm als Eigenwerte 3 und -3 bzw. 1,56 und -1,56 aus (je nachdem ob es eine gerade oder ungerade anzahl von Iterationen gab)
(Eigenwerte sollten laut WolframAlpha -3,6055 und 3,6055 sein)

So wie ich das sehe ist das Problem dabei dass aus A2 wieder die Ursprüngliche Matrix A0 wird und es somit unabhängig von der anzahl der Iterationen nur zwischen den beiden werten hin und her springt.
Also:
A0=Q0*R0
A1=R0*Q0=Q1*R1
A2=R1*Q1=Q2*R2=A0



Meine Ideen:
Als Lösung hab ich mir überlegt das ich einfach einen einfachen shift implementiere was zumindest per Hand schon nach einer Iteration weitaus bessere Ergebnisse liefert.
Allerdings ist meine Frage ob das diese problem wirklich verhindert oder ob es einfach nur genauere aber ebenfalls nicht ganz korrekte Ergebnisse liefert.
Ausserdem würde mich sehr interessieren Warum es ohne shift so gar nicht funktioniert?! sollte es doch eigentlich nach genügend Iterationen?

Achja und noch eine frage hätt ich bei größeren Matrizen also z.B. 5x5 hab ich dann 5 "Eigenwerte" in der Diagonale stehen wovon aber nicht alles tatsächliche sind. woher weiß ich was davon die Eigenwerte sind und was nicht?!

Wär schön wenn von euch jemand ein paar ideen dazu hätte smile
Captain Kirk Auf diesen Beitrag antworten »

Hallo,

es gibt etliche Varianten des QR-Algorithmus:
de.wikipedia.org/wiki/QR-Algorithmus

es ist vollkommen unklar welche du verwendest.

Und wenn eine Implementierung eines Algorithmus falsche Werte liefert ist entweder der Algorithmus falsch oder die Implentierung.
Woran's liegt ist hier ohne Glaskugel nicht auszumachen.
SchrödingersKatze Auf diesen Beitrag antworten »
Eigenwertproblem durch QR-Zerlegung lösen
Hallo
Sorry für die unzureichenden Informationen. Also ich versuch mal meinen aufbau besser zu beschreiben.
QR-Zerlegung durch Housholdertransformation der Matrix A
H1=E-(2/(v1T*v1)*v1*v1T) ( E=Einheitsmatrix )
v1[n]=A[n][0]+Signum(A[0][0])*a*e1 (a=||v|| / e1=1. Basisvektor)

A2=H1*A
H2=E-(2/(v2T*v2)*v2*v2T)
v2[n]=A[n][1]+Signum(A[1][1])*a*e2 (Wobei A[0][1] zuvor 0 gesetzt wurde)

A3=H2*A2
.
.
.
Q=H1*H2*H3....
R=QT*A
A=Q*R

und für die Eigenwerte wird dann eben ein neues A aus R*Q gewonnen und diese neue A wieder QR-zerlegt usw.

hilft das was? :/
Captain Kirk Auf diesen Beitrag antworten »

Zitat:
Also ich versuch mal meinen aufbau besser zu beschreiben.

Ganz ehrlich: Das ist ein Formelwust, keine Beschreibung.
Eine Beschreibung verwendet Worte.

Die verwendest extrem viele Buchstaben deren Bedeutung nicht erklärt wird.
(die, die du erklärst sind ungünstigerweise diejenigen die halbwegs klar sind, da übliche Bezeichnungen)
Ich vermute A ist die ursprüngliche Matrix, H1 eine Householdermatrix;
Was ist v1 was ist T ? Wie wählst du die?
Was soll der Opertor(?) [.] bedeuten?

Zitat:
und für die Eigenwerte wird dann eben ein neues A aus R*Q gewonnen und diese neue A wieder QR-zerlegt usw.

Und wie kriegst du die Eigenwerte aus der Matrix?
SchrödingersKatze Auf diesen Beitrag antworten »

Also hier z.b. Werte einer Matrix die Probleme macht:
A=
Q=
R=

A1=R*Q=


Q1=
R1=

A2=Q1*R1=


und da is dann das problem denn A2=A und damit dreht sich das dann im kreis...
SchrödingersKatze Auf diesen Beitrag antworten »

Ich entschuldige mich für meine undeutlichen Ausführungen Hammer
Also das A ist wie du richtig vermutet hast die Ursprungsmatrix und H1 eine Housholdermatrix.
v1 ist die erste Spalte der Matrix + Das Vorzeichen des ersten Elements Multipliziert mit der Norm der ersten Spalte Multipliziert mit dem ersten Basisvektor.
Das T steht jeweils für eine Transponierte Matrix/Vektor.
die Eckigen klammern sind für den index Also A[0][0] ist das erste element der Matrix links oben A[n][n] das letzte rechts unten


Die eigenwerte Sollten bei der dadurch erhaltenen Matrix in der Hauptdiagonale stehen da sie durch das oftmalige wiederholen ja gegen eine obere Dreiecksmatrix konvergiert
 
 
SchrödingersKatze Auf diesen Beitrag antworten »

Also bei der Matrix Funktioniert es z.B. einwandfrei:


A=
Q=
R=

A1=R*Q=


Q1=
R1=

A2=R1*Q1=

Q2=
R2=

A3=R2*Q2=


Hier sieht man das A3 schon nahe an den eigenwerten 5 und 1 liegt

bei A11 steht dann schließlich 5 und 1 in der Hauptdiagonale und darunter eine 0
Captain Kirk Auf diesen Beitrag antworten »

Problem 1:
Zitat:
(ich hab mir mal die Freiheit genommen Indezes zu verwenden)
rechts addierst du eine Zahl und einen Vektor. Das geht nicht. Da würde sich auch C++ beschweren.

Frage 2:
Wozu berechnest du die ?
Die kommen danach nie wieder vor.

Problem 3:
Zitat:


Wozu das denn?
Beschreibt du damit also schlicht die QR-Zerlegung?
Und wie itierierst du dann weiter?

Problem 4:
Dein Beispiel ist eine kompkett andere Rechnung.
Wie berechnest du denn ? (Ich hab irgendwie den Verdacht, dass du es gar nicht berechnest.)
SchrödingersKatze Auf diesen Beitrag antworten »

Also zu Problem 1:
Das geht sehr wohl da ich einen Vektor zu einem Vektor Addiere, da e1 der erste Basisvektor ist und ein Skalar mit einem Vektor Multipliziert einen Vektor ergibt.

Zu Frage 2:
Das Ai wird das neue A.
Also es wird für das A eine QR-Zerlegung durchgeführt. Dann aus R*Q ein neues A berechnet für welches dann wieder eine QR-Zerlegung durchgeführt wird und so weiter

Zu Problem 3:
Ja im prinzip beschreibt es nicht mehr als die QR-Zerlegung das Ursprüngliche A ist eben Q*R und das neue A mit dem die Prozedur dann von vorne beginnt ist R*Q

Zu 4:
Die Beispiele sind die Werte die mein Programm für die eingegebene Matrix ausgibt also auch berechnet, die zwischenschritte wurden ausgelassen da es sonst sehr lang werden würde.
aber hier mal explizit ein zwischenschritt.

A=
v1= kommt aus +5* wobei 5 die Norm der ersten Spalte ist
vT*v=80
v*vT=
H bzw. in diesem Fall auch Q ist dann: -(1/40)*=Q=

so kommts zum wert von Q und in weiterer folge von R und Ai die das Programm auch ganz gut berechnet...
Captain Kirk Auf diesen Beitrag antworten »

Zitat:
as geht sehr wohl da ich einen Vektor zu einem Vektor Addiere, da e1 der erste Basisvektor ist und ein Skalar mit einem Vektor Multipliziert einen Vektor ergibt.

Nein tut es nicht. Was du schreibst ist nicht das Problem.
Zum Einen ist nach deiner Auskunft A[n][0] das was man normalerweise schreibt, ein Eintrag der Matrix, einer Zahl. Und dazu addierst du nach dem was du hier selbst schreibst einen Vektor.
Und rauskommen soll v1[n], das ist eine Zahl.
Das funktioniert nicht.

Und wie ich jetzt in deinem Beispiel sehe verwendest du gar nicht die Zahl(!) A[n][0] sondern den Vektor (!)A[0] aka. die erste Spalte von A..



Zitat:
Zu Frage 2:
Das Ai wird das neue A.
Also es wird für das A eine QR-Zerlegung durchgeführt. Dann aus R*Q ein neues A berechnet für welches dann wieder eine QR-Zerlegung durchgeführt wird und so weiter



D.h. also dein Algorithmus ist.

Set
For i=1 to ?
Calculate Q,R als QR-Zerlegung von
Set


Zitat:
so kommts zum wert von Q

Das ist nachvollziehbar.
Erklärt aber nicht den Wert von .
Da bekomm ich mit dem Verfahren z.B. als rechten unteren Eintrag 1.28 raus.
SchrödingersKatze Auf diesen Beitrag antworten »

Okey es liegt schon wieder ein misserverständinss vor,
ich bin anscheinend schlecht darin mich auszudrücken... Hammer

Also mit A[n][0] war die erste Spalte der Matrix gemeint Also A[0][0], A[1][0], A[2][0],........,A[n][0]
Also vektor+vektor

der Algorithmus ist aber

1 A wird vom Programm eingelesen
2 for int i=0 to (gewünschte anzahl der Iterationen)
3 Calculate Q,R als QR-Zerlegung von
4 Set
5 End for

wobei das in zeile drei eine von mir programierte Funktion ist, die die QR-Zerlegung für die Matrix, mit der die Funktion aufgerufen wurde, Berechnet und dann Q und R zurück gibt.

Dan wird dass A neu Definiert und die Funktion mit neuem A erneut aufgerufen. dann gibt sie eben Q1 und R1 zurück
Captain Kirk Auf diesen Beitrag antworten »

Zitat:
der Algorithmus ist aber

In wie fern unterscheidet sich dein Pseudo-Code von meinem?
Ich seh da keinen wesentlichen Unterschied, der ein "aber" rechtfertigen würde.

Und den casus knaxus ignorierst du scheinbar weiterhin:

Berechne bitte per Hand das für den ersten Beispielfall und vergleiche mit dem was dein Programm ausspuckt.
SchrödingersKatze Auf diesen Beitrag antworten »

Du hast recht es ist eigentlich kaum ein unterschied am Pseudocode ausser das A mit dem nächsten Ai überschrieben wird...

so nun zum Q1 Ich komme wenn ich es mit der Hand rechne auf genau die selben Werte wie das Programm (siehe Bildund 5. post)
Ich hoffe du hast das beispiel aus dem 5. post gemeint?!


[attach]39118[/attach]
Captain Kirk Auf diesen Beitrag antworten »

Ich hätte jetzt ehrlich gesagt in der dritten Zeile ein -, kein + erwartet.

Abgesehen davon: Hast mal bei der beschreibung der Algorithmen - wo auch immer du die her hast - geschaut wann das Verfahren eigentlich konvergiert?
Finden sich z.B in diesem Skript:
math.umn.edu/~olver/aims_/qr.pdf
Deine Matrix erfüllt sie nicht.
Neue Frage »
Antworten »



Verwandte Themen

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