On the speed of convergence of Newton’s method for complex polynomials
HTML articles powered by AMS MathViewer
- by Todor Bilarev, Magnus Aspenberg and Dierk Schleicher PDF
- Math. Comp. 85 (2016), 693-705 Request permission
Abstract:
We investigate Newton’s method for complex polynomials of arbitrary degree $d$, normalized so that all their roots are in the unit disk. For each degree $d$, we give an explicit set $\mathcal {S}_d$ of $3.33d\log ^2 d(1 + o(1))$ points with the following universal property: for every normalized polynomial of degree $d$ there are $d$ starting points in $\mathcal {S}_d$ whose Newton iterations find all the roots with a low number of iterations: if the roots are uniformly and independently distributed, we show that with probability at least $1-2/d$ the number of iterations for these $d$ starting points to reach all roots with precision $\varepsilon$ is $O(d^2\log ^4 d + d\log |\log \varepsilon |)$. This is an improvement of an earlier result by Schleicher, where the number of iterations is shown to be $O(d^4\log ^2 d + d^3\log ^2d|\log \varepsilon |)$ in the worst case (allowing multiple roots) and $O(d^3\log ^2 d(\log d + \log \delta ) + d\log |\log \varepsilon |)$ for well-separated (so-called $\delta$-separated) roots.
Our result is almost optimal for this kind of starting points in the sense that the number of iterations can never be smaller than $O(d^2)$ for fixed $\varepsilon$. It provides theoretical support for an empirical study, by Schleicher and Stoll, in which all roots of polynomials of degree $10^6$ and more were found efficiently.
References
- Béla Bollobás, Malte Lackmann, and Dierk Schleicher, A small probabilistic universal set of starting points for finding roots of complex polynomials by Newton’s method, Math. Comp. 82 (2013), no. 281, 443–457. MR 2983031, DOI 10.1090/S0025-5718-2012-02640-8
- John Hubbard, Dierk Schleicher, and Scott Sutherland, How to find all roots of complex polynomials by Newton’s method, Invent. Math. 146 (2001), no. 1, 1–33. MR 1859017, DOI 10.1007/s002220100149
- M. Yu. Lyubich, The measure of maximal entropy of a rational endomorphism of a Riemann sphere, Funktsional. Anal. i Prilozhen. 16 (1982), no. 4, 78–79 (Russian). MR 684138
- Johannes Rückert, Rational and transcendental Newton maps, Holomorphic dynamics and renormalization, Fields Inst. Commun., vol. 53, Amer. Math. Soc., Providence, RI, 2008, pp. 197–211. MR 2477424
- Dierk Schleicher, Newton’s method as a dynamical system: efficient root finding of polynomials and the Riemann $\zeta$ function, Holomorphic dynamics and renormalization, Fields Inst. Commun., vol. 53, Amer. Math. Soc., Providence, RI, 2008, pp. 213–224. MR 2477425
- D. Schleicher, On the efficient global dynamics of Newton’s method for complex polynomials. Manuscript, submitted (2011). arXiv:1108.5773.
- D. Schleicher and R. Stoll, Newton’s method in practice: finding all roots of polynomials of degree one million efficiently. Manuscript, submitted (2015).
Additional Information
- Todor Bilarev
- Affiliation: Institut für Mathematik, Humboldt-Universität zu Berlin, Unter den Linden 6, D-10099 Berlin, Germany
- Email: bilarev.todor@gmail.com
- Magnus Aspenberg
- Affiliation: Centre of Mathematical Sciences, Lund University, Box 11, 221 00 Lund, Sweden
- MR Author ID: 862979
- Email: maspenberg@gmail.com
- Dierk Schleicher
- Affiliation: Research I, Jacobs University Bremen, Postfach 750 561, D-28725 Bremen, Germany
- MR Author ID: 359328
- Email: dierk@jacobs-university.de
- Received by editor(s): August 8, 2012
- Received by editor(s) in revised form: October 9, 2013, and August 5, 2014
- Published electronically: June 18, 2015
- © Copyright 2015 American Mathematical Society
- Journal: Math. Comp. 85 (2016), 693-705
- MSC (2010): Primary 37F10; Secondary 49M15
- DOI: https://doi.org/10.1090/mcom/2985
- MathSciNet review: 3434876