Error Analysis and Accuracy

The remarks in this section are for ordinary eigenvalue problems. Except in special cases, functions will not return the exact eigenvalue-eigenvector pair for the ordinary eigenvalue problem Ax = λ x. Typically, the computed pair

\[\tilde{x}, \tilde{\lambda}\]

is an exact eigenvector-eigenvalue pair for a “nearby” matrix A+E. Information about E is known only in terms of bounds of the form \(\| E \|_2 = f(n)\|A\|_2 \epsilon\). The value of f(n) depends on the algorithm, but is typically a small fractional power of n. The parameter ϵ is the machine precision. By a theorem due to Bauer and Fike, (see [1], p. 342),

\[\min |\tilde{\lambda} - \lambda| \le \kappa(X) \|E\|_2 \;\text{for all} \;\lambda \; \text{in} \; \sigma(A),\]

where σ (A) is the set of all eigenvalues of A (called the spectrum of A), X is the matrix of eigenvectors, \(\|\cdot\|_2\) the Euclidean length, and κ (X) is the condition number of X defined as \(\kappa(X) =\|X\|_2 \|X^{-1}\|_2\). If A is a real symmetric or complex Hermitian matrix, then its eigenvector matrix X is respectively orthogonal or unitary. For these matrices, κ (X) = 1.

The accuracy of the computed eigenvalues \(\tilde{\lambda}_j\) and eigenvectors \(\tilde{x}_j\) can be checked by computing their performance index τ. The performance index is defined to be

\[\tau = \max_{1 \le j \le n} \frac{\|A\tilde{x}_j -\tilde{\lambda}_j \tilde{x}_j\|_2}{n \epsilon \|A\|_2 \|\tilde{x}_j\|_2}\,,\]

where ϵ is again the machine precision.

The performance index τ is related to the error analysis because

\[\|E \tilde{x}_j\|_2 = \|A \tilde{x}_j - \tilde{\lambda}_j \tilde{x}_j\|_2\]

where E is the nearby matrix discussed above.

While the exact value of τ is precision and data dependent, the performance of an eigensystem analysis function is defined as excellent if τ < 1, good if 1 ≤ τ ≤ 100, and poor if τ > 100. This is an arbitrary definition, but large values of τ can serve as a warning that there is significant error in the calculation.

If the condition number κ (X) of the eigenvector matrix X is large, there can be large errors in the eigenvalues even if τ is small. In particular, it is often difficult to recognize near multiple eigenvalues or unstable mathematical problems from numerical results. This facet of the eigenvalue problem is often difficult for users to understand. Suppose the accuracy of an individual eigenvalue is desired. This can be answered approximately by computing the condition number of an individual eigenvalue (see [1], pp. 344-345). For matrices A, such that the computed array of normalized eigenvectors X is invertible, the condition number of \(\lambda_j\) is

\[\kappa_j = \|e_j^T X^{-1}\|\,,\]

the Euclidean length of the j -th row of \(X^{-1}\). Users can choose to compute this matrix using function imsl.linalg.lu_inv(). An approximate bound for the accuracy of a computed eigenvalue is then given by \(\kappa_j \epsilon \|A\|\). To compute an approximate bound for the relative accuracy of an eigenvalue, divide this bound by \(|\lambda_j|\).

References

[1]	(1, 2) Golub, G.H., and C.F. Van Loan (1989), Matrix Computations, Second Edition, The Johns Hopkins University Press, Baltimore, Maryland.