×

First-order perturbation theory for eigenvalues and eigenvectors. (English) Zbl 1516.15006

Summary: We present first-order perturbation analysis of a simple eigenvalue and the corresponding right and left eigenvectors of a general square matrix, not assumed to be Hermitian or normal. The eigenvalue result is well known to a broad scientific community. The treatment of eigenvectors is more complicated, with a perturbation theory that is not so well known outside a community of specialists. We give two different proofs of the main eigenvector perturbation theorem. The first, a block-diagonalization technique inspired by the numerical linear algebra research community and based on the implicit function theorem, has apparently not appeared in the literature in this form. The second, based on complex function theory and on eigenprojectors, as is standard in analytic perturbation theory, is a simplified version of well-known results in the literature. The second derivation uses a convenient normalization of the right and left eigenvectors defined in terms of the associated eigenprojector, but although this dates back to the 1950s, it is rarely discussed in the literature. We then show how the eigenvector perturbation theory is easily extended to handle other normalizations that are often used in practice. We also explain how to verify the perturbation results computationally. We conclude with some remarks about difficulties introduced by multiple eigenvalues and give references to work on perturbation of invariant subspaces corresponding to multiple or clustered eigenvalues. Throughout the paper we give extensive bibliographic commentary and references for further reading.

MSC:

15A18 Eigenvalues, singular values, and eigenvectors
65F15 Numerical computation of eigenvalues and eigenvectors of matrices
15A60 Norms of matrices, numerical range, applications of functional analysis to matrix theory
47A55 Perturbation theory of linear operators

Software:

PSAPSR; Eigtool

References:

[1] A. L. Andrew, K.-W. E. Chu, and P. Lancaster, Derivatives of eigenvalues and eigenvectors of matrix functions, SIAM J. Matrix Anal. Appl., 14 (1993), pp. 903-926, https://doi.org/10.1137/0614061. · Zbl 0786.15011
[2] H. Baumgärtel, Analytic Perturbation Theory for Matrices and Operators, Oper. Theory Adv. Appl. 15, Birkhäuser Verlag, Basel, 1985. · Zbl 0591.47013
[3] M. Bernasconi, C. Choirat, and R. Seri, Differentials of eigenvalues and eigenvectors in undamped discrete systems under alternative normalizations, in Proceedings of the World Congress on Engineering, International Association of Engineers, 2011, pp. 285-287.
[4] D. Bindel, J. Demmel, and M. Friedman, Continuation of invariant subspaces in large bifurcation problems, SIAM J. Sci. Comput., 30 (2008), pp. 637-656, https://doi.org/10.1137/060654219. · Zbl 1160.65065
[5] D. Bindel and A. Hood, Localization theorems for nonlinear eigenvalue problems, SIAM J. Matrix Anal. Appl., 34 (2013), pp. 1728-1749, https://doi.org/10.1137/130913651. · Zbl 1297.15021
[6] R. Bhatia, Matrix Analysis, Grad. Texts in Math. 169, Springer-Verlag, New York, 1997, https://doi.org/10.1007/978-1-4612-0653-8.
[7] R. Bhatia, Perturbation Bounds for Matrix Eigenvalues, Classics Appl. Math. 53, SIAM, Philadelphia, 2007, https://doi.org/10.1137/1.9780898719079; reprint of the 1987 original. · Zbl 1139.15303
[8] F. Chatelin, Spectral Approximation of Linear Operators, Classics Appl. Math. 65, SIAM, Philadelphia, 2011, https://doi.org/10.1137/1.9781611970678; reprint of the 1983 original. · Zbl 1214.01004
[9] F. Chatelin, Eigenvalues of Matrices, Classics Appl. Math. 71, SIAM, Philadelphia, 2012, https://doi.org/10.1137/1.9781611972467; revised reprint of the 1993 edition.
[10] S. L. Campbell and C. D. Meyer, Jr., Generalized Inverses of Linear Transformations, Dover, New York, 1991; corrected reprint of the 1979 original. · Zbl 0732.15003
[11] J. W. Demmel, Computing stable eigendecompositions of matrices, Linear Algebra Appl., 79 (1986), pp. 163-193, https://doi.org/10.1016/0024-3795(86)90298-3. · Zbl 0627.65031
[12] J. W. Demmel, Three methods for refining estimates of invariant subspaces, Computing, 38 (1987), pp. 43-57, https://doi.org/10.1007/BF02253743. · Zbl 0602.65022
[13] J. W. Demmel, The SVD, eigenproblem, and invariant subspaces: Algorithms, in G. W. Stewart: Selected Works with Commentaries, Contemp. Math., Birkhäuser Verlag, Basel, 2010, pp. 95-104, https://doi.org/10.1007/978-0-8176-4968-5_8.
[14] L. Dieci and M. J. Friedman, Continuation of invariant subspaces, Numer. Linear Algebra Appl., 8 (2001), pp. 317-327, https://doi.org/10.1002/nla.245. · Zbl 1055.65054
[15] M. Embree and L. N. Trefethen, Pseudospectral Gateway, https://www.cs.ox.ac.uk/pseudospectra/.
[16] W. Givens, Conference on matrix computations, J. ACM, 5 (1958), pp. 100-115, https://doi.org/10.1145/320911.320923. · Zbl 0084.35102
[17] I. Gohberg, P. Lancaster, and L. Rodman, Perturbation of analytic Hermitian matrix functions, Appl. Anal., 20 (1985), pp. 23-48, https://doi.org/10.1080/00036818508839556. · Zbl 0548.47012
[18] I. Gohberg, P. Lancaster, and L. Rodman, Invariant Subspaces of Matrices with Applications, Classics Appl. Math. 51, SIAM, Philadelphia, 2006, https://doi.org/10.1137/1.9780898719093; reprint of the 1986 original. · Zbl 1093.15502
[19] N. Guglielmi and M. L. Overton, Fast algorithms for the approximation of the pseudospectral abscissa and pseudospectral radius of a matrix, SIAM J. Matrix Anal. Appl., 32 (2011), pp. 1166-1192, https://doi.org/10.1137/100817048. · Zbl 1248.65034
[20] N. Guglielmi, M. L. Overton, and G. W. Stewart, An efficient algorithm for computing the generalized null space decomposition, SIAM J. Matrix Anal. Appl., 36 (2015), pp. 38-54, https://doi.org/10.1137/140956737. · Zbl 1327.65072
[21] I. C. F. Ipsen, The eigenproblem and invariant subspaces: Perturbation theory, in G. W. Stewart: Selected Works with Commentaries, Contemp. Math., Birkhäuser Verlag, Basel, 2010, pp. 71-93, https://doi.org/10.1007/978-0-8176-4968-5_7.
[22] T. Kato, Perturbation Theory for Linear Operators, Grundlehren Math. Wiss. 132, Springer-Verlag, New York, 1966. · Zbl 0148.12601
[23] T. Kato, Perturbation Theory for Linear Operators, 2nd ed., Grundlehren Math. Wiss. 132, Springer-Verlag, New York, 1976. · Zbl 0342.47009
[24] T. Kato, A Short Introduction to Perturbation Theory for Linear Operators, Springer-Verlag, New York, 1982. · Zbl 0493.47008
[25] T. Kato, Perturbation Theory for Linear Operators, Classics in Mathematics, Springer-Verlag, Berlin, 1995; reprint of the 1980 edition. · Zbl 0836.47009
[26] M. Karow and D. Kressner, On a perturbation bound for invariant subspaces of matrices, SIAM J. Matrix Anal. Appl., 35 (2014), pp. 599-618, https://doi.org/10.1137/130912372. · Zbl 1306.15011
[27] S. G. Krantz, Function Theory of Several Complex Variables, AMS, Providence, RI, 2001, https://doi.org/10.1090/chel/340; reprint of the 1992 edition. · Zbl 1087.32001
[28] P. Lancaster, On eigenvalues of matrices dependent on a parameter, Numer. Math., 6 (1964), pp. 377-387, https://doi.org/10.1007/BF01386087. · Zbl 0133.26201
[29] P. D. Lax, Linear Algebra and Its Applications, 2nd ed., Pure Appl. Math. (Hoboken), Wiley-Interscience, Hoboken, NJ, 2007. · Zbl 1152.15001
[30] R. Li, Matrix perturbation theory, in Handbook of Linear Algebra, 2nd ed., Discrete Math. Appl. (Boca Raton), L. Hogben, ed., CRC Press, Boca Raton, FL, 2014, pp. (21-1)–(21-20).
[31] V. B. Lidskii, Perturbation theory of non-conjugate operators, U.S.S.R. Comput. Math. and Math. Phys., 6 (1966), pp. 73-85.
[32] P. Lancaster, A. S. Markus, and F. Zhou, Perturbation theory for analytic matrix functions: The semisimple case, SIAM J. Matrix Anal. Appl., 25 (2003), pp. 606-626, https://doi.org/10.1137/S0895479803423792. · Zbl 1061.15009
[33] P. Lancaster and M. Tismenetsky, The Theory of Matrices, 2nd ed., Comput. Sci. Appl. Math., Academic Press, Orlando, FL, 1985. · Zbl 0558.15001
[34] J. Magnus, On differentiating eigenvalues and eigenvectors, Econom. Theory, 1 (1985), pp. 179-191.
[35] J. Moro, J. V. Burke, and M. L. Overton, On the Lidskii-Vishik-Lyusternik perturbation theory for eigenvalues of matrices with arbitrary Jordan structure, SIAM J. Matrix Anal. Appl., 18 (1997), pp. 793-817, https://doi.org/10.1137/S0895479895294666. · Zbl 0889.15016
[36] J. H. Mathews and R. W. Howell, Complex Analysis for Mathematics and Engineering, Jones and Bartlett, Sudbury, MA, 2006. · Zbl 0887.30001
[37] C. D. Meyer and G. W. Stewart, Derivatives and perturbations of eigenvectors, SIAM J. Numer. Anal., 25 (1988), pp. 679-691, https://doi.org/10.1137/0725041. · Zbl 0646.15005
[38] M. L. Overton, Numerical Computing with IEEE Floating Point Arithmetic, SIAM, Philadelphia, 2001, https://doi.org/10.1137/1.9780898718072. · Zbl 0981.68057
[39] F. Rellich, Perturbation Theory of Eigenvalue Problems, Gordon and Breach Science, New York, London, Paris, 1969. · Zbl 0181.42002
[40] B. Sz.-Nagy, Perturbations des transformations linéaires fermées, Acta Sci. Math. Szeged, 14 (1951), pp. 125-137. · Zbl 0045.21601
[41] G. W. Stewart and J. G. Sun, Matrix Perturbation Theory, Computer Science and Scientific Computing, Academic Press, Boston, MA, 1990. · Zbl 0706.65013
[42] G. W. Stewart, Error bounds for approximate invariant subspaces of closed linear operators, SIAM J. Numer. Anal., 8 (1971), pp. 796-808, https://doi.org/10.1137/0708073. · Zbl 0232.47010
[43] G. W. Stewart, Error and perturbation bounds for subspaces associated with certain eigenvalue problems, SIAM Rev., 15 (1973), pp. 727-764, https://doi.org/10.1137/1015095. · Zbl 0297.65030
[44] G. W. Stewart, Matrix Algorithms. Vol. II: Eigensystems, SIAM, Philadelphia, 2001, https://doi.org/10.1137/1.9780898718058. · Zbl 0984.65031
[45] J. G. Sun, Eigenvalues and eigenvectors of a matrix dependent on several parameters, J. Comput. Math., 3 (1985), pp. 351-364. · Zbl 0618.15009
[46] J.-G. Sun, Stability and Accuracy: Perturbation Analysis of Algebraic Eigenproblems, Tech. Report UMINF 98.07, Ume\aa University, 1998; revised 2002, https://people.cs.umu.se/jisun/Jiguang-Sun-UMINF98-07-rev2002-02-20.pdf.
[47] L. N. Trefethen and M. Embree, Spectra and Pseudospectra. The Behavior of Nonnormal Matrices and Operators, Princeton University Press, Princeton, NJ, 2005. · Zbl 1085.15009
[48] J. H. Wilkinson, The Algebraic Eigenvalue Problem, Clarendon Press, Oxford, 1965. · Zbl 0258.65037
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.