Der QZ Algorithmus oder die QZ Faktorisierung ist ein numerisches Verfahren zur Losung des verallgemeinerten Eigenwertproblems A x l B x displaystyle Ax lambda Bx mit A B R n n displaystyle A B in mathbb R n times n bzw A B C n n displaystyle A B in mathbb C n times n Das verallgemeinerte Eigenwertproblem ist aquivalent zum Eigenwertproblem A B 1 y l y displaystyle AB 1 y lambda y wobei y B x displaystyle y Bx und B displaystyle B invertierbar sein muss Es wird jedoch nicht explizit die Matrix B 1 displaystyle B 1 berechnet um die Kondition des Problems nicht zu verschlechtern sondern A displaystyle A und B displaystyle B werden simultan durch Ahnlichkeitstransformationen Givens Rotationen und Householder Spiegelungen in verallgemeinerte Schurform gebracht Gegeben ist ein Matrixbuschel A l B displaystyle A lambda B Gesucht sind orthogonale Matrizen Q displaystyle Q und Z displaystyle Z so dass Q T A l B Z T l S displaystyle Q T A lambda B Z T lambda S von verallgemeinerter Schurform ist d h T displaystyle T ist von quasi oberer Dreiecksform und S displaystyle S ist von oberer Dreiecksform Im Fall A B C n n displaystyle A B in mathbb C n times n ist T displaystyle T stets von oberer Dreiecksform Aus der verallgemeinerten Schurform lassen sich dann die Eigenwerte und aus Q displaystyle Q und Z displaystyle Z A B displaystyle A B invariante Unterraume des Matrixbuschels A l B displaystyle A lambda B bestimmen Inhaltsverzeichnis 1 Vortransformation 2 QZ Algorithmus mit impliziten Shifts 3 Wahl der Shifts 4 Der implizite QZ Schritt 5 Bestimmung der Eigenwerte 6 LiteraturVortransformation BearbeitenZiel dieses Schrittes ist es die Matrix A displaystyle A nbsp durch orthogonale Transformationen auf obere Hessenbergform und die Matrix B displaystyle B nbsp auf obere Dreiecksform zu bringen Durch n 1 displaystyle n 1 nbsp Householder Spiegelungen von links wird B displaystyle B nbsp auf obere Dreiecksform transformiert Wendet man die gleichen Transformationen gleichzeitig auf A displaystyle A nbsp an ergibt sich Veranschaulichung an einem Beispiel der Grosse 4 4 A B 0 0 0 0 0 0 displaystyle A begin pmatrix amp amp amp amp amp amp amp amp amp amp amp amp end pmatrix B begin pmatrix amp amp amp 0 amp amp amp 0 amp 0 amp amp 0 amp 0 amp 0 amp end pmatrix nbsp Man finde nun eine Givens Rotation die von links angewendet auf A folgende Matrix ergibt A 0 displaystyle A begin pmatrix amp amp amp amp amp amp amp amp amp 0 amp amp amp end pmatrix nbsp Damit erhalt man fur B 0 0 0 0 0 displaystyle B begin pmatrix amp amp amp 0 amp amp amp 0 amp 0 amp amp 0 amp 0 amp amp end pmatrix nbsp Durch Anwendung einer Givens Rotation von rechts kann die obere Dreiecksform von B displaystyle B nbsp wiederhergestellt werden ohne die Null an der linken unteren Position von A zu zerstoren A 0 B 0 0 0 0 0 0 displaystyle A begin pmatrix amp amp amp amp amp amp amp amp amp 0 amp amp amp end pmatrix B begin pmatrix amp amp amp 0 amp amp amp 0 amp 0 amp amp 0 amp 0 amp 0 amp end pmatrix nbsp Durch analoges spaltenweises Erzeugen von Nullen in A displaystyle A nbsp erhalt man eine obere Hessenbergmatrix A 0 0 B 0 0 0 0 0 displaystyle A begin pmatrix amp amp amp amp amp amp 0 amp amp amp 0 amp amp amp end pmatrix B begin pmatrix amp amp amp 0 amp amp amp 0 amp amp amp 0 amp 0 amp 0 amp end pmatrix nbsp A 0 0 B 0 0 0 0 0 0 displaystyle A begin pmatrix amp amp amp amp amp amp 0 amp amp amp 0 amp amp amp end pmatrix B begin pmatrix amp amp amp 0 amp amp amp 0 amp 0 amp amp 0 amp 0 amp 0 amp end pmatrix nbsp A 0 0 0 B 0 0 0 0 0 displaystyle A begin pmatrix amp amp amp amp amp amp 0 amp amp amp 0 amp 0 amp amp end pmatrix B begin pmatrix amp amp amp 0 amp amp amp 0 amp 0 amp amp 0 amp 0 amp amp end pmatrix nbsp A 0 0 0 B 0 0 0 0 0 0 displaystyle A begin pmatrix amp amp amp amp amp amp 0 amp amp amp 0 amp 0 amp amp end pmatrix B begin pmatrix amp amp amp 0 amp amp amp 0 amp 0 amp amp 0 amp 0 amp 0 amp end pmatrix nbsp Falls A B displaystyle A B nbsp invariante Unterraume berechnet werden sollen so ist es notwendig das Produkt der Transformationsmatrizen die jeweils von links auf A displaystyle A nbsp und B displaystyle B nbsp angewendet werden in einer Matrix Q displaystyle Q nbsp und das Produkt der Transformationsmatrizen die von rechts angewendet werden in einer Matrix Z displaystyle Z nbsp zu speichern QZ Algorithmus mit impliziten Shifts Bearbeiten1 q 0 displaystyle q 0 nbsp 2 while q lt n displaystyle q lt n nbsp do3 Bestimme alle j 1 n 1 displaystyle j in 1 cdots n 1 nbsp mit a j 1 j e a j j a j 1 j 1 displaystyle a j 1 j leq varepsilon a j j a j 1 j 1 nbsp Fur diese j displaystyle j nbsp setze a j j 1 0 displaystyle a j j 1 0 nbsp 4 Deflation Finde minimales p displaystyle p nbsp und maximales q displaystyle q nbsp mit p q 1 n displaystyle p q in 1 cdots n nbsp und definiere m n p q displaystyle m n p q nbsp so dass gilt A A 11 A 12 A 13 0 A 22 A 23 0 0 A 33 displaystyle A begin pmatrix A 11 amp A 12 amp A 13 0 amp A 22 amp A 23 0 amp 0 amp A 33 end pmatrix nbsp wobei A 11 R p p A 22 R m m A 33 R q q displaystyle A 11 in mathbb R p times p A 22 in mathbb R m times m A 33 in mathbb R q times q nbsp und A 11 displaystyle A 11 nbsp von oberer Hessenbergform A 22 displaystyle A 22 nbsp von unreduzierter oberer Hessenbergform und A 33 displaystyle A 33 nbsp von quasi oberer Dreiecksform ist 5 Partitioniere B displaystyle B nbsp wie A displaystyle A nbsp d h B B 11 B 12 B 13 0 B 22 B 23 0 0 B 33 displaystyle B begin pmatrix B 11 amp B 12 amp B 13 0 amp B 22 amp B 23 0 amp 0 amp B 33 end pmatrix nbsp wobei B 11 R p p B 22 R m m B 33 R q q displaystyle B 11 in mathbb R p times p B 22 in mathbb R m times m B 33 in mathbb R q times q nbsp obere Dreiecksmatrizen sind 6 Bringe A 33 displaystyle A 33 nbsp in obere Schurform Finde orthogonale Q 33 Z 33 displaystyle Q 33 Z 33 nbsp so dass A 33 Q 33 T A 33 Z 33 displaystyle A 33 Q 33 T A 33 Z 33 nbsp in Schurform und B 33 Q 33 T B 33 Z 33 displaystyle B 33 Q 33 T B 33 Z 33 nbsp obere Dreiecksmatrix ist Falls erforderlich Aufdatieren von Q displaystyle Q nbsp und Z displaystyle Z nbsp Q Q d i a g I p I m Q 33 displaystyle Q Q mathrm diag I p I m Q 33 nbsp Z Z d i a g I p I m Z 33 displaystyle Z Z mathrm diag I p I m Z 33 nbsp 7 if q lt n displaystyle q lt n nbsp if d e t B 22 0 displaystyle det B 22 0 nbsp Transformiere mithilfe einer Givens Rotation von rechts a n q n q 1 0 displaystyle a n q n q 1 0 nbsp um die Rang Defizienz von B 22 displaystyle B 22 nbsp auf B 33 displaystyle B 33 nbsp zu verschieben Durch die Annullierung von a n q n q 1 displaystyle a n q n q 1 nbsp ist A 22 displaystyle A 22 nbsp keine unreduzierte Hessenbergmatrix mehr somit wird q displaystyle q nbsp erhoht und es besteht die Moglichkeit dass B 22 displaystyle B 22 nbsp in der neuen Partionierung regular ist elseFuhre einen impliziten QZ Schritt fur A 22 B 22 displaystyle A 22 B 22 nbsp aus A 22 Q 22 T A 22 Z 22 B 22 Q 22 T B 22 Z 22 displaystyle A 22 Q 22 T A 22 Z 22 quad B 22 Q 22 T B 22 Z 22 nbsp end if8 end ifWahl der Shifts Bearbeiten9 Bestimme Shifts a b displaystyle a b nbsp als Eigenwerte von a m 1 m 1 a m 1 m a m m 1 a m m b m 1 m 1 b m 1 m 0 b m m 1 displaystyle begin pmatrix a m 1 m 1 amp a m 1 m a m m 1 amp a m m end pmatrix begin pmatrix b m 1 m 1 amp b m 1 m 0 amp b m m end pmatrix 1 nbsp 10 Bestimme A 22 B 22 1 a I A 22 B 22 1 b I e 1 a b g 0 0 displaystyle A 22 B 22 1 aI A 22 B 22 1 bI e 1 begin pmatrix alpha beta gamma 0 vdots 0 end pmatrix nbsp Der implizite QZ Schritt Bearbeiten11 Finde orthogonales Q 1 displaystyle Q 1 nbsp mit Q 1 T a b g 0 0 displaystyle Q 1 T begin pmatrix alpha beta gamma end pmatrix begin pmatrix 0 0 end pmatrix nbsp Fur B 22 displaystyle B 22 nbsp folgt nun Q 1 T 0 0 I m 3 B 22 0 0 0 0 0 0 displaystyle begin pmatrix Q 1 T amp 0 0 amp I m 3 end pmatrix B 22 begin pmatrix amp amp amp cdots amp cdots amp amp amp amp cdots amp cdots amp amp amp amp cdots amp cdots amp 0 amp 0 amp 0 amp ddots amp amp vdots vdots amp vdots amp vdots amp amp ddots amp vdots 0 amp 0 amp 0 amp cdots amp cdots amp end pmatrix nbsp Ziel ist es nun die Dreiecksgestalt von B 22 displaystyle B 22 nbsp durch orthogonale Transformationen Householder Spiegelungen von rechts wiederherzustellen 12 Finde orthogonales Z 1 R 3 3 displaystyle Z 1 in mathbb R 3 times 3 nbsp mit B 22 d i a g Z 1 I m 3 0 0 0 0 0 0 0 0 displaystyle B 22 mathrm diag Z 1 I m 3 begin pmatrix amp amp amp cdots amp cdots amp amp amp amp cdots amp cdots amp 0 amp 0 amp amp cdots amp cdots amp 0 amp 0 amp 0 amp ddots amp amp vdots vdots amp vdots amp vdots amp amp ddots amp vdots 0 amp 0 amp 0 amp cdots amp cdots amp end pmatrix nbsp Finde dann orthogonales Z 1 R 2 2 displaystyle Z 1 in mathbb R 2 times 2 nbsp so dassB 22 d i a g Z 1 I m 3 d i a g Z 1 I m 2 0 0 0 0 0 0 0 0 0 displaystyle B 22 mathrm diag Z 1 I m 3 mathrm diag Z 1 I m 2 begin pmatrix amp amp amp cdots amp cdots amp 0 amp amp amp cdots amp cdots amp 0 amp 0 amp amp cdots amp cdots amp 0 amp 0 amp 0 amp ddots amp amp vdots vdots amp vdots amp vdots amp amp ddots amp vdots 0 amp 0 amp 0 amp cdots amp cdots amp end pmatrix nbsp Fur A 22 displaystyle A 22 nbsp ergibt sich nun A 22 A 22 d i a g Z 1 I m 3 d i a g Z 1 I m 2 0 0 0 0 0 0 0 displaystyle tilde A 22 A 22 mathrm diag Z 1 I m 3 mathrm diag Z 1 I m 2 begin pmatrix amp amp amp cdots amp cdots amp cdots amp amp amp amp cdots amp cdots amp cdots amp amp amp amp cdots amp cdots amp cdots amp amp amp amp cdots amp cdots amp cdots amp 0 amp 0 amp 0 amp ddots amp amp amp vdots vdots amp vdots amp vdots amp amp ddots amp amp vdots 0 amp 0 amp 0 amp cdots amp 0 amp amp end pmatrix nbsp D h die Hessenbergstruktur von A 22 displaystyle A 22 nbsp ist durch einen unerwunschten 2x2 Buckel zerstort 13 Dieser Buckel kann durch elementare orthogonale Transformationen z B Householder Spiegelungen von links eliminiert werden Finde also orthogonales Q 1 R 3 3 displaystyle Q 1 in mathbb R 3 times 3 nbsp Q 1 R 3 3 displaystyle Q 1 in mathbb R 3 times 3 nbsp mitd i a g 1 Q 1 I m 4 T d i a g I 2 Q 1 I m 5 T A 22 0 0 0 0 0 0 0 0 0 0 displaystyle mathrm diag 1 Q 1 I m 4 T mathrm diag I 2 Q 1 I m 5 T tilde A 22 begin pmatrix amp amp amp cdots amp cdots amp cdots amp amp amp amp cdots amp cdots amp cdots amp 0 amp amp amp ddots amp cdots amp cdots amp 0 amp 0 amp amp ddots amp cdots amp cdots amp 0 amp 0 amp 0 amp amp amp vdots vdots amp vdots amp vdots amp amp ddots amp amp vdots 0 amp 0 amp 0 amp cdots amp 0 amp amp end pmatrix nbsp Es werden also nacheinander die Vektoren a 21 a 31 a 41 displaystyle begin pmatrix a 21 a 31 a 41 end pmatrix nbsp und a 32 a 42 a 52 displaystyle begin pmatrix a 32 a 42 a 52 end pmatrix nbsp auf 0 0 displaystyle begin pmatrix 0 0 end pmatrix nbsp transformiert Die Anwendung der Transformation auf B 22 displaystyle tilde B 22 nbsp von links ergibt jedochd i a g 1 Q 1 I m 4 T d i a g I 2 Q 1 I m 5 T B 22 0 0 0 0 0 0 0 0 0 0 0 0 displaystyle mathrm diag 1 Q 1 I m 4 T mathrm diag I 2 Q 1 I m 5 T tilde B 22 begin pmatrix amp amp amp cdots amp cdots amp cdots amp 0 amp amp amp cdots amp cdots amp cdots amp 0 amp amp amp ddots amp cdots amp cdots amp 0 amp amp amp amp ddots amp cdots amp 0 amp 0 amp 0 amp 0 amp amp vdots vdots amp vdots amp vdots amp amp ddots amp amp vdots 0 amp 0 amp 0 amp cdots amp 0 amp 0 amp end pmatrix nbsp d h ein Buckel ist jetzt eine Position tiefer entlang der Diagonalen entstanden 14 Man wiederhole die Schritte 11 13 so lange bis A 22 displaystyle A 22 nbsp wieder in oberer Hessenberg und B 22 displaystyle B 22 nbsp 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 B 22 displaystyle B 22 nbsp an der Diagonalposition j mit Transformationen von links fuhrt zu einem Buckel an der entsprechenden Position in A 22 displaystyle A 22 nbsp Wird dieser Buckel mit Transformationen von rechts eliminiert fuhrt das zu einem Buckel in B 22 displaystyle B 22 nbsp an der Diagonalposition j 1 usw 15 Nach m 2 displaystyle m 2 nbsp Schritten wird das Ziel erreicht und es ergibt sich Q 22 T d i a g Q 1 I m 3 T d i a g 1 Q 1 I m 4 T d i a g I 2 Q 1 I m 5 T d i a g I m 3 Q m 2 T displaystyle Q 22 T mathrm diag Q 1 I m 3 T mathrm diag 1 Q 1 I m 4 T mathrm diag I 2 Q 1 I m 5 T cdots mathrm diag I m 3 Q m 2 T nbsp Analog erhalt manZ 22 d i a g Z 1 I m 3 d i a g Z 1 I m 2 d i a g I m 2 Z m 2 d i a g I m 2 Z m 2 displaystyle Z 22 mathrm diag Z 1 I m 3 mathrm diag Z 1 I m 2 cdots mathrm diag I m 2 Z m 2 mathrm diag I m 2 Z m 2 nbsp Falls A B displaystyle A B nbsp invarianten Unterraume benotigt werden ist es notwendig die Matrizen Q displaystyle Q nbsp und Z displaystyle Z nbsp aufzudatieren Q Q d i a g I p Q 22 I q displaystyle Q Q mathrm diag I p Q 22 I q nbsp Z Z d i a g I p Z 22 I q displaystyle Z Z mathrm diag I p Z 22 I q nbsp 16 end whileBestimmung der Eigenwerte BearbeitenIn den meisten Fallen konvergiert A B displaystyle A B nbsp im QZ Algorithmus gegen seine verallgemeinerte reelle Schur Form Fur skalare Diagonalblocke in A gilt l i a i i b i i b i i 0 displaystyle lambda i frac a ii b ii b ii neq 0 nbsp und l i displaystyle lambda i infty nbsp falls b i i 0 displaystyle b ii 0 nbsp Falls ein i displaystyle i nbsp existiert fur das a i i b i i 0 displaystyle a ii b ii 0 nbsp ist so ist L A B C displaystyle Lambda A B mathbb C nbsp 2 2 displaystyle 2 times 2 nbsp Diagonalblocke von A displaystyle A nbsp beziehen sich analog zum QR Algorithmus auf Paare komplex konjugierter Eigenwerte l l L a i i a i i 1 a i 1 i a i 1 i 1 b i i b i i 1 0 b i 1 i 1 displaystyle lambda overline lambda Lambda left begin pmatrix a ii amp a i i 1 a i 1 i amp a i 1 i 1 end pmatrix begin pmatrix b ii amp b i i 1 0 amp b i 1 i 1 end pmatrix right nbsp Literatur BearbeitenGene 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 Abgerufen von https de wikipedia org w index php title QZ Algorithmus amp oldid 216521537
