Bisection Method
Roots of Equations - The Bisection Method
M311 - Chapter 2
September 27, 2008
M311 - Chapter 2 Roots of Equations - The Bisection Method
Bisection Method
Lesson Outline
1 Bisection Method
Intermediate Value Theorem
Bisection Method Algorithm
Bisection Error Analysis
M311 - Chapter 2 Roots of Equations - The Bisection Method
Intermediate Value Theorem
Bisection Method Bisection Method Algorithm
Bisection Error Analysis
Intermediate Value Theorem
Intermediate Value Theorem (IVT)
If a function f (x) is continuous on [a, b] and K is a number
between f (a) and f (b), then there exist a number c in (a, b) for
which f (c) = K .
Refer to Page 9 - Burden & Faires for sample diagram
If a function f (a) and f (b) have opposite signs
i.e if f (a)f (b) < 0, by the IVT
∃ a number c in (a, b) for which f (c) = 0.
M311 - Chapter 2 Roots of Equations - The Bisection Method
Intermediate Value Theorem
Bisection Method Bisection Method Algorithm
Bisection Error Analysis
Examples of IVT
1 Does the function x 5 − 2x 3 + 3x 2 − 1 = 0 have a solution in
[0,1]? - refer to Page 9 of B & F for solution.
2 Does h(x) = x sin x − 1 have a solution in [0, 2].
Answer: Compute h(0) and h(1).
h(0) = −1.000000 and h(2) = 0.818595
Since h(0)h(1) < 0 there is a root in (0,2)
M311 - Chapter 2 Roots of Equations - The Bisection Method
Intermediate Value Theorem
Bisection Method Bisection Method Algorithm
Bisection Error Analysis
Bisection Method Algorithm to find root in [a, b]
a+b
1 Bisect [a, b] into two halves [a, c] and [c, b] where c =
2
2 Identify the interval containing the root by checking the signs
of f (a)f (c) and f (c)f (b).
3 If f (a)f (c) < 0 then interval [a, c] has the root. Otherwise
the other interval [c, b] has the root.
4 Bisect the new interval that contains the root and repeat
steps 1-3.
5 At each step take the midpoint of the interval as the most
updated approximation of the root.
6 Stop the procedure after a specified number of iterations or
when the width of the interval containing the root is less than
a given tolerance ε.
M311 - Chapter 2 Roots of Equations - The Bisection Method
Intermediate Value Theorem
Bisection Method Bisection Method Algorithm
Bisection Error Analysis
Example 1. The root of e x − 2 = 0 is known to exist in [0,2]. Use
8 iterations to find an approximate value of the root (or find an
approximate value of the root to within a tolerance of ε)
iter. # a c b f (a) f (c) f (b)
1 0.0000 1.0000000 2.000000 -1.0000 0.7183 5.3891
2 0.0000 0.5000000 1.000000 -1.0000 -0.3513 0.7183
3 0.5000 0.7500000 1.000000 -0.3513 0.1170 0.7183
4 0.5000 0.6250000 0.750000 -0.3513 -0.1318 0.1170
5 0.6250 0.6875000 0.750000 -0.1318 -0.0113 0.1170
6 0.6875 0.7187500 0.750000 -0.0113 0.0519 0.1170
7 0.6875 0.7031250 0.718750 -0.0113 0.0201 0.0519
8 0.6875 0.6953125 0.703125 -0.0113 0.0043 0.0201
M311 - Chapter 2 Roots of Equations - The Bisection Method
Intermediate Value Theorem
Bisection Method Bisection Method Algorithm
Bisection Error Analysis
Bisection Error Analysis
Bisection Method Theorem
If the bisection algorithm is applied to a continuous function f on
an interval [a, b], where f (a)f (b) < 0, then, after n steps, an
approximate root will have been computed with error at most
b−a
2n+1
For Proof, refer to handout.
M311 - Chapter 2 Roots of Equations - The Bisection Method
Intermediate Value Theorem
Bisection Method Bisection Method Algorithm
Bisection Error Analysis
b 0 −a0
2
|r −c0 |
a0 r c0 b0
M311 - Chapter 2 Roots of Equations - The Bisection Method
Intermediate Value Theorem
Bisection Method Bisection Method Algorithm
Bisection Error Analysis
If an error tolerance has been prescribed in advance, it is possible
to determine the number of steps required in the bisection method.
Suppose that we want |r − cn | < ε. Then it is necessary to solve
the following inequality for n:
b−a
<ε
2n+1
By taking logarithms, we obtain
log(b − a) − log(2ε)
n>
log 2
M311 - Chapter 2 Roots of Equations - The Bisection Method
Intermediate Value Theorem
Bisection Method Bisection Method Algorithm
Bisection Error Analysis
Example 2. How many steps of the bisection algorithm are needed
to compute the root of a function f (x) to a precision of ε = 0.01
on the interval [0,2]
Answer. a = 0 and b = 2.
b−a
< ε
2n+1
2−0
< 0.01
2n+1
2 > 100
n
log 100
n > = 6.64
log 2
Thus no more than n = 7 iterations would be needed to achieve
the convergence to within 0.01.
M311 - Chapter 2 Roots of Equations - The Bisection Method
