Boost C++ Libraries of the most highly regarded and expertly designed C++ library projects in the world. Herb Sutter and Andrei Alexandrescu, C++ Coding Standards


Chapter 10. Root Finding & Minimization Algorithms

Table of Contents

Root Finding Without Derivatives
Bracket and Solve Root
Algorithm TOMS 748: Alefeld, Potra and Shi: Enclosing zeros of continuous functions
Brent-Decker Algorithm
Termination Condition Functors
Root Finding With Derivatives: Newton-Raphson, Halley & Schröder
Roots of Cubic Polynomials
Roots of Quartic Polynomials
Examples of Root-Finding (with and without derivatives)
Finding the Cubed Root With and Without Derivatives
Using C++11 Lambda's
Computing the Fifth Root
Root-finding using Boost.Multiprecision
Generalizing to Compute the nth root
A More complex example - Inverting the Elliptic Integrals
The Effect of a Poor Initial Guess
Examples Where Root Finding Goes Wrong
Locating Function Minima using Brent's algorithm
Comparison of Root Finding Algorithms
Comparison of Cube Root Finding Algorithms
Comparison of Nth-root Finding Algorithms
Comparison of Elliptic Integral Root Finding Algorithms

Several tools are provided to aid finding minima and roots of functions.

Some root-finding without derivatives methods are bisection, bracket and solve, including use of TOMS 748 algorithm.

For root-finding with derivatives the methods of Newton-Raphson iteration, Halley, and Schröder are implemented.

For locating minima of a function, a Brent minima finding example is provided.

There are several fully-worked root-finding examples, including: