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
