The Bisection Method is a numerical method for estimating the roots of a polynomial f(x). It is one of the simplest and most reliable but it is not the fastest method. Assume that f(x) is continuous.
Algorithm for the Bisection Method: Given a continuous function f(x)
For the i^{th} iteration, where i = 1, 2, . . . , n, the interval width is
x_{i} = 0.5
x_{i–1} = ( 0.5 )^{i} ( b – a )
and the new midpoint is
x_{i} = a_{i–1} + x_{i}
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.5 | 2 | –1 | 2.875 | 9 |
2 | 1 | 1.25 | 1.5 | –1 | 0.703125 | 2.875 |
3 | 1 | 1.125 | 1.25 | –1 | –0.201171875 | 0.703125 |
4 | 1.125 | 1.1875 | 1.25 | –0.201171875 | 0.237060546875 | 0.703125 |
5 | 1.125 | 1.15625 | 1.1875 | –0.201171875 | 0.014556884765625 | 0.237060546875 |
6 | 1.125 | 1.140625 | 1.15625 | –0.201171875 | –0.0941429138183594 | 0.014556884765625 |
7 | 1.140625 | 1.1484375 | 1.15625 | –0.0941429138183594 | –0.0400032997131348 | 0.014556884765625 |
8 | 1.1484375 | 1.15234375 | 1.15625 | –0.0400032997131348 | –0.0127759575843811 | 0.014556884765625 |
9 | 1.15234375 | 1.154296875 | 1.15625 | –0.0127759575843811 | 0.000877253711223602 | 0.014556884765625 |
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 Bisection Method. Determine an initial estimate of the first positive root within one unit interval. Use Horner's Method for evaluating f(x).
Questions: