ETNA  Electronic Transactions on Numerical Analysis

Verlag der Österreichischen Akademie der Wissenschaften Austrian Academy of Sciences Press
A1011 Wien, Dr. Ignaz SeipelPlatz 2
Tel. +431515 81/DW 3420, Fax +431515 81/DW 3400 https://verlag.oeaw.ac.at, email: verlag@oeaw.ac.at 

DATUM, UNTERSCHRIFT / DATE, SIGNATURE
BANK AUSTRIA CREDITANSTALT, WIEN (IBAN AT04 1100 0006 2280 0100, BIC BKAUATWW), DEUTSCHE BANK MÜNCHEN (IBAN DE16 7007 0024 0238 8270 00, BIC DEUTDEDBMUC)

ETNA  Electronic Transactions on Numerical Analysis ISBN 9783700182580 Online Edition Research Article
Vanni Noferini,
Leonardo Robol,
Raf Vandebril
S. 420  442 doi:10.1553/etna_vol54s420 Verlag der Österreichischen Akademie der Wissenschaften doi:10.1553/etna_vol54s420
Abstract: A standard approach to calculate the roots of a univariate polynomial is to compute the eigenvalues of an associated 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 nonstructureexploiting QR algorithm. In [J. L. Aurentz et al., Fast and backward stable computation of roots of polynomials, SIAM J. Matrix Anal. Appl., 36 (2015), pp. 942–973] it was shown that a structureexploiting QR algorithm for companion matrices leads to a structured backward error in the companion matrix. The proof relied on decomposing the error into two parts: a part related to the recurrence coefficients of the basis (a 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 in the confederate matrix gets mapped to the associated polynomial coefficients. This insight reveals which properties have to be preserved by a structureexploiting QR algorithm to end up with a backward stable algorithm. We will show that the previously formulated companion analysis fits into this framework, and we analyze in more detail Jacobi polynomials (comrade matrices) and Chebyshev polynomials (colleague matrices). Keywords: backward error, structured QR, linearization, comrade matrix, colleague matrix, companion matrix Published Online: 2021/06/07 14:04:44 Object Identifier: 0xc1aa5572 0x003c8ac7 Rights: . Electronic Transactions on Numerical Analysis (ETNA) is an electronic journal for the publication of significant new developments in numerical analysis and scientific computing. Papers of the highest quality that deal with the analysis of algorithms for the solution of continuous models and numerical linear algebra are appropriate for ETNA, as are papers of similar quality that discuss implementation and performance of such algorithms. New algorithms for current or new computer architectures are appropriate provided that they are numerically sound. However, the focus of the publication should be on the algorithm rather than on the architecture. The journal is published by the Kent State University Library in conjunction with the Institute of Computational Mathematics at Kent State University, and in cooperation with the Johann Radon Institute for Computational and Applied Mathematics of the Austrian Academy of Sciences (RICAM). Reviews of all ETNA papers appear in Mathematical Reviews and Zentralblatt für Mathematik. Reference information for ETNA papers also appears in the expanded Science Citation Index. ETNA is registered with the Library of Congress and has ISSN 10689613. …

Verlag der Österreichischen Akademie der Wissenschaften Austrian Academy of Sciences Press
A1011 Wien, Dr. Ignaz SeipelPlatz 2
Tel. +431515 81/DW 3420, Fax +431515 81/DW 3400 https://verlag.oeaw.ac.at, email: verlag@oeaw.ac.at 