430 CHAPTER 15. NUMERICAL METHODS, EIGENVALUES
By Gerschgorin’s theorem, the eigenvalues are pretty close to the diagonal entries ofthe above matrix. Note I didn’t use the theorem, just Lemma 15.3.3 and Gerschgorin’stheorem to verify the eigenvalues are close to the above numbers. The eigenvectors areclose to .79785
.48995
.35126
,
−.59912.70912.37176
,
−6.6943×10−2
−.50706.85931
Lets check one of these.
5 1 11 3 21 2 1
−6.0571
1 0 00 1 00 0 1
.79785
.48995
.35126
=
−2.1972×10−3
2.5439×10−3
1.3931×10−3
≊ 0
00
Now lets see how well the smallest approximate eigenvalue and eigenvector works.
5 1 11 3 21 2 1
− (−.2579)
1 0 00 1 00 0 1
−6.6943×10−2
−.50706.85931
=
2.704×10−4
−2.7377×10−4
−1.3695×10−4
≊ 0
00
For practical purposes, this has found the eigenvalues and eigenvectors.
15.3.3 The QR Algorithm In The General CaseIn the case where A has distinct positive eigenvalues it was shown above that under rea-sonable conditions related to a certain matrix having an LU factorization the QR algorithmproduces a sequence of matrices {Ak}which converges to an upper triangular matrix. Whatif A is just an n×n matrix having possibly complex eigenvalues but A is nondefective? Whathappens with the QR algorithm in this case? The short answer to this question is that theAk of the algorithm typically cannot converge. However, this does not mean the algorithmis not useful in finding eigenvalues. It turns out the sequence of matrices {Ak} have theappearance of a block upper triangular matrix for large k in the sense that the entries belowthe blocks on the main diagonal are small. Then looking at these blocks gives a way toapproximate the eigenvalues.
First it is important to note a simple fact about unitary diagonal matrices. In whatfollows Λ will denote a unitary matrix which is also a diagonal matrix. These matricesare just the identity matrix with some of the ones replaced with a number of the form eiθ
for some θ . The important property of multiplication of any matrix by Λ on either sideis that it leaves all the zero entries the same and also preserves the absolute values of the