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 [math]\displaystyle{ f(x) }[/math]. 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 [math]\displaystyle{ \sqrt{2} }[/math]. 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, [math]\displaystyle{ x_0 }[/math] and [math]\displaystyle{ x_2 }[/math], which are on two different sides of the root being sought, i.e.,[math]\displaystyle{ f(x_0)f(x_2) \lt 0 }[/math], the method begins by evaluating the function at the midpoint [math]\displaystyle{ x_1 = (x_0 +x_2)/2 }[/math]. One then finds the unique exponential function [math]\displaystyle{ e^{ax} }[/math] such that function [math]\displaystyle{ h(x)=f(x)e^{ax} }[/math] satisfies [math]\displaystyle{ h(x_1)=(h(x_0) +h(x_2))/2 }[/math]. Specifically, parameter [math]\displaystyle{ a }[/math] is determined by
- [math]\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)} . }[/math]
The false position method is then applied to the points [math]\displaystyle{ (x_0,h(x_0)) }[/math] and [math]\displaystyle{ (x_2,h(x_2)) }[/math], leading to a new value [math]\displaystyle{ x_3 }[/math] between [math]\displaystyle{ x_0 }[/math] and [math]\displaystyle{ x_2 }[/math],
- [math]\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)}}, }[/math]
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 [math]\displaystyle{ x_1 }[/math] if [math]\displaystyle{ f(x_1)f(x_3) \lt 0 }[/math] (well-behaved case), or otherwise whichever of [math]\displaystyle{ x_0 }[/math] and [math]\displaystyle{ x_2 }[/math] has function value of opposite sign to [math]\displaystyle{ f(x_3) }[/math]. The procedure can be terminated when a given accuracy is obtained.
References
- ↑ 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.
- ↑ Kiusalaas, Jaan (2010). Numerical Methods in Engineering with Python (2nd ed.). Cambridge University Press. pp. 146–150. ISBN 978-0-521-19132-6. https://books.google.com/books?id=9SG1r8EJawIC&pg=PT156.
- ↑ 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. http://apps.nrbook.com/empanel/index.html#pg=452.
 |  |
