Ridders' method

From Wikipedia, the free encyclopedia

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 found at each step tends to increase; but the function has to be evaluated twice for each step. The method is due to Ridders (1979).

[edit] Method

Press et al. (1988) describe the method as follows. Given two values of the independent variable, x1 and x2, which are on two different sides of the root being sought, the method begins by evaluating the function at the midpoint x3 between the two points. One then finds the unique exponential function which, when multiplied by f, transforms the function at the three points into a straight line. The false position method is then applied to the transformed values, leading to a new value x4, between x1 and x2, which can be used as one of the two bracketing values in the next step of the iteration.

The method can be summarized by the formula (equation 9.2.4 from Press et al.)

x_4 = x_3 + (x_3 - x_1)\frac{\operatorname{sign}[f(x_1) - f(x_2)]f(x_3)}{\sqrt{f(x_3)^2 - f(x_1)f(x_2)}} .

[edit] References

  • Press, W.H.; S.A. Teukolsky, W.T. Vetterling, B.P. Flannery [1988] (1992). Numerical Recipes in C: The Art of Scientific Computing, 2nd, Cambridge UK: Cambridge University Press, 358–359. 
  • Ridders, C.J.F. (1979). "Three-point iterations derived from exponential curve fitting". IEEE Transactions on Circuits and Systems 26 (8): 669−670. 


This applied mathematics-related article is a stub. You can help Wikipedia by expanding it.