{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,14]],"date-time":"2026-05-14T10:33:56Z","timestamp":1778754836939,"version":"3.51.4"},"reference-count":27,"publisher":"American Mathematical Society (AMS)","issue":"306","license":[{"start":{"date-parts":[[2017,12,7]],"date-time":"2017-12-07T00:00:00Z","timestamp":1512604800000},"content-version":"am","delay-in-days":365,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["267526"],"award-info":[{"award-number":["267526"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["EP\/I005293"],"award-info":[{"award-number":["EP\/I005293"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["267526"],"award-info":[{"award-number":["267526"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/I005293"],"award-info":[{"award-number":["EP\/I005293"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"

\n Computing the roots of a scalar polynomial, or the eigenvalues of a matrix polynomial, expressed in the Chebyshev basis\n \n \n \n \n {<\/mml:mo>\n \n T<\/mml:mi>\n k<\/mml:mi>\n <\/mml:msub>\n (<\/mml:mo>\n x<\/mml:mi>\n )<\/mml:mo>\n }<\/mml:mo>\n <\/mml:mrow>\n \\{ T_k(x)\\}<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n 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\n \n \n \n \n p<\/mml:mi>\n (<\/mml:mo>\n x<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n p(x)<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n or a matrix polynomial\n \n \n \n \n P<\/mml:mi>\n (<\/mml:mo>\n x<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n P(x)<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n 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,\n Polynomial roots for companion matrix eigenvalues<\/italic>\n , Math. Comp. 210, 763\u2013776, 1995] to the Chebyshev basis. We show that, if the absolute value of the coefficients of\n \n \n \n \n p<\/mml:mi>\n (<\/mml:mo>\n x<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n p(x)<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n (respectively, the norm of the coefficients of\n \n \n \n \n P<\/mml:mi>\n (<\/mml:mo>\n x<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n P(x)<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n ) are bounded by a moderate number, computing the roots of\n \n \n \n \n p<\/mml:mi>\n (<\/mml:mo>\n x<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n p(x)<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n (respectively, the eigenvalues of\n \n \n \n \n P<\/mml:mi>\n (<\/mml:mo>\n x<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n P(x)<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n ) 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,\n On the stability of computing polynomial roots via confederate linearizations<\/italic>\n , Math. Comp.\n 85<\/bold>\n (2016), no. 301, 2391\u20132425] that already showed that this algorithm is not backward normwise stable if the coefficients of the polynomial\n \n \n \n \n p<\/mml:mi>\n (<\/mml:mo>\n x<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n p(x)<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n do not have moderate norms.\n <\/p>","DOI":"10.1090\/mcom\/3149","type":"journal-article","created":{"date-parts":[[2016,11,25]],"date-time":"2016-11-25T14:59:29Z","timestamp":1480085969000},"page":"1741-1767","source":"Crossref","is-referenced-by-count":12,"title":["Chebyshev rootfinding via computing eigenvalues of colleague matrices: when is it stable?"],"prefix":"10.1090","volume":"86","author":[{"given":"Vanni","family":"Noferini","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Javier","family":"P\u00e9rez","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"14","published-online":{"date-parts":[[2016,12,7]]},"reference":[{"key":"1","series-title":"National Bureau of Standards Applied Mathematics Series, No. 55","volume-title":"Handbook of mathematical functions with formulas, graphs, and mathematical tables","author":"Abramowitz, Milton","year":"1964"},{"issue":"1","key":"2","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1093\/imanum\/drm051","article-title":"Linearization of matrix polynomials expressed in polynomial bases","volume":"29","author":"Amiraslani, A.","year":"2009","journal-title":"IMA J. Numer. Anal.","ISSN":"https:\/\/id.crossref.org\/issn\/0272-4979","issn-type":"print"},{"issue":"2","key":"3","first-page":"101","article-title":"On matrices depending on parameters","volume":"26","author":"Arnol\u2032d, V. I.","year":"1971","journal-title":"Uspehi Mat. Nauk","ISSN":"https:\/\/id.crossref.org\/issn\/0042-1316","issn-type":"print"},{"key":"4","series-title":"Monographs and Textbooks in Pure and Applied Mathematics","isbn-type":"print","volume-title":"Polynomials and linear control systems","volume":"77","author":"Barnett, Stephen","year":"1983","ISBN":"https:\/\/id.crossref.org\/isbn\/0824718984"},{"key":"5","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1016\/0024-3795(94)00158-8","article-title":"Leverrier\u2019s algorithm for orthogonal polynomial bases","volume":"236","author":"Barnett, Stephen","year":"1996","journal-title":"Linear Algebra Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0024-3795","issn-type":"print"},{"key":"6","doi-asserted-by":"crossref","first-page":"118","DOI":"10.1090\/S0025-5718-1955-0071856-0","article-title":"A note on the summation of Chebyshev series","volume":"9","author":"Clenshaw, C. W.","year":"1955","journal-title":"Math. Tables Aids Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0891-6837","issn-type":"print"},{"issue":"4","key":"7","doi-asserted-by":"publisher","first-page":"2181","DOI":"10.1137\/090772927","article-title":"Fiedler companion linearizations and the recovery of minimal indices","volume":"31","author":"De Ter\u00e1n, Fernando","year":"2009","journal-title":"SIAM J. Matrix Anal. Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0895-4798","issn-type":"print"},{"key":"8","unstructured":"F. De Ter\u00e1n, F. M. Dopico, and J. P\u00e9rez, Backward stability of polynomial root-finding using Fiedler companion matrices, IMA J. Numer. Anal., in press, DOI 10.1093\/imanum\/dru057."},{"issue":"210","key":"9","doi-asserted-by":"publisher","first-page":"763","DOI":"10.2307\/2153450","article-title":"Polynomial roots from companion matrix eigenvalues","volume":"64","author":"Edelman, Alan","year":"1995","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"4","key":"10","doi-asserted-by":"publisher","first-page":"933","DOI":"10.1007\/s10543-012-0381-5","article-title":"Chebyshev interpolation for nonlinear eigenvalue problems","volume":"52","author":"Effenberger, Cedric","year":"2012","journal-title":"BIT","ISSN":"https:\/\/id.crossref.org\/issn\/0006-3835","issn-type":"print"},{"key":"11","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1093\/qmath\/12.1.61","article-title":"The colleague matrix, a Chebyshev analogue of the companion matrix","volume":"12","author":"Good, I. J.","year":"1961","journal-title":"Quart. J. Math. Oxford Ser. (2)","ISSN":"https:\/\/id.crossref.org\/issn\/0033-5606","issn-type":"print"},{"key":"12","series-title":"Computer Science and Applied Mathematics","isbn-type":"print","volume-title":"The theory of matrices","author":"Lancaster, Peter","year":"1985","ISBN":"https:\/\/id.crossref.org\/isbn\/0124355609","edition":"2"},{"issue":"3","key":"13","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1007\/s11075-013-9770-3","article-title":"Stability of rootfinding for barycentric Lagrange interpolants","volume":"65","author":"Lawrence, Piers W.","year":"2014","journal-title":"Numer. Algorithms","ISSN":"https:\/\/id.crossref.org\/issn\/1017-1398","issn-type":"print"},{"issue":"1","key":"14","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1137\/15M1015777","article-title":"Backward error analysis of polynomial eigenvalue problems solved by linearization","volume":"37","author":"Lawrence, Piers W.","year":"2016","journal-title":"SIAM J. Matrix Anal. Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0895-4798","issn-type":"print"},{"key":"15","unstructured":"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."},{"key":"16","unstructured":"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."},{"issue":"1","key":"17","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/0022-247X(79)90282-8","article-title":"Polynomials with respect to a general basis. I. Theory","volume":"72","author":"Maroulas, John","year":"1979","journal-title":"J. Math. Anal. Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0022-247X","issn-type":"print"},{"issue":"301","key":"18","doi-asserted-by":"publisher","first-page":"2391","DOI":"10.1090\/mcom3049","article-title":"On the stability of computing polynomial roots via confederate linearizations","volume":"85","author":"Nakatsukasa, Yuji","year":"2016","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"19","unstructured":"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."},{"key":"20","doi-asserted-by":"publisher","first-page":"730","DOI":"10.1016\/j.laa.2015.01.015","article-title":"Duality of matrix pencils, Wong chains and linearizations","volume":"471","author":"Noferini, Vanni","year":"2015","journal-title":"Linear Algebra Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0024-3795","issn-type":"print"},{"issue":"4","key":"21","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/BF02165404","article-title":"Handbook Series Linear Algebra: Balancing a matrix for calculation of eigenvalues and eigenvectors","volume":"13","author":"Parlett, B. N.","year":"1969","journal-title":"Numer. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0029-599X","issn-type":"print"},{"key":"22","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1093\/imamat\/8.1.16","article-title":"Practical problems arising in the solution of polynomial equations","volume":"8","author":"Peters, G.","year":"1971","journal-title":"J. Inst. Math. Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/0020-2932","issn-type":"print"},{"key":"23","isbn-type":"print","volume-title":"Approximation theory and approximation practice","author":"Trefethen, Lloyd N.","year":"2013","ISBN":"https:\/\/id.crossref.org\/isbn\/9781611972399"},{"key":"24","unstructured":"L. N. Trefethen et al., Chebfun Version 5. The Chebfun Development Team, 2014. http:\/\/www.maths.ox.ac.uk\/chebfun\/."},{"issue":"3","key":"25","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1007\/s002110050069","article-title":"Pseudozeros of polynomials and pseudospectra of companion matrices","volume":"68","author":"Toh, Kim-Chuan","year":"1994","journal-title":"Numer. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0029-599X","issn-type":"print"},{"key":"26","volume-title":"Rounding errors in algebraic processes","author":"Wilkinson, J. H.","year":"1963"},{"key":"27","volume-title":"The algebraic eigenvalue problem","author":"Wilkinson, J. H.","year":"1965"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.ams.org\/mcom\/2017-86-306\/S0025-5718-2016-03149-X\/mcom3149_AM.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"http:\/\/www.ams.org\/mcom\/2017-86-306\/S0025-5718-2016-03149-X\/S0025-5718-2016-03149-X.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2017-86-306\/S0025-5718-2016-03149-X\/S0025-5718-2016-03149-X.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T19:12:49Z","timestamp":1776798769000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2017-86-306\/S0025-5718-2016-03149-X\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,12,7]]},"references-count":27,"journal-issue":{"issue":"306","published-print":{"date-parts":[[2017,7]]}},"alternative-id":["S0025-5718-2016-03149-X"],"URL":"https:\/\/doi.org\/10.1090\/mcom\/3149","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[2016,12,7]]}}}