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