FALSE POSITION METHOD

In numerical analysis, the 'false position method' or 'regula falsi method' is a root-finding algorithm that combines features from the bisection method and the secant method.

Contents

The method

Finding the root of the secant

Analysis

Example code

History

References

External links

The method

Like the bisection method, the false position method starts two points ''a''₀ and ''b''₀ such that ''f''(''a''₀) and ''f''(''b''₀) are of opposite signs, which implies by the intermediate value theorem that the function ''f'' has a root in the interval [''a''₀, ''b''₀]. The method proceeds by producing a sequence of shrinking intervals [''a''_''k'', ''b''_''k''] that all contain a root of ''f''.
At iteration number ''k'', the number
:
is computed. As explained below, ''c''_''k'' is the root of the secant line through (''a''_''k'', f(''a''_''k'')) and (''b''_''k'', f(''b''_''k'')). If f(''a''_''k'') and f(''c''_''k'') have the same sign, then we set ''a''_''k''+1 = ''c''_''k'' and ''b''_''k''+1 = ''b''_''k'', otherwise we set ''a''_''k''+1 = ''a''_''k'' and ''b''_''k''+1 = ''c''_''k''. This process is repeated until the root is approximated sufficiently well.
The above formula is also used in the secant method, but the secant method always retains the last two computed points, while the false position method retains two points which certainly bracket a root. On the other hand, the only difference between the false position method and the bisection method is that the latter uses ''c''_''k'' = (''a''_''k'' + ''b''_''k'') / 2.

Finding the root of the secant

Given ''a''_''k'' and ''b''_''k'', we construct the line through the points (''a''_''k'', ''f''(''a''_''k'')) and (''b''_''k'', ''f''(''b''_''k'')), as demonstrated in the picture on the right. Note that this line is a secant or chord of the graph of the function ''f''. In point-slope form, it can be defined as
:
We now choose ''c''_''k'' to be the root of this line, so ''c'' is chosen such that
:
Solving this equation gives the above equation for ''c''_''k''.

Analysis

If the initial end-points
''a''₀ and ''b''₀ are chosen such that ''f''(''a''₀) and ''f''(''b''₀) are of opposite signs, then one of the end-points will converge to a root of ''f''.
Asymptotically,
the other end-point will remain fixed for all subsequent
iterations while the one end-point always being updated. As a result,
unlike the bisection method, the width of the bracket does not tend to
zero. As a consequence, the linear
approximation to ''f''(''x''), which is used to pick the false position,
does not improve in its quality.
One example of this phenomenon is the function
:$f(x)\; =\; 2x^3-4x^2+3x$
on the initial bracket
[−1,1]. The left end, −1, is never replaced and thus the width
of the bracket never falls below 1. Hence, the right endpoint approaches 0 at
a linear rate (with a speed of convergence of 2/3).
While it is a misunderstanding to think that the method of false
position is a good method, it is equally a mistake to think that it
is unsalvagable. The failure mode is easy to detect (the same
end-point is retained twice in a row) and easily remedied by next
picking a modified false position, such as
:
or
:
down-weighting one of the endpoint values to force
the next ''c''_k to occur on that side of the function.
The factor of 2 above looks like a hack, but
it guarantees superlinear convergence (asymptotically, the algorithm
will perform two regular steps after any modified step). There are other
ways to pick the rescaling which give even better superlinear convergence
rates.
Ford (1995) summarizes and analyzes the superlinear variants of the modified
method of false position. Judging from the bibliography, modified
regula falsi methods were well known in the 1970s and have been
subsequently forgotten or misremembered in current textbooks.

Example code

The following C code was written for clarity instead of efficiency. It was designed to solve the same problem as solved by the Newton's method and secant method code: to find the positive number ''x'' where cos(''x'') = ''x''³. This problem is transformed into a root-finding problem of the form ''f''(''x'') = cos(''x'') - ''x''³ = 0.
'#include'
'#include'
 
'double' f('double' x)
{
'return' cos(x) - x
★ x
★ x;
}
 
'double' FalsiMethod('double' s, 'double' t, 'double' e, 'int' m)
{
'int' n,side=0;
'double' r,fr,fs = f(s),ft = f(t);
 
'for' (n = 1; n <= m; n++)
{
r = (fs
★ t - ft
★ s) / (fs - ft);
'if' (fabs(t-s) < e
★ fabs(t+s)) 'break';
fr = f(r);
 
'if' (fr
★ ft > 0)
{
t = r; ft = fr;
'if' (side==-1) fs /= 2;
side = -1;
}
'else if' (fs
★ fr > 0)
{
s = r; fs = fr;
'if' (side==+1) ft /= 2;
side = +1;
}
'else break';
}
'return' r;
}
 
'int' main('void')
{
printf("%0.15f
", FalsiMethod(0, 1, 5E-15, 100));
'return' 0;
}
After running this code, the final answer is approximately
0.865474033101614

History

The oldest surviving document demonstrating knowledge and proficiency in the false position method is the Indian mathematical text ''Vaishali Ganit'' (c. 3rd century BC). The ancient Chinese mathematical text called ''The Nine Chapters on the Mathematical Art'' (九章算術) dated from 200 BC to 100 CE also mentions the algorithm. In this text, however, the example problems posed apply the false position method to linear equations only, and the solutions reached are arrived at in only one step. Leonardo of Pisa (Fibonacci) cited False position in his 1202 AD book, Liber Abaci, following the method that he learned from Arab sources.

References

★ J.A. Ford (1995), ''Improved Algorithms of Illinois-type for the Numerical Solution of Nonlinear Equations'', Technical Report CSM-257, University of Essex, 1995

★ Richard L. Burden, J. Douglas Faires (2000), "Numerical Analysis, (7th Ed)", Brooks/Cole. ISBN 0-534-38216-9

★ L.E. Sigler, Fibonacci's Liber Abaci, Leonardo Pisno's Book of Calculation (2002), Springer-Verlag, New York, ISBN 0-387-40737-5.

External links

★ The Regula Falsi Method by John H. Mathews