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

DOI10.1090/MCOM/3472zbMATH Open1427.65045arXiv1810.11495OpenAlexW2963750573MaRDI QIDQ5207441FDOQ5207441

Authors: Luis Miguel Anguas, Froilán M. Dopico, M. I. Bueno 

Publication date: 27 December 2019

Published in: Mathematics of Computation (Search for Journal in Brave)

Abstract: M"{o}bius transformations have been used in numerical algorithms for computing eigenvalues and invariant subspaces of structured generalized and polynomial eigenvalue problems (PEPs). These transformations convert problems with certain structures arising in applications into problems with other structures and whose eigenvalues and invariant subspaces are easily related to the ones of the original problem. Thus, an algorithm that is efficient and stable for some particular structure can be used for solving efficiently another type of structured problem via an adequate M"{o}bius transformation. A key question in this context is whether these transformations may change significantly the conditioning of the problem and the backward errors of the computed solutions, since, in that case, their use may lead to unreliable results. We present the first general study on the effect of M"{o}bius transformations on the eigenvalue condition numbers and backward errors of approximate eigenpairs of 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"{o}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 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"{o}bius transformations induced by well-conditioned matrices only if a penalty factor, depending on those coefficients, is moderate. It is important to note that these simple results are no longer true if a non-homogeneous formulation is used.

Full work available at URL: https://arxiv.org/abs/1810.11495

Recommendations

• Möbius transformations of matrix polynomials
• Backward error and condition of polynomial eigenvalue problems
• On backward errors of structured polynomial eigenproblems solved by structure preserving linearizations
• Structured backward error analysis of linearized structured polynomial eigenvalue problems
• scientific article; zbMATH DE number 2185810

zbMATH Keywords

eigenvalue condition numbermatrix polynomialbackward errorpolynomial eigenvalue problemMöbius transformation

Mathematics Subject Classification ID

Eigenvalues, singular values, and eigenvectors (15A18) Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Numerical computation of matrix norms, conditioning, scaling (65F35) Matrix pencils (15A22)

Cites Work

• NLEVP, a collection of nonlinear eigenvalue problems
• An algorithm for the complete solution of quadratic eigenvalue problems
• Functions of Matrices
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Accuracy and Stability of Numerical Algorithms
• Structured Polynomial Eigenvalue Problems: Good Vibrations from Good Linearizations
• The autonomous linear quadratic control problem. Theory and numerical solution
• Möbius transformations of matrix polynomials
• Spectral equivalence of matrix polynomials and the index sum theorem
• Perturbation theory for homogeneous polynomial eigenvalue problems
• Backward error and condition of polynomial eigenvalue problems
• Triangularizing quadratic matrix polynomials
• The Conditioning of Linearizations of Matrix Polynomials
• The eigenstructure of an arbitrary polynomial matrix: Computational aspects
• Palindromic companion forms for matrix polynomials of odd degree
• On condition numbers of polynomial eigenvalue problems
• A numerically stable, structure preserving method for computing the eigenvalues of real Hamiltonian or symplectic pencils
• Normwise Scaling of Second Order Polynomial Matrices
• Matrix polynomials with completely prescribed eigenstructure
• Backward Error of Polynomial Eigenproblems Solved by Linearization
• Structured strong linearizations from Fiedler pencils with repetition. I.
• A structured staircase algorithm for skew-symmetric/symmetric pencils
• Condition operators, condition numbers, and condition number theorem for the generalized eigenvalue problem
• Structured Hölder condition numbers for multiple eigenvalues
• A step toward a unified treatment of continuous and discrete time control problems
• A comparison of eigenvalue condition numbers for matrix polynomials
• Structured backward error analysis of linearized structured polynomial eigenvalue problems
• A generalized structured doubling algorithm for the numerical solution of linear quadratic optimal control problems
• A backward stable algorithm for quadratic eigenvalue problems
• Block Kronecker linearizations of matrix polynomials and their backward errors
• A block-symmetric linearization of odd degree matrix polynomials with optimal eigenvalue condition number and backward error
• Polynomial eigenvalue solver based on tropically scaled Lagrange linearization
• Structure preserving deflation of infinite eigenvalues in structured pencils

Cited In (3)

• Möbius transformations of matrix polynomials
• Perturbation theory for homogeneous polynomial eigenvalue problems
• Solving the quadratic eigenvalue problem expressed in non-monomial bases by the tropical scaling

This page was built for publication: Conditioning and backward errors of eigenvalues of homogeneous matrix polynomials under Möbius transformations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5207441)