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^{\,}}
A
,
B
∈
R
n
×
n
{\displaystyle A,B\in \mathbb {R} ^{n\times n}}
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}
y
=
B
x
{\displaystyle y=Bx}
B
{\displaystyle B}
B
−
1
{\displaystyle B^{-1}}
Kondition des Problems nicht zu verschlechtern, sondern
A
{\displaystyle A}
B
{\displaystyle B}
Ähnlichkeitstransformationen (Givens-Rotationen und Householder-Spiegelungen ) in verallgemeinerte Schurform gebracht.
Gegeben ist ein Matrixbüschel
A
−
λ
B
{\displaystyle A-\lambda B}
Q
{\displaystyle Q}
Z
{\displaystyle Z}
Q
T
(
A
−
λ
B
)
Z
=
T
−
λ
S
{\displaystyle Q^{T}(A-\lambda B)Z=T-\lambda S}
Schurform ist, d. h.
T
{\displaystyle T}
Dreiecksform und
S
{\displaystyle S}
A
,
B
∈
C
n
×
n
{\displaystyle A,B\in \mathbb {C} ^{n\times n}}
T
{\displaystyle T}
Eigenwerte und aus
Q
{\displaystyle Q}
Z
{\displaystyle Z}
(
A
,
B
)
{\displaystyle (A,B)}
A
−
λ
B
{\displaystyle A-\lambda B}
Ziel dieses Schrittes ist es, die Matrix
A
{\displaystyle A}
B
{\displaystyle B}
n
−
1
{\displaystyle n-1}
B
{\displaystyle B}
A
{\displaystyle A}
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}}}
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}
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}
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)}
Produkt der Transformationsmatrizen, die jeweils von links auf
A
{\displaystyle A}
B
{\displaystyle B}
Q
{\displaystyle Q}
Z
{\displaystyle Z}
QZ-Algorithmus mit impliziten Shifts
Bearbeiten
1.
q
:=
0
{\displaystyle q:=0}
2. while
q
<
n
{\displaystyle q<n}
3. Bestimme alle
j
∈
{
1
,
⋯
,
n
−
1
}
{\displaystyle j\in \{1,\cdots ,n-1\}}
|
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}|)}
j
{\displaystyle j}
a
j
,
j
+
1
=
0
{\displaystyle a_{j,j+1}=0}
4. Deflation : Finde minimales
p
{\displaystyle p}
q
{\displaystyle q}
p
,
q
∈
{
1
,
⋯
,
n
}
{\displaystyle p,q\in \{1,\cdots ,n\}}
m
:=
n
−
p
−
q
{\displaystyle m:=n-p-q}
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}}}
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}}
A
11
{\displaystyle A_{11}}
Hessenbergform ,
A
22
{\displaystyle A_{22}}
A
33
{\displaystyle A_{33}}
5. Partitioniere
B
{\displaystyle B}
A
{\displaystyle A}
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}}}
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}}
6. Bringe
A
33
{\displaystyle A_{33}}
Schurform : Finde orthogonale
Q
33
,
Z
33
{\displaystyle Q_{33},Z_{33}}
A
33
:=
Q
33
T
A
33
Z
33
{\displaystyle A_{33}:=Q_{33}^{T}A_{33}Z_{33}}
B
33
:=
Q
33
T
B
33
Z
33
{\displaystyle B_{33}:=Q_{33}^{T}B_{33}Z_{33}}
Falls erforderlich: Aufdatieren von
Q
{\displaystyle Q}
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}
Rang-Defizienz von
B
22
{\displaystyle B_{22}}
B
33
{\displaystyle B_{33}}
a
n
−
q
,
n
−
q
−
1
{\displaystyle a_{n-q,n-q-1}}
A
22
{\displaystyle A_{22}}
q
{\displaystyle q}
B
22
{\displaystyle B_{22}}
else
Führe einen impliziten QZ-Schritt für
A
22
,
B
22
{\displaystyle A_{22},B_{22}}
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}
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}}}
Der implizite QZ-Schritt
Bearbeiten
11. Finde orthogonales
Q
1
{\displaystyle Q_{1}}
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}}
(
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}}
12. Finde orthogonales
Z
1
∈
R
3
×
3
{\displaystyle Z_{1}\in \mathbb {R} ^{3\times 3}}
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}}}
Z
1
′
∈
R
2
×
2
{\displaystyle Z_{1}'\in \mathbb {R} ^{2\times 2}}
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}}
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}}}
A
22
{\displaystyle A_{22}}
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}}
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}}}
(
a
21
a
31
a
41
)
{\displaystyle {\begin{pmatrix}a_{21}\\a_{31}\\a_{41}\end{pmatrix}}}
(
a
32
a
42
a
52
)
{\displaystyle {\begin{pmatrix}a_{32}\\a_{42}\\a_{52}\end{pmatrix}}}
(
∗
0
0
)
{\displaystyle {\begin{pmatrix}*\\0\\0\end{pmatrix}}}
Die Anwendung der Transformation auf
B
~
22
{\displaystyle {\tilde {B}}_{22}}
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}}}
14. Man wiederhole die Schritte 11–13 so lange, bis
A
22
{\displaystyle A_{22}}
B
22
{\displaystyle B_{22}}
B
22
{\displaystyle B_{22}}
A
22
{\displaystyle A_{22}}
B
22
{\displaystyle B_{22}}
15. Nach
m
−
2
{\displaystyle m-2}
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}}
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)}
Q
{\displaystyle {Q}}
Z
{\displaystyle Z}
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
Bestimmung der Eigenwerte
Bearbeiten
In den meisten Fällen konvergiert
(
A
,
B
)
{\displaystyle (A,B)}
λ
i
=
a
i
i
b
i
i
:
b
i
i
≠
0
{\displaystyle \lambda _{i}={\frac {a_{ii}}{b_{ii}}}:b_{ii}\neq 0}
λ
i
=
∞
{\displaystyle \lambda _{i}=\infty }
b
i
i
=
0
{\displaystyle b_{ii}=0}
i
{\displaystyle i}
a
i
i
=
b
i
i
=
0
{\displaystyle a_{ii}=b_{ii}=0}
Λ
(
A
,
B
)
=
C
{\displaystyle \Lambda (A,B)=\mathbb {C} }
2
×
2
{\displaystyle 2\times 2}
A
{\displaystyle A}
λ
,
λ
¯
=
Λ
(
(
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 . 
