Der QZ-Algorithmus oder die QZ-Faktorisierung ist ein numerisches Verfahren zur Lösung des verallgemeinerten Eigenwertproblems.
, mit
bzw. ![{\displaystyle A,B\in \mathbb {C} ^{n\times n}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5fab8e400f8f9009373e9b564a9d5b716b72a797)
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.
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:
![{\displaystyle A={\begin{pmatrix}*&*&*&*\\{*}&*&*&*\\0&*&*&*\\0&*&*&*\end{pmatrix}},B={\begin{pmatrix}*&*&*&*\\0&*&*&*\\0&*&*&*\\0&0&0&*\end{pmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/facd84a68950597c577b1f1e2c7dc04fcc0f8398)
![{\displaystyle A={\begin{pmatrix}*&*&*&*\\{*}&*&*&*\\0&*&*&*\\0&*&*&*\end{pmatrix}},B={\begin{pmatrix}*&*&*&*\\0&*&*&*\\0&0&*&*\\0&0&0&*\end{pmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/154b0443a9dc6f6ede4137e02bb4e3ec337a1d44)
![{\displaystyle A={\begin{pmatrix}*&*&*&*\\{*}&*&*&*\\0&*&*&*\\0&0&*&*\end{pmatrix}},B={\begin{pmatrix}*&*&*&*\\0&*&*&*\\0&0&*&*\\0&0&*&*\end{pmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8ba15225c80b95ec88cff74361c2226624f93b4f)
.
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
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
9. Bestimme Shifts
als Eigenwerte von
10. Bestimme
Der implizite QZ-Schritt
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
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
- 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.