QZ-Algorithmus

numerisches Verfahren zur Lösung des verallgemeinerten Eigenwertproblems

Der QZ-Algorithmus oder die QZ-Faktorisierung ist ein numerisches Verfahren zur Lösung des verallgemeinerten Eigenwertproblems.

, mit bzw.

Das verallgemeinerte Eigenwertproblem ist äquivalent zum Eigenwertproblem , wobei und invertierbar sein muss. Es wird jedoch nicht explizit die Matrix berechnet, um die Kondition des Problems nicht zu verschlechtern, sondern und werden simultan durch Ähnlichkeitstransformationen (Givens-Rotationen und Householder-Spiegelungen) in verallgemeinerte Schurform gebracht.

Gegeben ist ein Matrixbüschel . Gesucht sind orthogonale Matrizen und , so dass von verallgemeinerter Schurform ist, d. h. ist von quasi-oberer Dreiecksform und ist von oberer Dreiecksform. Im Fall ist stets von oberer Dreiecksform. Aus der verallgemeinerten Schurform lassen sich dann die Eigenwerte und aus und -invariante Unterräume des Matrixbüschels bestimmen.

Vortransformation

Bearbeiten

Ziel dieses Schrittes ist es, die Matrix   durch orthogonale Transformationen auf obere Hessenbergform und die Matrix   auf obere Dreiecksform zu bringen. Durch   Householder-Spiegelungen von links wird   auf obere Dreiecksform transformiert. Wendet man die gleichen Transformationen gleichzeitig auf   an, ergibt sich (Veranschaulichung an einem Beispiel der Größe (4,4)):  .

Man finde nun eine Givens-Rotation, die von links angewendet auf A folgende Matrix ergibt:  . Damit erhält man für  .

Durch Anwendung einer Givens-Rotation von rechts kann die obere Dreiecksform von   wiederhergestellt werden, ohne die Null an der linken unteren Position von A zu zerstören:  .

Durch analoges spaltenweises Erzeugen von Nullen in   erhält man eine obere Hessenbergmatrix:

  1.  
  2.  
  3.  
  4.  .

Falls  -invariante Unterräume berechnet werden sollen, so ist es notwendig, das Produkt der Transformationsmatrizen, die jeweils von links auf   und   angewendet werden, in einer Matrix   und das Produkt der Transformationsmatrizen, die von rechts angewendet werden, in einer Matrix   zu speichern.

QZ-Algorithmus mit impliziten Shifts

Bearbeiten

1.  

2. while   do

3. Bestimme alle   mit  . Für diese   setze  .

4. Deflation: Finde minimales   und maximales   mit   und definiere  , so dass gilt:  , wobei   und   von oberer Hessenbergform,   von unreduzierter oberer Hessenbergform und   von quasi-oberer Dreiecksform ist.

5. Partitioniere   wie  , d. h.  , wobei   obere Dreiecksmatrizen sind.

6. Bringe   in obere Schurform: Finde orthogonale   so, dass   in Schurform und   obere Dreiecksmatrix ist.

Falls erforderlich: Aufdatieren von   und  :  ,  .

7. if  :

if  

Transformiere mithilfe einer Givens-Rotation von rechts  , um die Rang-Defizienz von   auf   zu verschieben. Durch die Annullierung von   ist   keine unreduzierte Hessenbergmatrix mehr, somit wird   erhöht und es besteht die Möglichkeit, dass   in der neuen Partitionierung regulär ist.

else

Führe einen impliziten QZ-Schritt für   aus:  .

end if

8. end if

Wahl der Shifts

Bearbeiten

9. Bestimme Shifts   als Eigenwerte von  

10. Bestimme  

Der implizite QZ-Schritt

Bearbeiten

11. Finde orthogonales   mit  

Für   folgt nun:  .

Ziel ist es nun, die Dreiecksgestalt von   durch orthogonale Transformationen (Householder-Spiegelungen) von rechts wiederherzustellen:

12. Finde orthogonales   mit  . Finde dann orthogonales  , so dass

 .

Für   ergibt sich nun:  . D.h., die Hessenbergstruktur von   ist durch einen unerwünschten 2x2 „Buckel“ zerstört.

13. Dieser Buckel kann durch elementäre, orthogonale Transformationen (z. B. Householder-Spiegelungen) von links eliminiert werden. Finde also orthogonales  ,   mit

 . Es werden also nacheinander die Vektoren   und  auf  transformiert.

Die Anwendung der Transformation auf  von links ergibt jedoch

 , d. h. ein Buckel ist jetzt eine Position tiefer entlang der Diagonalen entstanden.

14. Man wiederhole die Schritte 11–13 so lange, bis   wieder in oberer Hessenberg- und   wieder in oberer Dreieckstruktur vorliegt. Diesen Prozess bezeichnet man, analog zum QR-Algorithmus, auch als „Buckel-Jagen“ oder „Bulge-Chasing“. Die Eliminierung eines Buckels in   an der Diagonalposition j mit Transformationen von links führt zu einem Buckel an der entsprechenden Position in  . Wird dieser Buckel mit Transformationen von rechts eliminiert, führt das zu einem Buckel in   an der Diagonalposition j+1 usw.

15. Nach   Schritten wird das Ziel erreicht und es ergibt sich  . Analog erhält man

 .

Falls  -invarianten Unterräume benötigt werden, ist es notwendig die Matrizen   und   aufzudatieren:  ,  

16. end while

Bestimmung der Eigenwerte

Bearbeiten

In den meisten Fällen konvergiert   im QZ-Algorithmus gegen seine verallgemeinerte, reelle Schur-Form. Für skalare Diagonalblöcke in A gilt   und   falls  . Falls ein   existiert, für das   ist, so ist  .   Diagonalblöcke von   beziehen sich (analog zum QR-Algorithmus) auf Paare komplex konjugierter Eigenwerte  .

Literatur

Bearbeiten
  • Gene H. Golub, Charles F. Van Loan: Matrix Computations. Johns Hopkins University Press, 1996, ISBN 0-8018-5414-8.
  • G. W. Stewart: Matrix Algorithms. Band II: Eigensystems. SIAM 2001, ISBN 0-89871-503-2.