Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 
 

 

Chebyshev rootfinding via computing eigenvalues of colleague matrices: when is it stable?


Authors: Vanni Noferini and Javier Pérez
Journal: Math. Comp. 86 (2017), 1741-1767
MSC (2010): Primary 65H04, 65H17, 65F15, 65G50
DOI: https://doi.org/10.1090/mcom/3149
Published electronically: December 7, 2016
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Computing the roots of a scalar polynomial, or the eigenvalues of a matrix polynomial, expressed in the Chebyshev basis $ \{ T_k(x)\}$ is a fundamental problem that arises in many applications. In this work, we analyze the backward stability of the polynomial rootfinding problem solved with colleague matrices. In other words, given a scalar polynomial $ p(x)$ or a matrix polynomial $ P(x)$ expressed in the Chebyshev basis, the question is to determine whether or not the whole set of computed eigenvalues of the colleague matrix, obtained with a backward stable algorithm, like the QR algorithm, are the set of roots of a nearby polynomial. In order to do so, we derive a first order backward error analysis of the polynomial rootfinding algorithm using colleague matrices adapting the geometric arguments in [A. Edelman and H. Murakami, Polynomial roots for companion matrix eigenvalues, Math. Comp. 210, 763-776, 1995] to the Chebyshev basis. We show that, if the absolute value of the coefficients of $ p(x)$ (respectively, the norm of the coefficients of $ P(x)$) are bounded by a moderate number, computing the roots of $ p(x)$ (respectively, the eigenvalues of $ P(x)$) via the eigenvalues of its colleague matrix using a backward stable eigenvalue algorithm is backward stable. This backward error analysis also expands on the very recent work [Y. Nakatsukasa and V. Noferini, On the stability of computing polynomial roots via confederate linearizations, Math. Comp. 85 (2016), no. 301, 2391-2425] that already showed that this algorithm is not backward normwise stable if the coefficients of the polynomial $ p(x)$ do not have moderate norms.


References [Enhancements On Off] (What's this?)

  • [1] Milton Abramowitz and Irene A. Stegun, Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, National Bureau of Standards Applied Mathematics Series, vol. 55, For sale by the Superintendent of Documents, U.S. Government Printing Office, Washington, D.C., 1964. MR 0167642
  • [2] A. Amiraslani, R. M. Corless, and P. Lancaster, Linearization of matrix polynomials expressed in polynomial bases, IMA J. Numer. Anal. 29 (2009), no. 1, 141-157. MR 2470944, https://doi.org/10.1093/imanum/drm051
  • [3] V. I. Arnol'd, On matrices depending on parameters, Uspehi Mat. Nauk 26 (1971), no. 2(158), 101-114; English transl., Russian Matehmatical Surveys 26 (1971), no. 2, 29-43 (Russian). MR 0301242
  • [4] Stephen Barnett, Polynomials and Linear Control Systems, Monographs and Textbooks in Pure and Applied Mathematics, vol. 77, Marcel Dekker, Inc., New York, 1983. MR 704016
  • [5] Stephen Barnett, Leverrier's algorithm for orthogonal polynomial bases, Linear Algebra Appl. 236 (1996), 245-263. MR 1375617, https://doi.org/10.1016/0024-3795(94)00158-8
  • [6] C. W. Clenshaw, A note on the summation of Chebyshev series, Math. Tables Aids Comput. 9 (1955), 118-120. MR 0071856
  • [7] Fernando De Terán, Froilán M. Dopico, and D. Steven Mackey, Fiedler companion linearizations and the recovery of minimal indices, SIAM J. Matrix Anal. Appl. 31 (2009/10), no. 4, 2181-2204. MR 2678963, https://doi.org/10.1137/090772927
  • [8] F. De Terán, F. M. Dopico, and J. Pérez,
    Backward stability of polynomial root-finding using Fiedler companion matrices,
    IMA J. Numer. Anal., in press, DOI 10.1093/imanum/dru057.
  • [9] Alan Edelman and H. Murakami, Polynomial roots from companion matrix eigenvalues, Math. Comp. 64 (1995), no. 210, 763-776. MR 1262279, https://doi.org/10.2307/2153450
  • [10] Cedric Effenberger and Daniel Kressner, Chebyshev interpolation for nonlinear eigenvalue problems, BIT 52 (2012), no. 4, 933-951. MR 2995213, https://doi.org/10.1007/s10543-012-0381-5
  • [11] I. J. Good, The colleague matrix, a Chebyshev analogue of the companion matrix., Quart. J. Math. Oxford Ser. (2) 12 (1961), 61-68. MR 0132755
  • [12] Peter Lancaster and Miron Tismenetsky, The Theory of Matrices, 2nd ed., Computer Science and Applied Mathematics, Academic Press, Inc., Orlando, FL, 1985. MR 792300
  • [13] Piers W. Lawrence and Robert M. Corless, Stability of rootfinding for barycentric Lagrange interpolants, Numer. Algorithms 65 (2014), no. 3, 447-464. MR 3172327, https://doi.org/10.1007/s11075-013-9770-3
  • [14] Piers W. Lawrence, Marc Van Barel, and Paul Van Dooren, Backward Error Analysis of Polynomial Eigenvalue Problems Solved by Linearization, SIAM J. Matrix Anal. Appl. 37 (2016), no. 1, 123-144. MR 3456391, https://doi.org/10.1137/15M1015777
  • [15] D. Lemmonier and P. Van Dooren,
    Optimal scaling of companion pencils for the QZ-algorithm,
    Proceedings SIAM Appl. Lin. Alg. Conference, Paper CP7-4, 2003.
  • [16] D. Lemmonier and P. Van Dooren,
    Optimal Scaling of Block Companion Pencils,
    Proceedings of the International Symposium on Mathematical Theory of Networks and Systems, Leuven, Belgium, 2004.
  • [17] John Maroulas and Stephen Barnett, Polynomials with respect to a general basis. I. Theory, J. Math. Anal. Appl. 72 (1979), no. 1, 177-194. MR 552330, https://doi.org/10.1016/0022-247X(79)90282-8
  • [18] Yuji Nakatsukasa and Vanni Noferini, On the stability of computing polynomial roots via confederate linearizations, Math. Comp. 85 (2016), no. 301, 2391-2425. MR 3511286, https://doi.org/10.1090/mcom3049
  • [19] Y. Nakatsukasa, V. Noferini, and A. Townsend,
    Vector spaces of linearizations for matrix polynomials: A bivariate polynomial approach, to appear in SIAM J. Matrix Anal. Appl.
  • [20] Vanni Noferini and Federico Poloni, Duality of matrix pencils, Wong chains and linearizations, Linear Algebra Appl. 471 (2015), 730-767. MR 3314361, https://doi.org/10.1016/j.laa.2015.01.015
  • [21] B. N. Parlett and C. Reinsch, Handbook Series Linear Algebra: Balancing a matrix for calculation of eigenvalues and eigenvectors, Numer. Math. 13 (1969), no. 4, 293-304. MR 1553969, https://doi.org/10.1007/BF02165404
  • [22] G. Peters and J. H. Wilkinson, Practical problems arising in the solution of polynomial equations, J. Inst. Math. Appl. 8 (1971), 16-35. MR 0298931
  • [23] Lloyd N. Trefethen, Approximation Theory and Approximation Practice, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2013. MR 3012510
  • [24] L. N. Trefethen et al.,
    Chebfun Version 5. The Chebfun Development Team, 2014. http://www.maths.ox.ac.uk/chebfun/.
  • [25] Kim-Chuan Toh and Lloyd N. Trefethen, Pseudozeros of polynomials and pseudospectra of companion matrices, Numer. Math. 68 (1994), no. 3, 403-425. MR 1313152, https://doi.org/10.1007/s002110050069
  • [26] J. H. Wilkinson, Rounding Errors in Algebraic Processes, Prentice-Hall, Inc., Englewood Cliffs, NJ, 1963. MR 0161456
  • [27] J. H. Wilkinson, The algebraic eigenvalue problem, Clarendon Press, Oxford, 1965. MR 0184422

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 65H04, 65H17, 65F15, 65G50

Retrieve articles in all journals with MSC (2010): 65H04, 65H17, 65F15, 65G50


Additional Information

Vanni Noferini
Affiliation: School of Mathematics, The University of Manchester, Manchester, England, M13 9PL
Address at time of publication: Department of Mathematical Sciences, University of Essex, Wivenhoe Park, Colchester CO4 3SQ, United Kingdom
Email: vnofer@essex.ac.uk

Javier Pérez
Affiliation: School of Mathematics, The University of Manchester, Manchester, England, M13 9PL
Address at time of publication: Department of Rehabilitation Sciences, Biomedical Sciences Group, KU Leuven – University, Tervuursevest 101 – box 1500, 3001 Leuven, Belgium
Email: javier.perezalvaro@kuleuven.be

DOI: https://doi.org/10.1090/mcom/3149
Keywords: Polynomial, roots, Chebyshev basis, matrix polynomial, colleague matrix, backward stability, polynomial eigenvalue problem, Arnold transversality theorem
Received by editor(s): April 5, 2015
Received by editor(s) in revised form: January 13, 2016, and February 9, 2016
Published electronically: December 7, 2016
Additional Notes: The work of the first-named author was supported by European Research Council Advanced Grant MATFUN (267526)
The work of the second-named author was supported by Engineering and Physical Sciences Research Council grant EP/I005293.
Article copyright: © Copyright 2016 American Mathematical Society

American Mathematical Society