Next: Convergence, divergence, random walk,
Up: Introduction
Previous: Introduction
Solving non-linear equations is a classical topic in numerical
analysis [6,7,9,11,1].
Many algorithms are well-known and well-studied.
Few algorithms give any guarantee that they can find all the
roots in a given interval, and the ones which do [10]
depend on bounding higher order derivatives.
It is fair to say that the behaviour of algorithms under convergence
is well understood, and most of them are very efficient.
In the absence of convergence, however, the algorithms usually perform a
useless walk over the valid domain.
In our experience, the biggest challenge for a zero-finder is this
focusing on a convergence area, and not on the performance during
convergence.
We will use the term random walk to describe the sequence of
values before the convergence criteria are met, and refinement
to describe the iterations performed under convergence.
In this paper we suggest the use of fixed point iterators to find
the first approximations to roots of non-linear equations.
These approximate roots may be refined further with other methods.
Gaston Gonnet
1998-07-08