Linear Algebra and Analysis

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 matrix.

Let A be an invertible n × n matrix. Let Q₁^′ be a unitary matrix

( ∘ ---------- ) ( ) ( ) ∑nj=2|aj1|2 a | a21 | || || || 0 || Q′1|( ... |) = || 0. || ≡ || . || |( .. |) ( .. ) an1 0 0

The vector Q₁^′ is multiplying is just the bottom n − 1 entries of the first column of A. Then let Q₁ be

( ) 1 0 0 Q ′1

It follows

( ) ( ) a11 a12 ⋅⋅⋅ a1n ( ) 1 0 || a || 1 0 Q1AQ ∗1 = ′ AQ ∗1 = || .. ′ || ′∗ 0 Q1 ( . A 1 ) 0 Q1 0

( ) ∗ ∗ ⋅⋅⋅ ∗ || a || = || . || ( .. A1 ) 0

Now let Q₂^′ be the n − 2 × n − 2 matrix which does to the first column of A₁ the same sort of thing that the n − 1 × n − 1 matrix Q₁^′ did to the first column of A. Let

( ) I 0 Q2 ≡ 0 Q′ 2

where I is the 2 × 2 identity. Then applying block multiplication,

( ∗ ∗ ⋅⋅⋅ ∗ ∗ ) | | || ∗ ∗ ⋅⋅⋅ ∗ ∗ || Q2Q1AQ ∗1Q ∗2 = || 0 ∗ || |( ... ... A |) 2 0 0

where A₂ 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

( ) ∗ ∗ ⋅⋅⋅ ∗ ∗ || ∗ ∗ ⋅⋅⋅ ∗ ∗ || || . || QAQT = || 0 ∗ ∗ .. || |( .. .. ... ... |) . . ∗ 0 0 ∗ ∗

This matrix equals zero below the subdiagonal. It is called an upper Hessenberg matrix.

It happens that in the QR algorithm, if A_k is upper Hessenberg, so is A_k+1. To see this, note that the matrix is upper Hessenberg means that A_ij = 0 whenever i − j ≥ 2.

Ak+1 = RkQk

where A_k = Q_kR_k. Therefore as shown before,

−1 Ak+1 = RkAkR k

Let the ij^th entry of A_k be a_ij^k. Then if i − j ≥ 2

n j ak+1= ∑ ∑ ripakr−1 ij p=iq=1 pq qj

It is  given that a_pq^k = 0 whenever p − q ≥ 2. However, from the above sum,

p− q ≥ i− j ≥ 2

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.

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.

A= [2 1 3;- 5,3,- 2;1,2,3]; [P,H]=hess(A )

Then the Hessenberg matrix similar to A is

( ) − 1.4476 − 4.9048 0 0 || − 4.9048 3.2553 − 2.0479 0 || H = |( 0 − 2.0479 2.1923 − 5.0990|) 0 0 − 5.0990 − 3

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.

H= [enter H here] hold on for k=1:100 [Q,R ]=qr (H ); H=R*Q; end Q R H

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.

( ) 7.4618 0 0 0 || 0 − 6.3804 0 0 || |( 0 0 − 4.419 − .3679 |) 0 0 − .3679 4.3376

The eigenvalues of this matrix are

7.4618,− 6.3804,4.353,− 4.4344

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 A.