
Once a root is sufficiently isolated by bisection and narrowing, a faster numerical method can be applied to obtain remaining digits of the root. Newton's method, the secant method, Muller's algorithm, thirdorder Newton iteration, and quadratic inverse interpolation all have superlinear convergence and are described in Rice[13]. We use Newton's method because it is wellknown, is efficient, has lowoverhead, and is easy to analyze. Given function , define function by
If is a root of on , then . Hence is a fixed point of . Newton's method for calculating root of starts with an approximation and then successively computes . Under the right conditions, explained below, the sequence , , , converges to . Formulas for the derivatives of are:
Letting and using and we obtain via Taylor series expansions the results
for some . If and for all and for all , then Newton's method is safe to use and converges faster than bisection if either
and we can guarantee that all . The latter can be arranged by tweaking Newton's method so that if overshoots the boundaries of interval , then is shoved back towards the root . Subsequent computed by then proceeds without incident. Hence, we use
Now we assume 's continuity property extends to derivatives of on subinterval . If interval is sufficiently small, then and will determine finite bounds and .
We modify procedure
Locate
and introduce procedures
NewtonTest
and
Newton. Procedure
NewtonTest
tests whether Newton's method should be used and procedure
Newton
actually implements Newton's method. These are listed below.


©20042024 Planet Quantum  Kelly Roach 