STEP 7

NONLINEAR EQUATIONS 2

The bisection method

The bisection method, suitable for implementation on a computer (cf. the Pseudo-code) allows to find the roots of the equation f (x) = 0, based on the following theorem:

Theorem: If f is continuous for x between a and b and if f (a) and f(b) have opposite signs, then there exists at least one real root of f (x) = 0 between a and b.

  1. Procedure
  2. Suppose that a continuous function f is negative at x = a and positive at
    x = b, so that there is at least one real root between a and b. (As a rule, a and b may be found from a graph of f.) If we calculate f ((a +b)/2), which is the function value at the point of bisection of the interval a< x < b, there are three possibilities:
    1. f ((a + b)/2) = 0, in which case (a + b)/2 is the root;
    2. f ((a + b)/2) < 0, in which case the root lies between (a + b)/2 and b;
    3. f ((a + b)/2) > 0, in which case the root lies between a and (a + b)/2.
    Presuming there is just one root, in Case 1 the process is terminated. In either Case 2 or Case 3, the process of bisection of the interval containing the root can be repeated until the root is obtained to the desired accuracy. In Figure 5, the successive points of bisection are denoted by x1 , x2, and x3.

  3. Effectiveness

    The bisection method is almost certain to give a root. Provided the conditions of the above theorem hold; it can only fail if the accumulated error in the calculation of f at a bisection point gives it a small negative value when actually it should have a small positive value (or vice versa); the interval subsequently chosen would then be wrong. This can be overcome by working to sufficient accuracy, and this almost-assured convergence is not true of many other methods of finding roots.

    One drawback of the bisection method is that it applies only to roots of f about which f (x) changes sign. In particular, double roots can be overlooked; one should be careful to examine f(x) in any range where it is small, so that repeated roots about which f (x) does not change sign are otherwise evaluated (for example, see Steps 9 and 10). Of course, such a close examination also avoids another nearby root being overlooked.

    Finally, note that bisection is rather slow; after n iterations the interval containing the root is of length (b - a)/2n. However, provided values of f can be generated readily, as when a computer is used, the rather large number of iterations which can be involved in the application of bisection is of relatively little consequence.

  4. Example

  5. Let us solve 3xex = 1 to three decimal places by the bisection method.

    We can consider f(x) = 3x - ex, which changes sign in the interval 0.25 < x < 0.27: one may tabulate (working to 4D ) as follows:

    (The student should ascertain graphically that there is just one root.)

    Let us denote the lower and upper endpoints of the interval bracketing the root at the n-th iteration by an and bn, respectively (with a1 = 0.25 and b1 = 0.27). Then the approximation to the root at the n-th iteration is given by xn = an + bn)/2. Since the root is either in [an, bn] or [xn, bn] and both intervals are of length bn - an)/2, we see that xn will be accurate to three decimal places when bn - an)/2 < 5*10-4. Proceeding to bisection:

    (Note that the values in the table are displayed to only 4D.) Hence the root accurate to three decimal places is 0.258.

    Checkpoint

  6. When may the bisection method be used to find a root of the equation f(x) = 0?
  7. What are the three possible choices after a bisection value is calcu lated?
  8. What is the maximum error after n iterations of the bisection method`?

EXERCISES

  1. Use the bisection method to find the root of the equation

    x+cosx = 0.

    correct to two decimal places (2D ).

  2. Use the bisection method to find to 3D the positive root of the equation

    x - 0.2sinx - 0.5=0
    .

  3. Each equation in Exercises 2(a)-2(c) of Step 6 has onlyone root. For each equation use the bisection method to find the root correct to 2 D.