Roots of Nonlinear Equations

A root of an equation y = f(x) is a number a such that f(a) = 0.

Find a value of x such that f(x) = a .
Consider the function g(x) = f(x) - a and apply the procedure to the function g(x).
Find the intersection of two curves f(x) and g(x).
Consider the function h(x) = f(x) - g(x) and apply the procedure to the function h(x).
Optimization problems where one wants a local maximum or minimum of a differentiable function f(x).
Consider the function f'(x) = d/dx (f(x)) and apply the procedure to the function f'(x).

The most commonly used methods for finding a root of a nonlinear equation are the bisection method, secant methods, Newton-Raphson, and certain variants Mueller's method, van Wijngaarden,Dekker,Brent method.

Caveats

All of the numerical methods listed above require that the function be continuous and some methods require that the function be differentiable. Also all of the numerical methods listed above are iterative methods that require at least one initial estimate of the root and some require two initial estimates which not only bracket a root but also must satisfy the condition that if the function evaluated at one estimate is positive then the function evaluated at the other estimate is negative. Note that those methods that need two estimates which bracket a root cannot be applied to functions which are nonnegative everywhere or nonpositive everywhere, e.g. y = x ². Those methods which require only one initial estimate may behave poorly in a neighborhood of a local minimum or local maximum and may behave poorly if the order of the root exceeds 1. The order of a root a of a function f(x) is a number n such that f(x) = ( x - a )ⁿ g(x) , where g(x) is defined at a and g(a) is non-zero. The order of a root is also called the multiplicity of the root.

Root Solution Check List.

Is the function f(x) nonnegative or nonpositive?
Consider the secant method or Newton_Raphson's method or consider the function g(x) = f(x) / f'(x), in order for a nonnegative differentiable function to have a root, the root must have order greater than 1, but beware g(x) may behave badly in a neighborhood of a root of f'(x) unless it is also a root of f(x).
Is the root of f(x) a multiple root?
If it is, consider the function g(x) = f(x) / f'(x), but see beware above.
Is there a local minimum or maximum near the root.
Try to use a bracketing method if possible. If a bracketing method is not available, create a hybrid method.

Bisection Method

The bisection method is one of the simplest to understand and program and one of the slowest. In order to apply the bisection method, two approximations to a root must be obtained which bracket the root. Moreover, the function evaluated at the two approximations must be of opposite signs, i.e. if a and b are two numbers such that a < b, then f(a)·f(b) < 0. Note that this technique cannot be applied to functions such as f(x) = x².

Bisection Method

Secant Methods

A secant is a line through two points on a curve. There are many numerical methods which use the secants to obtain new estimates for a root. Below are three common secant methods called (1) the secant method, (2) regula falsi, and (3) the Illinois Algorithm.

The secant method requires two approximations to the root, the approximations do not need to bracket the root. In fact, since the secant method is equivalent to the Newton-Raphson method in which the derivative is replaced by a numerical approximation to the derivative, all one needs to do is find an estimate to the root and for the second estimate simply add a small number to the first estimate so as to approximate the derivative. Successive approximations are obtained by finding the root of the secant determined by the immediate two previous approximations. The secant method can have difficulties if the root is located near a local maximum or minimum because the estimate can be quite far from the root.

The regula falsi method requires two initial estimates which not only bracket the root but also for which the function evaluated at the two estimates has opposite signs. In the regula falsi method the secant is chosen from points on the curve corresponding to the most recent estimates which bracket a root. Regula falsi is sometimes a good method for starting the iterative procedure, but it should not be used for final convergence to a root.

The Illinois algorithm is a variant of the regula falsi method in which during the iterative process if a change to the same endpoint occurs twice in succession, then the ordinate corresponding to the other endpoint is halved. This technique avoids the potentially slow convergence of the regula falsi method.

Secant Method
Regula Falsi
Illinois Algorithm

Newton-Raphson

The Newton-Raphson method is similar to the secant method only instead of estimating a root by the intersection of the x-axis with a secant throught two points on the curve, the estimate is obtained from the intersection of the x-axis and the tangent to the curve at a point. The Newton-Raphson method requires only a single initial estimate, but unlike the other methods it also requires that the user program both the function and its derivative. In the neighborhood of a root of order 1, Newton-Raphson converges quadratically to the root. However, other methods may be superior in terms of the number of function calls because the Newton-Raphson method requires two function calls per iterative step whereas the other methods require only one and often the derivative can be much more complicated than the function itself.

Newton_Raphson

Mueller, van Wijngaarden, Dekker, Brent

Mueller created a method of finding roots of a nonlinear equation by a method of successive bisection and inverse quadratic interpolation. His technique has undergone refinements by van Wijngaarden, Dekker and later Brent. The numerical method programmed below requires initial estimates which bracket a root in which the function evaluated at the two initial estimates has opposite signs. Initially, the midpoint is chosen as a third estimation point. The procedure then iterates by trying to fit a quadratic in the ordinate values and interpolate for the zero of the quadratic. If the zero is within the bounds of the bounding estimates, that value is used to reduce the length of the bracketing interval, if the zero is exterior to the bounding estimates, the bisection method is employed and the interval is halved. If the new estimate is too near one of the endpoints, the next estimate is either the midpoint or the process is terminated because the root has been determined within a preassigned tolerance. The inverse quadratic interpolation - bisection method should be the method of choice when trying to find a root of a real-valued function of a real-value. Some tests I have made, shows that it requires upto 1/3 of the number of function calls of the Illinois Algorithm, about the same number of function calls as the secant method which depends different initial conditions, and fewer than the Newton-Raphson which required two function calls per iterative step. Moreover, this method is not susceptible to poor estimates due to local minima and maxima as the secant method or the Newton-Raphson method can be.

Inverse Quadratic Interpolation - Bisection Method