16.3.4 Upper Hessenberg Matrices
It seems like most of the attention to the QR algorithm has to do with finding ways to get it to
“converge” faster. Great and marvelous are the clever tricks which have been proposed to do
this but my intent is to present the basic ideas, not to go in to the numerous refinements of
this algorithm. However, there is one thing which should be done. It involves reducing to the
case of an upper Hessenberg matrix which is one which is zero below the main sub diagonal.
The following shows that any square matrix is unitarily similar to such an upper Hessenberg
Let A be an invertible n × n matrix. Let Q1′ be a unitary matrix
The vector Q1′ is multiplying is just the bottom n − 1 entries of the first column of A. Then let Q1
Now let Q2′ be the n − 2 × n − 2 matrix which does to the first column of A1 the same sort of thing
that the n − 1 × n − 1 matrix Q1′ did to the first column of A. Let
where I is the 2 × 2 identity. Then applying block multiplication,
where A2 is now an n− 2 ×n− 2 matrix. Continuing this way you eventually get a unitary matrix Q which
is a product of those discussed above such that
This matrix equals zero below the subdiagonal. It is called an upper Hessenberg matrix.
It happens that in the QR algorithm, if Ak is upper Hessenberg, so is Ak+1. To see this, note that the
matrix is upper Hessenberg means that Aij = 0 whenever i − j ≥ 2.
where Ak = QkRk. Therefore as shown before,
Let the ijth entry of Ak be aijk. Then if i − j ≥ 2
It is given that apqk = 0 whenever p − q ≥ 2. However, from the above sum,
and so the sum equals 0.
Since upper Hessenberg matrices stay that way in the algorithm and it is closer to being upper
triangular, it is reasonable to suppose the QR algorithm will yield good results more quickly for this upper
Hessenberg matrix than for the original matrix. This would be especially true if the matrix is good sized.
The other important thing to observe is that, starting with an upper Hessenberg matrix, the algorithm will
restrict the size of the blocks which occur to being 2 × 2 blocks which are easy to deal with. These blocks
allow you to identify the eigenvalues.
Example 16.3.10 Let A =
a symmetric matrix. Thus it has real
eigenvalues and can be diagonalized. Find its eigenvalues.
As explained above, there is an upper Hessenberg matrix. Matlab can find it using the techniques given
above pretty quickly. The syntax is as follows.
Then the Hessenberg matrix similar to A is
Note how it is symmetric also. This will always happen when you begin with a symmetric matrix. Now use
the QR algorithm on this matrix. The syntax is as follows in Matlab.
You already have H and matlab knows about it so you don’t need to enter H again. This yields the
following matrix similar to the original one.
The eigenvalues of this matrix are
You might want to check that the product of these equals the determinant of the matrix and that the sum
equals the trace of the matrix. In fact, this works out very well. To find eigenvectors, you could use the
shifted inverse power method. They will be different for the Hessenberg matrix than for the original matrix