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

Source abstract

We investigate Newton’s method for complex polynomials of arbitrary degree d d , normalized so that all their roots are in the unit disk. For each degree d d , we give an explicit set S d \mathcal {S}_d of 3.33 d log 2 ⁡ d ( 1 + o ( 1 ) ) 3.33d\log ^2 d(1 + o(1)) points with the following universal property: for every normalized polynomial of degree d d there are d d starting points in S d \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 1-2/d the number of iterations for these d d starting points to reach all roots with precision ε \varepsilon is O ( d 2 log 4 ⁡ d + d log ⁡ | log ⁡ ε | ) 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 2 ⁡ d | log ⁡ ε | ) 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 ⁡ δ ) + d log ⁡ | log ⁡ ε | ) 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 ) 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 10^6 and more were found efficiently.