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

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 $\epsilon$ is $O(d^2{\log }^{4}d+d\log |\log \epsilon |)$. This is an improvement of an earlier result in \cite{Schleicher}, where the number of iterations is shown to be $O(d^4{\log }^{2}d+d^3{\log }^{2}d|\log \epsilon |)$ in the worst case (allowing multiple roots) and $O(d^3{\log }^{2}d(\log d+\log \delta )+d\log |\log \epsilon |)$ 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 $\epsilon$.

13 pages, 1 figure, to appear in AMS Mathematics of Computation

References in corpus (1)

• On the Efficient Global Dynamics of Newton's Method for Complex Polynomials

Cited by in corpus (4)

• Newton's method in practice: finding all roots of polynomials of degree one million efficiently
• Newton's method in practice II: The iterated refinement Newton method and near-optimal complexity for finding all roots of some polynomials of very large degrees
• Geometry of Polynomials and Root-Finding via Path-Lifting
• The Weierstrass root finder is not generally convergent