Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

Request Permissions   Purchase Content 
 

 

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 $ 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 \vert\log \varepsilon \vert)$. 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\vert\log \varepsilon \vert)$ in the worst case (allowing multiple roots) and $ O(d^3\log ^2 d(\log d + \log \delta ) + d\log \vert\log \varepsilon \vert)$ 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 [Enhancements On Off] (What's this?)


Similar Articles

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