Bisection

NOTE:  If the applet below does not appear, you may need to download the latest version of Java or enable Java applets in your browser (in IE: Tools/Internet Options/Advanced/Java)

The Bisection Method for Root Finding

The Bisection Method is a bracketing method.  A bracket is an interval  for which the function values at the bounds of the interval have opposite signs:

Given an initial bracket (provided by the user), the bisection method divides the bracket into two intervals of equal size and determines which of the two intervals is again a bracket, that is, has bounds with function values with opposite signs.  This is where the method gets its name: in each iteration, it divides (sections) the bracket into two (bi=two in Latin).  Once a new bracket (half the size of the original bracket) has been determined, the method repeats the same process in an iterative fashion until the size of the remaining bracket is sufficiently small (smaller than a desired absolute error).  Note: For pratical reasons, the number of iterations in the interactive window below is limited to 8.

From the definition of the relative approximate error, one can derive the error of the bisection method:

If the size of the initial bracket is given by  then the absolute approximate error is:

For additional details about the Bisection Method, review "Chapter 5: Bracketing Methods" in Numerical Methods for Engineers by Chapra and Canale. A succinct on-line overview can be found at Wikipedia

Start Exploring!

In the interactive window below you can perform the following operations:

• Move a control point: click-and-drag a control point to a different position
• Add a control point: ctrl-click in the location where you want to add it
• Remove a control point: ctrl-click on the control point to be removed
• Retrieve a pre-programmed curve: click on one of the buttons S0 through S3
• Print this entire page: click the printer button at the top right of this web-page

Learn by Exploring

1. Verify the formula (given above) for predicting the absolute error of the bisection algorithm  by converting the listed relative error to absolute error.
2. Is it possible to have a large relative error even when in the graphical window it looks like the root is found?  If so, can you generate an example illustrating this?
3. Does the bisection algorithm always find a root when one exist?  If not, can you generate an example illustrating this?
4. How does the root finding algorithm behave when the curve has more than one root? 
5. Construct a curve with two roots.  Does the bisection algorithm converge?  Explain.  Does the method behave in the same way for all curves with two roots?