Smale's notion of an approximate zero of an analytic function f: C → C is extended to take into account the errors incurred in the evaluation of the Newton operator. Call this stronger notion a robust approximate zero. We develop a corresponding robust point estimate for such zeros: we prove that if z_0 ∈ C satisfies α(f, Z_0) < 0.02 then Z_0 is a robust approximate zero, with the associated zero z~* lying in the closed disc B(Z_0, (0.07/γ(f, z_0))). Here α(f, z), γ(f, z) are standard functions in point estimates. Suppose f(z) is an L-bit integer square-free polynomial of degree d. Using our new algorithm, we can compute an n-bit absolute approximation of 2~* ∈ IR starting from a bigfloat zo, in time O[dM(n + d~2(L + lg d) lg(n + L))], where M(n) is the complexity of multiplying n-bit integers.
展开▼
