On the stability of computing polynomial roots via confederate linearizations

Nakatsukasa, Yuji; Noferini, Vanni

doi:10.1090/mcom3049

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

M. Abramowitz and I. A. Stegun, Handbook of Mathematical Functions: with Formulas, Graphs, and Mathematical Tables, Number 55, Courier Dover Publications, 1972.
Robert A. Adams, Sobolev spaces, Pure and Applied Mathematics, Vol. 65, Academic Press [Harcourt Brace Jovanovich, Publishers], New York-London, 1975. MR 0450957
D. E. Amos, Algorithm $610$. A portable FORTRAN subroutine for derivatives of the psi function, ACM Trans. Math. Software 9 (1983), no. 4, 494–502. MR 791979, DOI 10.1145/356056.356065
V. I. Arnol′d, On matrices depending on parameters, Uspehi Mat. Nauk 26 (1971), no. 2(158), 101–114 (Russian). MR 0301242
J. L. Aurentz, T. Mach, R. Vandebril, and D. S. Watkins, Fast and backward stable computation of roots of polynomials, preprint, 2014.
Jared L. Aurentz, Raf Vandebril, and David S. Watkins, Fast computation of eigenvalues of companion, comrade, and related matrices, BIT 54 (2014), no. 1, 7–30. MR 3177953, DOI 10.1007/s10543-013-0449-x
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
R. Bevilacqua, G. M. Del Corso, and L. Gemignani, A CMV–based eigensolver for companion matrices, arXiv preprint arXiv:1406.2820, 2014.
Dario Andrea Bini and Giuseppe Fiorentino, Design, analysis, and implementation of a multiprecision polynomial rootfinder, Numer. Algorithms 23 (2000), no. 2-3, 127–173. MR 1772050, DOI 10.1023/A:1019199917103
Dario A. Bini, Luca Gemignani, and Victor Y. Pan, Fast and stable QR eigenvalue algorithms for generalized companion matrices and secular equations, Numer. Math. 100 (2005), no. 3, 373–408. MR 2194524, DOI 10.1007/s00211-005-0595-4
D. Bini, L. Gemignani, and V. Y. Pan, Fast QR eigenvalue algorithms for Hessenberg matrices which are rank-one perturbations of unitary matrices, SIAM J. Matrix Anal. Appl. 29 (2007), no. 2, 556–585.
Dario A. Bini and Leonardo Robol, Solving secular and polynomial equations: a multiprecision algorithm, J. Comput. Appl. Math. 272 (2014), 276–292. MR 3227386, DOI 10.1016/j.cam.2013.04.037
Dario Andrea Bini, Numerical computation of polynomial zeros by means of Aberth’s method, Numer. Algorithms 13 (1996), no. 3-4, 179–200 (1997). MR 1430518, DOI 10.1007/BF02207694
P. Boito, Y. Eidelman, and L. Gemignani, Implicit QR for companion-like pencils, arXiv preprint 1401.5606, 2014.
P. Boito, Y. Eidelman, and L. Gemignani, Implicit QR for rank-structured matrix pencils, BIT 54 (2014), no. 1, 85–111. MR 3177956, DOI 10.1007/s10543-014-0478-0
John P. Boyd, Computing real roots of a polynomial in Chebyshev series form through subdivision, Appl. Numer. Math. 56 (2006), no. 8, 1077–1091. MR 2234841, DOI 10.1016/j.apnum.2005.09.007
Carl B. Boyer, A history of mathematics, John Wiley & Sons, Inc., New York-London-Sydney, 1968. MR 0234791
E. W. Cheney, Introduction to approximation theory, AMS Chelsea Publishing, Providence, RI, 1998. Reprint of the second (1982) edition. MR 1656150
David A. Cox, John Little, and Donal O’Shea, Using algebraic geometry, 2nd ed., Graduate Texts in Mathematics, vol. 185, Springer, New York, 2005. MR 2122859
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, MIMS EPrint 2014.38, 2014, preprint.
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
Miroslav Fiedler, A note on companion matrices, Linear Algebra Appl. 372 (2003), 325–331. MR 1999154, DOI 10.1016/S0024-3795(03)00548-2
Gene H. Golub and John H. Welsch, Calculation of Gauss quadrature rules, Math. Comp. 23 (1969), 221-230; addendum, ibid. 23 (1969), no. 106, loose microfiche suppl, A1–A10. MR 0245201, DOI 10.1090/S0025-5718-69-99647-1
G. H. Golub and C. F. Van Loan. Matrix Computations. The Johns Hopkins University Press, 4th edition, 2012.
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
N. Hale and A. Townsend, A fast FFT-based discrete Legendre transform, IMA J. Numer. Anal., to appear.
Nicholas J. Higham, Accuracy and stability of numerical algorithms, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1996. MR 1368629
Roger A. Horn and Charles R. Johnson, Matrix analysis, 2nd ed., Cambridge University Press, Cambridge, 2013. MR 2978290
E. K. Ifantis and P. D. Siafarikas, Perturbation of the coefficients in the recurrence relation of a class of polynomials, Proceedings of the Fourth International Symposium on Orthogonal Polynomials and their Applications (Evian-Les-Bains, 1992), 1995, pp. 163–170. MR 1340933, DOI 10.1016/0377-0427(93)E0242-E
M. A. Jenkins and J. F. Traub, A three-stage variable-shift iteration for polynomial zeros and its relation to generalized Rayleigh iteration, Numer. Math. 14 (1969/70), 252–263. MR 258271, DOI 10.1007/BF02163334
Gudbjörn F. Jónsson and Stephen Vavasis, Solving polynomials with small leading coefficients, SIAM J. Matrix Anal. Appl. 26 (2004/05), no. 2, 400–414. MR 2124155, DOI 10.1137/S0895479899365720
Immo O. Kerner, Ein Gesamtschrittverfahren zur Berechnung der Nullstellen von Polynomen, Numer. Math. 8 (1966), 290–294 (German). MR 203931, DOI 10.1007/BF02162564
Piers W. Lawrence, Fast reduction of generalized companion matrix pairs for barycentric Lagrange interpolants, SIAM J. Matrix Anal. Appl. 34 (2013), no. 3, 1277–1300. MR 3095477, DOI 10.1137/130904508
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
John M. Lee, Introduction to smooth manifolds, Graduate Texts in Mathematics, vol. 218, Springer-Verlag, New York, 2003. MR 1930091, DOI 10.1007/978-0-387-21752-9
D. Lemonnier and P. Van Dooren, Optimal scaling of companion pencils for the QZ algorithm, in Proceedings SIAM Applied Linear Algebra Conference, 2003.
Elie Leopold, Perturbed recurrence relations, Numer. Algorithms 33 (2003), no. 1-4, 357–366. International Conference on Numerical Algorithms, Vol. I (Marrakesh, 2001). MR 2005575, DOI 10.1023/A:1025592811765
F. Marcellán, J. S. Dehesa, and A. Ronveaux, On orthogonal polynomials with perturbed recurrence relations, J. Comput. Appl. Math. 30 (1990), no. 2, 203–212. MR 1062324, DOI 10.1016/0377-0427(90)90028-X
J. C. Mason and D. C. Handscomb, Chebyshev polynomials, Chapman & Hall/CRC, Boca Raton, FL, 2003. MR 1937591
NAG Ltd. The NAG C Library Manual, Mark 7. The Numerical Algorithms Group, 2002. http://www.nag.co.uk/numeric/cl/manual/pdf/G05/g05cac.pdf and http://www.nag.co.uk/numeric/fl/manual/pdf/G05/g05kaf.pdf.
Y. Nakatsukasa, V. Noferini, and A. Townsend, Vector spaces of linearizations for matrix polynomials: a bivariate polynomial approach, The Mathematical Institute, University of Oxford, Eprints Archive 1638, 2013.
Yuji Nakatsukasa, Vanni Noferini, and Alex Townsend, Computing the common zeros of two bivariate functions via Bézout resultants, Numer. Math. 129 (2015), no. 1, 181–209. MR 3296156, DOI 10.1007/s00211-014-0635-z
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
Victor Y. Pan, Solving a polynomial equation: some history and recent progress, SIAM Rev. 39 (1997), no. 2, 187–220. MR 1453318, DOI 10.1137/S0036144595288554
Victor Y. Pan, Approximating complex polynomial zeros: modified Weyl’s quadtree construction and improved Newton’s iteration, J. Complexity 16 (2000), no. 1, 213–264. Real computation and complexity (Schloss Dagstuhl, 1998). MR 1762403, DOI 10.1006/jcom.1999.0532
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. W. Stewart and Ji Guang Sun, Matrix perturbation theory, Computer Science and Scientific Computing, Academic Press, Inc., Boston, MA, 1990. MR 1061154
G. Szegő. Orthogonal Polynomials, AMS Colloquium Publications, 1992.
Françoise Tisseur, Backward error and condition of polynomial eigenvalue problems, Proceedings of the International Workshop on Accurate Solution of Eigenvalue Problems (University Park, PA, 1998), 2000, pp. 339–361. MR 1758374, DOI 10.1016/S0024-3795(99)00063-4
A. Townsend, Private communication, 2015.
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/.
Paul Van Dooren and Patrick Dewilde, The eigenstructure of an arbitrary polynomial matrix: computational aspects, Linear Algebra Appl. 50 (1983), 545–579. MR 699575, DOI 10.1016/0024-3795(83)90069-1
Raf Vandebril, Chasing bulges or rotations? A metamorphosis of the QR-algorithm, SIAM J. Matrix Anal. Appl. 32 (2011), no. 1, 217–247. MR 2811298, DOI 10.1137/100809167
Alfonso Villani, Another note on the inclusion $L^p(\mu )\subset L^q(\mu )$, Amer. Math. Monthly 92 (1985), no. 7, 485–487. MR 801221, DOI 10.2307/2322503
H. S. Wilf, Mathematics for the Physical Sciences. Courier Dover Publications, 2013.