QZ algorithm

The QZ algorithm is a numerical method for solving the generalized eigenvalue problem .

${\displaystyle Ax=\lambda Bx^{\,}}$, with resp. ${\displaystyle A,B\in \mathbb {R} ^{n\times n}}$ ${\displaystyle A,B\in \mathbb {C} ^{n\times n}}$

The generalized eigenvalue problem is equivalent to the eigenvalue problem , where and must be invertible. However, it is not explicitly the matrix calculated to the condition of the problem not to degrade, but and simultaneously by similarity transformations ( Givens rotations and Householder reflections ) in generalized Schur form brought. ${\displaystyle AB^{-1}y=\lambda y}$ ${\displaystyle y=Bx}$ ${\displaystyle B}$ ${\displaystyle B^{-1}}$ ${\displaystyle A}$ ${\displaystyle B}$

A matrix tuft is given . We are looking for orthogonal matrices and , so that is of generalized Schur form , i.e. H. is of quasi-upper triangular shape and is of upper triangular shape. In the case is always of the upper triangular shape. The eigenvalues and the subspaces of the matrix cluster from and invariant can then be determined from the generalized Schurform . ${\displaystyle A-\lambda B}$ ${\displaystyle Q}$ ${\displaystyle Z}$ ${\displaystyle Q^{T}(A-\lambda B)Z=T-\lambda S}$ ${\displaystyle T}$ ${\displaystyle S}$ ${\displaystyle A,B\in \mathbb {C} ^{n\times n}}$ ${\displaystyle T}$ ${\displaystyle Q}$ ${\displaystyle Z}$ ${\displaystyle (A,B)}$ ${\displaystyle A-\lambda B}$

Pre-transformation

The aim of this step is to bring the matrix to the upper Hessenberg shape and the matrix to the upper triangular shape by means of orthogonal transformations . By Householder reflections from left is transformed to upper triangular form. Applying the same transformations simultaneously on, this results (illustrating an example of the size of (4,4)) . ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle n-1}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle A={\begin{pmatrix}*&*&*&*\\{*}&*&*&*\\{*}&*&*&*\\{*}&*&*&*\end{pmatrix}},B={\begin{pmatrix}*&*&*&*\\0&*&*&*\\0&0&*&*\\0&0&0&*\end{pmatrix}}}$

If we now find a Givens rotation gives the applied from the left of A, the following matrix: . So you get for . ${\displaystyle A={\begin{pmatrix}*&*&*&*\\{*}&*&*&*\\{*}&*&*&*\\0&*&*&*\end{pmatrix}}}$ ${\displaystyle B={\begin{pmatrix}*&*&*&*\\0&*&*&*\\0&0&*&*\\0&0&*&*\end{pmatrix}}}$

By using a Givens rotation from the right upper triangular shape can of be restored without destroying the zero on the left lower position of A: . ${\displaystyle B}$ ${\displaystyle A={\begin{pmatrix}*&*&*&*\\{*}&*&*&*\\{*}&*&*&*\\0&*&*&*\end{pmatrix}},B={\begin{pmatrix}*&*&*&*\\0&*&*&*\\0&0&*&*\\0&0&0&*\end{pmatrix}}}$

By creating zeros in columns in the same way, an upper Hessenberg matrix is ​​obtained : ${\displaystyle A}$

1. ${\displaystyle A={\begin{pmatrix}*&*&*&*\\{*}&*&*&*\\0&*&*&*\\0&*&*&*\end{pmatrix}},B={\begin{pmatrix}*&*&*&*\\0&*&*&*\\0&*&*&*\\0&0&0&*\end{pmatrix}}}$
2. ${\displaystyle A={\begin{pmatrix}*&*&*&*\\{*}&*&*&*\\0&*&*&*\\0&*&*&*\end{pmatrix}},B={\begin{pmatrix}*&*&*&*\\0&*&*&*\\0&0&*&*\\0&0&0&*\end{pmatrix}}}$
3. ${\displaystyle A={\begin{pmatrix}*&*&*&*\\{*}&*&*&*\\0&*&*&*\\0&0&*&*\end{pmatrix}},B={\begin{pmatrix}*&*&*&*\\0&*&*&*\\0&0&*&*\\0&0&*&*\end{pmatrix}}}$
4. ${\displaystyle A={\begin{pmatrix}*&*&*&*\\{*}&*&*&*\\0&*&*&*\\0&0&*&*\end{pmatrix}},B={\begin{pmatrix}*&*&*&*\\0&*&*&*\\0&0&*&*\\0&0&0&*\end{pmatrix}}}$.

If -invariant subspaces are to be calculated, it is necessary that the product of the transformation matrices that from the left, respectively , and are applied in a matrix , and the product of the transformation matrices that are applied from the right in a matrix store. ${\displaystyle (A,B)}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle Q}$ ${\displaystyle Z}$

QZ algorithm with implicit shifts

1. ${\displaystyle q:=0}$

2. while do ${\displaystyle q<n}$

3. Determine all with . For this set . ${\displaystyle j\in \{1,\cdots ,n-1\}}$ ${\displaystyle |a_{j+1,j}|\leq \varepsilon (|a_{j,j}|+|a_{j+1,j+1}|)}$ ${\displaystyle j}$ ${\displaystyle a_{j,j+1}=0}$

4. Deflation : Find the minimum and the maximum with and define such that:, where and is of the upper Hessenberg form , of the unreduced upper Hessenberg form and of the quasi-upper triangular form. ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle p,q\in \{1,\cdots ,n\}}$ ${\displaystyle m:=n-p-q}$ ${\displaystyle A={\begin{pmatrix}A_{11}&A_{12}&A_{13}\\0&A_{22}&A_{23}\\0&0&A_{33}\end{pmatrix}}}$ ${\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}}$ ${\displaystyle A_{11}}$ ${\displaystyle A_{22}}$ ${\displaystyle A_{33}}$

5. Partition like , d. H. , where top are triangular matrices. ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle B={\begin{pmatrix}B_{11}&B_{12}&B_{13}\\0&B_{22}&B_{23}\\0&0&B_{33}\end{pmatrix}}}$ ${\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. Bring into upper shear form : Find orthogonal such that in shear form and upper triangular matrix is. ${\displaystyle A_{33}}$ ${\displaystyle Q_{33},Z_{33}}$ ${\displaystyle A_{33}:=Q_{33}^{T}A_{33}Z_{33}}$ ${\displaystyle B_{33}:=Q_{33}^{T}B_{33}Z_{33}}$

If necessary: ​​update from and : , . ${\displaystyle Q}$ ${\displaystyle Z}$ ${\displaystyle Q:=Q\mathrm {diag} (I_{p},I_{m},Q_{33})}$ ${\displaystyle Z:=Z\mathrm {diag} (I_{p},I_{m},Z_{33})}$

7. if : ${\displaystyle q<n}$

if ${\displaystyle det(B_{22})=0}$

Transform from the right using a Givens rotation to move the rank deficiency from to . Due to the cancellation of there is no longer an unreduced Hessenberg matrix, so it is increased and there is the possibility that the new partitioning is regular. ${\displaystyle a_{n-q,n-q-1}=0}$ ${\displaystyle B_{22}}$ ${\displaystyle B_{33}}$ ${\displaystyle a_{n-q,n-q-1}}$ ${\displaystyle A_{22}}$ ${\displaystyle q}$ ${\displaystyle B_{22}}$

else

Make a implicit QZ-step of: . ${\displaystyle A_{22},B_{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

Choice of shifts

9. Determine shifts as eigenvalues of ${\displaystyle a,b}$ ${\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. Determine ${\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}}}$

The implicit QZ step

11. Find orthogonal with ${\displaystyle Q_{1}}$ ${\displaystyle Q_{1}^{T}{\begin{pmatrix}\alpha \\\beta \\\gamma \end{pmatrix}}={\begin{pmatrix}*\\0\\0\end{pmatrix}}}$

For now follows . ${\displaystyle B_{22}}$ ${\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}}}$

The aim is now to restore the triangular shape from the right by means of orthogonal transformations (Householder reflections): ${\displaystyle B_{22}}$

12. Find orthogonal with . Then find orthogonal such that ${\displaystyle Z_{1}\in \mathbb {R} ^{3\times 3}}$ ${\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}}}$ ${\displaystyle Z_{1}'\in \mathbb {R} ^{2\times 2}}$

${\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}}}$.

For now we have: . Ie, the Hessenberg structure of is destroyed by an undesirable 2x2 "hump". ${\displaystyle A_{22}}$ ${\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}}}$ ${\displaystyle A_{22}}$

13. This hump can be eliminated from the left by elementary, orthogonal transformations (e.g. Householder reflections). So find orthogonal , with ${\displaystyle Q''_{1}\in \mathbb {R} ^{3\times 3}}$ ${\displaystyle Q_{1}'\in \mathbb {R} ^{3\times 3}}$

${\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}}}$. The vectors and are transformed one after the other . ${\displaystyle {\begin{pmatrix}a_{21}\\a_{31}\\a_{41}\end{pmatrix}}}$ ${\displaystyle {\begin{pmatrix}a_{32}\\a_{42}\\a_{52}\end{pmatrix}}}$ ${\displaystyle {\begin{pmatrix}*\\0\\0\end{pmatrix}}}$

However, applying the transformation to from the left yields ${\displaystyle {\tilde {B}}_{22}}$

${\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. a hump has now been created one position lower along the diagonal.

14. Repeat steps 11-13 until there is again the upper Hessenberg and the upper triangular structure again. Similar to the QR algorithm, this process is also known as "hump chasing" or "bulge chasing". The elimination of a hump in at the diagonal position j with transformations from the left leads to a hump at the corresponding position in . If this hump is eliminated with transformations from the right, this leads to a hump in at the diagonal position j + 1 etc. ${\displaystyle A_{22}}$ ${\displaystyle B_{22}}$ ${\displaystyle B_{22}}$ ${\displaystyle A_{22}}$ ${\displaystyle B_{22}}$

15. After taking steps, the goal is achieved and it results . Analogously one obtains ${\displaystyle m-2}$ ${\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}}$

${\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}')}$.

If -invariant subspaces are required, it is necessary the matrices and aufzudatieren: , ${\displaystyle (A,B)}$ ${\displaystyle {Q}}$ ${\displaystyle Z}$ ${\displaystyle Q:=Q\mathrm {diag} (I_{p},Q_{22},I_{q})}$ ${\displaystyle Z:=Z\mathrm {diag} (I_{p},Z_{22},I_{q})}$

16. end while

Determination of the eigenvalues

In most cases the QZ algorithm converges to its generalized, real Schur form. For scalar diagonal blocks in A applies and if . If there is one for which is, so is . Diagonal blocks of refer (analogous to the QR algorithm) to pairs of complex conjugate eigenvalues . ${\displaystyle (A,B)}$ ${\displaystyle \lambda _{i}={\frac {a_{ii}}{b_{ii}}}:b_{ii}\neq 0}$ ${\displaystyle \lambda _{i}=\infty }$ ${\displaystyle b_{ii}=0}$ ${\displaystyle i}$ ${\displaystyle a_{ii}=b_{ii}=0}$ ${\displaystyle \Lambda (A,B)=\mathbb {C} }$ ${\displaystyle 2\times 2}$ ${\displaystyle A}$ ${\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)}$

literature

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