|
|
False Position MethodIn 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. The method Like the bisection method, the false position method starts two points a0 and b0 such that f(a0) and f(b0) are of opposite signs, which implies by the intermediate value theorem that the function f has a root in the interval b0. The method proceeds by producing a sequence of shrinking intervals bk that all contain a root of f. At iteration number k, the number -
is computed. As explained below, ck is the root of the secant line through (ak, f(ak)) and (bk, f(bk)). If f(ak) and f(ck) have the same sign, then we set ak+1 = ck and bk+1 = bk, otherwise we set ak+1 = ak and bk+1 = ck. 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 ck = (ak + bk) / 2. Finding the root of the secant Given a and b, we construct the line through the points (a, f(a)) and (b, f(b)), 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 to be the root of this line, so c is chosen such that -
Solving this equation gives the above equation for ck. Analysis If the initial values a0 and b0 are chosen such that f(a0) and f(b0) are of opposite signs, then the false position method will converge to a root of f. The speed of convergence will typically be superlinear, thus faster than the bisection method, but slower that the secant method. 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) = x3. This problem is transformed into a root-finding problem of the form f(x) = cos(x) - x3 = 0. #include #include double f(double x) { return cos(x) - x*x*x; } double FalsiMethod(double s, double t, double e, double m) { int n; double r; for (n = 1; n <= m; n++) { r = t - f(t) * (s - t) / (f(s) - f(t)); if (f(r) < e) return r; if (f(s) * f(r) < 0) t = r; else if (f(r) * f(t) < 0) s = r; } return r; } int main(void) { printf("%0.15f\n", FalsiMethod(0, 1, 5E-11, 100)); return 0; } After running this code, the final answer is approximately 0.865474032979005. History Although the oldest surviving documents demonstrating knowledge and proficiency in the false position method date from between 200 BC and 100 CE in the ancient Chinese text called The Nine Chapters on the Mathematical Art (九章算術), ancient Egyptian methods demonstrated in the few documents we have principally employed the method of doubling and halving a known number to approach the solution, together with the method of false position. Allied with their decimal number systems, unit fractions, and tables of common results (such as the decomposition of non-unit fractions, such as 2/n) into unit fractions, these methods allowed ancient Egyptian mathematicians complex manipulation of problems. See Egyptian mathematics. Moreover, in the ancient Chinese text mentioned above the example problems posed apply the false position method to linear equations only, and the solutions reached are arrived at in only one step. References Richard L. Burden, J. Douglas Faires (2000), "Numerical Analysis, (7th Ed)", Brooks/Cole. ISBN 0534382169
|
 |