426 CHAPTER 15. NUMERICAL METHODS, EIGENVALUES

15.3.2 The Case Of Real EigenvaluesWith 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 11 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 λ

is sufficiently large and positive that A + λ I has all positive eigenvalues. (Recall Ger-schgorin’s theorem.) Then if µ is an eigenvalue of A+λ I with

(A+λ I)x= µx

then Ax=(µ−λ )x so to find the eigenvalues of A you just subtract λ from the eigenvaluesof A+λ I. Thus there is no loss of generality in assuming at the outset that the eigenvaluesof A are all positive. Here is the theorem. It involves a technical condition which will oftenhold. The proof presented here follows [42] and is a special case of that presented in thisreference.

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 15.3.5 Let A be a real matrix having eigenvalues

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

and let A = SDS−1 where

D =

λ 1 0

. . .

0 λ n

and suppose S−1 has an LU factorization. Then the matrices Ak in the QR algorithmdescribed above converge to an upper triangular matrix T ′ having the eigenvalues of A,λ 1, · · · ,λ n descending on the main diagonal. The matrices Q(k) converge to Q′, an orthog-onal matrix which equals Q except for possibly having some columns multiplied by −1 forQ the unitary part of the QR factorization of S, S = QR,and

limk→∞

Ak = T ′ = Q′T AQ′

Proof: From Lemma 15.3.3

Ak = Q(k)R(k) = SDkS−1 (15.9)