Ridders' method explained

In numerical analysis, Ridders' method is a root-finding algorithm based on the false position method and the use of an exponential function to successively approximate a root of a continuous function

f(x) . The method is due to C. Ridders.^{[1] [2]}

Ridders' method is simpler than Muller's method or Brent's method but with similar performance.^[3] 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 of the method is

\sqrt{ 2 } . 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 ^{ax} such that function h(x) = f(x)e ^{ax} satisfies h(x _{1)=(h(x} _{0)} + h(x _{2))/2} . Specifically, parameter a is determined bye ^{a(x _{1} - x _{0)}} = (f(x _{1)-\operatorname{sign})/([f(x) _{0)]\sqrt{f(x} ^{2} ^{1 )} - f(x _{0)f(x} _{2)}}{f(x} _{2)}} .

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 ) (\operatorname{sign)/([f(x)} _{0)]f(x} _{1)}{\sqrt{f(x} ^{2} ^{1 )} - f(x _{0)f(x} _{2)}},} 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} if 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.

Notes and References

1. Ridders . C. . 10.1109/TCS.1979.1084580 . A new algorithm for computing a single root of a real continuous function . IEEE Transactions on Circuits and Systems . 26 . 979–980. 1979 . 11 .
2. Book: Kiusalaas, Jaan . Numerical Methods in Engineering with Python. Cambridge University Press. 2010. 978-0-521-19132-6 . 2nd. 146–150.
3. Book: Press . WH . Teukolsky . SA . Vetterling . WT . Flannery . BP . 2007 . Numerical Recipes

   The Art of Scientific Computing

   . 3rd . Cambridge University Press . New York . 978-0-521-88068-8 . Section 9.2.1. Ridders' Method . http://apps.nrbook.com/empanel/index.html#pg=452.