MATH/APPM 4650
Class notes, January 28

The bisection method

Recall the Intermediate Value Theorem:
If f is a continuous function and f(a) f(b) < 0, then there is a point x between a and b such that f(x) = 0.


This theorem is the basic idea behind the bisection method.

1. Start with points a_old and b_old such that f(a_old) and f(b_old) have opposite signs.
2. Let m = (a + b)/2 be the midpoint of the interval [a, b]. Find the sign of f(m). Either f(m) = 0, or f(m) > 0, or f(m) < 0.
   • If f(m) is zero, we are done. The root is x = m.
   • If f(m) is the same sign as f(a_old), then the root is between m and b_old. Let a_new = m and let b_new = b_old.
   • If f(m) is the same sign as f(b_old), then the root is between a_old and m. Let a_new = a_old and b_new = m.
3. Either we are done (having found the solution x = m), or we have a new interval [a_new, b_new] which is half the length of the old interval [a_old, b_old].
4. Continue in this way until we either find the exact solution or the interval is sufficiently small.

How long will this take? If the tolerance is ε, and the initial length of the interval is L = b - a, then after N steps, the length of the interval is L / 2^N.

So the root is somewhere in this interval, and so the distance from the midpoint to the root is at most L / 2^N+1.

We want L / 2^N+1 < ε. Solve for N.

We get N > ln(L/ε)/ln(2) - 1.


Here is a pseudocode algorithm to run this. We set N = int( ln(L/ε)/ln(2) ), rounding down to get the integer.


# THE BISECTION METHOD
F(X) = X^3 - 3*X + 1
A = 0
B = 1
Tol = 0.001
N = INT( ln((B-A)/Tol) / ln(2) )
Count = 1
RootFound = FALSE
WHILE( (RootFound = FALSE) AND (Count <= N) ) DO
   M = (A+B)/2
   IF (F(M) = 0) THEN
      RootFound = TRUE
      X = M
   ELSE
      IF (F(M)*F(A) > 0) THEN
         A = M
      ELSE
         B = M
      END IF
      X = (A+B)/2
   END IF
   Count = Count + 1
END DO
PRINT(X)


Notice this is slightly different from the pseudocode in the book.

Preferred style is to use structured programming.
That is, we avoid BREAK or STOP in the middle of a loop.
If you want to end a loop, put an end criterion in the loop-checking.

We also avoid GOTO. If we want to loop at all, we always use FOR or WHILE loops.

The advantage of this style is that, as programs get complicated, it makes their overall structures clearer.

It's not essential, but most professional programmers STRONGLY RECOMMEND it.



Maple version:
F:=x->x^3-3*x+1:
a:=0:
b:=1:
Tol:=0.0001:
N:=floor(ln((b-a)/Tol)/ln(2)):
Count:=1:
RootFound:=false:
while ( (RootFound=false) and (Count<=N) ) do
   m := evalf((a+b)/2):
   if (evalf(F(m))=0) then
      RootFound:=true:
      x:=m:
   else
      if (F(m)*F(a)>0) then
         a:=m:
      else
         b:=m:
      end if:
      x:=evalf((a+b)/2):
   end if:
   Count:=Count+1:
end do:
print(x):


MATLAB version:
MATLAB needs its functions defined in separate files. So to do a bisection program, you need one file for the function and another for the program.

First save the following two-line file as "myfunction.m" in the same place as your bisection code.

function F=myfunction(x);
F=x^3-3*x+1;

Then save the following file as "bisection.m":

a=0;
b=1;
Tol=0.001;
N=floor(log((b-a)/Tol)/log(2));
Count=1;
RootFound=false;
while ((RootFound==false) && (Count<=N))
    m=(a+b)/2;
    if(myfunction(m)==0)
        RootFound=true;
        r=m;
 else
        if(myfunction(m)*myfunction(a)>0)
            a=m;
        else
            b=m;
        end
        r=(a+b)/2;
    end
    Count=Count+1;
end
r


Mathematica version:

F[x_]:=x^3-3*x+1;
a=0;
b=1;
Tol=0.001;
M=Floor[Log[(b-a)/Tol]/Log[2]];
Counter=1;
RootFound=False;
While[ ((RootFound==False) && (Counter<=M)),
  {m=N[(a+b)/2];
   If[F[m]==0,
     {RootFound=True;
      r=m},
     If[F[m]*F[a]>0,
      a=m,
     b=m
      ];
    r=N[(a+b)/2];
    Counter+=1;
    ];
   }
  ];
Print[r];




Question:
How could these programs be improved?

Think about the ways in which something could go wrong.

Could a user enter inputs that break the program?

A good program not only works when everything is perfect, it also checks its assumptions and gives proper error messages.