Hostname: page-component-78c5997874-94fs2 Total loading time: 0 Render date: 2024-11-13T07:05:35.300Z Has data issue: false hasContentIssue false
  • English
  • Français

Relative perturbation results for matrix eigenvalues and singular values

Published online by Cambridge University Press:  07 November 2008

Ilse C. F. Ipsen
Ilse C. F. Ipsen
Affiliation:
Department of Mathematics, North Carolina State University, Raleigh, NC 27695-8205, USA E-mail: [email protected]://www4.ncsu.edu/~ipsen/info.html
Get access Rights & Permissions [Opens in a new window]

Abstract

It used to be good enough to bound absolute of matrix eigenvalues and singular values. Not any more. Now it is fashionable to bound relative errors. We present a collection of relative perturbation results which have emerged during the past ten years.

No need to throw away all those absolute error bound, though. Deep down, the derivation of many relative bounds can be based on absolute bounds. This means that relative bounds are not always better. They may just be better sometimes – and exactly when depends on the perturbation.

Type
Research Article
Information
Acta Numerica , Volume 7 , January 1998 , pp. 151 - 201
Copyright
Copyright © Cambridge University Press 1998

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

Barlow, J. and Demmel, J. (1990), ‘Computing accurate eigensystems of scaled diagonally dominant matrices’, SIAM J. Numer. Anal. 27, 762–91.CrossRefGoogle Scholar
Bauer, F. and Fike, C. (1960), ‘Norms and exclusion theorems’, Numer. Math. 2, 137–41.CrossRefGoogle Scholar
Bhatia, R. (1997), Matrix Analysis, Springer, New York.CrossRefGoogle Scholar
Chan, T. (1982), ‘An improved algorithm for computing the singular value decomposition’, ACM Trans. Math. Software 8, 72–83.CrossRefGoogle Scholar
Chandrasekaran, S. and Ipsen, I. (1995), ‘Analysis of a QR algorithm for computing singular values’, SIAM J. Matrix Anal. Appl. 16, 520–35.CrossRefGoogle Scholar
Deift, P., Demmel, J., Li, L. and Tomei, C. (1991), ‘The bidiagonal singular value decomposition and Hamiltonian mechanics’, SIAM J. Numer. Anal. 28, 1463–1516.CrossRefGoogle Scholar
Demmel, J. (1997), Applied Numerical Linear Algebra, SIAM, Philadelphia.CrossRefGoogle Scholar
Demmel, J. and Gragg, W. (1993), ‘On computing accurate singular values and eigenvalues of matrices with acyclic graphs’, Linear Algebra Appl. 185, 203–17.CrossRefGoogle Scholar
Demmel, J. and Kahan, W. (1990), ‘Accurate singular values ofbidiagonal matrices’, SIAM J. Sci. Statist. Comput. 11, 873–912.CrossRefGoogle Scholar
Demmel, J. and Veselić, K. (1992), ‘Jacobi's method is more accurate than QR’ SIAM J. Matrix Anal. Appl. 13, 1204–45.CrossRefGoogle Scholar
Demmel, J., Gu, M., Eisenstat, S., Slapničar, I., Veselić, K. and Drmač, Z. (1997), Computing the singular value decomposition with high relative accuracy, Technical report, Computer Science Division, University of California, Berkeley, CA.Google Scholar
Dhillon, I. (1997), A new O(n 2) algorithm for the symmetric tridiagonal eigenvalue/eigenvector problem, PhD thesis, University of California, Berkeley, California.Google Scholar
Dhillon, I., Fann, G. and Parlett, B. (1997), Application of a new algorithm for the symmetric eigenproblem to computational quantum chemistry, in Proceedings of the Eighth SIAM Conference on Parallel Processing for Scientific Computing, SIAM, Philadelphia.Google Scholar
Di Lena, G., Peluso, R. and Piazza, G. (1993), ‘Results on the relative perturbation of the singular values of a matrix’, BIT 33, 647–53.CrossRefGoogle Scholar
Drmač, Z. (1994), Computing the singular and the generalized singular values, PhD thesis, Fachbereich Mathematik, Fernuniversität Gesamthochschule Hagen, Germany.Google Scholar
Drmač, Z. (1996a), ‘On relative residual bounds for the eigenvalues of a Hermitian matrix’, Linear Algebra Appl. 244, 155–64.CrossRefGoogle Scholar
Drmač, Z. (1996b), ‘On the condition behaviour in the Jacobi method’, SIAM J. Matrix Anal. Appl. 17, 509–14.CrossRefGoogle Scholar
Drmač, Z. and Hari, V. (1997), ‘Relative residual bounds for the eigenvalues of a Hermitian semidefinite matrix’, SIAM J. Matrix Anal. Appl. 18, 21–9.CrossRefGoogle Scholar
Eisenstat, S. and Ipsen, I. (1994), Relative perturbation bounds for eigenspaces and singular vector subspaces, in Applied Linear Algebra, SIAM, Philadelphia, pp. 62–5.Google Scholar
Eisenstat, S. and Ipsen, I. (1995), ‘Relative perturbation techniques for singular value problems’, SIAM J. Numer. Anal. 32, 1972–88.CrossRefGoogle Scholar
Eisenstat, S. and Ipsen, I. (1996), Relative perturbation results for eigenvalues and eigenvectors of diagonalisable matrices, Technical Report CRSC-TR96-6, Center for Research in Scientific Computation, Department of Mathematics, North Carolina State University.Google Scholar
Eisenstat, S. and Ipsen, I. (1997), Three absolute perturbation bounds for matrix eigenvalues imply relative bounds, Technical Report CRSC-TR97-16, Center for Research in Scientific Computation, Department of Mathematics, North Carolina State University. Under review for SIAM J. Matrix Anal. Appl.Google Scholar
Eisner, L. and Friedland, S. (1995), ‘Singular values, doubly stochastic matrices, and applications’, Linear Algebra Appl. 220, 161–9.CrossRefGoogle Scholar
Fernando, K. and Parlett, B. (1994), ‘Accurate singular values and differential qd algorithms’, Numer. Math. 67, 191–229.CrossRefGoogle Scholar
Gu, M. and Eisenstat, S. (1993), Relative perturbation theory for eigenproblems, Research Report YALEU/DCS/RR-934, Department of Computer Science, Yale University.Google Scholar
Hari, V. and Drmač, Z. (1997), ‘On scaled almost diagonal Hermitian matrix pairs’, SIAM J. Matrix Anal. Appl. 18, 1000–1012.CrossRefGoogle Scholar
Horn, R. and Johnson, C. (1985), Matrix Analysis, Cambridge University Press.CrossRefGoogle Scholar
Horn, R. and Johnson, C. (1991), Topics in Matrix Analysis, Cambridge University Press.CrossRefGoogle Scholar
Kahan, W. (1966), Accurate eigenvalues of a symmetric tri–diagonal matrix, Technical Report CS41, Computer Science Department, Stanford University. Revised June 1968.Google Scholar
Li, C. and Mathias, R. (1997), On the Lidskii–Mirsky–Wielandt theorem, Technical report, Department of Mathematics, College of William and Mary, Williamsburg, VA.Google Scholar
Li, R. (1994a), Relative perturbation theory: (I) eigenvalue variations, LAPACK working note 84, Computer Science Department, University of Tennessee, Knoxville. Revised May 1997.Google Scholar
Li, R. (1994b), Relative perturbation theory: (II) eigenspace variations, LAPACK working note 85, Computer Science Department, University of Tennessee, Knoxville. Revised May 1997.Google Scholar
Li, R. (1997), ‘Relative perturbation theory: (III) more bounds on eigenvalue variation’, Linear Algebra Appl. 266, 337–45.CrossRefGoogle Scholar
Löwner, K. (1934), ‘Über monotone Matrix Funktionen’, Math. Z. 38, 177–216.CrossRefGoogle Scholar
Matejaš, J. and Hari, V. (1998), ‘Scaled almost diagonal matrices with multiple singular values’, Z. Angew. Math. Mech. 78, 121–31.3.0.CO;2-Y>CrossRefGoogle Scholar
Mathias, R. (1995), ‘Accurate eigensystem computations by Jacobi methods’, SIAM J. Matrix Anal. Appl. 16, 977–1003.CrossRefGoogle Scholar
Mathias, R. (1996), ‘Fast accurate eigenvalue methods for graded positive–definite matrices’, Numer. Math. 74, 85–103.CrossRefGoogle Scholar
Mathias, R. (1997a), ‘A bound for matrix square root with application to eigenvector perturbation’, SIAM J. Matrix Anal. Appl. 18, 861–7.CrossRefGoogle Scholar
Mathias, R. (1997b), ‘Spectral perturbation bounds for positive definite matrices’, SIAM J. Matrix Anal. Appl. 18, 959–80.CrossRefGoogle Scholar
Mathias, R. and Stewart, G. (1993), ‘A block QR algorithm and the singular value decomposition’, Linear Algebra Appl. 182, 91–100.CrossRefGoogle Scholar
Mathias, R. and Veselić, K. (1995), A relative perturbation bound for positive–definite matrices, revised December 1996.Google Scholar
Ostrowski, A. (1959), ‘A quantitative formulation of Sylvester's law of inertia’, Proc. Nat. Acad. Sci. 45, 740–4.CrossRefGoogle ScholarPubMed
Parlett, B. (1980), The Symmetric Eigenvalue Problem, Prentice Hall.Google Scholar
Parlett, B. (1995), ‘The new qd algorithms’, in Acta Numerica, Vol. 4, Cambridge University Press, pp. 459–91.Google Scholar
Parlett, B. (1997), Spectral sensitivity of products of bidiagonals. Unpublished manuscript.Google Scholar
Pietzsch, E. (1993), Genaue Eigenwertberechnung nichtsingulärer schiefsymme–trischer Matrizen, PhD thesis, Fachbereich Mathematik, Fernuniversität Gesamthochschule Hagen, Germany.Google Scholar
Rosanoff, R., Glouderman, J. and Levy, S. (1968), Numerical conditions of stiffness matrix formulations for frame structures, in Proceedings of the Conference on Matrix Methods in Structural Mechanics, AFFDL–TR-68-150, Wright-Patterson Air Force Base, Ohio, pp. 1029–60.Google Scholar
Slapničar, I. (1992), Accurate symmetric eigenreduction by a Jacobi method, PhD thesis, Fernuniversität Gesamthochschule Hagen, Germany.CrossRefGoogle Scholar
Slapničar, I. and Veselić, K. (1995), ‘Perturbations of the eigenprojections of a factorised Hermitian matrix’, Linear Algebra Appl. 218, 273–80.CrossRefGoogle Scholar
Truhar, N. and Slapničar, I. (1997), Relative perturbation bounds for invariant subspaces of indefinite Hermitian matrices. Unpublished manuscript.Google Scholar
van der Sluis, A. (1969), ‘Condition, equilibration, and pivoting in linear algebraic systems’, Numer. Math. 15, 74–86.CrossRefGoogle Scholar
Veselić, K. and Hari, V. (1989), A note on a one-sided Jacobi algorithm, Numer. Math. 56, 627–33.CrossRefGoogle Scholar
Veselić, K. and Slapničar, I. (1993), ‘Floating–point perturbations of Hermitian matrices’, Linear Algebra Appl. 195, 81–116.CrossRefGoogle Scholar