362 CHAPTER 15. NUMERICAL METHODS, EIGENVALUES

15.6 MATLAB And The QR AlgorithmThis is most easily done in MATLAB. Given H you would then just do the QR algorithmon this matrix to get eigenvalues. The syntax for doing this is as follows. Here 50 iterationsare being used.

H=[enter H here]hold onfor k=1:50[Q,R]=qr(H);H=R*Q;endQRH

Of course if MATLAB already knows H then you don’t need to re-enter it. This happenswhen you use MATLAB to find an upper Hessenberg matrix similar to the original matrix.This is discussed later.

The main significance of this algorithm is in the following easy but important theorem.

Theorem 15.6.1 Let A be any n×n complex matrix and let {Ak} be the sequence of matri-ces described above by the QR algorithm. Then each of these matrices is unitarily similarto A.

Proof: Clearly A0 is orthogonally similar to A because they are the same thing. Supposethen that

Ak−1 = Q∗AQ

Then from the algorithm,Ak−1 = QkRk, Rk = Q∗kAk−1

Therefore, from the algorithm,

Ak ≡ RkQk = Q∗kAk−1Qk = Q∗kQ∗AQQk = (QQk)∗AQQk,

and so Ak is unitarily similar to A also. ■Although the sequence {Ak} may fail to converge, it is nevertheless often the case that

for large k, Ak is of the form

Ak =

Bk ∗

. . .

e Br

where the Bi are blocks which run down the diagonal of the matrix, and all of the entriesbelow this block diagonal are very small. Then letting TB denote the matrix obtained bysetting all of these small entries equal to zero, one can argue, using methods of analysis,that the eigenvalues of Ak are close to the eigenvalues of TB. From Lemma 15.5.1 the