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 continuous function f ( x ) {\displaystyle 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 2 {\displaystyle {\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 {\displaystyle x_{0}} and x 2 {\displaystyle x_{2}} , which are on two different sides of the root being sought, i.e., f ( x 0 ) f ( x 2 ) < 0 {\displaystyle f(x_{0})f(x_{2})<0} , the method begins by evaluating the function at the midpoint x 1 = ( x 0 + x 2 ) / 2 {\displaystyle x_{1}=(x_{0}+x_{2})/2} . One then finds the unique exponential function e a x {\displaystyle e^{ax}} such that function h ( x ) = f ( x ) e a x {\displaystyle h(x)=f(x)e^{ax}} satisfies h ( x 1 ) = ( h ( x 0 ) + h ( x 2 ) ) / 2 {\displaystyle h(x_{1})=(h(x_{0})+h(x_{2}))/2} . Specifically, parameter a {\displaystyle a} is determined by

e a ( x 1 − x 0 ) = f ( x 1 ) − sign ⁡ [ f ( x 0 ) ] f ( x 1 ) 2 − f ( x 0 ) f ( x 2 ) f ( x 2 ) . {\displaystyle e^{a(x_{1}-x_{0})}={\frac {f(x_{1})-\operatorname {sign} [f(x_{0})]{\sqrt {f(x_{1})^{2}-f(x_{0})f(x_{2})}}}{f(x_{2})}}.}

The false position method is then applied to the points ( x 0 , h ( x 0 ) ) {\displaystyle (x_{0},h(x_{0}))} and ( x 2 , h ( x 2 ) ) {\displaystyle (x_{2},h(x_{2}))} , leading to a new value x 3 {\displaystyle x_{3}} between x 0 {\displaystyle x_{0}} and x 2 {\displaystyle x_{2}} ,

x 3 = x 1 + ( x 1 − x 0 ) sign ⁡ [ f ( x 0 ) ] f ( x 1 ) f ( x 1 ) 2 − f ( x 0 ) f ( x 2 ) , {\displaystyle x_{3}=x_{1}+(x_{1}-x_{0}){\frac {\operatorname {sign} [f(x_{0})]f(x_{1})}{\sqrt {f(x_{1})^{2}-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 {\displaystyle x_{1}} if f ( x 1 ) f ( x 3 ) < 0 {\displaystyle f(x_{1})f(x_{3})<0} (well-behaved case), or otherwise whichever of x 0 {\displaystyle x_{0}} and x 2 {\displaystyle x_{2}} has function value of opposite sign to f ( x 3 ) {\displaystyle f(x_{3})} . The procedure can be terminated when a given accuracy is obtained.


References

  1. ^ Ridders, C. (1979). "A new algorithm for computing a single root of a real continuous function". IEEE Transactions on Circuits and Systems. 26 (11): 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.


  • v
  • t
  • e