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: 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 x₁ , x₂, and x₃.

   

2. 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)/2ⁿ. 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.

3. Example

   Solve 3xe^x = 1 to three decimal places by the bisection method. Cconsider f(x) = 3x - e^x, which changes sign in the interval 0.25 < x < 0.27: one tabulates (working to 4D ) as follows:

   

   (Ascertain graphically that there is just one root!)

   Denote the lower and upper endpoints of the interval bracketing the root at the n-th iteration by a_n and b_n, respectively (with a₁ = 0.25 and b₁ = 0.27). Then the approximation to the root at the n-th iteration is given by x_n = a_n + b_n)/2. Since the root is either in [a_n, b_n] or [x_n, b_n] and both intervals are of length b_n - a_n)/2, we see that x_n will be accurate to three decimal places when (b_n - a_n)/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

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