15.3. THE QR ALGORITHM 429

because formula 15.11 is unaffected by replacing Q with Q′. ■When using the QR algorithm, it is not necessary to check technical condition about

S−1 having an LU factorization. The algorithm delivers a sequence of matrices which aresimilar to the original one. If that sequence converges to an upper triangular matrix, thenthe algorithm worked. Furthermore, the technical condition is sufficient but not necessary.The algorithm will work even without the technical condition.

Example 15.3.7 Find the eigenvalues and eigenvectors of the matrix

A =

 5 1 11 3 21 2 1

It is a symmetric matrix but other than that, I just pulled it out of the air. By Lemma

15.3.3 it follows Ak = Q(k)T AQ(k). And so to get to the answer quickly I could have thecomputer raise A to a power and then take the QR factorization of what results to get thekth iteration using the above formula. Lets pick k = 10.

 5 1 11 3 21 2 1

10

=

 4.2273×107 2.5959×107 1.8611×107

2.5959×107 1.6072×107 1.1506×107

1.8611×107 1.1506×107 8.2396×106

Now take QR factorization of this. The computer will do that also.This yields  .79785 −.59912 −6.6943×10−2

.48995 .70912 −.50706

.35126 .37176 .85931

 · 5.2983×107 3.2627×107 2.338×107

0 1.2172×105 71946.0 0 277.03

Next it follows

A10 =

 .79785 −.59912 −6.6943×10−2

.48995 .70912 −.50706

.35126 .37176 .85931

T

·

 5 1 11 3 21 2 1

 .79785 −.59912 −6.6943×10−2

.48995 .70912 −.50706

.35126 .37176 .85931

and this equals 6.0571 3.698×10−3 3.4346×10−5

3.698×10−3 3.2008 −4.0643×10−4

3.4346×10−5 −4.0643×10−4 −.2579

