On the speed of convergence of Newton's method for complex polynomials

Authors:
Todor Bilarev, Magnus Aspenberg and Dierk Schleicher

Journal:
Math. Comp. **85** (2016), 693-705

MSC (2010):
Primary 37F10; Secondary 49M15

DOI:
https://doi.org/10.1090/mcom/2985

Published electronically:
June 18, 2015

MathSciNet review:
3434876

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We investigate Newton's method for complex polynomials of arbitrary degree , normalized so that all their roots are in the unit disk. For each degree , we give an explicit set of points with the following universal property: for every normalized polynomial of degree there are starting points in 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 the number of iterations for these starting points to reach all roots with precision is . This is an improvement of an earlier result by Schleicher, where the number of iterations is shown to be in the worst case (allowing multiple roots) and for well-separated (so-called -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 for fixed . It provides theoretical support for an empirical study, by Schleicher and Stoll, in which all roots of polynomials of degree and more were found efficiently.

**[BLS]**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**, https://doi.org/10.1090/S0025-5718-2012-02640-8**[HSS]**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**, https://doi.org/10.1007/s002220100149**[L]**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****[R]**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****[S1]**Dierk Schleicher,*Newton’s method as a dynamical system: efficient root finding of polynomials and the Riemann 𝜁 function*, Holomorphic dynamics and renormalization, Fields Inst. Commun., vol. 53, Amer. Math. Soc., Providence, RI, 2008, pp. 213–224. MR**2477425**- [S2]
D. Schleicher,
*On the efficient global dynamics of Newton's method for complex polynomials*. Manuscript, submitted (2011). arXiv:1108.5773. - [SSt]
D. Schleicher and R. Stoll,
*Newton's method in practice: finding all roots of polynomials of degree one million efficiently*. Manuscript, submitted (2015).

Retrieve articles in *Mathematics of Computation*
with MSC (2010):
37F10,
49M15

Retrieve articles in all journals with MSC (2010): 37F10, 49M15

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

Email:
maspenberg@gmail.com

**Dierk Schleicher**

Affiliation:
Research I, Jacobs University Bremen, Postfach 750 561, D-28725 Bremen, Germany

Email:
dierk@jacobs-university.de

DOI:
https://doi.org/10.1090/mcom/2985

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

Article copyright:
© Copyright 2015
American Mathematical Society