Structured backward errors in linearizations
From MaRDI portal
Abstract: A standard approach to compute the roots of a univariate polynomial is to compute the eigenvalues of an associated emph{confederate} matrix instead, such as, for instance the companion or comrade matrix. The eigenvalues of the confederate matrix can be computed by Francis's QR algorithm. Unfortunately, even though the QR algorithm is provably backward stable, mapping the errors back to the original polynomial coefficients can still lead to huge errors. However, the latter statement assumes the use of a non-structure exploiting QR algorithm. In [J. Aurentz et al., Fast and backward stable computation of roots of polynomials, SIAM J. Matrix Anal. Appl., 36(3), 2015] it was shown that a structure exploiting QR algorithm for companion matrices leads to a structured backward error on the companion matrix. The proof relied on decomposing the error into two parts: a part related to the recurrence coefficients of the basis (monomial basis in that case) and a part linked to the coefficients of the original polynomial. In this article we prove that the analysis can be extended to other classes of comrade matrices. We first provide an alternative backward stability proof in the monomial basis using structured QR algorithms; our new point of view shows more explicitly how a structured, decoupled error on the confederate matrix gets mapped to the associated polynomial coefficients. This insight reveals which properties must be preserved by a structure exploiting QR algorithm to end up with a backward stable algorithm. We will show that the previously formulated companion analysis fits in this framework and we will analyze in more detail Jacobi polynomials (Comrade matrices) and Chebyshev polynomials (Colleague matrices).
Recommendations
- Structured backward errors for a class of linear systems
- Backward Error and Condition of Structured Linear Systems
- A note on backward errors for structured linear systems
- scientific article; zbMATH DE number 2221123
- Linearization estimates of the backward errors for least squares problems.
- Structured backward errors for generalized saddle point systems
- scientific article; zbMATH DE number 1961187
- Backward errors of the linear complementarity problem
- scientific article; zbMATH DE number 1786285
- Linearised Estimate of the Backward Error for Equality Constrained Indefinite Least Squares Problems
Cites work
- scientific article; zbMATH DE number 3839766 (Why is no real title available?)
- scientific article; zbMATH DE number 3962168 (Why is no real title available?)
- scientific article; zbMATH DE number 3477793 (Why is no real title available?)
- scientific article; zbMATH DE number 3273551 (Why is no real title available?)
- A note on companion matrices
- Backward error analysis of polynomial eigenvalue problems solved by linearization
- Backward stability of polynomial root-finding using Fiedler companion matrices
- Chebyshev rootfinding via computing eigenvalues of colleague matrices: when is it stable?
- Core-Chasing Algorithms for the Eigenvalue Problem
- Efficient eigenvalue computation for quasiseparable Hermitian matrices under low rank perturbations
- Fast Hessenberg reduction of some rank structured matrices
- Fast and Backward Stable Computation of Roots of Polynomials
- Fast and backward stable computation of eigenvalues and eigenvectors of matrix polynomials
- Fast and backward stable computation of roots of polynomials. II: Backward error analysis; companion matrix and companion pencil
- MPFR
- On the stability of computing polynomial roots via confederate linearizations
- Polynomial Roots from Companion Matrix Eigenvalues
- Stability of rootfinding for barycentric Lagrange interpolants
- The Matrix Eigenvalue Problem
- The eigenstructure of an arbitrary polynomial matrix: Computational aspects
- Vector Spaces of Linearizations for Matrix Polynomials
- Vector spaces of linearizations for matrix polynomials: a bivariate polynomial approach
Cited in
(7)- The Componentwise Structured and Unstructured Backward Errors Can be Arbitrarily Far Apart
- Structured backward errors for KKT systems
- Backward Error and Condition of Structured Linear Systems
- Structured backward errors for generalized saddle point systems
- Fast and backward stable computation of roots of polynomials. II: Backward error analysis; companion matrix and companion pencil
- A note on backward errors for structured linear systems
- On the stability of computing polynomial roots via confederate linearizations
This page was built for publication: Structured backward errors in linearizations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q822680)
