Bisection method

Bisection Method 

Theorem :

An equation f (x) = 0 , where f (x) is a real continuous function, has at least one root between x_/ and x_u if f(x_l) .f(x_u) < 0.

What is the bisection method and what is it based on? 

One of the first numerical methods developed to find the root of a nonlinear equation f (x) = 0 was the bisection method (also called binary-search method). 

The method is based on the following theorem:

Note that :if f(x_l)f(x_u) > 0, there may or may not be any root between x_l and x_u.

[ fig (2) and (3)] suggests If f(x_l)f(x_u) < 0 then there may be more than one root between x_l and x_u, [ fig (1) and (4)]. so theorem guarantees one root between x_l and x_u 

Fig1: at least one root between two points if the function is real, continuous and changes sign.

Fig2 : If the function doesn't change sign between two points, the root of the function f(x)=0 may still exist between two points.

Fig4 : If the function f(x) changes sign between the two points, more than one root fo the equation f(x)=0 may exist between the two points.

 Understanding to Bisection method :

1. Since the method is based on finding the root between two points, the method falls under the category of bracketing methods.

2.Since the root is bracketed between two points, x_l and x_u, one can find the midpoint, x_m between x_l and x_u

. This gives us two new intervals (x_l,x_m), and (x_m ,x_u).

 3.Now, our problem is in which interval root of the equation f(x)= 0 lies?

4.Well, one can find the sign of f( x_l).f(x_m ) and if f(x_l).f(x_m ) < 0 then the new bracket is between x_l and x_m , otherwise, it is between x_m and x_u.

5.So, you can see that you are literally halving the interval. As one repeats this process, the width of the interval [x_l,x_u] becomes smaller and smaller, and you can zero in to the root of the equation f(x)=0.

Important while solving problem

(1) An algebraic equation f(x) = 0 can have at most as many as positive roots as the number of changes of sign of f(x).(2) An algebraic equation f(x) = 0 can have at most as many as negative roots as the number of changes of sign of f(-x).