×

On estimating the condition of eigenvalues and eigenvectors. (English) Zbl 0631.65030

The author computes condition numbers for a given matrix eigenvalue and the corresponding eigenvector. For this purpose he applies the packages EISPACK and LINPACK. He claims that it requires only \(O(n^ 2)\) flops per eigenpair under the assumption that the matrix is reduced to Hessenberg form. The implementation of the method is discussed and numerical test results are presented.
Reviewer: T.Reginska

MSC:

65F15 Numerical computation of eigenvalues and eigenvectors of matrices
65F35 Numerical computation of matrix norms, conditioning, scaling
15A42 Inequalities involving eigenvalues and eigenvectors
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Bartels, R. S.; Stewart, G. W., A solution of the equation \(AX + XB = C\), Comm. ACM, 15, 820-826 (1972) · Zbl 1372.65121
[2] Bavely, C.; Stewart, G. W., An algorithm for computing reduced subspaces by block diagonalization, SIAM J. Numer. Anal., 16, 359-367 (1979) · Zbl 0413.65034
[3] Businger, P., Numerically stable deflation of Hessenberg and symmetric tridiagonal matrices, BIT, 11, 262-270 (1971) · Zbl 0226.65028
[4] Byers, R., Hamiltonian and symplectic algorithms for the algebraic Riccati equation, (Ph.D. Thesis (1983), Center for Applied Mathematics, Cornell Univ: Center for Applied Mathematics, Cornell Univ Ithaca, N.Y.14853)
[5] Chan, S. P.; Feldman, R.; Parlett, B. N., Algorithm 517—a probram for computing the condition numbers of matrix eigenvalues without computing eigenvectors, ACM Trans. Math. Software, 3, 186-203 (1977) · Zbl 0353.65026
[6] Cline, A. K.; Conn, A. R.; Van Loan, C. F., Generalizing the LINPACK condition estimator, (Cornell Computer Science Tech. Report TR 81-462 (1981)), Ithaca, N.Y. · Zbl 0532.65032
[7] Cline, A. K.; Moler, C. B.; Stewart, G. W.; Wilkinson, J. H., An estimate for the condition number of a matrix, SIAM J. Numer. Anal., 16, 368-375 (1979) · Zbl 0403.65012
[8] Cline, A. K.; Rew, R. K., A set of counterexamples to three condition estimators, SIAM J. Sci. Statis. Comput., 4, 602-611 (1983) · Zbl 0532.65033
[9] Dongarra, J.; Bunch, J. R.; Moler, C. B.; Stewart, G. W., LINPACK User’s Guide (1979), SIAM: SIAM Philadelphia
[10] Dongarra, J.; Moler, C. B.; Wilkinson, J. H., Improving the accuracy of computed eigenvalues and eigenvectors, SIAM J. Numer. Anal, 20, 23-45 (1983) · Zbl 0523.65021
[11] Dongarra, J., Improving the accuracy of computed singular values, SIAM J. Sci. Statist. Comput., 4, 712-719 (1983) · Zbl 0534.65012
[12] Forsythe, G. E.; Moler, C. B., Computer Solution of Linear Algebraic Systems (1967), Prentice-Hall: Prentice-Hall Englewood Cliffs, N.J · Zbl 0154.40401
[13] Gill, P. E.; Golub, G. H.; Murray, W.; Saunders, M. A., Methods for modifying matrix factorizations, Math. Comp., 28, 505-535 (1974) · Zbl 0289.65021
[14] Goldfarb, D., Factorized variable metric methods for unconstrained optimization, Math. Comp., 30, 796-811 (1976) · Zbl 0357.90065
[15] Golub, G. H.; Van Loan, C., Matrix Computations (1983), Johns Hopkins U.P: Johns Hopkins U.P Baltimore · Zbl 0559.65011
[16] Golub, G. H.; Reinsch, C., Singular value decomposition and least squares solutions, Numer. Math., 14, 403-420 (1970) · Zbl 0181.17602
[17] Golub, G. H.; Wilkinson, J. H., Ill-conditioned eigensystems and the computation of the Jordan canonical form, SIAM Rev., 18, 578-619 (1976) · Zbl 0341.65027
[18] Gregory, R.; Karney, D., A Collection of Matrices for Testing Computational Algorithms (1969), Wiley-Interscience: Wiley-Interscience New York
[19] Kagstrom, B.; Ruhe, A., An algorithm for numerical computation of the Jordan normal form of a complex matrix, ACM Trans. Math. Software, 6, 398-419 (1980) · Zbl 0434.65020
[20] Moler, C.; Stewart, G. W., An algorithm for generalized matrix eigenvalue problems, SIAM J. Numer. Anal., 10, 241-256 (1973) · Zbl 0253.65019
[21] O’Leary, D. P., Estimating matrix condition numbers, SIAM J. Sci. Statist. Comput., 1, 205-209 (1980) · Zbl 0445.65024
[22] Ruhe, A., An algorithm for numerical determination of the structure of a general matrix, BIT, 10, 196-216 (1970) · Zbl 0255.65023
[23] Smith, B. T.; Boyle, J. M.; Garbow, B. S.; Ikebe, Y.; Klema, V. C.; Moler, C. B., Matrix Eigensystem Routines—EISPACK Guide (1970), Springer: Springer New York · Zbl 0289.65017
[24] Smith, R. A., The condition numbers of the matrix eigenvalue problem, Numer. Math., 10, 232-240 (1967) · Zbl 0189.47801
[25] Stewart, G. W., On the sensitivity of the eigenvalue problem \(Ax = λ Bx \), SIAM J. Numer. Anal., 9, 669-686 (1972) · Zbl 0252.65026
[26] Stewart, G. W., Error bounds for approximate invariant subspaces of closed linear operators, SIAM J. Numer. Anal., 8, 796-808 (1971) · Zbl 0232.47010
[27] Stewart, G. W., Error and perturbation bounds for subspaces associated with certain eigenvalue problems, SIAM Rev., 15, 727-764 (1973) · Zbl 0297.65030
[28] Stewart, G. W., Introduction to Matrix Computations (1973), Academic: Academic New York · Zbl 0302.65021
[29] Stewart, G. W., Algorithm 506: HQR3 and EXCHNG: Fortran subroutines for calculating and ordering the eigenvalues of a real upper Hessenberg matrix, ACM Trans. Math. Software, 2, 275-280 (1976)
[30] Stewart, G. W., On the perturbation of pseudo-inverses, projections, and linear least squares problems, SIAM Rev., 19, 634-662 (1977) · Zbl 0379.65021
[31] Symm, H. J.; Wilkinson, J. H., Realistic error bounds for a simple eigenvalue and its associated eigenvector, Numer. Math., 35, 113-126 (1980) · Zbl 0447.65015
[32] Varah, J. M., Rigorous machine bounds for the eigensystem of a general complex matrix, Math. Comp., 22, 793-801 (1968) · Zbl 0176.13503
[33] Varah, J. M., Computing invariant subspaces of a general matrix when the eigensystem is poorly determined, Math. Comp., 24, 137-149 (1970) · Zbl 0195.45101
[34] Varah, J. M., On the separation of two matrices, SIAM J. Numer. Anal., 16, 216-222 (1979) · Zbl 0435.65034
[35] Wilkinson, J. H., Rounding Errors in Algebraic Processes (1963), Prentice-Hall: Prentice-Hall Englewood Cliffs, N.J · Zbl 0868.65027
[36] Wilkinson, J. H., The Algebraic Eigenvalue Problem (1965), Oxford U.P: Oxford U.P Oxford · Zbl 0258.65037
[37] Wilkinson, J. H., Note on matrices with a very ill-conditioned eigenproblem, Numer. Math., 19, 176-178 (1972) · Zbl 0252.65027
[38] Wilkinson, J. H., Sensitivity of Eigenvalues, Utilitas Math., 25, 5-76 (1984) · Zbl 0551.65018
[39] Yakamoto, T., Error bounds for computed eigenvalues and eigenvectors, Numer. Math., 34, 189-199 (1980) · Zbl 0411.65022
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.