Newton’s method as an interesting dynamical system and as an unexpectedly efficient root finder

Dierk Schleicher (Math, Jacobs University, Bremen, Germany)

Abstract: We discuss Newton’s method as a root finder for polynomials of large degrees, and as an interesting dynamical system in its own right. There is recent progress on Newton’s method in at least three directions:

- We present recent experiments on finding all roots of Newton’s method for a number of large polynomials, for degrees exceeding one billion, on standard laptops with surprising ease and in short time, with observed complexity O(d log^2 d) (joint with Marvin Randig, Simon Schmitt and Robin Stoll).
- We outline theory about the complexity of Newton’s method as a root finder: unlike various other known methods, Newton as a root finder has both good theory and good implementation results in practice (partly joint work with Magnus Aspenberg, Todor Bilarev, Bela Bollobas, and Malte Lackmann).
- We discuss Newton’s method as a dynamical system: if p is a polynomial, then the Newton map is a rational map that very naturally “wants to be iterated”. Among all rational maps, Newton’s method has the best understood dynamics, and these dynamical systems can be classified (in the sense of a theory developed by Bill Thurston). As a byproduct, we offer an answer to a question of Steve Smale on existence of attracting cycles of higher period (joint work with Kostiantyn Drach, Russell Lodge and Yauhen Mikulich).