Der QZ-Algorithmus oder die QZ-Faktorisierung ist ein numerisches Verfahren zur Lösung des verallgemeinerten Eigenwertproblems .
A
x
=
λ
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 äquivalent zum Eigenwertproblem
A
B
−
1
y
=
λ
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 Ähnlichkeitstransformationen (Givens-Rotationen und Householder-Spiegelungen ) in verallgemeinerte Schurform gebracht.
Gegeben ist ein Matrixbüschel
A
−
λ
B
{\displaystyle A-\lambda B}
.
Gesucht sind orthogonale Matrizen
Q
{\displaystyle Q}
und
Z
{\displaystyle Z}
, so dass
Q
T
(
A
−
λ
B
)
Z
=
T
−
λ
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
Unterräume des Matrixbüschels
A
−
λ
B
{\displaystyle A-\lambda B}
bestimmen.
Ziel dieses Schrittes ist es, die Matrix
A
{\displaystyle A}
durch orthogonale Transformationen auf obere Hessenbergform und die Matrix
B
{\displaystyle B}
auf obere Dreiecksform zu bringen.
Durch
n
−
1
{\displaystyle n-1}
Householder-Spiegelungen von links wird
B
{\displaystyle B}
auf obere Dreiecksform transformiert. Wendet man die gleichen Transformationen gleichzeitig auf
A
{\displaystyle A}
an, ergibt sich (Veranschaulichung an einem Beispiel der Größe (4,4)):
A
=
(
∗
∗
∗
∗
∗
∗
∗
∗
∗
∗
∗
∗
∗
∗
∗
∗
)
,
B
=
(
∗
∗
∗
∗
0
∗
∗
∗
0
0
∗
∗
0
0
0
∗
)
{\displaystyle A={\begin{pmatrix}*&*&*&*\\{*}&*&*&*\\{*}&*&*&*\\{*}&*&*&*\end{pmatrix}},B={\begin{pmatrix}*&*&*&*\\0&*&*&*\\0&0&*&*\\0&0&0&*\end{pmatrix}}}
.
Man finde nun eine Givens-Rotation, die von links angewendet auf A folgende Matrix ergibt:
A
=
(
∗
∗
∗
∗
∗
∗
∗
∗
∗
∗
∗
∗
0
∗
∗
∗
)
{\displaystyle A={\begin{pmatrix}*&*&*&*\\{*}&*&*&*\\{*}&*&*&*\\0&*&*&*\end{pmatrix}}}
.
Damit erhält man für
B
=
(
∗
∗
∗
∗
0
∗
∗
∗
0
0
∗
∗
0
0
∗
∗
)
{\displaystyle B={\begin{pmatrix}*&*&*&*\\0&*&*&*\\0&0&*&*\\0&0&*&*\end{pmatrix}}}
.
Durch Anwendung einer Givens-Rotation von rechts kann die obere Dreiecksform von
B
{\displaystyle B}
wiederhergestellt
werden, ohne die Null an der linken unteren Position von A zu zerstören:
A
=
(
∗
∗
∗
∗
∗
∗
∗
∗
∗
∗
∗
∗
0
∗
∗
∗
)
,
B
=
(
∗
∗
∗
∗
0
∗
∗
∗
0
0
∗
∗
0
0
0
∗
)
{\displaystyle A={\begin{pmatrix}*&*&*&*\\{*}&*&*&*\\{*}&*&*&*\\0&*&*&*\end{pmatrix}},B={\begin{pmatrix}*&*&*&*\\0&*&*&*\\0&0&*&*\\0&0&0&*\end{pmatrix}}}
.
Durch analoges spaltenweises Erzeugen von Nullen in
A
{\displaystyle A}
erhält man eine obere Hessenbergmatrix :
A
=
(
∗
∗
∗
∗
∗
∗
∗
∗
0
∗
∗
∗
0
∗
∗
∗
)
,
B
=
(
∗
∗
∗
∗
0
∗
∗
∗
0
∗
∗
∗
0
0
0
∗
)
{\displaystyle A={\begin{pmatrix}*&*&*&*\\{*}&*&*&*\\0&*&*&*\\0&*&*&*\end{pmatrix}},B={\begin{pmatrix}*&*&*&*\\0&*&*&*\\0&*&*&*\\0&0&0&*\end{pmatrix}}}
A
=
(
∗
∗
∗
∗
∗
∗
∗
∗
0
∗
∗
∗
0
∗
∗
∗
)
,
B
=
(
∗
∗
∗
∗
0
∗
∗
∗
0
0
∗
∗
0
0
0
∗
)
{\displaystyle A={\begin{pmatrix}*&*&*&*\\{*}&*&*&*\\0&*&*&*\\0&*&*&*\end{pmatrix}},B={\begin{pmatrix}*&*&*&*\\0&*&*&*\\0&0&*&*\\0&0&0&*\end{pmatrix}}}
A
=
(
∗
∗
∗
∗
∗
∗
∗
∗
0
∗
∗
∗
0
0
∗
∗
)
,
B
=
(
∗
∗
∗
∗
0
∗
∗
∗
0
0
∗
∗
0
0
∗
∗
)
{\displaystyle A={\begin{pmatrix}*&*&*&*\\{*}&*&*&*\\0&*&*&*\\0&0&*&*\end{pmatrix}},B={\begin{pmatrix}*&*&*&*\\0&*&*&*\\0&0&*&*\\0&0&*&*\end{pmatrix}}}
A
=
(
∗
∗
∗
∗
∗
∗
∗
∗
0
∗
∗
∗
0
0
∗
∗
)
,
B
=
(
∗
∗
∗
∗
0
∗
∗
∗
0
0
∗
∗
0
0
0
∗
)
{\displaystyle A={\begin{pmatrix}*&*&*&*\\{*}&*&*&*\\0&*&*&*\\0&0&*&*\end{pmatrix}},B={\begin{pmatrix}*&*&*&*\\0&*&*&*\\0&0&*&*\\0&0&0&*\end{pmatrix}}}
.
Falls
(
A
,
B
)
{\displaystyle (A,B)}
-invariante Unterräume berechnet werden sollen, so ist es notwendig, das Produkt der Transformationsmatrizen, die jeweils von links auf
A
{\displaystyle A}
und
B
{\displaystyle B}
angewendet werden, in einer Matrix
Q
{\displaystyle Q}
und das Produkt der Transformationsmatrizen, die von rechts angewendet werden, in einer Matrix
Z
{\displaystyle Z}
zu speichern.
1.
q
:=
0
{\displaystyle q:=0}
2. while
q
<
n
{\displaystyle q<n}
do
3. Bestimme alle
j
∈
{
1
,
⋯
,
n
−
1
}
{\displaystyle j\in \{1,\cdots ,n-1\}}
mit
|
a
j
+
1
,
j
|
≤
ε
(
|
a
j
,
j
|
+
|
a
j
+
1
,
j
+
1
|
)
{\displaystyle |a_{j+1,j}|\leq \varepsilon (|a_{j,j}|+|a_{j+1,j+1}|)}
. Für diese
j
{\displaystyle j}
setze
a
j
,
j
+
1
=
0
{\displaystyle a_{j,j+1}=0}
.
4. Deflation : Finde minimales
p
{\displaystyle p}
und maximales
q
{\displaystyle q}
mit
p
,
q
∈
{
1
,
⋯
,
n
}
{\displaystyle p,q\in \{1,\cdots ,n\}}
und definiere
m
:=
n
−
p
−
q
{\displaystyle m:=n-p-q}
, 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}&A_{12}&A_{13}\\0&A_{22}&A_{23}\\0&0&A_{33}\end{pmatrix}}}
, 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}}
und
A
11
{\displaystyle A_{11}}
von oberer Hessenbergform ,
A
22
{\displaystyle A_{22}}
von unreduzierter oberer Hessenbergform und
A
33
{\displaystyle A_{33}}
von quasi-oberer Dreiecksform ist.
5. Partitioniere
B
{\displaystyle B}
wie
A
{\displaystyle A}
, d. h.
B
=
(
B
11
B
12
B
13
0
B
22
B
23
0
0
B
33
)
{\displaystyle B={\begin{pmatrix}B_{11}&B_{12}&B_{13}\\0&B_{22}&B_{23}\\0&0&B_{33}\end{pmatrix}}}
, 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}}
obere Dreiecksmatrizen sind.
6. Bringe
A
33
{\displaystyle A_{33}}
in obere Schurform : Finde orthogonale
Q
33
,
Z
33
{\displaystyle Q_{33},Z_{33}}
so, dass
A
33
:=
Q
33
T
A
33
Z
33
{\displaystyle A_{33}:=Q_{33}^{T}A_{33}Z_{33}}
in Schurform und
B
33
:=
Q
33
T
B
33
Z
33
{\displaystyle B_{33}:=Q_{33}^{T}B_{33}Z_{33}}
obere Dreiecksmatrix ist.
Falls erforderlich: Aufdatieren von
Q
{\displaystyle Q}
und
Z
{\displaystyle Z}
:
Q
:=
Q
d
i
a
g
(
I
p
,
I
m
,
Q
33
)
{\displaystyle Q:=Q\mathrm {diag} (I_{p},I_{m},Q_{33})}
,
Z
:=
Z
d
i
a
g
(
I
p
,
I
m
,
Z
33
)
{\displaystyle Z:=Z\mathrm {diag} (I_{p},I_{m},Z_{33})}
.
7. if
q
<
n
{\displaystyle q<n}
:
if
d
e
t
(
B
22
)
=
0
{\displaystyle det(B_{22})=0}
Transformiere mithilfe einer Givens-Rotation von rechts
a
n
−
q
,
n
−
q
−
1
=
0
{\displaystyle a_{n-q,n-q-1}=0}
, um die Rang-Defizienz von
B
22
{\displaystyle B_{22}}
auf
B
33
{\displaystyle B_{33}}
zu verschieben. Durch die Annullierung von
a
n
−
q
,
n
−
q
−
1
{\displaystyle a_{n-q,n-q-1}}
ist
A
22
{\displaystyle A_{22}}
keine unreduzierte Hessenbergmatrix mehr, somit wird
q
{\displaystyle q}
erhöht und es besteht die Möglichkeit, dass
B
22
{\displaystyle B_{22}}
in der neuen Partitionierung regulär ist.
else
Führe einen impliziten QZ-Schritt für
A
22
,
B
22
{\displaystyle A_{22},B_{22}}
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}}
.
end if
8. end if
9. Bestimme Shifts
a
,
b
{\displaystyle a,b}
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}&a_{m-1,m}\\a_{m,m-1}&a_{m,m}\end{pmatrix}}{\begin{pmatrix}b_{m-1,m-1}&b_{m-1,m}\\0&b_{m,m}\end{pmatrix}}^{-1}}
10. Bestimme
(
A
22
B
22
−
1
−
a
I
)
(
A
22
B
22
−
1
−
b
I
)
e
1
=
(
α
β
γ
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}}}
11. Finde orthogonales
Q
1
{\displaystyle Q_{1}}
mit
Q
1
T
(
α
β
γ
)
=
(
∗
0
0
)
{\displaystyle Q_{1}^{T}{\begin{pmatrix}\alpha \\\beta \\\gamma \end{pmatrix}}={\begin{pmatrix}*\\0\\0\end{pmatrix}}}
Für
B
22
{\displaystyle B_{22}}
folgt nun:
(
Q
1
T
0
0
I
m
−
3
)
B
22
=
(
∗
∗
∗
⋯
⋯
∗
∗
∗
∗
⋯
⋯
∗
∗
∗
∗
⋯
⋯
∗
0
0
0
⋱
⋮
⋮
⋮
⋮
⋱
⋮
0
0
0
⋯
⋯
∗
)
{\displaystyle {\begin{pmatrix}Q_{1}^{T}&0\\0&I_{m-3}\end{pmatrix}}B_{22}={\begin{pmatrix}*&*&*&\cdots &\cdots &*\\{*}&*&*&\cdots &\cdots &*\\{*}&*&*&\cdots &\cdots &*\\0&0&0&\ddots &&\vdots \\\vdots &\vdots &\vdots &&\ddots &\vdots \\0&0&0&\cdots &\cdots &*\end{pmatrix}}}
.
Ziel ist es nun, die Dreiecksgestalt von
B
22
{\displaystyle B_{22}}
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}}
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}*&*&*&\cdots &\cdots &*\\{*}&*&*&\cdots &\cdots &*\\0&0&*&\cdots &\cdots &*\\0&0&0&\ddots &&\vdots \\\vdots &\vdots &\vdots &&\ddots &\vdots \\0&0&0&\cdots &\cdots &*\end{pmatrix}}}
. Finde dann orthogonales
Z
1
′
∈
R
2
×
2
{\displaystyle Z_{1}'\in \mathbb {R} ^{2\times 2}}
, so dass
B
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}*&*&*&\cdots &\cdots &*\\0&*&*&\cdots &\cdots &*\\0&0&*&\cdots &\cdots &*\\0&0&0&\ddots &&\vdots \\\vdots &\vdots &\vdots &&\ddots &\vdots \\0&0&0&\cdots &\cdots &*\end{pmatrix}}}
.
Für
A
22
{\displaystyle A_{22}}
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}*&*&*&\cdots &\cdots &\cdots &*\\{*}&*&*&\cdots &\cdots &\cdots &*\\{*}&*&*&\cdots &\cdots &\cdots &*\\{*}&*&*&\cdots &\cdots &\cdots &*\\0&0&0&\ddots &&&\vdots \\\vdots &\vdots &\vdots &&\ddots &&\vdots \\0&0&0&\cdots &0&*&*\end{pmatrix}}}
. D.h., die Hessenbergstruktur von
A
22
{\displaystyle A_{22}}
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
Q
1
″
∈
R
3
×
3
{\displaystyle Q''_{1}\in \mathbb {R} ^{3\times 3}}
,
Q
1
′
∈
R
3
×
3
{\displaystyle Q_{1}'\in \mathbb {R} ^{3\times 3}}
mit
d
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}*&*&*&\cdots &\cdots &\cdots &*\\*&*&*&\cdots &\cdots &\cdots &*\\0&*&*&\ddots &\cdots &\cdots &*\\0&0&*&\ddots &\cdots &\cdots &*\\0&0&0&*&&\vdots \\\vdots &\vdots &\vdots &&\ddots &&\vdots \\0&0&0&\cdots &0&*&*\end{pmatrix}}}
. Es werden also nacheinander die Vektoren
(
a
21
a
31
a
41
)
{\displaystyle {\begin{pmatrix}a_{21}\\a_{31}\\a_{41}\end{pmatrix}}}
und
(
a
32
a
42
a
52
)
{\displaystyle {\begin{pmatrix}a_{32}\\a_{42}\\a_{52}\end{pmatrix}}}
auf
(
∗
0
0
)
{\displaystyle {\begin{pmatrix}*\\0\\0\end{pmatrix}}}
transformiert.
Die Anwendung der Transformation auf
B
~
22
{\displaystyle {\tilde {B}}_{22}}
von links ergibt jedoch
d
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}*&*&*&\cdots &\cdots &\cdots &*\\0&*&*&\cdots &\cdots &\cdots &*\\0&*&*&\ddots &\cdots &\cdots &*\\0&*&*&*&\ddots &\cdots &*\\0&0&0&0&*&\vdots \\\vdots &\vdots &\vdots &&\ddots &&\vdots \\0&0&0&\cdots &0&0&*\end{pmatrix}}}
, 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}}
wieder in oberer Hessenberg- und
B
22
{\displaystyle B_{22}}
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}}
an der Diagonalposition j mit Transformationen von links führt zu einem Buckel an der entsprechenden Position in
A
22
{\displaystyle A_{22}}
. Wird dieser Buckel mit Transformationen von rechts eliminiert, führt das zu einem Buckel in
B
22
{\displaystyle B_{22}}
an der Diagonalposition j+1 usw.
15. Nach
m
−
2
{\displaystyle m-2}
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}}
. Analog erhält man
Z
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}')}
.
Falls
(
A
,
B
)
{\displaystyle (A,B)}
-invarianten Unterräume benötigt werden, ist es notwendig die Matrizen
Q
{\displaystyle {Q}}
und
Z
{\displaystyle Z}
aufzudatieren:
Q
:=
Q
d
i
a
g
(
I
p
,
Q
22
,
I
q
)
{\displaystyle Q:=Q\mathrm {diag} (I_{p},Q_{22},I_{q})}
,
Z
:=
Z
d
i
a
g
(
I
p
,
Z
22
,
I
q
)
{\displaystyle Z:=Z\mathrm {diag} (I_{p},Z_{22},I_{q})}
16. end while
In den meisten Fällen konvergiert
(
A
,
B
)
{\displaystyle (A,B)}
im QZ-Algorithmus gegen seine verallgemeinerte, reelle Schur-Form.
Für skalare Diagonalblöcke in A gilt
λ
i
=
a
i
i
b
i
i
:
b
i
i
≠
0
{\displaystyle \lambda _{i}={\frac {a_{ii}}{b_{ii}}}:b_{ii}\neq 0}
und
λ
i
=
∞
{\displaystyle \lambda _{i}=\infty }
falls
b
i
i
=
0
{\displaystyle b_{ii}=0}
. Falls ein
i
{\displaystyle i}
existiert, für das
a
i
i
=
b
i
i
=
0
{\displaystyle a_{ii}=b_{ii}=0}
ist, so ist
Λ
(
A
,
B
)
=
C
{\displaystyle \Lambda (A,B)=\mathbb {C} }
.
2
×
2
{\displaystyle 2\times 2}
Diagonalblöcke von
A
{\displaystyle A}
beziehen sich (analog zum QR-Algorithmus) auf Paare komplex konjugierter Eigenwerte
λ
,
λ
¯
=
Λ
(
(
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}&a_{i,i+1}\\a_{i+1,i}&a_{i+1,i+1}\end{pmatrix}},{\begin{pmatrix}b_{ii}&b_{i,i+1}\\0&b_{i+1,i+1}\end{pmatrix}}\right)}
.
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 .