The Bisection
Method
1. Information
About the Bisection Method
Suppose 
is a continuous
function defined on the interval 
, with 
and 
of opposite sign. By
the Intermediate Value Theorem, there exists p in 
with 
. Although the procedure will work for the case when 
and 
have opposite signs
and there is more than one root in the interval 
, we assume for simplicity that the root in this interval is
unique. The method calls for a repeated halving of subintervals of 
and, at each step,
locating the half containing p.
The
implementation of this can be done by setting 
and 
, and letting 
be the midpoint of 
. So, the following
can be written:
If 
,then 
; then 
has the same sign as either 
or
. If 
and
have the same sign, then 
, and we set 
and 
. If 
and 
have the opposite
signs, then 
, and we set 
and 
. We then reapply the process to the interval 
.
The
following algorithm and the figure explain how the above explanation can be
implemented by using computer.
Figure.1:
Bisection Method
INPUT: endpoints a, b; tolerance TOL ; maximum
number of iterations N0.
OUTPUT:
approximate solution p or message of failure.
Step 1: Set i = 1
Step 2:
While 
do steps 3-6
Step 3: Set 
(Compute pi.)
Step 4: If 
or 
then
OUTPUT (p); (Procedure
completed successfully.)
STOP.
Step 5: Set i = i + 1
Step 6: If 
then set a = p (Compute ai, bi)
Step 7: OUTPUT (Procedure
completed unsuccessfully.)
STOP
The
following procedures can be used as stopping criteria for the above algorithm.
In our program we use one of them or the both according the desire of the user.
The typical values for these criteria are set at the initial state of the
applet.
Absolute Error: 
Relative Error: 
2. Some Numerical
Results
f(x) = x3+4x2-10
The results of the
problem f(x) = x3+4x2-10 = 0 is obtained by using the
Bisection Method. The iteration number and the p value obtained after
this iteration are provided as follows:
IterationNumber |
Pn |
|
1 |
1.5 |
|
2 |
1.25 |
|
3 |
1.375 |
|
4 |
1.3125 |
|
5 |
1.34375 |
|
6 |
1.359375 |
|
7 |
1.3671875 |
|
8 |
1.36328125 |
|
9 |
1.365234375 |
|
10 |
1.3642578125 |
|
11 |
1.36474609375 |
|
12 |
1.364990234375 |
|
13 |
1.3651123046875 |
|
14 |
1.36517333984375 |
|
15 |
1.365203857421875 |
Table.1:
The results for the Bisection Method.
While
the above results are being obtained, the absolute error is chosen and its
value is 0.0001. The initial interval is [1,2]. The correct value of the root
is 1.365230013 (up to nine digits). The approximated value of root by this
method is 1.365203857. Then the absolute error is 0.00003 that is already
smaller than the desired value 0.0001.
f(x)=cos(x)-x
The results of the
problem f(x) = cos(x)-x = 0 is obtained by using the Bisection Method. The
initial interval is chosen as [0,1]. The iteration number and the p
value obtained after each iteration are provided as follows:
IterationNumber |
Pn |
|
1 |
0.5 |
|
2 |
0.75 |
|
3 |
0.625 |
|
4 |
0.6875 |
|
5 |
0.71875 |
|
6 |
0.734375 |
|
7 |
0.7421875 |
|
8 |
0.73828125 |
|
9 |
0.740234375 |
|
10 |
0.7392578125 |
|
11 |
0.73876953125 |
|
12 |
0.739013671875 |
|
13 |
0.7391357421875 |
|
14 |
0.73907470703125 |
|
15 |
0.739105224609375 |
Table.2: The
results for Bisection Method
The
absolute value of the error is again smaller than the desired value 0.0001.
That is the input for the applet by the user.
f(x)=ex^3–8
The
results of the problem f(x)=ex^3–8=0 is obtained by using the
Bisection Method. The initial interval is chosen as [0,3]. The iteration number
and the p value obtained after each iteration are provided as follows:
IterationNumber |
Pn |
|
1 |
1.5 |
|
2 |
0.75 |
|
3 |
1.125 |
|
4 |
1.3125 |
|
5 |
1.21875 |
|
6 |
1.265625 |
|
7 |
1.2890625 |
|
8 |
1.27734375 |
|
9 |
1.271484375 |
|
10 |
1.2744140625 |
|
11 |
1.27587890625 |
|
12 |
1.276611328125 |
|
13 |
1.2762451171875 |
|
14 |
1.27642822265625 |
|
15 |
1.276336669921875 |
|
16 |
1.2763824462890625 |
Table.3:
The results for Bisection Method
The
absolute value of the error is again smaller than the desired value 0.0001.
f(x)=xtan(x)-3
The
results of the problem f(x)=xtan(x)-3=0 is obtained by using the Bisection
Method. The initial interval is chosen as [6,7]. The iteration number and the p
value obtained after each iteration are provided as follows:
IterationNumber |
Pn |
|
1 |
6.5 |
|
2 |
6.75 |
|
3 |
6.625 |
|
4 |
6.6875 |
|
5 |
6.71875 |
|
6 |
6.703125 |
|
7 |
6.7109375 |
|
8 |
6.70703125 |
|
9 |
6.705078125 |
|
10 |
6.7041015625 |
|
11 |
6.70361328125 |
|
12 |
6.703857421875 |
|
13 |
6.7039794921875 |
|
14 |
6.70391845703125 |
|
15 |
6.703948974609375 |
Table.4:
The results for Bisection Method
The
absolute value of the error is again smaller than the desired value 0.0001.
3. Conclusion
The
Bisection Method has an important drawback. It is very slow in converging.(that
is, N may become quite large before 
is sufficiently
small). In addition the method cannot be applied for intervals for which 
is not satisfied. The
advantage of Bisection Method is that it is easy to determine the value of p
at the given iteration number as the method divides the interval into two equal
parts at each iteration. Another advantageous property of the method is that it
always converges to the root unlike Newton’s Method and the Secant Method. For
that reason it is often used as a ‘starter’ for the more efficient methods.
4. References
[1]
Numerical Analysis, R.L. Burden, J.D. Faires, PWS Publishing Company,
Boston 1993.