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

Abstract

This paper studies the efficiency of an algorithm based on Newton's method is approximating all zeros of a system of polynomials f = (f₁, f₂, …, f_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.