372 CHAPTER 14. NUMERICAL METHODS, EIGENVALUES

This algorithm was proposed by Francis in 1961. The sequence {Ak} is the desiredsequence of iterates. Now with the above definition of the algorithm, here are its properties.The next lemma shows each of the Ak is unitarily similar to A and the amazing thing aboutthis algorithm is that often it becomes increasingly easy to find the eigenvalues of the Ak.

Lemma 14.2.3 Let A be an n×n matrix and let the Qk and Rk be as described in the algo-rithm. Then each Ak is unitarily similar to A and denoting by Q(k) the product Q1Q2 · · ·Qk

and R(k) the product RkRk−1 · · ·R1, it follows that

Ak = Q(k)R(k)

(The matrix on the left is A raised to the kth power.)

A = Q(k)AkQ(k)∗, Ak = Q(k)∗AQ(k).

Proof: From the algorithm, Rk+1 = Ak+1Q∗k+1 and so

Ak = Qk+1Rk+1 = Qk+1Ak+1Q∗k+1

Now iterating this, it follows

Ak−1 = QkAkQ∗k = QkQk+1Ak+1Q

∗k+1Q

∗k

Ak−2 = Qk−1Ak−1Q∗k−1 = Qk−1QkQk+1Ak+1Q

∗k+1Q

∗kQ

∗k−1

etc. Thus, after k − 2 more iterations,

A = Q(k+1)Ak+1Q(k+1)∗

The product of unitary matrices is unitary and so this proves the first claim of the lemma.Now consider the part about Ak. From the algorithm, this is clearly true for k = 1.

(A1 = QR) Suppose then that

Ak = Q1Q2 · · ·QkRkRk−1 · · ·R1

What was just shown indicated

A = Q1Q2 · · ·Qk+1Ak+1Q∗k+1Q

∗k · · ·Q∗

1

and now from the algorithm, Ak+1 = Rk+1Qk+1 and so

A = Q1Q2 · · ·Qk+1Rk+1Qk+1Q∗k+1Q

∗k · · ·Q∗

1

ThenAk+1 = AAk =

A︷ ︸︸ ︷Q1Q2 · · ·Qk+1Rk+1Qk+1Q

∗k+1Q

∗k · · ·Q∗

1Q1 · · ·QkRkRk−1 · · ·R1

= Q1Q2 · · ·Qk+1Rk+1RkRk−1 · · ·R1 ≡ Q(k+1)R(k+1) ■

Here is another very interesting lemma.

Lemma 14.2.4 Suppose Q(k), Q are unitary and Rk is upper triangular such that the di-agonal entries on Rk are all positive and

Q = limk→∞

Q(k)Rk

Thenlimk→∞

Q(k) = Q, limk→∞

Rk = I.

Also the QR factorization of A is unique whenever A−1 exists.