Bisection Method
Bisection Method:
Suppose f (x) is continuous on an interval [a,b], such that
f (a). f (b) < 0;
Then f (x) changes sign on [a,b], and f (x) = 0 has at least one root on the interval. Bisection method repeatedly halve the interval [a,b], keeping the half on which f (x) changes sign. It guaranteed to converge to a root.
Figure of Bisection Method:
More preciously, Suppose that we are given an interval [a,b] satisfying and an error tolerance ε > 0. Then the bisection method is consists of the following steps:
[B1.] Compute c = (a b)/2
[B2.] If b−c ≤ ε, then accept c as the root and stop the procedure.
[B3.] If f (a). f (c) ≤ 0, then set b = c else, set a = c. Go to step B1.
Convergence of Bisection Method:
In Bisection Method, the original interval is divided into half in each iteration. Thus, if error in ith iteration is εi = |xi − α|, and error in (i 1)th iteration is εi 1 = |xi 1− α|, then we have
Then by definition in section 16.1, sequence of approximations in bisection method is linearly convergent. Sometimes it is said Bisection method is linearly convergent. Further the rate of convergence of this method is 0.5.
Example: Find a real root of the equation x2 − 2x− 5 = 0.
Solution: Let f (x) = x3 − 2x− 5. Then f (2) = −1 and f (3) = 16, therefore a root lies between 2 and 3 and we take;
Since f (a). f (c) < 0, we choose [2,2.5] as the new interval. Then, again;
and f (a). f (c) < 0. Proceeding in this way, the following table is obtained.
At n = 12, it is seen that the difference between two successive iterates is 0.0005 . Therefore root is 2.094