380 CHAPTER 14. NUMERICAL METHODS, EIGENVALUES

for which |λi| = |λj | while Ek → 0. (Note the entries of Lk are all bounded independent ofk but some may fail to converge.) Then

Q(k)R(k) = S (Lk + Ek)DkU

LetSLk = QkRk (14.16)

where this is the QR factorization of SLk. Then

Q(k)R(k) = (QkRk + SEk)DkU

= Qk

(I +Q∗

kSEkR−1k

)RkD

kU

= Qk (I + Fk)RkDkU

where Fk → 0. Let I + Fk = Q′kR

′k. Then Q

(k)R(k) = QkQ′kR

′kRkD

kU. By Lemma 14.2.4

Q′k → I and R′

k → I. (14.17)

Now let Λk be a diagonal unitary matrix which has the property that Λ∗kD

kU is an uppertriangular matrix which has all the diagonal entries positive. Then

Q(k)R(k) = QkQ′kΛk (Λ

∗kR

′kRkΛk) Λ

∗kD

kU

That matrix in the middle has all positive diagonal entries because it is itself an uppertriangular matrix, being the product of such, and is similar to the matrix R′

kRk which isupper triangular with positive diagonal entries. By Lemma 14.2.4 again, this time using theuniqueness assertion,

Q(k) = QkQ′kΛk, R

(k) = (Λ∗kR

′kRkΛk) Λ

∗kD

kU

Note the term QkQ′kΛk must be real because the algorithm gives all Q(k) as real matrices.

By 14.17 it follows that for k large enough Q(k) ≊ QkΛk where ≊ means the two matricesare close. Recall Ak = Q(k)TAQ(k) and so for large k,

Ak ≊ (QkΛk)∗A (QkΛk) = Λ∗

kQ∗kAQkΛk

As noted above, the form of Λ∗kQ

∗kAQkΛk in terms of which entries are large and small is

not affected by the presence of Λk and Λ∗k. Thus, in considering what form this is in, it

suffices to consider Q∗kAQk.

This could get pretty complicated but I will consider the case where

if |λi| = |λi+1| , then |λi+2| < |λi+1| . (14.18)

This is typical of the situation where the eigenvalues are all distinct and the matrix A is realso the eigenvalues occur as conjugate pairs. Then in this case, Lk above is lower triangularwith some nonzero terms on the diagonal right below the main diagonal but zeros everywhereelse. Thus maybe (Lk)s+1,s ̸= 0 Recall 14.16 which implies

Qk = SLkR−1k (14.19)

where R−1k is upper triangular. Also recall from the definition of S in 14.14, it follows that

S−1AS = D. Thus the columns of S are eigenvectors of A, the ith being an eigenvector forλi. Now from the form of Lk, it follows LkR

−1k is a block upper triangular matrix denoted

by TB and so Qk = STB . It follows from the above construction in 14.15 and the given