In this appendix I briefly outline numerical algorithms and codes for solving a single 1-dimensional nonlinear algebraic equation , where the continuous function is given.

The process generally begins by evaluating on a suitable grid of points and looking for sign changes. By the intermediate value theorem, each sign change must bracket at least one root. Given a pair of such ordinates and , there are a variety of algorithms available to accurately and efficiently find the (a) root:

If is small, say on the order of a finite-difference grid spacing, then closed-form approximations are probably accurate enough:

- The simplest approximation is a simple linear interpolation of between and .
- A slightly more sophisticated algorithm, “inverse quadratic interpolation”, is to use three
ordinates, two of which bracket a root, and estimate the root as the root of the (unique) parabola
which passes through the three given points
^{64}.

For larger , iterative algorithms are necessary to obtain an accurate root:

- Bisection (binary search on the sign of ) is a well-known iterative scheme which is very robust. However, it is rather slow if high accuracy is desired.
- Newton’s method can be used, but it requires that the derivative be available. Alternatively, the secant algorithm (similar to Newton’s method but estimating from the most recent pair of function evaluations) gives similarly fast convergence without requiring to be available. Unfortunately, if is small enough at any iteration point, both these algorithms can fail to converge, or more generally they can generate “wild” trial ordinates.
- Probably the most sophisticated algorithm is that of van Wijngaarden, Dekker, and Brent. This is a carefully engineered hybrid of the bisection, secant, and inverse quadratic interpolation algorithms, and generally combines the rapid convergence of the secant algorithm with the robustness of bisection. The van Wijngaarden–Dekker–Brent algorithm is described by Forsythe, Malcolm, and Moler [71, Chapter 7], Kahaner, Moler, and Nash [92, Chapter 7], and Press et al. [125, Section 9.3]. An excellent implementation of this, the Fortran subroutine ZEROIN, is freely available from http://www.netlib.org/fmm/.

http://www.livingreviews.org/lrr-2007-3 |
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 2.0 Germany License. Problems/comments to |