On the Convergence of Newton's Method
  • Postscript version.
  • Dvi version.
  • PDF version.

  • Abstract:

    Let $P_d$ be the set of polynomials over the complex numbers of degree $d$ with all its roots in the unit ball. For $f\in P_d$, let $\Gamma_f$ be the set of points for which Newton's method converges to a root, and let $A_f\equiv |\Gamma_f \cap B_2(0)| /|B_2(0)|$, i.e. the density of $\Gamma_f$ in the ball of radius 2 (where $|\ |$ denotes Lebesgue measure on $\complex$ viewed as $\reals^2$). For each $d$ we consider $A_d$, the worst-case density (i.e. infimum) of $A_f$ for $f\in P_d$. In [S], S. Smale conjectured that $A_d \gt 0$ for all $d \ge 3$ (it was well-known that $A_1=A_2=1$). In this paper we prove that $$ \biggl( {1\over d} \biggr) ^ {cd^2\log d} \le A_d $$ for some constant $c$. In particular, $A_d\gt 0$ for all $d$. Remark: Our definition of $A_d$ differs slightly from that in [S], but the conclusions hold for $A_d$ as defined in [S] as well.