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 $\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.