Root-Finding in Numerical Methods

Last modified: December 22, 2024

This article is written in: 🇺🇸

Root-finding algorithms are used to solve equations of the form $f(x) = 0$. This form aligns with how we express linear equations associated with linear functions. Our goal will be to obtain a solution $x$ for this equation, like $x = -b/a$ in linear problems.
They are fundamental in numerical methods and are used in a variety of scientific and engineering fields.

Basic Concepts

Root: A root of a function $f(x)$ is a value $x = r$ such that $f(r) = 0$. This applies not only to linear functions but can also extend to nonlinear systems, such as those including powers ($x^2, x^3, \ldots$), roots, radicals and non-integer polynomials ($\sqrt{x}, x^{3/5}, x^{pi} \ldots$), or trigonometric and special functions ($\sin(x), \tan(x), \log(x), \ldots$).
Brackets: A bracket is an interval $[a, b]$ such that $f(a)f(b) < 0$. This indicates that there is at least one root in the interval (provided the function is continuous).
Convergence: An algorithm converges to a solution if the sequence of approximations it generates approaches the actual solution as the number of iterations increases.
Tolerance: The tolerance is a pre-specified threshold below which the difference between two successive approximations is considered close enough to consider that the algorithm has converged to a solution.

Bracketing methods (e.g., Bisection Method, False Position Method): These methods start with two initial guesses that bracket a root, and generate a sequence of intervals that converge to the root.
Open methods (e.g., Newton's Method, Secant Method): These methods start with one or two initial guesses, and generate a sequence of points that converge to a root. They usually converge faster than bracketing methods, but they aren't always guaranteed to converge.
Combination methods (e.g., Brent's Method): These methods combine the advantages of bracketing and open methods. They usually provide a good balance between speed of convergence and guarantee of convergence.

The choice of root-finding method depends on the specific problem, the properties of the function, and the available computational resources. This is important as we may need to generalize insights from linear problems to nonlinear systems.
Bracketing methods are generally slower but more reliable, while open methods are usually faster but can fail to converge.
In general, it's a good idea to start with a bracketing method to get an initial approximation of the root, and then use an open method to refine the approximation.