Ridders' method

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 function "f".

Ridders' method is simpler than Brent's method but Press et al. (1988) claim that it usually performs about as well. It converges quadratically, which implies that the number of additional significant digits doubles at each step; but the function has to be evaluated twice for each step so the order of the method is 2^1/2. The method is due to Ridders (1979).

Method

The method is described by Ridders as follows ("exponential case"). Given three evenly spaced x values at which the function F(x) has been calculated, a function of the following form is found which takes the same values as F(x) at the three points::$p(x)\; =\; A\; +\; Bcdot\; exp(Cx)$Then x₃ is found as the point where p(x) = 0, and can be found by the following formula::$x\_3\; =\; x\_1\; +\; d\_0\; cdot\; ln\; b\; /\; ln\; a$where:$a\; =\; (y\_0\; -\; y\_1)/(y\_1\; -\; y\_2)$ and :$b\; =\; (y\_0\; -\; y\_1)/(y\_0\; -\; ay\_1).$

To save having to calculate logarithms at each iteration, Ridders suggests that an approximation for the logarithm can be used; one such approximation leads to the following formula::$x\_3\; =\; x\_1\; +\; d\_0\; cdot\; frac\{u(3\; +\; u^2)\}\{v\; (3\; +\; v^2)\}$where:$u\; =\; (b\; -\; 1)/(b\; +\; 1)$ and :$v\; =\; (a\; -\; 1)/(a\; +\; 1).$

Once x₃ has been found, the closest one of the original three points is used as one of the three new points, along with one more new point chosen so as to have three equally spaced points with x₃ in the middle.

References

*cite book |title=Numerical Recipes in C: The Art of Scientific Computing |last=Press |first=W.H. |authorlink= |coauthors=S.A. Teukolsky, W.T. Vetterling, B.P. Flannery |year=1992 |origyear=1988 |publisher=Cambridge University Press |location=Cambridge UK |isbn= |pages=358–359 |edition=2nd
*cite journal |title=Three-point iterations derived from exponential curve fitting |last=Ridders |first=C.J.F. |year=1979 |journal=IEEE Transactions on Circuits and Systems |volume=26 |issue=8 |pages=669−670 |url=http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=23495&arnumber=1084682&count=9&index=5