TY - JOUR

T1 - Backward stability of polynomial root-finding using Fiedler companion matrices

AU - De Terán, Fernando

AU - Dopico, Froilán M.

AU - Pérez, Javier

N1 - Publisher Copyright:
© 2015 The Authors.

PY - 2014/7/11

Y1 - 2014/7/11

N2 - Computing roots of scalar polynomials as the eigenvalues of Frobenius companion matrices using backward stable eigenvalue algorithms is a classical approach. The introduction of new families of companion matrices allows for the use of other matrices in the root-finding problem. In this paper, we analyse the backward stability of polynomial root-finding algorithms via Fiedler companion matrices. In other words, given a polynomial p(z), the question is to determine whether the whole set of computed eigenvalues of the companion matrix, obtained with a backward stable algorithm for the standard eigenvalue problem, is the set of roots of a nearby polynomial or not. We show that, if the coefficients of p(z) are bounded in absolute value by a moderate number, then algorithms for polynomial root-finding using Fiedler matrices are backward stable, and Fiedler matrices are as good as the Frobenius companion matrices. This allows us to use Fiedler companion matrices with favourable structures in the polynomial root-finding problem. However, when some of the coefficients of the polynomial are large, Fiedler companion matrices may produce larger backward errors than Frobenius companion matrices, although in this case neither Frobenius nor Fiedler matrices lead to backward stable computations. To prove this we obtain explicit expressions for the change, to first-order, of the characteristic polynomial coefficients of Fiedler matrices under small perturbations. We show that, for all Fiedler matrices except the Frobenius ones, this change involves quadratic terms in the coefficients of the characteristic polynomial of the original matrix, while for the Frobenius matrices it only involves linear terms. We present extensive numerical experiments that support these theoretical results. The effect of balancing these matrices is also investigated.

AB - Computing roots of scalar polynomials as the eigenvalues of Frobenius companion matrices using backward stable eigenvalue algorithms is a classical approach. The introduction of new families of companion matrices allows for the use of other matrices in the root-finding problem. In this paper, we analyse the backward stability of polynomial root-finding algorithms via Fiedler companion matrices. In other words, given a polynomial p(z), the question is to determine whether the whole set of computed eigenvalues of the companion matrix, obtained with a backward stable algorithm for the standard eigenvalue problem, is the set of roots of a nearby polynomial or not. We show that, if the coefficients of p(z) are bounded in absolute value by a moderate number, then algorithms for polynomial root-finding using Fiedler matrices are backward stable, and Fiedler matrices are as good as the Frobenius companion matrices. This allows us to use Fiedler companion matrices with favourable structures in the polynomial root-finding problem. However, when some of the coefficients of the polynomial are large, Fiedler companion matrices may produce larger backward errors than Frobenius companion matrices, although in this case neither Frobenius nor Fiedler matrices lead to backward stable computations. To prove this we obtain explicit expressions for the change, to first-order, of the characteristic polynomial coefficients of Fiedler matrices under small perturbations. We show that, for all Fiedler matrices except the Frobenius ones, this change involves quadratic terms in the coefficients of the characteristic polynomial of the original matrix, while for the Frobenius matrices it only involves linear terms. We present extensive numerical experiments that support these theoretical results. The effect of balancing these matrices is also investigated.

KW - Backward stability, conditioning

KW - Characteristic polynomial

KW - Eigenvalues

KW - Fiedler companion matrices

KW - Roots of polynomials

UR - http://www.scopus.com/inward/record.url?scp=84959909620&partnerID=8YFLogxK

U2 - 10.1093/imanum/dru057

DO - 10.1093/imanum/dru057

M3 - Article

AN - SCOPUS:84959909620

SN - 0272-4979

VL - 36

SP - 133

EP - 173

JO - IMA Journal of Numerical Analysis

JF - IMA Journal of Numerical Analysis

IS - 1

ER -