In
numerical analysis
Numerical analysis is the study of algorithms that use numerical approximation (as opposed to symbolic computation, symbolic manipulations) for the problems of mathematical analysis (as distinguished from discrete mathematics). It is the study of ...
, Ridders' method is a
root-finding algorithm
In mathematics and computing, a root-finding algorithm is an algorithm for finding zeros, also called "roots", of continuous functions. A zero of a function , from the real numbers to real numbers or from the complex numbers to the complex numbers ...
based on the
false position method
In mathematics, the ''regula falsi'', method of false position, or false position method is a very old method for solving an equation with one unknown; this method, in modified form, is still in use. In simple terms, the method is the trial and er ...
and the use of an
exponential function
The exponential function is a mathematical function denoted by f(x)=\exp(x) or e^x (where the argument is written as an exponent). Unless otherwise specified, the term generally refers to the positive-valued function of a real variable, a ...
to successively approximate a root of a continuous function
. The method is due to C. Ridders.
Ridders' method is simpler than
Muller's method
Muller's method is a root-finding algorithm, a numerical method for solving equations of the form ''f''(''x'') = 0. It was first presented by David E. Muller in 1956.
Muller's method is based on the secant method, which constructs at every iterat ...
or
Brent's method
In numerical analysis, Brent's method is a hybrid root-finding algorithm combining the bisection method, the secant method and inverse quadratic interpolation. It has the reliability of bisection but it can be as quick as some of the less-reliable ...
but with similar performance.
The formula below converges quadratically when the function is well-behaved, which implies that the number of additional significant digits found at each step approximately doubles; but the function has to be evaluated twice for each step, so the overall
order of convergence
In numerical analysis, the order of convergence and the rate of convergence of a convergent sequence are quantities that represent how quickly the sequence approaches its limit. A sequence (x_n) that converges to x^* is said to have ''order of co ...
of the method is
. If the function is not well-behaved, the root remains bracketed and the length of the bracketing interval at least halves on each iteration, so convergence is guaranteed.
Method
Given two values of the independent variable,
and
, which are on two different sides of the root being sought, i.e.,
, the method begins by evaluating the function at the midpoint
. One then finds the unique exponential function
such that function
satisfies
. Specifically, parameter
is determined by
:
The false position method is then applied to the points
and
, leading to a new value
between
and
,
:
which will be used as one of the two bracketing values in the next step of the iteration.
The other bracketing value is taken to be
if
(well-behaved case), or otherwise whichever of
and
has function value of opposite sign to
. The procedure can be terminated when a given accuracy is obtained.
References
Root-finding algorithms
{{mathapplied-stub