numerical analysis Numerical analysis is the study of algorithms that use numerical approximation (as opposed to symbolic manipulations) for the problems of mathematical analysis (as distinguished from discrete mathematics). It is the study of numerical methods th ...

, 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 numbe ...

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 e ...

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, ...

to successively approximate a root of a continuous function

f(x)

. 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 iter ...

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-reliabl ...

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

\sqrt

. 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,

x_0

and

x_2

, which are on two different sides of the root being sought, i.e.,

f(x_0)f(x_2) < 0

, the method begins by evaluating the function at the midpoint

x_1 = (x_0 +x_2)/2

. One then finds the unique exponential function

e^

such that function

h(x)=f(x)e^

satisfies

h(x_1)=(h(x_0) +h(x_2))/2

. Specifically, parameter

a

is determined by :

e^ = \frac .

The false position method is then applied to the points

(x_0,h(x_0))

and

(x_2,h(x_2))

, leading to a new value

x_3

between

x_0

and

x_2

, :

x_3 = x_1 + (x_1 - x_0)\frac,

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

x_1

f(x_1)f(x_3) <0

(well-behaved case), or otherwise whichever of

x_0

and

x_2

has function value of opposite sign to

f(x_3)

. The procedure can be terminated when a given accuracy is obtained.

References

Root-finding algorithms {{mathapplied-stub