ISSAC 94 - Symbolic-Numeric Nonlinear Equation Solving
 Contents News View

 Simple Zeros of a Holomorphic Function

In this section we sketch ideas we have implemented to compute zeros of a smooth real-valued function on a real interval.  Let be holomorphic on , be a closed real interval contained in , be real valued on , be not constant on , and have simple zeros on

Since is holomorphic, is infinitely differentiable.  (Corollary 2.12, page 73, Conway[5]).  Since is compact, and have finitely many zeros on .  (Theorem 3.7, page 78, Conway[5]).  The zeros of on are distinct from the zeros of on because the zeros of are simple.  Therefore, recursively bisecting into increasingly smaller subintervals eventually isolates each zero of on in a subinterval on which is also strictly monotone.

Now, we assume the existence of an interval arithmetic package such that given any derivative of and subinterval , we have

with either or .  Given any set , define open neighborhoods about by

We let represent the closure of

We will assume has the following continuity property: Given any , , and derivative of , there exists ( may depend on , , and ) such that if , then .  In fact, by the compactness of we can suppose is independent of (see Rudin[14]).

All of the above leads us to the following primitive algorithm for detecting zeros of .

proc Zeros
if not CouldBeZero then
return ;
elif not CouldBeZero then
if then
return ;
else
return Locate;
fi;
else
;
if then
return Zeros Zeros;
else
;
while CouldBeZero do
;
od;
return Zeros
Zeros;
fi;
fi;

proc CouldBeZero
return ( or );

proc Locate
if and then
return ;
else
while true do
;
if
and then
break;
elif then
;
else
;
fi;
od;
return ;
fi;

is a small positive number like determined by the current working precision.  The next two sections sketch ideas that improve the time efficiency of this algorithm.  The Mean-Value Theorem speeds up procedure Zeros.  Newton's method speeds up procedure Locate.