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)$ . 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 ${\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}$ and $x_{2}$ , which are on two different sides of the root being sought, i.e., $f(x_{0})f(x_{2})<0$ .The method begins by evaluating the function at the midpoint $x_{1}=(x_{0}+x_{2})/2<0$ between the two points. One then finds the unique exponential function of the form $e^{ax}$ such that function $h(x)=f(x)e^{ax}$ satisfies $h(x_{1})=(h(x_{0})+h(x_{2}))/2$ . The false position method is then applied to the transformed values, leading to a new value x₃, between x₀ and x₂, which can 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₃ if f(x₃) has the opposite sign to f(x₄), or otherwise whichever of x₁ and x₂ has f(x) of opposite sign to f(x₄).

The method can be summarized by the formula

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})}}}.

References

^ 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.
^ Kiusalaas, Jaan (2010). Numerical Methods in Engineering with Python (2nd ed.). Cambridge University Press. pp. 146–150. ISBN 978-0-521-19132-6.
^ 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.

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

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

[1]

[2]

[3]