Anguas, Luis Miguel; Bueno, Maria Isabel; Dopico, Froilán M. Conditioning and backward errors of eigenvalues of homogeneous matrix polynomials under Möbius transformations. (English) Zbl 1427.65045 Math. Comput. 89, No. 322, 767-805 (2020). Summary: 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. MSC: 65F15 Numerical computation of eigenvalues and eigenvectors of matrices 65F35 Numerical computation of matrix norms, conditioning, scaling 15A18 Eigenvalues, singular values, and eigenvectors 15A22 Matrix pencils Keywords:backward error; eigenvalue condition number; matrix polynomial; Möbius transformation; polynomial eigenvalue problem Software:mctoolbox; NLEVP; quadeig PDFBibTeX XMLCite \textit{L. M. Anguas} et al., Math. Comput. 89, No. 322, 767--805 (2020; Zbl 1427.65045) Full Text: DOI arXiv References: [1] Anguas, Luis Miguel; Bueno, Mar\'{\i}a Isabel; Dopico, Froil\'{a}n M., A comparison of eigenvalue condition numbers for matrix polynomials, Linear Algebra Appl., 564, 170-200 (2019) · Zbl 1407.15010 [2] Bailey, W. N., Generalized Hypergeometric Series, Cambridge Tracts in Mathematics and Mathematical Physics, No. 32, v+108 pp. (1964), Stechert-Hafner, Inc., New York [3] Benner, Peter; Mehrmann, Volker; Xu, Hongguo, A numerically stable, structure preserving method for computing the eigenvalues of real Hamiltonian or symplectic pencils, Numer. Math., 78, 3, 329-358 (1998) · Zbl 0889.65036 [4] Betcke, Timo; Higham, Nicholas J.; Mehrmann, Volker; Schr\"{o}der, Christian; Tisseur, Fran\c{c}oise, NLEVP: a collection of nonlinear eigenvalue problems, ACM Trans. Math. Software, 39, 2, Art. 7, 28 pp. (2013) · Zbl 1295.65140 [5] Brualdi, Richard A., Introductory Combinatorics, xii+605 pp. (2010), Pearson Prentice Hall, Upper Saddle River, NJ [6] Bueno, M. I.; Dopico, F. M.; Furtado, S.; Medina, L., A block-symmetric linearization of odd degree matrix polynomials with optimal eigenvalue condition number and backward error, Calcolo, 55, 3, Art. 32, 43 pp. (2018) · Zbl 1416.65091 [7] Bueno, M. I.; Curlett, K.; Furtado, S., Structured strong linearizations from Fiedler pencils with repetition I, Linear Algebra Appl., 460, 51-80 (2014) · Zbl 1298.65064 [8] Byers, Ralph; Mehrmann, Volker; Xu, Hongguo, A structured staircase algorithm for skew-symmetric/symmetric pencils, Electron. Trans. Numer. Anal., 26, 1-33 (2007) · Zbl 1113.65065 [9] Dedieu, Jean-Pierre, Condition operators, condition numbers, and condition number theorem for the generalized eigenvalue problem, Linear Algebra Appl., 263, 1-24 (1997) · Zbl 0920.15001 [10] Dedieu, Jean-Pierre; Tisseur, Fran\c{c}oise, Perturbation theory for homogeneous polynomial eigenvalue problems, Linear Algebra Appl., 358, 71-94 (2003) · Zbl 1087.65033 [11] De Ter\'{a}n, Fernando; Dopico, Froil\'{a}n M.; Mackey, D. Steven, Palindromic companion forms for matrix polynomials of odd degree, J. Comput. Appl. Math., 236, 6, 1464-1480 (2011) · Zbl 1239.15010 [12] De Ter\'{a}n, Fernando; Dopico, Froil\'{a}n M.; Mackey, D. Steven, Spectral equivalence of matrix polynomials and the index sum theorem, Linear Algebra Appl., 459, 264-333 (2014) · Zbl 1297.65038 [13] De Ter\'{a}n, Fernando; Dopico, Froil\'{a}n M.; Van Dooren, Paul, Matrix polynomials with completely prescribed eigenstructure, SIAM J. Matrix Anal. Appl., 36, 1, 302-328 (2015) · Zbl 1315.15021 [14] Dopico, Froil\'{a}n M.; Lawrence, Piers W.; P\'{e}rez, Javier; Van Dooren, Paul, Block Kronecker linearizations of matrix polynomials and their backward errors, Numer. Math., 140, 2, 373-426 (2018) · Zbl 1416.65094 [15] Dopico, Froil\'{a}n M.; P\'{e}rez, Javier; Van Dooren, Paul, Structured backward error analysis of linearized structured polynomial eigenvalue problems, Math. Comp., 88, 317, 1189-1228 (2019) · Zbl 1408.65015 [16] Fan, Hung-Yuan; Lin, Wen-Wei; Van Dooren, Paul, Normwise scaling of second order polynomial matrices, SIAM J. Matrix Anal. Appl., 26, 1, 252-256 (2004) · Zbl 1088.15010 [17] Golub, Gene H.; Van Loan, Charles F., Matrix Computations, Johns Hopkins Studies in the Mathematical Sciences, xxx+698 pp. (1996), Johns Hopkins University Press, Baltimore, MD · Zbl 0865.65009 [18] Hammarling, Sven; Munro, Christopher J.; Tisseur, Fran\c{c}oise, An algorithm for the complete solution of quadratic eigenvalue problems, ACM Trans. Math. Software, 39, 3, Art. 18, 19 pp. (2013) · Zbl 1295.65060 [19] Higham, Nicholas J., Accuracy and Stability of Numerical Algorithms, xxx+680 pp. (2002), Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA · Zbl 1011.65010 [20] Higham, Nicholas J., Functions of Matrices, xx+425 pp. (2008), Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA · Zbl 1167.15001 [21] Higham, Nicholas J.; Li, Ren-Cang; Tisseur, Fran\c{c}oise, Backward error of polynomial eigenproblems solved by linearization, SIAM J. Matrix Anal. Appl., 29, 4, 1218-1241 (2007) · Zbl 1159.65042 [22] Higham, Nicholas J.; Mackey, D. Steven; Tisseur, Fran\c{c}oise, The conditioning of linearizations of matrix polynomials, SIAM J. Matrix Anal. Appl., 28, 4, 1005-1028 (2006) · Zbl 1131.65034 [23] Kressner, Daniel; Pel\'{a}ez, Mar\'{\i}a Jos\'{e}; Moro, Julio, Structured H\"{o}lder condition numbers for multiple eigenvalues, SIAM J. Matrix Anal. Appl., 31, 1, 175-201 (2009) · Zbl 1269.65035 [24] Lancaster, Peter; Rodman, Leiba, Algebraic Riccati Equations, Oxford Science Publications, xviii+480 pp. (1995), The Clarendon Press, Oxford University Press, New York · Zbl 0836.15005 [25] Mackey, D. Steven; Mackey, Niloufer; Mehl, Christian; Mehrmann, Volker, Structured polynomial eigenvalue problems: good vibrations from good linearizations, SIAM J. Matrix Anal. Appl., 28, 4, 1029-1051 (2006) · Zbl 1132.65028 [26] Mackey, D. Steven; Mackey, Niloufer; Mehl, Christian; Mehrmann, Volker, M\"{o}bius transformations of matrix polynomials, Linear Algebra Appl., 470, 120-184 (2015) · Zbl 1309.65042 [27] McMillan, Brockway, Introduction to formal realizability theory. I, Bell System Tech. J., 31, 217-279 (1952) [28] McMillan, Brockway, Introduction to formal realizability theory. II, Bell System Tech. J., 31, 541-600 (1952) [29] Mehrmann, V. L., The Autonomous Linear Quadratic Control Problem, Lecture Notes in Control and Information Sciences 163, vi+177 pp. (1991), Springer-Verlag, Berlin [30] Mehrmann, Volker, A step toward a unified treatment of continuous and discrete time control problems, Linear Algebra Appl.. Proceedings of the Fourth Conference of the International Linear Algebra Society (Rotterdam, 1994), 241/243, 749-779 (1996) · Zbl 0859.93013 [31] Mehrmann, Volker; Poloni, Federico, A generalized structured doubling algorithm for the numerical solution of linear quadratic optimal control problems, Numer. Linear Algebra Appl., 20, 1, 112-137 (2013) · Zbl 1289.49038 [32] Mehrmann, Volker; Xu, Hongguo, Structure preserving deflation of infinite eigenvalues in structured pencils, Electron. Trans. Numer. Anal., 44, 1-24 (2015) · Zbl 1312.65055 [33] Papathanasiou, Nikolaos; Psarrakos, Panayiotis, On condition numbers of polynomial eigenvalue problems, Appl. Math. Comput., 216, 4, 1194-1205 (2010) · Zbl 1211.15008 [34] Stewart, G. W.; Sun, Ji Guang, Matrix Perturbation Theory, Computer Science and Scientific Computing, xvi+365 pp. (1990), Academic Press, Inc., Boston, MA · Zbl 0706.65013 [35] Tisseur, Fran\c{c}oise, Backward error and condition of polynomial eigenvalue problems, Linear Algebra Appl.. Proceedings of the International Workshop on Accurate Solution of Eigenvalue Problems (University Park, PA, 1998), 309, 1-3, 339-361 (2000) · Zbl 0955.65027 [36] Tisseur, Fran\c{c}oise; Zaballa, Ion, Triangularizing quadratic matrix polynomials, SIAM J. Matrix Anal. Appl., 34, 2, 312-337 (2013) · Zbl 1273.15014 [37] Van Barel, Marc; Tisseur, Fran\c{c}oise, Polynomial eigenvalue solver based on tropically scaled Lagrange linearization, Linear Algebra Appl., 542, 186-208 (2018) · Zbl 1418.65052 [38] Van Dooren, Paul; Dewilde, Patrick, The eigenstructure of an arbitrary polynomial matrix: computational aspects, Linear Algebra Appl., 50, 545-579 (1983) · Zbl 0507.65008 [39] Weyl, Hermann, The Classical Groups, Princeton Landmarks in Mathematics, xiv+320 pp. (1997), Princeton University Press, Princeton, NJ · Zbl 1024.20501 [40] Zeng, Linghui; Su, Yangfeng, A backward stable algorithm for quadratic eigenvalue problems, SIAM J. Matrix Anal. Appl., 35, 2, 499-516 (2014) · Zbl 1385.65031 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.