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 was the bisection method (also called Binary-Search method). The method is based on the following theorem.

Theorem: An equation , where is a real continuous function, has at least one root between and if (See Figure 1).

Note that if , there may or may not be any root between and (Figures 2 and 3). If , then there may be more than one root between and . (Figure 4) So the theorem only guarantees one root between and .

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

Since the root is bracketed between two points, and , one can find the mid-point, between and _. This gives us two new intervals

1. and , and

2. and

Figure 1: At least one root exists between two points if the function is real, continuous, and changes sign.

Figure 2: If function does not change sign between two points, roots of may still exist between the two points.

Figure 3: If the function does not change sign between two points, there may not be any roots between the two points.

Figure 4: If the function changes sign between two points, more than one root for may exist between the two points.

Is the root now between and , or between and ? Well, one can find the sign of , and if then the new bracket is between and , otherwise, it is between and . So, you can see that you are literally halving the interval. As one repeats this process, the width of the interval becomes smaller and smaller, and you can zero in to the root of the equation . The algorithm for the bisection method is given as follows.

Дата добавления: 2014-12-27