Ridders' method

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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 . 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 . 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[edit]

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[edit]

  1. ^ Ridders, C. (1979). "A new algorithm for computing a single root of a real continuous function". IEEE Transactions on Circuits and Systems. 26: 979–980. doi:10.1109/TCS.1979.1084580. 
  2. ^ Kiusalaas, Jaan (2010). Numerical Methods in Engineering with Python (2nd ed.). Cambridge University Press. pp. 146–150. ISBN 978-0-521-19132-6. 
  3. ^ Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Section 9.2.1. Ridders' Method". Numerical Recipes: The Art of Scientific Computing (3rd ed.). New York: Cambridge University Press. ISBN 978-0-521-88068-8.