Our goal is to find a value for x in the interval (a, b) that satisfies f(x) = 0 (called the root of the function) for any continuous function on the interval. A function f(x) is continuous in the interval (a,b) if for any x in this interval, f(x) is defined.
We first consider the case where f(a) and f(b) have opposite signs, which guarantees that the function has at least one root in the interval (a,b).
Bisection Method
We can use the bisection method to find such a root. This is an iterative approach defined as follows.
Step 1: Set c = (a+b)/2
Step 2: If f(c) = 0, then stop since a root has been found. If f(c) has the same sign as f(a), then set a = c; otherwise set b = c. In either case, return to step 1.
Continue to iterate until either a root has been found in step 2 or |b–a| < є for some predetermined small positive value є. This method is guaranteed to converge to a solution in at most n steps where n is the smallest number ≥ log2 (|b–a|/є). We could instead use the criterion |f(c)| < є.
Secant Method
Another approach to finding a root of the function f(x) is to use the secant method. This method does not require that we start with two values a and b that bracket the root. Instead, we can start with any two points x0 and x1, preferably near a root. This approach may be faster than the bisection method but is not guaranteed to find the root.
In this method, we generate a series x0, x1, x2, … such that for n ≥ 1
Essentially, this is a form of linear interpolation. This method terminates when f(xn) is sufficiently close to zero, i.e. |f(xn)| < є. Alternatively, we can use a criterion such as |xn–xn-1| < є.
Brent’s Method
Brent’s method has the same assumptions as the bisection method but uses the secant method when feasible (and even a more efficient interpolation approach, namely inverse quadratic interpolation) and the bisection method otherwise. We won’t go through the details here, but instead provide an implementation in Excel (see Root-finding Functions).
Newton’s Method
Newton’s method is a refinement of the secant method using differentiation. See Newton’s Method for more details.
Real Statistics Functions
See Root-finding Functions for a description of the Real Statistics worksheet functions that implement each of the root-finding methods described above.
Solutions to n equations in n unknowns
We can extend the approaches to finding a root of a function f(x) to simultaneously finding the roots of two functions f(x, y) and g(x, y) in two variables x and y, and similarly to finding the roots of n functions in n variables. This is equivalent to finding the solutions to n equations in n unknowns.
See Newton’s Method for more details about how to accomplish this using Newton’s method. See also Multivariate Roots that describe Real Statistics worksheet functions for the case of functions in two or three variables.
References
Wikipedia (2021) Bisection method
https://en.wikipedia.org/wiki/Bisection_method
Wikipedia (2021) Secant method
https://en.wikipedia.org/wiki/Secant_method
Wikipedia (2021) Brent’s method
https://en.wikipedia.org/wiki/Brent%27s_method
Wikipedia (2021) Newton’s method
https://en.wikipedia.org/wiki/Newton%27s_method