Next: Root Finding Caveats, Up: One dimensional Root-Finding [Index]

One-dimensional root finding algorithms can be divided into two classes,
*root bracketing* and *root polishing*. Algorithms which proceed
by bracketing a root are guaranteed to converge. Bracketing algorithms
begin with a bounded region known to contain a root. The size of this
bounded region is reduced, iteratively, until it encloses the root to a
desired tolerance. This provides a rigorous error estimate for the
location of the root.

The technique of *root polishing* attempts to improve an initial
guess to the root. These algorithms converge only if started “close
enough” to a root, and sacrifice a rigorous error bound for speed. By
approximating the behavior of a function in the vicinity of a root they
attempt to find a higher order improvement of an initial guess. When the
behavior of the function is compatible with the algorithm and a good
initial guess is available a polishing algorithm can provide rapid
convergence.

In GSL both types of algorithm are available in similar frameworks. The user provides a high-level driver for the algorithms, and the library provides the individual functions necessary for each of the steps. There are three main phases of the iteration. The steps are,

- initialize solver state,
`s`, for algorithm`T` - update
`s`using the iteration`T` - test
`s`for convergence, and repeat iteration if necessary

The state for bracketing solvers is held in a `gsl_root_fsolver`

struct. The updating procedure uses only function evaluations (not
derivatives). The state for root polishing solvers is held in a
`gsl_root_fdfsolver`

struct. The updates require both the function
and its derivative (hence the name `fdf`

) to be supplied by the
user.

Next: Root Finding Caveats, Up: One dimensional Root-Finding [Index]