The Regula–Falsi Method is a numerical method for estimating the roots of a polynomial f(x). A value x replaces the midpoint in the Bisection Method and serves as the new approximation of a root of f(x). The objective is to make convergence faster. Assume that f(x) is continuous.
Algorithm for the Regula–Falsi Method: Given a continuous function f(x)
Observe that
EC / BC | = | E / AB |
---|---|---|
[ x – a ] / [ b – a ] | = | [ f(x) – f(a) ] / [ f(b) – f(a) ] |
x – a | = | [ b – a ] [ 0 – f(a) ] / [ f(b) – f(a) ] |
x | = | a + [ b – a ] [ – f(a) ] / [ f(b) – f(a) ] |
x | = | a – [ b – a ] f(a) / [ f(b) – f(a) ] |
Note that the line segment drawn from f(a) to f(b) is called the interpolation line.
Graphically, if the root is in [ a, x_{i} ], then the next interpolation line is drawn between ( a, f(a) ) and ( x_{i}, f(x_{i}) ); otherwise, if the root is in [ x_{i}, b ], then the next interpolation line is drawn between ( x_{i}, f(x_{i}) ) and (b, f(b)).
EXAMPLE: Consider f(x) = x^{3} + 3x – 5, where [ a = 1, b = 2 ] and DOA = 0.001.
i | a | x | b | f(a) | f(x) | f(b) |
---|---|---|---|---|---|---|
1 | 1 | 1.1 | 2 | – 1 | – 0.369 | 9 |
2 | 1.1 | 1.13544668587896 | 2 | – 0.369 | – 0.129797592130931 | 9 |
3 | 1.13544668587896 | 1.14773797024856 | 2 | – 0.129797592130931 | – 0.0448680509813286 | 9 |
4 | 1.14773797024856 | 1.15196570867269 | 2 | – 0.0448680509813286 | – 0.0154155863909917 | 9 |
5 | 1.15196570867269 | 1.15341577448 | 2 | – 0.0154155863909917 | – 0.0052852985292482 | 9 |
6 | 1.15341577448 | 1.15391264384212 | 2 | – 0.0052852985292482 | – 0.00181077883487646 | 9 |
7 | 1.15391264384212 | 1.15408284038531 | 2 | – 0.00181077883487646 | – 0.000620231485743084 | 9 |
PROBLEM: Develop an algorithm, expressed as a NSD, that will find an estimate of the first positive root of a given polynomial f(x) within a certain degree of accuracy DOA using the Regula–Falsi Method. Determine an initial estimate of the first positive root within one unit interval. Use Horner's Method for evaluating f(x).