15.6. MATLAB AND THE QR ALGORITHM 363
eigenvalues of TB are the eigenvalues of the blocks Bi. Thus, the eigenvalues of A are thesame as those of Ak and these are close to the eigenvalues of TB.
In proving things about this algorithm and also for the sake of convenience, here is atechnical result.
Corollary 15.6.2 For Qk,Rk,Ak given in the QR algorithm,
A = Q1 · · ·QkAkQ∗k · · ·Q∗1 (15.3)
For Q(k) ≡ Q1 · · ·Qk and R(k) ≡ Rk · · ·R1, it follows that
Ak = Q(k)R(k)
Here Ak is the usual thing, A raised to the kth power.
Proof: From the algorithm,
A = A0 = Q1R1, Q∗1A0 = R1, A1 ≡ R1Q1 = Q∗1AQ1
HenceQ1A1Q∗1 = A
Suppose the formula 15.3 holds for k. Then from the algorithm,
Ak = Qk+1Rk+1, Rk+1 = Q∗k+1Ak, Ak+1 = Rk+1Qk+1 = Q∗k+1AkQk+1
Hence Qk+1Ak+1Q∗k+1 = Ak and so
A = Q1 · · ·QkAkQ∗k · · ·Q∗1 = Q1 · · ·QkQk+1Ak+1Q∗k+1Q∗k · · ·Q∗1
This shows the first part.The second part is clearly true from the algorithm if k = 1. Then from the first part and
the algorithm,
A = Q1 · · ·QkQk+1Ak+1Q∗k+1Q∗k · · ·Q∗1 = Q1 · · ·QkQk+1Rk+1
I︷ ︸︸ ︷Qk+1Q∗k+1Q∗k · · ·Q∗1
It follows that
Ak+1 = AAk = Q1 · · ·QkQk+1Rk+1Q∗k · · ·Q∗1Q(k)R(k)
= Q(k+1)Rk+1
(Q(k)
)∗Q(k)R(k)
HenceAk+1 = Q(k+1)Rk+1R(k) = Q(k+1)R(k+1) ■
Now suppose that A−1 exists. How do two QR factorizations compare? Since A−1
exists, it would require that if A=QR, then R−1 must exist. Now an upper triangular matrixhas inverse which is also upper triangular. This follows right away from the algorithmpresented early in the book for finding the inverse. If A = Q1R1 = Q2R2, then Q∗1Q2 =R1R−1
2 and so R1R−12 is an upper triangular matrix which is also unitary and in addition has
all positive entries down the diagonal. For simplicity, call it R. Thus R is upper triangular