Root Finding

numerics4c++ provides the means to find roots of functions through the use of common numerical methods. The following routines are available for root finding:

Method Description
Bisection Root Finder An implementation of the bisection method.
Bracket Techniques to create intervals that bracket a root. Many root finding methods require a bracketted root for initialization in order to function properly.
False Position Root Finder An implementation of the false position method.
Newton Root Finder An implementation of Newton's method.
Secant Root Finder An implementation of the secant method.

Bisection Root Finder

The bisection_root_finder class provides an implementation of the bisection method. The bisection method is a solid, general purpose root finding method. It is not the fastest root finding method but it provides guaranteed convergance and can find roots for any continuous function. For those reasons, it is a good fail-safe routine in situations where other root finding methods may fail to perform.

Finding roots using the bisection method involves creating a bisection_root_finder instance providing a functor for the target function. Once, the root finder is created, roots can be evaluated by calling the find_root method providing a bracketting interval. Here is an example of finding roots for sine:

typedef double function(double x);

num::bisection_root_finder<function> finder(std::sin);

// find the root between 3 and 4.
double pi = finder.find_root(3.0, 4.0);

// find the root between -1 and 1.
double zero = finder.find_root(-1.0, 1.0);

Bracket

The bracket class provides the means to construct an interval known to contain at least one root. This is accomplished by taking a single, initial pivot point and expanding outward from that point until a bracketing interval is formed. Once this interval is created, it can be used as a starting point for root finding routines, such as the bisection method.

Constructing a bracketing interval involve creating a bracket instance instance providing a functor for the target function. Once, the bracketer is created, intervals can be created by calling the bracket_out method providing an initial point and a lower and upper bound for the interval. The two bounds are not critical in the construction of the interval and only serve to provide numerical stability to the algorithm. Here is an example of bracketing roots for sine:

typedef double function(double x);

num::bracket<function> bracket(std::sin);

// bracket a root near three
bracket.bracket_out(-100.0, 3.0, 100.0);
double lower = bracket.lower_bound(); // lower <= pi
double upper = bracket.upper_bound(); // upper >= pi

// bracket a root near six
bracket.bracket_out(-100.0, 6.0, 100.0);
lower = bracket.lower_bound(); // lower <= 2pi
upper = bracket.upper_bound(); // upper >= 2pi

False Position Root Finder

The false_position_root_finder class provides an implementation of the false position method. The false position method is more numerically stable than its cousin algorithm, the secant method, as the false position method maintains a bracketted root at all times. Thus, the false position is guaranteed to converge given a bracketting interval but, no such guaranteed is granted with the secant method.

Finding roots using the false position method involves creating a false_position_root_finder instance providing a functor for the target function. Once, the root finder is created, roots can be evaluated by calling the find_root method providing a bracketting interval. Here is an example of finding roots for sine:

typedef double function(double x);

num::false_position_root_finder<function> finder(std::sin);

// find the root between 3 and 4.
double pi = finder.find_root(3.0, 4.0);

// find the root between -1 and 1.
double zero = finder.find_root(-1.0, 1.0);

Newton Root Finder

The newton_root_finder class provides an implementation of Newton's method. Newton's method is fast converging root finding method that utilizes not only a function but the function's derivative. As such, Newton's method only is applicable for functions with a first derivative.

Finding roots using Newton's method involves creating a newton_root_finder instance providing a functor for the target function and the function's associated derivative function. Once, the root finder is created, roots can be evaluated by calling the find_root method providing an initial approximation to the root. Here is an example of finding roots for sine:

typedef double function(double x);

num::newton_root_finder<function> finder(std::sin, std::cos);

// find the root near 3.
double pi = finder.find_root(3.0);

// find the root near 1.
double zero = finder.find_root(1.0);

Secant Root Finder

The secant_root_finder class provides an implementation of the secant method.

Finding roots using the secant method involves creating a secant_root_finder instance providing a functor for the target function. Once, the root finder is created, roots can be evaluated by calling the find_root method providing a bracketting interval. Here is an example of finding roots for sine:

typedef double function(double x);

num::secant_root_finder<function> finder(std::sin);

// find the root around 3 and 4.
double pi = finder.find_root(3.0, 4.0);

// find the root around 3.5 and 4.
pi = finder.find_root(3.5, 4.0);

// find the root around -1 and 1.
double zero = finder.find_root(-1.0, 1.0);