n this module, I include a file called Bisection Technique. I use an example similar to the textbook described in section 2.1. I start to solve the example by hand and complete it using MATLAB. After reading the Bisection technique lesson 4 and section 2.1 of the textbook, answer the following discussion question in your own words.
When running the Bisection method in lesson 4 (program 1.1), with a tolerance of 0.001 the answer is 1.3652 which is equivalent to p9 according to the table 2.1 from the textbook. When running p13 in lesson 4 (program 1.2), the answer is 1.3651 which is equivalent to p13. Which one of the answers do you think is the most accurate answer closest to the solution and why? Which of the two calculation methods do you prefer and why? Elaborate in your answers.
file attached
Lesson 4
Bisection Technique
To find a solution or root of an equation f(x) we can apply the bisection method, which is an
approximation technique to get closer and closer to the value of the root by dividing the
interval in half after each iteration. The bisection method or binary search technique is based
on the Intermediate Value Theorem. Suppose f is a continuous function on the interval [a,b]
with f(a) and f(b) of opposite sign, the Intermediate Value Theorem implies that a number p
exists in [a,b] with f(p) = 0. The method calls for a repeated halving or bisecting of subintervals
of [a,b] and at each step locating the half containing p.
Example:
Does
f(x) = x
3
+4x
2
-10
has a root or solution in
[a,b] = [1,2]?
1) Let’s check if f(1) and f(2) have opposite signs according to the Intermediate Value
Theorem.
f(a) = f(1)
= (1)
3
+ 4(1)
2
– 10 = -5
(negative)
f(b) = f(2)
= (2)
3
+ 4(2)
2
– 10 = 8+16-10 = 14
(positive)
The answer is yes, which means since f is continuous there must be a solution in the
interval [1,2].
2) Let p be the solution we are searching for and let p1 be the first midpoint of [a,b] = [1,2].
p1
= (a+b)/2 = (1+2)/2 = 3/2 = 1.5
f(p1)
=
f(1.5)
= (1.5)
3
+4(1.5)
2
-10 = 2.375
(positive)
3) If
f(p1)
= 0
then p1 is the root or the solution, so p= p1. Done.
Otherwise, if
f(p1)
is not equal to zero, which is the case, we’re going to replace either a or b by
p1 to obtain a new interval closer to the root or the solution.
How do we know which one to replace? Simple. The goal is to keep two intervals of which
their functions have opposite signs when we calculate the function
f
at these two intervals. The
question to ask is rather which of the two
f(a)
and
f(b)
has opposite sign to the function
f(p1)
?
a) If
f(p1)
and
f(a)
have the same sign, then they don’t satisfy the Intermediate Value
Theorem. We replace
a
by
p1
, so the new interval that contains the solution p will be
[p1, b].
b) If
f(p1)
and
f(a)
have opposite signs, then they satisfy the Intermediate Value Theorem.
We replace
b
by
p1
so the new interval that contains the solution p will be [a, p1].
In our case,
f(a) which is f(1)
has opposite sign to
f(p1) which is f(1.5)
. We replace (
b
which is 2 by
p1
which is 1.5). The new interval that contains a solution is [a, p1] = [1,
1.5].
Next we go back to step 2 and step 3 by repeating this process again to find the new
midpoint p2, check if p2 is the solution, if not obtain a new interval.
Let’s continue with steps 2 and 3.
Step 2:
a. let p2 be the second midpoint of [a, p1] = [1, 1.5].
p2
= (a+p1)/2 = (1+1.5)/2 = 2.5/2 = 1.25
f(p2)
= f(1.25) = (1.25)
3
+4(1.25)
2
-10 = -1.796875
(negative)
Step 3:
Which of the two
f(a)
and
f(p1)
has opposite sign to the function
f(p2)
OR
Which of the two
f(1)
and
f(1.5)
has opposite sign to the function
f(1.25)
?
f(a)
=
f(1)
= -5;
f(p1) = f(1.5) = 2.375;
f(p2) = f(1.25) = -1.796875
The answer is
f(p1) = f(1.5)
and
f(p2) = f(1.25), so we replace a by p2.
Therefore, the new interval that contains a solution is: [p2, p1] = [1.25, 1.5].
We repeat steps 2 and 3 again and again until
f(midpoint) = 0
or within a Tolerance, let’s
say 0.001 = 10
-4
.
To do this we can use the MATLAB tool. The following program 1.1 can be used to find
the root of the same function using bisection method with a tolerance of 0.001 = 10
-4
%Program 1.1 Bisection Method
%Computes approximate solution of f(x)=0
%Input: inline function f; a,b such that f(a)*f(b)<0,
% and tolerance tol
%Output: Approximate solution xc
function xc = bisect(f,a,b,tol)
if sign(f(a))*sign(f(b)) >= 0,
error(‘f(a)f(b)<0 not satisfied!’)
%ceases execution
end
fa=f(a);
fb=f(b);
k = 0;
while (b-a)/2>tol
c=(a+b)/2;
fc=f(c);
if fc == 0
%c is a solution, done
break
end
if sign(fc)*sign(fa)<0 %
a and c make the new interval
b=c;fb=fc;
else %
c and b make the new interval
a=c;fa=fc;
end
end
xc=(a+b)/2;
%new midpoint is best estimate
1. Copy and paste this program in MATLAB in the editor window.
2. Save the program as bisect.
3. To run the program, type the following in the command window:
>> bisect(@(x) x^3+4*x^2-10,1,2,0.0001)
@(x) x^3+4*x^2-10
represents the function
1,2
represents the interval
0.01
represents the Tolerance.
The output is:
ans =
1.3652
The following MATLAB program 1.2 can be used to find the root of the same function
using bisection method with 13 iterations meaning that we will find the midpoint 13 times pn =
p13.
%Program 1.2 Bisection Method
function [x e] = mybisect(f,a,b,n)
% function [x e] = mybisect(f,a,b,n)
% Does n iterations of the bisection method for a function f
% Inputs: f — an inline function
% a,b — left and right edges of the interval
% n — the number of bisections to do.
% Outputs: x — the estimated solution of f(x) = 0
% e — an upper bound on the error
format long
c = f(a); d = f(b);
if c*d > 0.0
error(‘Function has same sign at both endpoints.’)
end
disp(‘ x y’)
for i = 1:n
x = (a + b)/2;
y = f(x);
disp([ x y])
if y == 0.0
% solved the equation exactly
e = 0;
break
% jumps out of the for loop
end
if c*y < 0
b=x;
else
a=x;
end
end
e = (b-a)/2;
1. Copy and paste this program in MATLAB in the editor window.
2. Save the program as bisection.
3. To run the program, type the following in the command window:
>> bisection(@(x) x^3+4*x^2-10,1,2,13)
@(x) x^3+4*x^2-10
represents the function
1,2
represents the interval
13
represents the number of iterations.
The output is:
x
y
1.500000000000000 2.375000000000000
1.250000000000000 -1.796875000000000
1.375000000000000 0.162109375000000
1.312500000000000 -0.848388671875000
1.343750000000000 -0.350982666015625
1.359375000000000 -0.096408843994141
1.367187500000000 0.032355785369873
1.363281250000000 -0.032149970531464
1.365234375000000 0.000072024762630
1.364257812500000 -0.016046690754592
1.364746093750000 -0.007989262812771
1.364990234375000 -0.003959101522923
1.365112304687500 -0.001943659010067
ans =
1.365112304687500
