Schur decomposition#Generalized Schur decomposition

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

The generalized eigenvalue problem is equivalent to the eigenvalue problem has to be with and is invertible. However, it is not explicitly calculated the matrix so as not to worsen the condition of the problem, but and placed simultaneously by similarity transformations ( Givens rotations and Householder reflections ) in generalized Schur form.

Given a matrix pencils Wanted are orthogonal matrices and so is of generalized Schur form, i.e., is quasi- upper triangular form and is of upper triangular form. In the case is always of upper triangular form. From the generalized Schur form can then be used to determine the eigenvalues ​​and invariant subspaces and of the matrix pencil.

Preliminary transformation

The aim of this step is to bring the matrix by orthogonal transformations on upper Hesse mountain shape and the upper triangular matrix. By Householder reflections from the left is transformed to upper triangular form. Applying the same transformations simultaneously on to ( illustrating an example of the quantity ( 4.4 ) ) gives:.

We now find a Givens rotation that results from left applied to A, the following matrix: . Thus one obtains for.

By applying a Givens rotation from the right upper triangular form of can be restored without the zero at the lower-left position of A to destroy.

By analogous column-wise generation of zeros in one obtains an upper Hessenberg matrix:

If -invariant subspaces are to be calculated, it is necessary to store the product of the transformation matrices that are applied from left on and, in a matrix and the product of the transformation matrices that are applied from right, in a matrix.

QZ algorithm with implicit shifts

1

2 while do

3 Determine all with. For this set.

4 Deflation: Find minimum and maximum with and defining, so that: where and of the upper Hessenberg form of unreduced upper Hessenberg form and quasi- upper triangular form.

5 to partition such, that is, where are upper triangular.

6 Bring in upper Schur form: Find orthogonal so that is in Schur form and upper triangular matrix.

If necessary: ​​Aufdatieren of and: .

7 if:

If

Transform using a Givens rotation from right to move the rank deficiency of on. Due to the cancellation of unreduced Hessenberg matrix is no more, thus increasing and there is the possibility that in the new partitioning is regular.

Else

Make a implicit QZ- step of:.

End if

8 end if

Choosing the shifts

9 Determine shifts as eigenvalues ​​of the lower 2 × 2 block of

10 Determine

The implicit QZ- step

11 Find orthogonal with

For now follows.

The objective now is to restore the triangular shape of by orthogonal transformations ( Householder reflections ) from the right:

12 Find orthogonal with.

For arises now: .

13 Find orthogonal with.

For now arises analogous to multiplication by:

.

14 We repeat steps 11-14 now for the vector, then for, etc. In this way "walk" the non-zero elements below the secondary diagonal of step by step from the matrix. This process is referred to as the " Bulge - Chasing ".

After 15 steps is again present in upper Hessenberg form. For results now. Are obtained analogously for:

.

If invariant subspaces are required, it is necessary that matrices and aufzudatieren:

16 end while

Determination of the eigenvalues

In most cases, the QZ algorithm converges towards its Schur form. It is true. If one exists, is for, then. If and, the -th eigenvalue is infinite.