Conditioning and backward errors of eigenvalues of homogeneous matrix polynomials under Möbius transformations

Anguas, Luis Miguel; Bueno, Maria; Dopico, Froilán

doi:10.1090/mcom/3472

Conditioning and backward errors of eigenvalues of homogeneous matrix polynomials under Möbius transformations
HTML articles powered by AMS MathViewer

by Luis Miguel Anguas, Maria Isabel Bueno and Froilán M. Dopico;

Math. Comp. 89 (2020), 767-805

DOI: https://doi.org/10.1090/mcom/3472

Published electronically: August 26, 2019

HTML | PDF | Request permission

Abstract:

We present the first general study on the effect of Möbius transformations on the eigenvalue condition numbers and backward errors of approximate eigenpairs of polynomial eigenvalue problems (PEPs). By using the homogeneous formulation of PEPs, we are able to obtain two clear and simple results. First, we show that if the matrix inducing the Möbius transformation is well-conditioned, then such transformation approximately preserves the eigenvalue condition numbers and backward errors when they are defined with respect to perturbations of the matrix polynomial which are small relative to the norm of the whole polynomial. However, if the perturbations in each coefficient of the matrix polynomial are small relative to the norm of that coefficient, then the corresponding eigenvalue condition numbers and backward errors are preserved approximately by the Möbius transformations induced by well-conditioned matrices only if a penalty factor, depending on the norms of those matrix coefficients, is moderate. It is important to note that these simple results are no longer true if a non-homogeneous formulation of the PEP is used.

References

Luis Miguel Anguas, María Isabel Bueno, and Froilán M. Dopico, A comparison of eigenvalue condition numbers for matrix polynomials, Linear Algebra Appl. 564 (2019), 170–200. MR 3884702, DOI 10.1016/j.laa.2018.11.031
W. N. Bailey, Generalized hypergeometric series, Cambridge Tracts in Mathematics and Mathematical Physics, No. 32, Stechert-Hafner, Inc., New York, 1964. MR 185155
Peter Benner, Volker Mehrmann, and Hongguo Xu, A numerically stable, structure preserving method for computing the eigenvalues of real Hamiltonian or symplectic pencils, Numer. Math. 78 (1998), no. 3, 329–358. MR 1603338, DOI 10.1007/s002110050315
Timo Betcke, Nicholas J. Higham, Volker Mehrmann, Christian Schröder, and Françoise Tisseur, NLEVP: a collection of nonlinear eigenvalue problems, ACM Trans. Math. Software 39 (2013), no. 2, Art. 7, 28. MR 3031626, DOI 10.1145/2427023.2427024
Richard A. Brualdi, Introductory combinatorics, 5th ed., Pearson Prentice Hall, Upper Saddle River, NJ, 2010. MR 2655770
M. I. Bueno, F. M. Dopico, S. Furtado, and L. Medina, A block-symmetric linearization of odd degree matrix polynomials with optimal eigenvalue condition number and backward error, Calcolo 55 (2018), no. 3, Paper No. 32, 43. MR 3832990, DOI 10.1007/s10092-018-0273-4
M. I. Bueno, K. Curlett, and S. Furtado, Structured strong linearizations from Fiedler pencils with repetition I, Linear Algebra Appl. 460 (2014), 51–80. MR 3250531, DOI 10.1016/j.laa.2014.07.039
Ralph Byers, Volker Mehrmann, and Hongguo Xu, A structured staircase algorithm for skew-symmetric/symmetric pencils, Electron. Trans. Numer. Anal. 26 (2007), 1–33. MR 2366088
Jean-Pierre Dedieu, Condition operators, condition numbers, and condition number theorem for the generalized eigenvalue problem, Linear Algebra Appl. 263 (1997), 1–24. MR 1453962, DOI 10.1016/S0024-3795(96)00366-7
Jean-Pierre Dedieu and Françoise Tisseur, Perturbation theory for homogeneous polynomial eigenvalue problems, Linear Algebra Appl. 358 (2003), 71–94. Special issue on accurate solution of eigenvalue problems (Hagen, 2000). MR 1942724, DOI 10.1016/S0024-3795(01)00423-2
Fernando De Terán, Froilán M. Dopico, and D. Steven Mackey, Palindromic companion forms for matrix polynomials of odd degree, J. Comput. Appl. Math. 236 (2011), no. 6, 1464–1480. MR 2854064, DOI 10.1016/j.cam.2011.09.010
Fernando De Terán, Froilán M. Dopico, and D. Steven Mackey, Spectral equivalence of matrix polynomials and the index sum theorem, Linear Algebra Appl. 459 (2014), 264–333. MR 3247227, DOI 10.1016/j.laa.2014.07.007
Fernando De Terán, Froilán M. Dopico, and Paul Van Dooren, Matrix polynomials with completely prescribed eigenstructure, SIAM J. Matrix Anal. Appl. 36 (2015), no. 1, 302–328. MR 3324973, DOI 10.1137/140964138
Froilán M. Dopico, Piers W. Lawrence, Javier Pérez, and Paul Van Dooren, Block Kronecker linearizations of matrix polynomials and their backward errors, Numer. Math. 140 (2018), no. 2, 373–426. MR 3851061, DOI 10.1007/s00211-018-0969-z
Froilán M. Dopico, Javier Pérez, and Paul Van Dooren, Structured backward error analysis of linearized structured polynomial eigenvalue problems, Math. Comp. 88 (2019), no. 317, 1189–1228. MR 3904143, DOI 10.1090/mcom/3360
Hung-Yuan Fan, Wen-Wei Lin, and Paul Van Dooren, Normwise scaling of second order polynomial matrices, SIAM J. Matrix Anal. Appl. 26 (2004), no. 1, 252–256. MR 2112859, DOI 10.1137/S0895479803434914
Gene H. Golub and Charles F. Van Loan, Matrix computations, 3rd ed., Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 1996. MR 1417720
Sven Hammarling, Christopher J. Munro, and Françoise Tisseur, An algorithm for the complete solution of quadratic eigenvalue problems, ACM Trans. Math. Software 39 (2013), no. 3, Art. 18, 19. MR 3094974, DOI 10.1145/2450153.2450156
Nicholas J. Higham, Accuracy and stability of numerical algorithms, 2nd ed., Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2002. MR 1927606, DOI 10.1137/1.9780898718027
Nicholas J. Higham, Functions of matrices, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2008. Theory and computation. MR 2396439, DOI 10.1137/1.9780898717778
Nicholas J. Higham, Ren-Cang Li, and Françoise Tisseur, Backward error of polynomial eigenproblems solved by linearization, SIAM J. Matrix Anal. Appl. 29 (2007), no. 4, 1218–1241. MR 2369292, DOI 10.1137/060663738
Nicholas J. Higham, D. Steven Mackey, and Françoise Tisseur, The conditioning of linearizations of matrix polynomials, SIAM J. Matrix Anal. Appl. 28 (2006), no. 4, 1005–1028. MR 2276551, DOI 10.1137/050628283
Daniel Kressner, María José Peláez, and Julio Moro, Structured Hölder condition numbers for multiple eigenvalues, SIAM J. Matrix Anal. Appl. 31 (2009), no. 1, 175–201. MR 2487056, DOI 10.1137/060672893
Peter Lancaster and Leiba Rodman, Algebraic Riccati equations, Oxford Science Publications, The Clarendon Press, Oxford University Press, New York, 1995. MR 1367089
D. Steven Mackey, Niloufer Mackey, Christian Mehl, and Volker Mehrmann, Structured polynomial eigenvalue problems: good vibrations from good linearizations, SIAM J. Matrix Anal. Appl. 28 (2006), no. 4, 1029–1051. MR 2276552, DOI 10.1137/050628362
D. Steven Mackey, Niloufer Mackey, Christian Mehl, and Volker Mehrmann, Möbius transformations of matrix polynomials, Linear Algebra Appl. 470 (2015), 120–184. MR 3314310, DOI 10.1016/j.laa.2014.05.013
Brockway McMillan, Introduction to formal realizability theory. I, Bell System Tech. J. 31 (1952), 217–279. MR 49079, DOI 10.1002/j.1538-7305.1952.tb01383.x
Brockway McMillan, Introduction to formal realizability theory. II, Bell System Tech. J. 31 (1952), 541–600. MR 49080, DOI 10.1002/j.1538-7305.1952.tb01396.x
V. L. Mehrmann, The autonomous linear quadratic control problem, Lecture Notes in Control and Information Sciences, vol. 163, Springer-Verlag, Berlin, 1991. Theory and numerical solution. MR 1133203, DOI 10.1007/BFb0039443
Volker Mehrmann, A step toward a unified treatment of continuous and discrete time control problems, Proceedings of the Fourth Conference of the International Linear Algebra Society (Rotterdam, 1994), 1996, pp. 749–779. MR 1400462, DOI 10.1016/0024-3795(95)00257-X
Volker Mehrmann and Federico Poloni, A generalized structured doubling algorithm for the numerical solution of linear quadratic optimal control problems, Numer. Linear Algebra Appl. 20 (2013), no. 1, 112–137. MR 3007242, DOI 10.1002/nla.1828
Volker Mehrmann and Hongguo Xu, Structure preserving deflation of infinite eigenvalues in structured pencils, Electron. Trans. Numer. Anal. 44 (2015), 1–24. MR 3313392
Nikolaos Papathanasiou and Panayiotis Psarrakos, On condition numbers of polynomial eigenvalue problems, Appl. Math. Comput. 216 (2010), no. 4, 1194–1205. MR 2607228, DOI 10.1016/j.amc.2010.02.011
G. W. Stewart and Ji Guang Sun, Matrix perturbation theory, Computer Science and Scientific Computing, Academic Press, Inc., Boston, MA, 1990. MR 1061154
Françoise Tisseur, Backward error and condition of polynomial eigenvalue problems, Proceedings of the International Workshop on Accurate Solution of Eigenvalue Problems (University Park, PA, 1998), 2000, pp. 339–361. MR 1758374, DOI 10.1016/S0024-3795(99)00063-4
Françoise Tisseur and Ion Zaballa, Triangularizing quadratic matrix polynomials, SIAM J. Matrix Anal. Appl. 34 (2013), no. 2, 312–337. MR 3038110, DOI 10.1137/120867640
Marc Van Barel and Françoise Tisseur, Polynomial eigenvalue solver based on tropically scaled Lagrange linearization, Linear Algebra Appl. 542 (2018), 186–208. MR 3778737, DOI 10.1016/j.laa.2017.04.025
Paul Van Dooren and Patrick Dewilde, The eigenstructure of an arbitrary polynomial matrix: computational aspects, Linear Algebra Appl. 50 (1983), 545–579. MR 699575, DOI 10.1016/0024-3795(83)90069-1
Hermann Weyl, The classical groups, Princeton Landmarks in Mathematics, Princeton University Press, Princeton, NJ, 1997. Their invariants and representations; Fifteenth printing; Princeton Paperbacks. MR 1488158
Linghui Zeng and Yangfeng Su, A backward stable algorithm for quadratic eigenvalue problems, SIAM J. Matrix Anal. Appl. 35 (2014), no. 2, 499–516. MR 3196946, DOI 10.1137/130921234