Das QR-Verfahren für unsymmetrische Matrizen

• Um alle Eigenwerte (auch komplexe) und Eigenvektoren einer unsymmetrischen reellen Matrix A zu bestimmen, benutzt man meistens das QR-Verfahren .
• Das Verfahren ist interpretierbar als eine Wielandt-Iteration unter Verwendung eines variablen Shifts mu, kombiniert mit der Schurschen Transformation, die im Falle, dass mu ein exakter Eigenwert ist, die Matrix auf eine zerfallende Form transformiert, sodass man die übrigen Eigenwerte aus einem Problem reduzierter Dimension finden kann. In dieser neuen Matrix tritt der soeben bestimmte Eigenwert nicht mehr auf. Dieser Vorgang wiederholt sich, bis alle Eigenwerte bestimmt sind. Hier wird die Matrix zuerst auf obere Hessenbergform transformiert, sodass die Konvergenz am letzten Subdiagonalelement ablesbar ist. (Wenn die Hessenbergform bereits zerfällt werden die nichtzerfallenden Submatrizen separat abgearbeitet)
• Formal kann man das Verfahren beschreiben wie folgt:
  A_k-mu_kI = Q_kR_k
  A_k+1 = R_kQ_k+mu_kI
  
• Die Konvergenz ist im allgemeinen quadratisch. Wenn es keine schnelle Reduktion des letzten Subdiagonalelements gibt, was z.B. bei mehreren betragsgleichen Eigenwerten und mu=0 immer der Fall ist, wird diese Situation durch einen "Ausnahmeshift" durchbrochen.

Die Eingaben

• Es gibt hier mehrere Möglichkeiten, die Matrix A zu wählen:
  1. Eine unsymmetrische 4x4 Matrix mit den Eigenwerten 1, 2, 3, 4.
  2. Eine unsymmetrische 4x4 Matrix mit den Eigenwerten 1+/-5i, 2, 12.
  3. Eine unsymmetrische 6x6 Matrix mit den Eigenwerten 1, 1, 2+/-i, 3, 3. Diese Matrix ist nicht diagonalisierbar.
  4. Eine Matrix A, die aus der Eingabe von n komplexen Eigenwerten erzeugt wird, mit einer fest vorgegebenen Eigenvektormatrix. Die Eigenwerte sind als Paare (x,y) für x+iy einzugeben. Falls ein Eigenwert mit Imaginärteil ungleich 0 auftritt, dann muss der entsprechende konjugierte Eigenwert gleich als nächstes eingetragen werden.
  5. Eine eigene (un)symmetrische Matrix A. Die Eingabe der Elemente erfolgt zeilenweise und durch Kommata bzw. Leerzeichen getrennt.
• Die Dimension n der Matrix falls der Fall 4,5 gewählt wurde. Wichtig: 2 <= n <= 30 !
• Ausgabe der Matrix A, falls dies gewünscht ist.
• Ausgabe der approximierten Eigenvektormatrix, falls dies gewünscht ist.

Die Ausgaben

• Ausgegeben wird die Matrix A, falls dies gewünscht wurde.
• Die approximativen Eigenwerte, falls kein Programmabbbruch aufgetreten ist, und die Abweichung zu den echten Eigenwerten, falls diese bekannt ist (also im Fall der vorgegebenen Eigenwerte).
• Die approximative Eigenvektormatrix, falls dies gewünscht wird und kein Programmabbbruch aufgetreten ist.
• Ein kurzes Iterationsprotokoll, das die Anzahl der Iterationen bis zur Berechnung eines Eigenwertes angibt.

Fragen ?!

• Wie hängt die Konvergenz von der Eigenwertverteilung ab ?
• Wie ändern sich Eigenwerte und Eigenvektoren, wenn man die Matrix abändert ?

Das Eingabeformular

Zurück: Eigenwertprobleme