Speaker: Dierk Schleicher Title: Newton’s method as an unexpectedly efficient root finder Time: Friday, October 23; 10:00 Place: Aula Magna, Dipartimento di Matematica
Abstract: Newton’s method is well known as a root finder locally near the roots. It is often “not recommended” as a global root finder because of its “chaotic” properties. We give a very efficient theoretical upper bound on its speed of convergence: all roots of a degree d polynomial can be found with accuracy eps in
O(d^2 log^4 d + d log|\log eps|)
Newton iterations in the expected case — very close to the theoretical upper bound of O(d^2) for this method. In practice, all roots of polynomials of degree more than a million are found routinely and in (4log 2) d^2 iterations — in practice, this means less than a day for degree a million on standard laptops. A modified method, for which we do not yet have a complete theory, brings this down to 3 d log^2 d iterations, which in practice for certain polynomials finds all roots of degree a million in a matter of minutes.
===
Everyone is welcome!
Dario A. Bini