374 CHAPTER 14. NUMERICAL METHODS, EIGENVALUES

and so from the first part, Rk → I but Rk = R and so R = I. Thus applying this toQ∗Q′ = R (R′)

−1yields both sides equal I. ■

A case of all this is of great interest. Suppose A has a largest eigenvalue λ which isreal. Then An is of the form

(An−1a1, · · · , An−1an

)and so likely each of these columns

will be pointing roughly in the direction of an eigenvector of A which corresponds to thiseigenvalue. Then when you do the QR factorization of this, it follows from the fact that Ris upper triangular, that the first column of Q will be a multiple of An−1a1 and so will endup being roughly parallel to the eigenvector desired. Also this will require the entries belowthe top in the first column of An = QTAQ will all be small because they will be of the formqTi Aq1 ≊ λqT

i q1 = 0. Therefore, An will be of the form(λ′ a

e B

)

where e is small. It follows that λ′ will be close to λ and q1 will be close to an eigenvector forλ. Then if you like, you could do the same thing with the matrix B to obtain approximationsfor the other eigenvalues. Finally, you could use the shifted inverse power method to getmore exact solutions.

14.2.2 The Case of Real Eigenvalues

With these lemmas, it is possible to prove that for the QR algorithm and certain conditions,the sequence Ak converges pointwise to an upper triangular matrix having the eigenvaluesof A down the diagonal. I will assume all the matrices are real here.

This convergence won’t always happen. Consider for example the matrix

(0 1

1 0

).

You can verify quickly that the algorithm will return this matrix for each k. The problemhere is that, although the matrix has the two eigenvalues −1, 1, they have the same absolutevalue. The QR algorithm works in somewhat the same way as the power method, exploitingdifferences in the size of the eigenvalues.

If A has all real eigenvalues and you are interested in finding these eigenvalues alongwith the corresponding eigenvectors, you could always consider A + λI instead where λ issufficiently large and positive that A+λI has all positive eigenvalues. (Recall Gerschgorin’stheorem.) Then if µ is an eigenvalue of A+ λI with

(A+ λI)x = µx

thenAx = (µ− λ)x

so to find the eigenvalues of A you just subtract λ from the eigenvalues of A + λI. Thusthere is no loss of generality in assuming at the outset that the eigenvalues of A are allpositive. Here is the theorem. It involves a technical condition which will often hold. Theproof presented here follows [27] and is a special case of that presented in this reference.

Before giving the proof, note that the product of upper triangular matrices is uppertriangular. If they both have positive entries on the main diagonal so will the product.Furthermore, the inverse of an upper triangular matrix is upper triangular. I will use thesesimple facts without much comment whenever convenient.

Theorem 14.2.5 Let A be a real matrix having eigenvalues

λ1 > λ2 > · · · > λn > 0