15.5. THE QR ALGORITHM 361
15.5 The QR Algorithm15.5.1 Basic ConsiderationsThe QR algorithm is one of the most remarkable techniques for finding eigenvalues. In thissection, I will discuss this method. To see more on this algorithm, consult Golub and VanLoan [6]. For an explanation of why the algorithm works see Wilkinson [18]. There isalso more discussion in [13]. This will only discuss real matrices for the sake of simplicity.Also, there is a lot more to this algorithm than will be presented here. First here is anintroductory lemma.
Lemma 15.5.1 Suppose A is a block upper triangular matrix,
A =
B1 ∗
. . .
0 Br
This means that the Bi are ri×ri matrices whose diagonals are subsets of the main diagonalof A. Then σ (A) = ∪r
i=1σ (Bi).
Proof: Say Q∗i BiQi = Ti where Ti is upper triangular. Such unitary matrices exist bySchur’s theorem. Then consider the similarity transformation,
Q∗1 0. . .
0 Q∗r
B1 ∗. . .
0 Br
Q1 0. . .
0 Qr
By block multiplication this equals
Q∗1 0. . .
0 Q∗r
B1Q1 ∗. . .
0 BrQr
=
Q∗1B1Q1 ∗
. . .
0 Q∗r BrQr
=
T1 ∗
. . .
0 Tr
Now this is a real upper triangular matrix and the eigenvalues of A consist of the union ofthe eigenvalues of the Ti which is the same as the union of the eigenvalues of the Bi. ■
Here is the description of the great and glorious QR algorithm.
The QR Algorithm
Let A be an n×n real matrix. Let A0 = A. Suppose that Ak−1 has been found. To findAk let
Ak−1 = QkRk, Ak = RkQk,
where QkRk is a QR factorization of Ak−1. Thus R is upper triangular with nonnegativeentries on the main diagonal and Q is real and unitary (orthogonal).