Backward error and conditioning of Fiedler companion linearizations
HTML articles powered by AMS MathViewer
- by Fernando De Terán HTML | PDF
- Math. Comp. 89 (2020), 1259-1300 Request permission
Abstract:
The standard way to solve polynomial eigenvalue problems is through linearizations. The family of Fiedler linearizations, which includes the classical Frobenius companion forms, presents many interesting properties from both the theoretical and the applied point of view. These properties make the Fiedler pencils a very attractive family of linearizations to be used in the solution of polynomial eigenvalue problems. However, their numerical features for general matrix polynomials had not yet been fully investigated. In this paper, we analyze the backward error of eigenpairs and the condition number of eigenvalues of Fiedler linearizations in the solution of polynomial eigenvalue problems. We get bounds for: (a) the ratio between the backward error of an eigenpair of the matrix polynomial and the backward error of the corresponding (computed) eigenpair of the linearization, and (b) the ratio between the condition number of an eigenvalue in the linearization and the condition number of the same eigenvalue in the matrix polynomial. A key quantity in these bounds is $\rho$, the ratio between the maximum norm of the coefficients of the polynomial and the minimum norm of the leading and trailing coefficient. If the matrix polynomial is well scaled (i. e., all its coefficients have a similar norm, which implies $\rho \approx 1$), then solving the Polynomial Eigenvalue Problem with any Fiedler linearization will give a good performance from the point of view of backward error and conditioning. In the more general case of badly scaled matrix polynomials, dividing the coefficients of the polynomial by the maximum norm of its coefficients allows us to get better bounds. In particular, after this scaling, the ratio between the eigenvalue condition number in any two Fiedler linearizations is bounded by a quantity that depends only on the size and the degree of the polynomial. We also analyze the effect of parameter scaling in these linearizations, which improves significantly the backward error and conditioning in some cases where $\rho$ is large. Several numerical experiments are provided to support our theoretical results.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
- E. N. Antoniou and S. Vologiannidis, A new family of companion forms of polynomial matrices, Electron. J. Linear Algebra 11 (2004), 78–87. MR 2111515, DOI 10.13001/1081-3810.1124
- T. Betcke, Optimal scaling of generalized and polynomial eigenvalue problems, SIAM J. Matrix Anal. Appl. 30 (2008/09), no. 4, 1320–1338. MR 2448671, DOI 10.1137/070704769
- 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
- María I. Bueno and Fernando De Terán, Eigenvectors and minimal bases for some families of Fiedler-like linearizations, Linear Multilinear Algebra 62 (2014), no. 1, 39–62. MR 3175399, DOI 10.1080/03081087.2012.762713
- 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 and S. Furtado, Palindromic linearizations of a matrix polynomial of odd degree obtained from Fiedler pencils with repetition, Electron. J. Linear Algebra 23 (2012), 562–577. MR 2946810, DOI 10.13001/1081-3810.1541
- 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, Fiedler companion linearizations and the recovery of minimal indices, SIAM J. Matrix Anal. Appl. 31 (2009/10), no. 4, 2181–2204. MR 2678963, DOI 10.1137/090772927
- 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, Fiedler companion linearizations for rectangular matrix polynomials, Linear Algebra Appl. 437 (2012), no. 3, 957–991. MR 2921748, DOI 10.1016/j.laa.2012.03.028
- 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 Javier Pérez, Condition numbers for inversion of Fiedler companion matrices, Linear Algebra Appl. 439 (2013), no. 4, 944–981. MR 3061748, DOI 10.1016/j.laa.2012.09.020
- Fernando De Terán, Froilán M. Dopico, and Javier Pérez, Backward stability of polynomial root-finding using Fiedler companion matrices, IMA J. Numer. Anal. 36 (2016), no. 1, 133–173. MR 3463436, DOI 10.1093/imanum/dru057
- Fernando De Terán, Froilán M. Dopico, and Javier Pérez, Eigenvalue condition numbers and pseudospectra of Fiedler matrices, Calcolo 54 (2017), no. 1, 319–365. MR 3612924, DOI 10.1007/s10092-016-0189-9
- 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
- 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
- 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
- Heike Faßbender and Philip Saltenberger, Block Kronecker ansatz spaces for matrix polynomials, Linear Algebra Appl. 542 (2018), 118–148. MR 3778734, DOI 10.1016/j.laa.2017.03.019
- I. Gohberg, P. Lancaster, and L. Rodman, Matrix polynomials, Computer Science and Applied Mathematics, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, 1982. MR 662418
- 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
- Laurence Grammont, Nicholas J. Higham, and Françoise Tisseur, A framework for analyzing nonlinear eigenproblems and parametrized linear systems, Linear Algebra Appl. 435 (2011), no. 3, 623–640. MR 2794594, DOI 10.1016/j.laa.2009.12.038
- 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
- Roger A. Horn and Charles R. Johnson, Matrix analysis, Cambridge University Press, Cambridge, 1985. MR 832183, DOI 10.1017/CBO9780511810817
- Lars Karlsson and Françoise Tisseur, Algorithms for Hessenberg-triangular reduction of Fiedler linearization of matrix polynomials, SIAM J. Sci. Comput. 37 (2015), no. 3, C384–C414. MR 3352618, DOI 10.1137/140970458
- Nicola Mastronardi and Paul Van Dooren, Revisiting the stability of computing the roots of a quadratic polynomial, Electron. Trans. Numer. Anal. 44 (2015), 73–82. MR 3313395
- D. Steven Mackey, Niloufer Mackey, Christian Mehl, and Volker Mehrmann, Vector spaces of linearizations for matrix polynomials, SIAM J. Matrix Anal. Appl. 28 (2006), no. 4, 971–1004. MR 2276550, DOI 10.1137/050628350
- M. Sharify, Scaling Algorithms and Tropical Methods in Numerical Matrix Analysis: Application to the Optimal Assignment Problem and to the Accurate Computation of Eigenvalues, Ph.D. Thesis. École Polythechnique, Paris, 2011.
- 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
- G. W. Stewart, Matrix algorithms. Vol. II, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2001. Eigensystems. MR 1853468, DOI 10.1137/1.9780898718058
- 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
- S. Vologiannidis and E. N. Antoniou, A permuted factors approach for the linearization of polynomial matrices, Math. Control Signals Systems 22 (2011), no. 4, 317–342. MR 2820569, DOI 10.1007/s00498-011-0059-6
Additional Information
- Fernando De Terán
- Affiliation: Departamento de Matemáticas, Universidad Carlos III de Madrid, Avda. Universidad 30, 28911 Leganés, Spain
- Email: fteran@math.uc3m.es
- Received by editor(s): February 22, 2019
- Received by editor(s) in revised form: June 11, 2019
- Published electronically: October 17, 2019
- Additional Notes: This work was partially supported by the Ministerio de Ciencia e Innovación of Spain through grant MTM-2009-09281, and by the Ministerio de Economía y Competitividad of Spain through grants MTM-2012-32542, MTM2015-68805-REDT, and MTM2015-65798-P
- © Copyright 2019 American Mathematical Society
- Journal: Math. Comp. 89 (2020), 1259-1300
- MSC (2010): Primary 15A18, 65F15, 65F35
- DOI: https://doi.org/10.1090/mcom/3480
- MathSciNet review: 4063318