Sajun.org
A '''root-finding algorithm''' is a numerical method or
algorithm for finding a value ''x'' such that ''f(x) = 0'', for a given
function ''f''. Here, ''x'' is a single
real number called the '''
root'''.
When ''x'' is a vector, algorithms to find ''x'' such that ''f(x)'' = 0 are generally called "equation-solving algorithms". These algorithms are a generalization of root-finding and can operate either on
linear or
non-linear equations. Some root-finding algorithms (such as
Newton's method) can be directly generalized to solve non-linear equations.
Root-finding algorithms are studied in
numerical analysis.
==Specific algorithms==
The simplest root-finding algorithm is the
bisection method: we start with two points ''a'' and ''b'' which bracket a root, and at every iteration, we pick either the subinterval [''a'', ''c''] or [''c'', ''b''], where ''c'' = (''a'' + ''b'') / 2 is the midpoint between ''a'' and ''b''. The algorithm always select a subinterval which contains a root. The bisection method is guaranteed to converge to a root, however, its progress is rather slow (the
rate of convergence is linear).
Newton's method, also called the Newton-Raphson method, linearizes the function ''f'' at the current approximation to the root. This yields the
recurrence relation
:<math> x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)}. </math>
Newton's method may not converge if you start too far away from a root. However, if it does converge, it is faster than the bisection method (convergence is quadratical). Newton's method is also important because it readily generalizes to higher-dimensional problems.
If we replace the derivative in Newton's method with a
finite difference, we get the
secant method. It is defined by the recurrence relation
:<math>x_{n+1} = x_n - \frac{x_n-x_{n-1}}{f(x_n)-f(x_{n-1})} f(x_n). </math>
So, the secant method does not require the computation of a derivative, but the price is slower convergence (the order is approximately 1.6).
The
false position method, also called the regula falsi method, is like the bisection method. However, it does not cut the interval in two equal parts at every iteration, but it cuts the interval at the point given by the formula for the secant method. The false position method inherits the robustness of the bisection method and the superlinear convergence of the secant method,
Other root-finding algorithms include:
*
Ruffini's method
*
Successive substitutions
*
Laguerre's method
*
Brent's method
*
Broyden's method
*
Fixed-point iteration
==External links==
*
Numerical Recipes Homepage
