Backward stability of polynomial root-finding using Fiedler companion matrices

e-Archivo Repository

Show simple item record

dc.contributor.author Terán Vergara, Fernando de
dc.contributor.author Martínez Dopico, Froilán César
dc.contributor.author Pérez Álvaro, Javier
dc.date.accessioned 2015-12-01T12:25:09Z
dc.date.available 2015-12-01T12:25:09Z
dc.date.issued 2014-09-08
dc.identifier.bibliographicCitation Martínez Dopico, Froilán C.; Terán Vergara, Fernando de; Pérez, J. (2014). Backward stability of polynomial root-finding using Fiedler companion matrices. In Journal of Numerical Analysis, 2015, Number Anal, pp. 1-41.
dc.identifier.issn 0272-4979 (Print)
dc.identifier.issn 1464-3642 (Online)
dc.identifier.uri http://hdl.handle.net/10016/22060
dc.description The proceeding at: 6th Conference on Structured Numerical Linear and Multilinear Algebra: Analysis, Algorithms and Applications (SLA 2014), took place at 2014, Septembe 8-12, in Kalamata (Grece),
dc.description.abstract 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 analyze 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, are 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 favorable 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 Fielder 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.
dc.description.sponsorship This work has been supported by the Ministerio de Economía y Competitividad of Spain through grant MTM2012-32542
dc.format.extent 41
dc.format.mimetype application/pdf
dc.language.iso eng
dc.publisher Oxford University Press
dc.rights © The author 2015.
dc.rights © Oxford University Press 2015.
dc.subject.other roots of polynomials
dc.subject.other eigenvalues
dc.subject.other characteristic polynomial
dc.subject.other fiedler companion matrices
dc.subject.other backward stability
dc.subject.other conditioning
dc.title Backward stability of polynomial root-finding using Fiedler companion matrices
dc.type article
dc.type conferenceObject
dc.description.status Publicado
dc.relation.publisherversion http://dx.doi.org/10.1093/imanum/dru057
dc.subject.eciencia Matemáticas
dc.identifier.doi 10.1093/imanum/dru057
dc.rights.accessRights openAccess
dc.relation.projectID Gobierno de España. MTM-2012-32542
dc.type.version acceptedVersion
dc.relation.eventdate 2014, September 08-12
dc.relation.eventnumber 6
dc.relation.eventplace Kalamata (Grece)
dc.relation.eventtitle Conference on Structured Numerical Linear and Multilinear Algebra: Analysis, Algorithms and Applications (SLA 2014)
dc.relation.eventtype proceeding
dc.identifier.publicationfirstpage 1
dc.identifier.publicationlastpage 41
dc.identifier.publicationtitle Journal of Numerical Analysis, 2015
dc.identifier.publicationvolume Anal
dc.identifier.uxxi CC/0000022769
 Find Full text

Files in this item

*Click on file's image for preview. (Embargoed files's preview is not supported)


This item appears in the following Collection(s)

Show simple item record