 |
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.
|