Bisection Method

Bisection Method

The bisection method in mathematics is a root-finding method which repeatedly bisects an interval and then selects a subinterval in which a root must lie for further processing. It is a very simple and robust method, but it is also relatively slow. Because of this, it is often used to obtain a rough approximation to a solution which is then used as a starting point for more rapidly converging methods. The method is also called the binary search method and is similar to the Binary Search algorithm in computing, where the range of possible solutions is halved each iteration.

Bisection Method Advantages

• ·         Since the bisection method discards 50% of the current interval at each step, it brackets the root much more quickly than the incremental search method does.
• ·         To compare:
• ·         On average, assuming a root is somewhere on the interval between 0 and 1, it takes 6–7 function evaluations to estimate the root to within 0.1 accuracy.
• ·         Those same 6–7 function evaluations using bisection estimates the root to within 1 24 = 0.625 to 1 25 = 0.031 accuracy.

Bisection Method Disadvantages

• ·         Like incremental search, the bisection method only finds roots where the function crosses the x axis. It cannot find roots where the function is tangent to the x axis.
• ·         Like incremental search, the bisection method can be fooled by singularities in the function.
• ·         Like incremental search, the bisection method cannot find complex roots of polynomials.

Matlab Code

format long;

x = sym('x');

expr = input('Please enter the equation : ');

fx = sym(expr);

x1 = input('Please enter value of X1 : ');

x2 = input('Please enter value of X2 : ');

iter = input('Please enter number of Iterations : ');

fx1 = subs(fx,x,x1);

fx2 = subs(fx,x,x2);

x3 = 0;

counter = 0;

fid=fopen('c:\bisection.csv','w');

fprintf(fid,'%s\n','Iteration,x1,x2,x3,F(x1),F(x2),F(x3),Max Errors');

if fx1*fx2 >= 0

    message = 'x1 and x2 values are not valid for desired root';

    disp(message)

else 

   while ((counter == 0 || abs(x1-x2) > 0.000001 || subs(fx,x,x3) == 0) && counter <= iter)

       counter = counter + 1;

       x3 = (x1 + x2) / 2;   

       fprintf(fid,'%d,',counter);

       fprintf(fid,'%5.8f,',x1);

       fprintf(fid,'%5.8f,',x2);

       fprintf(fid,'%5.8f,',x3);

       fprintf(fid,'%5.8f,',subs(fx,x,x1));

       fprintf(fid,'%5.8f,',subs(fx,x,x2));

       fprintf(fid,'%5.8f,',subs(fx,x,x3));

       fprintf(fid,'%5.8f\n',abs((x2-x1)/(2^counter)));

       x3 = (x1 + x2) / 2;

       if subs(fx,x,x3) * subs(fx,x,x1)< 0

           x2 = x3;

       else

           x1 = x3;

       end    

   end    

end    

sprintf('The root of the equation using Bisection method is :: %d', x3)

fclose(fid);