Lec 6 Bisection Method

Numerical Methods
Solution of Nonlinear Equations
Topic: Bisection method
Dr. Nasir M Mirza

Email: [email protected]
Bisection Method
The method is known as the Bolzano method
and can be called interval halving technique.
The method is simple and straight-forward.
Given a bracketed root, the method repeatedly
halves the interval while continuing to bracket
the root and it will converge on the solution.
Step 1
Choose xl and xu
as two guesses
for the root such
that f(xl) f(xu) < 0,
or in other words,
f(x) changes sign
between xl and
xu.
f(x)
x
xu
Step 2
Estimate the root, xm
of the equation f (x) =
0 as the mid-point
between xl and xu as
x xu
xm =
2
f(x)
x
xu
Step 3
Now check the following
f(x)
If f(xl) f(xm) < 0, then the root

lies between xl and xm;
then xl = xl ; xu = xm.
If f(xl ) f(xm) > 0, then the root
lies between xm and xu;
then xl = xm; xu = xu.
x
If f(xl) f(xm) = 0; then the root

is xm. Stop the algorithm
if this is true.
xm
xu
Step 4
New estimate
x xu
xm =
2
Absolute Relative Approximate Error
old
x new
x
m
m
new
m
100
xmold previous estimate of root

xmnew current estimate of root
Step 5
Check if absolute
relative approximate
error is less
than pre-specified
tolerance or if
maximum number
of iterations is
reached.
Yes
No
Stop
Using the new

upper and lower
guesses from Step
3, go to Step 2.
Example
You are working for DOWN THE TOILET COMPANY that
makes floats for ABC commodes. The ball has a specific
gravity of 0.6 and has a radius of 5.5 cm. You are asked to
find the distance to which the ball will get submerged when
floating in water.
Solution
The equation that gives the depth x to which the ball is
submerged under water is given by
f x x 3-0.165 x 2+3.993 x10 - 4

Use the Bisection method of finding
roots of equations to find the depth
x to which the ball is submerged
under water. Conduct three
iterations to estimate the root of
the above equation.
Graph of function f(x)

f x x 3-0.165 x 2+3.993 x10 - 4
Checking if the bracket is valid

Choose the bracket
x 0.00
xu 0.11
f 0.0 3.993x104
f 0.11 2.662x10
Iteration #1
x 0, xu 0.11
0 0.11
xm
0.055
2
f 0 3.993 x10 4
f 0.11 2.662 x10 4
f 0.055 6.655 x10 5
x 0.055
xu 0.11
Iteration #2
x 0.055, xu 0.11
0.055 0.11
0.0825
2
a 33.33%
xm
f 0.055 6.655x105
f 0.11 2.662x10 4
f 0.0825 1.62216x10 4
x 0.055, xu 0.0825
Iteration #3
x 0.055 , xu 0.0825
0.055 0.0825
xm
0.06875
2
a 20%
f 0.055 6.655x105
f 0.0825 1.62216x10 4
f 0.06875 5.5632x105
Convergence
Table 1: Root of f(x)=0 as function of number of iterations for bisection method.
Iteration
xu
xm
a %
f(xm)
0.00000
0.11
0.055
----------
6.655x10-5
0.055
0.11
0.0825
33.33
-1.6222x10-4
0.055
0.0825
0.06875
20.00
-5.5632x10-5
0.055
0.06875
0.06188
11.11
4.4843x10-6
0.06188
0.06875
0.06531
5.263
-2.5939x10-5
0.06188
0.06531
0.06359
2.702
-1.0804x10-5
0.06188
0.06359
0.06273
1.369
-3.1768x10-6
0.06188
0.06273
0.0623
0.6896
6.4973x10-7
0.0623
0.06273
0.06252
0.3436
-1.2646x10-6
10
0.0623
0.06252
0.06241
0.1721
-3.0767x10-7
Bisection Method
A basic loop that is used to find root between two points for a
function f(x) is shown here.
DO while 0.5*|x1 - x2| >= tolerance_value
Set xmid =(x1 + x2)/2
IF f(xmid) of opposite sign of f(x1);
Set x2 = xmid;
ELSE
Set x1 = xxmid;
ENDIF
END loop
Bisection Method
DemoBisect: the example program does a simple bisection for a

cubic polynomial equation.
Bisection Method
Example Problem:
y(x) = a5 x5 + a4 x4 + a3 x3 + a2 x2 + a1 x + a0
Let us consider constants to be following:
a0 = -2, a1 = -3, a2 = 4, a3 = 1, a4 = 0, a5 = 1
Then the function:

y(x) = x5 + x3 + 4x2 - 3x - 2
First we plot this function in a range from -3 to 3 and
see visually where roots are located.
Bisectional Method
There are 3 roots
(a) -2 < x < -1
60
(b) -1 < x < 0

40
(c) 0.5 < x <1.5

The graph for the
function is shown here.
y(x)
20
-20
-40
-2
-1
Computer Program for Bisection method

% A program in matlab
% bisection method to find the roots of x^5+x^3+4*x^2-3*x-2=0
xleft = -2.0 ; xright = -1.0 ; n = 100
% Input: xleft,xright = left and right brackets of the root
% n = (optional) number of iterations; default: n =15
% Output:
x = estimate of the root
if nargin<3, n=15; end
% Default number of iterations
a = xleft;
b =xright; % Copy orig bracket to local variables
fa = a^5 + a^3 +4*a^2 - 3*a - 2;
% Initial values
fb = b^5 + b^3 +4*b^2 - 3*b - 2;
% Initial values
fprintf(' k
a
xmid
b
f(xmid)\n');
for k=1:n
xm = a + 0.5*(b-a);
% Minimize roundoff in the midpoint
fm = xm^5 + xm^3 +4*xm^2 - 3*xm - 2; % f(x) at midpoint
fprintf('%3d %12.8f
%12.8f %12.8f
%12.3e\n',k,a,xm,b,fm);
if sign(fm) == sign(fa)
a = xm;
fa = fm;
else
b = xm;
fb = fm;
end
end
Bisection Method
k
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
a
-2.00000000
-2.00000000
-1.75000000
-1.62500000
-1.56250000
-1.53125000
-1.53125000
-1.53125000
-1.53125000
-1.53125000
-1.53027344
-1.52978516
-1.52954102
-1.52941895
-1.52941895
-1.52938843
-1.52937317
-1.52937317
-1.52936935
-1.52936935
xmid
-1.50000000
-1.75000000
-1.62500000
-1.56250000
-1.53125000
-1.51562500
-1.52343750
-1.52734375
-1.52929688
-1.53027344
-1.52978516
-1.52954102
-1.52941895
-1.52935791
-1.52938843
-1.52937317
-1.52936554
-1.52936935
-1.52936745
-1.52936840
b
-1.00000000
-1.50000000
-1.50000000
-1.50000000
-1.50000000
-1.50000000
-1.51562500
-1.52343750
-1.52734375
-1.52929688
-1.52929688
-1.52929688
-1.52929688
-1.52929688
-1.52935791
-1.52935791
-1.52935791
-1.52936554
-1.52936554
-1.52936745
f(xmid)
5.313e-001
-6.272e+000
-2.184e+000
-6.748e-001
-3.612e-002
2.562e-001
1.122e-001
3.860e-002
1.379e-003
-1.734e-002
-7.971e-003
-3.294e-003
-9.572e-004
2.108e-004
-3.732e-004
-8.117e-005
6.482e-005
-8.174e-006
2.832e-005
1.008e-005
For range of x = [-2, -1]; we see x = -1.5293684 as root here.
Advantages & Disadvantages

Advatages:
Always convergent
The root bracket gets halved with each iteration guaranteed.
Disadvatanges:
Slow convergence
If one of the initial guesses is close to the root, the
convergence is slower
Drawbacks (continued)
If a function f(x) is such that it just touches the x-axis it will be
unable to find the lower and upper guesses.
100
y=x
f x x 2
y(x)
80
60
40
20
-10
-5
10
Drawbacks (continued)
Function changes sign but root does not exist
100
f x
y = 1/x
80
60
40
y(x)
20
0
-20
-40
-60
-80
-100
-0.9
-0.6
-0.3
0.0
0.3
0.6
0.9
1
x

Lec 6 Bisection Method

Uploaded by

Copyright:

Available Formats

Lec 6 Bisection Method

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Lec 6 Bisection Method

Uploaded by

Copyright:

Available Formats

What is the bisection method?

What is the bisection method?

What are the steps of the bisection method?

What are the steps of the bisection method?

Numerical Methods

Solution of Nonlinear Equations

Topic: Bisection method

Dr. Nasir M Mirza

If f(xl) f(xm) < 0, then the root

If f(xl) f(xm) = 0; then the root

Absolute Relative Approximate Error

xmold previous estimate of root

Using the new

f x x 3-0.165 x 2+3.993 x10 - 4

Graph of function f(x)

Checking if the bracket is valid

DemoBisect: the example program does a simple bisection for a

Then the function:

(b) -1 < x < 0

(c) 0.5 < x <1.5

Computer Program for Bisection method

For range of x = [-2, -1]; we see x = -1.5293684 as root here.

Advantages & Disadvantages

You might also like