The bisection algorithm

Goal:

To understand the Bisection algorithm, and to reflect on possible ways to implement and generalize it.

Program:

1. Start matlab and run your setpath script to get access to the gui library.

2. Give the command open('RM+.fig') to open the Road Map to the Mathematics Laboratory, and press the Bisection button to enter into the Bisection lab. Alternatively you may enter this lab directly from the matlab prompt by the command open('BISECT.fig').

3. Use the Bisection lab as follows:

Give f(x), and a "return" to plot its graph (or choose one from the menu).

Look for a root (solution) of the equation f(x)=0 to be solved, and give a x-value (somewhat) to the left of the root in the left x= box below the plot window, followed by a "return" to have the corresponding f(x) value computed and displayed.

Then give a x-value to the right of the root in the rightmost x= box, again followed by a "return" to get the corresponding f(x) value.

Check that the two f(x) values just computed have opposite signs, indicating an f(x)=0 value in between.

Now start the iteration process by computing and give the x-value of the midpoint of the given interval in the middle x= box, and a "return" to have the corresponding f(x) value computed and displayed. Then choose the left or right subinterval by pressing the left or right button, depending on where you think the root is. You determine this by checking the sign of f(x) in the three present x points (or simpler by locking at the graph, possible for you but not the computer). Watch how the current left or right x point is replaced by the previous midpoint, and how the previous midpoint is replaced by the midpoint of the choosen subinterval, and how all the corresponding f(x) values are updated.

Next just repeat this procedure by choosing the left or right subinterval of the current interval, etc.

After a few iterations you may want to zoom in to see what is going on.

Also, note the list of left and right interval endpoints presented in the Matlab command window.

You may also automize the iteration process by giving a certain number of iterations, or a certain tolerance.

4. As a first example, solve the equation 3x=2.

5. Then solve the equation x(1+x)^2=1.

6. Find all roots of the equation x^3-3x+1=0.

7. How many iterations is required, starting with an interval of length 1, to have a root caught in an interval of length at most 0.01?

8. What happens if the midpoint happens to be a root? Test!

9. If there are roots in both subintervals, which one is chosen?

10. Is the tolerance related to the error in x or to the residual, as it seems?

11. Observing that the graph appears more and more linear as we zoom in on a root, it should be possible to compute a good expected value of the root from the last subinterval based on the size of f(x) in the two endpoints. Derive a formula for this.

12. Is the midpoint of the current interval the best point to make the cut into two subintervals?

13. Pose further questions of your own problems and experiment!!

14. Now make your own f(x)=0 solver by implementating the Bisection algorithm (for example) according to the specification in Bisection code shell. First replace the ?'s to get the code working. Then perform adequate tests to make sure the solver works as desired.

15. Finally you may want to add functionality to your bisection code as indicated (the add's), so it can handle also inconsistent input data. Consider also what happens if x (the computed midpoint) should be an exact root.

/Kenneth


Last modified: Tue Aug 15 15:18:36 MET DST 2000