Home · Pages · Index · Overviews

Root Finding Module Reference

Root finding of a unary function with and without a derivative. More...

 #include <fct.root.h>

Structures

  Root_Bundle : struct
lft : double
rgt : double
A bracket for root finding:
    lft < rgt and f(lft)*f(rgt) < 0

Routines

Root_Bundle * Find_Root_Bracket (Root_Bundle *brack RM, double (*f)(double x))

double Find_Function_Root (Root_Bundle *brack, double (*f)(double x), double (*df)(double x))

Detailed Description

This module contains a single numerical routine, Find_Function_Root, for finding the root of a unary function. It employs different strategies depending on whether or not your supply it with a function for the derivative. In either case, the function needs a pair of points that bracket a root, modeled by a Root_Bundle, that can be computed in teh vicinity of an initial interval of interest with Find_Root_Bracket.

Root finding of n-ary functions is equivalent to solving a system of non-linear equations. There are basically no good, universal methods for such a problem and so there is no attempt to provide root finding of n-ary functions.

For a description of Brent's method and the Raphson-Newton method employed here in see Press, Vetterling, Teukolsky and Flannery, Numerical Recipes in C (Cambridge University Press, 1992), Chapter 9.3 and 9.4.


Structure Documentation

Root_Bundle : struct
lft: double
rgt: double

A bracket for root finding pruposes is two points lft < rgt such that f(lft) * f(rgt) < 0, i.e. are of opposite signs.


Routine Documentation

Root_Bundle * Find_Root_Bracket (Root_Bundle *brack RM, double (*f)(double x))

Given a function f and an initial interval in brack, Find_Root_Bracket attempts to find a bracket about a root by expanding the interval toward the point closer to 0. Return NULL if a bracket could not be found, otherwise fill in the root bracket values in brack and return a pointer to it for convenience.

double Find_Function_Root (Root_Bundle *brack, double (*f)(double x), double (*df)(double x))

Given a root bracket brack, Find_Function_Root returns a root of f within the bracket. Generally accurate to 15 digits (double-precision). If the derivative of f, df, is NULL, then Brent's algorithm which uses quadratic estimation is employed, otherwise the Raphson-Newton which uses the derivative is employed. In the event df is used, one may take advantage of the fact that a call to df with a value x, always follows a prior call to f with the same value. So one may, via globally shared values, optimize the computation of f and df by sharing the computation of any common sub-expressions.