Bisection method

From Wikipedia, the free encyclopedia

Jump to: navigation, search
A few steps of the bisection method applied over the starting range [a1;b1]. The bigger red dot is the root of the function.

In mathematics, the bisection method is a root-finding algorithm which repeatedly bisects an interval 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.

Contents

[edit] The method

The method is applicable when we wish to solve the equation f(x) = 0 \ for the scalar variable x, where f is a continuous function.

The bisection method requires two initial points a and b such that f(a) and f(b) have opposite signs. This is called a bracket of a root, for by the intermediate value theorem the continuous function f must have at least one root in the interval (a, b). The method now divides the interval in two by computing the midpoint c = (a+b) / 2 of the interval. Unless c is itself a root--which is very unlikely, but possible--there are now two possibilities: either f(a) and f(c) have opposite signs c, or f(c) and f(b) have opposite signs and bracket a root. We select the subinterval that is a bracket, and apply the same bisection step to it. In this way the interval that might contain a zero of f is reduced in width by 50% at each step. We continue until we have a bracket sufficiently small for our purposes.

Explicitly, if f(a) f(c) < 0, then the method sets b equal to c, and if f(b) f(c) < 0, then the method sets a equal to c. In both cases, the new f(a) and f(b) have opposite signs, so the method is applicable to this smaller interval. A practical implementation of this method must guard against the uncommon occurrence that the midpoint is indeed a solution.

[edit] Analysis

If f is a continuous function on the interval [a, b] and f(a)f(b) < 0, then the bisection method converges to a root of f. In fact, the absolute error is halved at each step. Thus, the method converges linearly, which is quite slow. On the other hand, the method is guaranteed to converge if f(a) and f(b) have different signs.

The bisection method gives only a range where the root exists, rather than a single estimate for the root's location. Without using any other information, the best estimate for the location of the root is the midpoint of the smallest bracket found. In that case, the absolute error after n steps is at most

\frac{\left|b-a\right|}{2^{n+1}}.

If either endpoint of the interval is used, then the maximum absolute error is

\frac{\left|b-a\right|}{2^{n}},

the entire length of the interval.

These formulas can be used to determine in advance the number of iterations that the bisection method would need to converge to a root to within a certain tolerance. For, using the second formula for the error, the number of iterations n has to satisfy

n > \log_2\frac{b-a}{\epsilon}

to ensure that the error is smaller than the tolerance ε.

If f has several simple roots in the interval [a,b], then the bisection method will find one of them.

[edit] Pseudo-code

Here is a representation of the bisection method in Visual Basic code. The variables left and right correspond to a and b above. The initial left and right must be chosen so that f(left) and f(right) are of opposite sign (they 'bracket' a root). The variable epsilon specifies how precise the result will be.

 'Bisection Method
 
 'Start loop
 Do While (abs(right - left) > 2*epsilon)
 
   'Calculate midpoint of domain
   midpoint = (right + left) / 2
 
   'Find f(midpoint)
   If ((f(left) * f(midpoint)) > 0) Then
     'Throw away left half
     left = midpoint
   Else
     'Throw away right half
     right = midpoint
   End If
 Loop
 Return (right + left) / 2

[edit] Practical considerations

For robust usage in practice, some care is required due to the properties of floating-point arithmetic.

  1. The expression f(left) * f(midpoint) is very likely to underflow to 0 since both arguments are approaching a zero of f. To avoid this possibility, the two function values should be tested separately rather than multiplied.
  2. If epsilon is too small, the value of abs(right - left) might never become as small as 2*epsilon, as left and right can get stuck at adjacent non-equal floating-point values. This possibility can be avoided by disallowing epsilon to be too small (depending on the precision of the arithmetic) or by adding extra tests to detect the stuck condition. Another method relies on the assumption that (right+left)/2 exactly equals left or right if left and right are adjacent non-equal floating-point values. This is true for most hardware, including IEEE arithmetic in the absence of overflow, but can be violated if intermediate expressions are calculated to greater precision than stored variables (depending on computer optimization).

Code which takes both these problems into account (and relies on the uncertain assumption) is as follows. It attempts to find a zero as accurately as the machine precision allows.

  // Assumption: One of f(a) is ≥ 0 and the other is ≤ 0
  if f(a) <= 0 then
      lo := a; hi := b
  else
      lo := b; hi := a
  endif
 
  mid := lo + (hi-lo)/2
  while (mid ≠ lo) and (mid ≠ hi) do
     if f(mid) ≤ 0 then
        lo := mid
     else
        hi := mid
     endif
     mid := lo + (hi-lo)/2
  endwhile
 
  return mid

[edit] See also

Search Wikibooks The Wikibook Numerical Methods has a page on the topic of

[edit] References

[edit] External links

Retrieved from "http://en.wikipedia.org/wiki/Bisection_method"
Personal tools