Newton dynamics and root finding

Beyond the theory of polynomials, iterated rational maps seem to be much harder to understand: for polynomials, the superattracting fixed point at  \infty provides a very powerful structure that general rational maps are lacking. A most interesting class of rational maps that can be understood are Newton maps: if  p is a polynomial, then its associated Newton map is  N_p(z)=z-p(z)/p'(z). This is a rational map where the roots of  p are (super)attracting fixed points, and the only further fixed point is  \infty.

Newton maps are of importance for at least two reasons: they can be investigated as dynamical systems — more easily than general rational maps — , and they can be used as root finders of polynomials; both aspects are remarkably successful.

One of the key goals in holomorphic dynamics is to distinguish different dynamical systems in terms of combinatorial invariants. The first, and structurally perhaps most important step, is a classification of all maps in which all critical points have finite orbits: these are the postcritically finite maps. The first large space of holomorphic maps for which we have a classification of postcritically finite maps are polynomials: they can be described and distinguished in terms of Hubbard trees, or equivalently in terms of external angles of the critical value. This classification has been accomplished by Poirier.

Beyond polynomials, the only large space of rational maps for which we have a complete classification is the space of Newton maps of polynomials (while the general space of degree  d rational maps has dimension  2d-2, polynomials have dimension  d-1 and Newton maps have dimension  d-2). This classification has been developed in recent years in our group by our former graduate students Johannes Rückert and Yauhen “Zhenya” Mikulich, and completed recently by Russell Lodge. (Other known classification results usually concern one-dimensional families of maps. Quite different and very interesting classification results are possible using iterated monodromy groups.)

Perhaps surprisingly, there are also transcendental entire functions  f for which the associated Newton maps  N_f(z)=z-f(z)/f'(z) are rational: these have the form  f(z) = p(z)e^{q(z)} with polynomials  p,  q. These Newton maps are never postcritically finite, but one can investigate and classify the postcritically minimal maps within this family; this is another recent result from our group (by Khudoyor Mamayusupov).

One of the most interesting features of Newton maps is their use as root finders: if  p is a polynomial (or a transcendental entire function), then  N_p has fixed points in  \mathbb{C} exactly at the roots of  p, and all of them are superattracting (or, in case of multiple roots, attracting). That means an open set of starting points in  \mathbb{C} will converge to each of the roots under iteration of  N_p. The traditional wisdom is that Newton is very fast once approximate roots are found that still need to be “polished”, while its global dynamics is “chaotic”, so Newton’s method is often not recommended to find approximations of the roots. In recent work, we developed both a good theory of the global dynamics of Newton’s map (after all, we know something about chaos!), and we performed practical experiments on finding roots even of large polynomials. In particular, in joint work with Robin Stoll (then a high school student!), we routinely found all roots of various polynomials of degree one million or more — sometimes much faster than high performance software packages. It turns out that after all, at least for certain families of polynomials Newton’s method is much faster than other known root finding algorithms. We find it quite exciting that even today significant progress can be accomplished on a topic that seems to be classical and well known.

 

Some of our main results:

  • Small universal sets of starting points from which all roots of polynomials of given degree can be found (subject to appropriate normalization):
    John Hubbard, Dierk Schleicher and Scott Sutherland: How to find all roots of complex polynomials with Newton’s method. Inventiones Mathematicae, 146 (2001), 1-33. (article)
    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. Mathematics of Computation 82 281 (2013), 443-457. (arxiv)
  • Theoretical estimates on how many iterations are required to find all roots of polynomials of given degree with guaranteed accuracy:
    Dierk Schleicher: On the Efficient Global Dynamics of Newton's Method for Complex Polynomials. Submitted. (arxiv)
    Todor Bilarev, Magnus Aspenberg, and Dierk Schleicher: On the speed of convergence of Newton's method for complex polynomials. Mathematics of Computation 85 298 (2016), 693-705. (arxiv)
  • Practical algorithms and studies that show that Newton’s method can in practice find all roots of polynomials of degree a million or more, sometimes faster than optimized software packages:
    Dierk Schleicher, Robin Stoll: Newton's method in practice: finding all roots of polynomials of degree one million efficiently. Journal of Theoretical Computer Science (to appear)(arxiv)

Experts within our team: Russell Lodge, Khudoyor Mamayusupov, Dierk Schleicher