Ridders' method


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 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 doubles at each step; but the function has to be evaluated twice for each step so the order of the method is 21/2. The method is due to Ridders (1979).

Method

The method is described by Ridders as follows ("exponential case"). Given three evenly spaced x values at which the function F(x) has been calculated, a function of the following form is found which takes the same values as F(x) at the three points::p(x) = A + Bcdot exp(Cx)Then x3 is found as the point where p(x) = 0, and can be found by the following formula::x_3 = x_1 + d_0 cdot ln b / ln awhere:a = (y_0 - y_1)/(y_1 - y_2) and :b = (y_0 - y_1)/(y_0 - ay_1).

To save having to calculate logarithms at each iteration, Ridders suggests that an approximation for the logarithm can be used; one such approximation leads to the following formula::x_3 = x_1 + d_0 cdot frac{u(3 + u^2)}{v (3 + v^2)}where:u = (b - 1)/(b + 1) and :v = (a - 1)/(a + 1).

Once x3 has been found, the closest one of the original three points is used as one of the three new points, along with one more new point chosen so as to have three equally spaced points with x3 in the middle.

References

*cite book |title=Numerical Recipes in C: The Art of Scientific Computing |last=Press |first=W.H. |authorlink= |coauthors=S.A. Teukolsky, W.T. Vetterling, B.P. Flannery |year=1992 |origyear=1988 |publisher=Cambridge University Press |location=Cambridge UK |isbn= |pages=358–359 |edition=2nd
*cite journal |title=Three-point iterations derived from exponential curve fitting |last=Ridders |first=C.J.F. |year=1979 |journal=IEEE Transactions on Circuits and Systems |volume=26 |issue=8 |pages=669−670 |url=http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=23495&arnumber=1084682&count=9&index=5


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • False position method — The false position method or regula falsi method is a term for problem solving methods in algebra and calculus. In simple terms, these methods begin by attempting to evaluate a problem using test ( false ) values for the variables, and then… …   Wikipedia

  • List of numerical analysis topics — This is a list of numerical analysis topics, by Wikipedia page. Contents 1 General 2 Error 3 Elementary and special functions 4 Numerical linear algebra …   Wikipedia

  • Root-finding algorithm — A root finding algorithm is a numerical method, or algorithm, for finding a value x such that f(x) = 0, for a given function f. Such an x is called a root of the function f. This article is concerned with finding scalar, real or complex roots,… …   Wikipedia

  • List of mathematics articles (R) — NOTOC R R. A. Fisher Lectureship Rabdology Rabin automaton Rabin signature algorithm Rabinovich Fabrikant equations Rabinowitsch trick Racah polynomials Racah W coefficient Racetrack (game) Racks and quandles Radar chart Rademacher complexity… …   Wikipedia


We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.