Question

Bisection search

1. In MATLAB, implement a function that performs a bisection search. It should take the following parameters:

• F: A function (assumed to be continuous) whose roots you want to find,

• a: A floating-point number giving the left endpoint of the initial interval in which you want to search for a root of F.

• b: A floating-point number giving the right endpoint of the initial interval.

• delta: A non-negative floating-point number giving the acceptable proximity of the output to a root of F.

Your function should first check a and b to determine whether or not they satisfy the condition given by the Intermediate Value Theorem that allows us to conclude that [a, b] contains a root of F. If this condition is not satisfied, return NaN (Matlab for “Not a number”). If the condition is satisfied, your function should perform a bisection search until it finds a number z that it can guarantee satisfies |x−x∗| < delta, for some real-valued root x∗ of F. It should return z.

2. Use the MATLAB function that you wrote to find a real-valued root of the function F(x) = x 5 +x+ 1, with accuracy to 4 decimal places (this last requirement will determine your choice of delta).

3. Suppose that you use bisection search to find a root of F(x) = sin x, with a = −π/2, b = 5π/2. To which root will the bisection search converge?

Answer 1

clc;
clear all;
format short
f=@(x)x^5 +x+ 1; %function

a=-3;b=6; % interval

% function [c ,niter]=bisecion(f,a,b,tol)

if(f(a)*f(b)>0)
fprintf('Root is not applicable in [%f, %f]\n',a,b)
else
tol = 1e-4; % tolerance

Nmax=30;
err=0.1;
niter=1;

while (err >= tol && niter<=Nmax )

x = (a + b)/2;
if ( f(x) == 0 )
break;
elseif ( f(a)*f(x) < 0 )
b = x;
else
a = x;
end
p(niter+1)=x;
err=abs( (p(niter+1)-p(niter))/p(niter+1));
niter=niter+1;
Tf(niter)=x;
end
end

disp('_____________________________________________________________')

disp('n x(n)) f(x(n)) ')
disp('____________________________________________________________')

for i=1:niter-1
fprintf('%d\t%15f \t %20f \n',i ,Tf(i),f(Tf(i)))
end
% x is root
%niter is number of iteration
disp('Root of the function')
x
disp('Number of iteration to converge the root')
niter-1

%%%%%%%%%%%%%%% Answer

_____________________________________________________________
n x(n)) f(x(n))
____________________________________________________________
1   0.000000    1.000000
2   1.500000    10.093750
3   -0.750000    0.012695
4   -1.875000    -24.049286
5   -1.312500    -4.207402
6   -1.031250    -1.197576
7   -0.890625    -0.450994
8   -0.820313    -0.191759
9   -0.785156    -0.083544
10   -0.767578    -0.034026
11   -0.758789    -0.010328
12   -0.754395    0.001267
13   -0.756592    -0.004510
14   -0.755493    -0.001616
15   -0.754944    -0.000174
16   -0.754669    0.000547
17   -0.754807    0.000187
Root of the function

x =

-0.7549

Number of iteration to converge the root

ans =

17

>>

clc;
clear all;
format short
f=@(x)sin(x); %function

a=-pi/2;b=5*pi/2; % interval

% function [c ,niter]=bisecion(f,a,b,tol)

if(f(a)*f(b)>0)
fprintf('Root is not applicable in [%f, %f]\n',a,b)
else
tol = 1e-4; % tolerance

Nmax=33;
err=0.1;
niter=1;

while (err >= tol && niter<=Nmax )

x = (a + b)/2;
if ( f(x) == 0 )
break;
elseif ( f(a)*f(x) < 0 )
b = x;
else
a = x;
end
p(niter+1)=x;
err=abs( (p(niter+1)-p(niter))/p(niter+1));
niter=niter+1;
Tf(niter)=x;
end
end

disp('_____________________________________________________________')

disp('n x(n)) f(x(n)) ')
disp('____________________________________________________________')

for i=1:niter-1
fprintf('%d\t%15f \t %20f \n',i ,Tf(i),f(Tf(i)))
end
% x is root
%niter is number of iteration
disp('Root of the function')
x
disp('Number of iteration to converge the root')
niter-1
%

%%%%%%%%%%%% Answer

n x(n)) f(x(n))
____________________________________________________________
1   0.000000    0.000000
2   3.141593    0.000000
3   0.785398    0.707107
4   -0.392699    -0.382683
5   0.196350    0.195090
6   -0.098175    -0.098017
7   0.049087    0.049068
8   -0.024544    -0.024541
9   0.012272    0.012272
10   -0.006136    -0.006136
11   0.003068    0.003068
12   -0.001534    -0.001534
13   0.000767    0.000767
14   -0.000383    -0.000383
15   0.000192    0.000192
16   -0.000096    -0.000096
17   0.000048    0.000048
18   -0.000024    -0.000024
19   0.000012    0.000012
20   -0.000006    -0.000006
21   0.000003    0.000003
22   -0.000001    -0.000001
23   0.000001    0.000001
24   -0.000000    -0.000000
25   0.000000    0.000000
26   -0.000000    -0.000000
27   0.000000    0.000000
28   -0.000000    -0.000000
29   0.000000    0.000000
30   -0.000000    -0.000000
31   0.000000    0.000000
32   -0.000000    -0.000000
33   0.000000    0.000000
Root of the function

x =

-3.6573e-10

Number of iteration to converge the root

ans =

33

>>