[alogo] Regula falsi

(The term means rule of false position, referred also as method of chords or secant method.) This is a method to determine the roots of an equation F(x) = 0, which may be regarded as a modification of Newton's method (see NewtonIterative.html ). We simply replace the derivative with the ratio of differences. Hence to find next term xn+1, from previously calculated terms, we use the intersection of the x-axis with the chord passing through (xn,F(xn)) and (xn-1,F(xn-1)). The basic theorem of convergence for the resulting sequence is given by the following:

Theorem Let the function F(x) be defined in the open interval D = (a,b), where it satisfies:
(i) F is differentiable at least up to order 2,
(ii) F has a simple root z in (a,b) i.e. F(z)=0, and F'(z), F''(z) are different from zero.
Then there is an r>0 such that for every pair of start-values x0, x1 in the interval (z-r, z+r) the sequence defined through

[0_0] [0_1]

converges to z, the convergence being of order k = (1+sqrt(5))/2 = 1.61803 ...

Recall that the convergence is of order k (integer), when the limit of |xn+1-z|/|xn-z|k exists and is a constant L>=0.
In actual calculation of the sequence terms one should use the first formula, since the second may represent a division with a very small number.
The picture below illustrates the method by showing the first few terms, in the case of a quartic and arbitrary x0, x1.

[0_0] [0_1] [0_2]
[1_0] [1_1] [1_2]
[2_0] [2_1] [2_2]

Notice that the method is not an iterative one, since it can not be written in the form xn+1 = G(xn) from some appropriate G.

See Also



Gisela-Jordan Engeln und Fritz Reutter Formelsammlung zur Numerischen Mathematik Mannheim B.I.-Wissenschaftsverlag 1978, p. 22

Return to Gallery

Produced with EucliDraw©