Algorithm 517: A Program for Computing the Condition Numbers of Matrix Eigenvalues Without Computing Eigenvectors [F2]
S. P. Chan, R. Feldman, Beresford Ν. Parlett · ACM Transactions on Mathematical Software · 1977
Background1.1 The Sensitivity of Eigenvalues.Several good programs are available for the computation of the eigenvalues of real and complex matrices [2, 3,7].Because of the limitations of finite precision arithmetic, these programs cannot produce, in general, the exact eigenvalues of the given matrix A. However the computed numbers are always (very close to) the eigenvalues of a matrix A -k E which is very close to A. This matrix E is not unique and error analyses ~6] have shown the existence of E's with satisfactorily small upper bounds on IIE II / II A If.Here I1" II denotes an appropriate matrix norm.It follows from these remarks that a good program will not always deliver accurate approximations to the eigenvalues of A. It can happen that some, or all, of the eigenvalues are very sensitive to changes in the matrix elements; so some, or all, of the eigenvalues of A ~-E may differ sharply from those of A. Actually this is true only for non-normal matrices.Real symmetric matrices--indeed all normal matrices--determine their eigenvalues very well; the change induced in an eigenvalue of such an A cannot exceed the spectral norm of E (which is defined below).Two questions arise: How can this sensitivity be measured, and how cheaply can it be computed?Simple eigenvalues.To any simple eigenvalue ~ of A there correspond both a