Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society, the Mathematics of Computation (MCOM) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

ISSN 1088-6842 (online) ISSN 0025-5718 (print)

The 2020 MCQ for Mathematics of Computation is 1.98.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

On the stability of computing polynomial roots via confederate linearizations
HTML articles powered by AMS MathViewer

by Yuji Nakatsukasa and Vanni Noferini PDF
Math. Comp. 85 (2016), 2391-2425 Request permission

Abstract:

A common way of computing the roots of a polynomial is to find the eigenvalues of a linearization, such as the companion (when the polynomial is expressed in the monomial basis), colleague (Chebyshev basis) or comrade matrix (general orthogonal polynomial basis). For the monomial case, many studies exist on the stability of linearization-based rootfinding algorithms. By contrast, little seems to be known for other polynomial bases. This paper studies the stability of algorithms that compute the roots via linearization in nonmonomial bases, and has three goals. First we prove normwise stability when the polynomial is properly scaled and the QZ algorithm (as opposed to the more commonly used QR algorithm) is applied to a comrade pencil associated with a Jacobi orthogonal polynomial. Second, we extend a result by Arnold that leads to a first-order expansion of the backward error when the eigenvalues are computed via QR, which shows that the method can be unstable. Based on the analysis we suggest how to choose between QR and QZ. Finally, we focus on the special case of the Chebyshev basis and finding real roots of a general function on an interval, and discuss how to compute accurate roots. The main message is that to guarantee backward stability QZ applied to a properly scaled pencil is necessary.
References
Similar Articles
  • Retrieve articles in Mathematics of Computation with MSC (2010): 65H04, 65F15
  • Retrieve articles in all journals with MSC (2010): 65H04, 65F15
Additional Information
  • Yuji Nakatsukasa
  • Affiliation: Department of Mathematical Informatics, University of Tokyo, Tokyo 113-8656, Japan
  • Email: nakatsukasa@mist.i.u-tokyo.ac.jp
  • Vanni Noferini
  • Affiliation: School of Mathematics, University of Manchester, Manchester, M13 9PL, United Kingdom
  • Address at time of publication: Department of Mathematical Sciences, University of Essex, Wivenhoe Park, Colchester CO4 3SQ, United Kingdom
  • MR Author ID: 936379
  • Email: vnofer@essex.ac.uk
  • Received by editor(s): September 25, 2014
  • Received by editor(s) in revised form: February 12, 2015
  • Published electronically: November 10, 2015
  • Additional Notes: The first author was supported by JSPS Scientific Research Grant No. 26870149.
    The second author was supported by ERC Advanced Grant MATFUN (267526)
  • © Copyright 2015 American Mathematical Society
  • Journal: Math. Comp. 85 (2016), 2391-2425
  • MSC (2010): Primary 65H04; Secondary 65F15
  • DOI: https://doi.org/10.1090/mcom3049
  • MathSciNet review: 3511286