Title: Robust Approximate Zeros in Higher Dimensions.
Abstract: Smale had introduced the notion of approximate zeros: If $f$
is an analytic function between two Banach spaces $E$, $F$ then a
point $z_0$ is called an approximate zero of $f$ if there is a unique
zero $z^*$ of $f$ such that the Newton iterates $z_i$ quadratically
converge to $z^*$, i.e., $||z_i - z*^|| \le 2^{1-2^i}||z_0 -
z^*||$. To computationally identify approximate zeros, Smale
introduced the notion of point estimates. In particular, he showed
that there is an easily computable function $\alpha(f,z)$ such that if
$\alpha(f, z) < C$, for some universal global constant $C$, then $z$
is an approximate zero; one choice of $C$ is $0.03$. The problem with
Smale's approach is that he assumes it is possible to compute the
Newton iterates exactly. In practice, however, this is rarely the case
so. We extend Smale's concept of approximate zeros to two
computational models that account for errors in the computation:
first, the weak model where the computations are done with a fixed
precision; and second, the strong model where the computations are
done with varying precision. For both models, we develop a notion of
robust approximate zero and derive a corresponding robust point
estimate.
For the special case of a zero-dimensional system of integer
polynomials, we bound the complexity of computing an absolute
approximation to a root of the system using the strong model variant
of Newton's method initiated from a robust approximate zero. The bound
is expressed in terms of the condition number of the system and is a
generalization of a well-known bound of Brent to higher
dimensions. For implementation's sake, we also derive the explicit
constants involved in the asymptotic bound on the precision required
at each iteration of Newton's method in both the weak and the strong
computational model.