On the Efficiency of Newton's Method in Approximating All Zeros of a System of Complex Polynomials

This paper studies the efficiency of an algorithm based on Newton's method is approximating all zeros of a system of polynomials f = (f 1 , f 2 , …, f n ): ℂ n → ℂ n . The criteria for a successful approximation y of a zero w of f include the following: given ϵ > 0, y is within distance ϵ of w; Newton's method applied to f and initiated at y results in quadratic convergence to w; given ϵ > 0, |f i (y)| < ϵ for all i = 1, 2, …, n, where | | is the Euclidean norm on ℂ. It is shown that, probabilistically, each zero of f is successfully approximated within a determined number of steps.