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

HTML articles powered by AMS MathViewer

- by Vanni Noferini and Javier Pérez PDF
- Math. Comp.
**86**(2017), 1741-1767 Request permission

## 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

- Milton Abramowitz and Irene A. Stegun,
*Handbook of mathematical functions with formulas, graphs, and mathematical tables*, National Bureau of Standards Applied Mathematics Series, No. 55, U. S. Government Printing Office, Washington, D.C., 1964. For sale by the Superintendent of Documents. MR**0167642** - 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**, DOI 10.1093/imanum/drm051 - V. I. Arnol′d,
*On matrices depending on parameters*, Uspehi Mat. Nauk**26**(1971), no. 2(158), 101–114 (Russian). MR**0301242** - 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** - Stephen Barnett,
*Leverrier’s algorithm for orthogonal polynomial bases*, Linear Algebra Appl.**236**(1996), 245–263. MR**1375617**, DOI 10.1016/0024-3795(94)00158-8 - C. W. Clenshaw,
*A note on the summation of Chebyshev series*, Math. Tables Aids Comput.**9**(1955), 118–120. MR**71856**, DOI 10.1090/S0025-5718-1955-0071856-0 - 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**, DOI 10.1137/090772927 - 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. - Alan Edelman and H. Murakami,
*Polynomial roots from companion matrix eigenvalues*, Math. Comp.**64**(1995), no. 210, 763–776. MR**1262279**, DOI 10.1090/S0025-5718-1995-1262279-2 - Cedric Effenberger and Daniel Kressner,
*Chebyshev interpolation for nonlinear eigenvalue problems*, BIT**52**(2012), no. 4, 933–951. MR**2995213**, DOI 10.1007/s10543-012-0381-5 - I. J. Good,
*The colleague matrix, a Chebyshev analogue of the companion matrix*, Quart. J. Math. Oxford Ser. (2)**12**(1961), 61–68. MR**132755**, DOI 10.1093/qmath/12.1.61 - Peter Lancaster and Miron Tismenetsky,
*The theory of matrices*, 2nd ed., Computer Science and Applied Mathematics, Academic Press, Inc., Orlando, FL, 1985. MR**792300** - Piers W. Lawrence and Robert M. Corless,
*Stability of rootfinding for barycentric Lagrange interpolants*, Numer. Algorithms**65**(2014), no. 3, 447–464. MR**3172327**, DOI 10.1007/s11075-013-9770-3 - 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**, DOI 10.1137/15M1015777 - 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. - 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. - 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**, DOI 10.1016/0022-247X(79)90282-8 - 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**, DOI 10.1090/mcom3049 - 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. - Vanni Noferini and Federico Poloni,
*Duality of matrix pencils, Wong chains and linearizations*, Linear Algebra Appl.**471**(2015), 730–767. MR**3314361**, DOI 10.1016/j.laa.2015.01.015 - 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**, DOI 10.1007/BF02165404 - G. Peters and J. H. Wilkinson,
*Practical problems arising in the solution of polynomial equations*, J. Inst. Math. Appl.**8**(1971), 16–35. MR**298931** - Lloyd N. Trefethen,
*Approximation theory and approximation practice*, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2013. MR**3012510** - L. N. Trefethen et al., Chebfun Version 5. The Chebfun Development Team, 2014. http://www.maths.ox.ac.uk/chebfun/.
- 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**, DOI 10.1007/s002110050069 - J. H. Wilkinson,
*Rounding errors in algebraic processes*, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1963. MR**0161456** - J. H. Wilkinson,
*The algebraic eigenvalue problem*, Clarendon Press, Oxford, 1965. MR**0184422**

## 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
- MR Author ID: 936379
- 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
- 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. - © Copyright 2016 American Mathematical Society
- Journal: Math. Comp.
**86**(2017), 1741-1767 - MSC (2010): Primary 65H04, 65H17, 65F15, 65G50
- DOI: https://doi.org/10.1090/mcom/3149
- MathSciNet review: 3626535