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, third-order Newton iteration, and quadratic inverse interpolation all have superlinear convergence and are described in Rice. We use Newton's method because it is well-known, is efficient, has low-overhead, 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
and introduce procedures
tests whether Newton's method should be used and procedure
actually implements Newton's method. These are listed below.
|©2004-2021 Planet Quantum||Kelly Roach|