Boost C++ Libraries

...one 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

Bisection
Bracket and Solve Root
Algorithm TOMS 748: Alefeld, Potra and Shi: Enclosing zeros of continuous functions
Brent-Decker Algorithm
Termination Condition Functors
Implementation

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:

Copyright © 2006-2021 Nikhar Agrawal, Anton Bikineev, Matthew Borland, Paul A. Bristow, Marco Guazzone, Christopher Kormanyos, Hubert Holin, Bruno Lalande, John Maddock, Evan Miller, Jeremy Murphy, Matthew Pulver, Johan Råde, Gautam Sewani, Benjamin Sobotta, Nicholas Thompson, Thijs van den Berg, Daryle Walker and Xiaogang Zhang

Distributed under the Boost Software License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)