Sponsored by the Rutgers University Department of Mathematics and the
Center for Discrete Mathematics and Theoretical Computer Science (DIMACS)

Andrew Baxter, Rutgers University, baxter{at} math [dot] rutgers [dot] edu
Doron Zeilberger, Rutgers University, zeilberg {at} math [dot] rutgers [dot] edu

Title: Convergence conditions and simultaneous point estimates for Newton's method

Speaker: Prashant Batra, Hamburg Univ. of Tech. (Hamburg, Germany)

Date: Monday, June 9, 2008 5:00pm

Location: Hill Center, Room 705, Rutgers University, Busch Campus, Piscataway, NJ


The classical semi-local convergence conditions for Newton's method imply quadratic convergence. The essence of quadratic convergence may be captured in the property of starting points to be 'approximate zeros'. Certificates for approximate zeros were developed in the 1980's by Smale, Shub, Kim and others.

These certificates are known as point estimates using only function values at a single point. In the polynomial case, all quantities are effectively computable. This leads to a study of computable convergence methods for single as well as simultaneous iterations, like Newton's, Halley's, the Weierstrass-Durand-Kerner method as well as others.

We show that Newton's method may be used to approximate all zeros of a square-free polynomial simultaneously. Combining this with ideas of Weierstrass, we obtain a completely effective proof of the fundamental theorem of algebra. Our conditions for simultaneous convergence generalize to other iterative methods for polynomials.