next up previous
Next: Convergence, divergence, random walk, Up: Introduction Previous: Introduction

Problem definition.

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