4.3 Numerical root finding

Root-finding algorithms are algorithms for finding the values \(x\) such that \(f(x) = 0\), for a given continuous function \(f(x)\). Such values \(x\) are named roots (or zeros) of a function. Most root-finding algorithms are based on the intermediate value theorem, which states that if a continuous function has values of opposite sign at the end points of an interval then the function has at least one root in the interval.

For instance, the easiest root-finding method is the bisection method: let \(f(x)\) be a continuous function, for which one knows an interval \([a, b]\) such that \(f(a)\) and \(f(b)\) have opposite sign. Let \(c = (a + b) / 2\) be the midpoint the bisect the interval: now, either \(f(a)\) and \(f(c)\) or \(f(c)\) and \(f(b)\) have opposite sign, and one has in fact divided by two the size of the interval. One can iterate this method until the difference between the extremities of the interval is small enough (e.g. \(<1 \times 10^{-8}\)).

Another well established method is the secant method: it uses a succession of roots of secant lines to approximate the root of a function \(f(x)\). Starting with values \(x_0\) and \(x_1\), a line is constructed between \((x_0, f(x_0))\) and \((x_1, f(x_1))\): \[ y = \frac{f(x_1) - f(x_0)}{x_1 - x_0}(x - x_1) + f(x_1) \] The root of this line is \[ x = x_1 - f(x_1) \frac{x_1 - x_0}{f(x_1) - f(x_0)} \] Now, we set \(x_2 = x\) and we iterate this method until the difference between the extremities of the interval is small enough (e.g. \(<1 \times 10^{-8}\)).

The secant method is also known as a linear interpolation method; it is also possible to use higher order interpolation, specifically quadratic interpolation, to find the root of a function using the same rationale presented for the secant method.

Finally, a well-established and robust method is the Brent-Dekker method, implemented in R with the uniroot() function. It combines the three methods presented before, trying to use the secant or quadratic interpolation method first - as they tend to converge faster to a solution - but falling back to the bisection method if necessary, for its robustness properties. More details on the Brent-Dekker method in Brent (1973).

References

Brent, Richard P. 1973. Algorithms for Minimization Without Derivatives. Prentice-Hall.