Bisection Method

Dr. Kevin G. TeBeest
Assoc. Prof. of Applied Mathematics
Kettering University

This Maple script uses the bisection method to approximate the zero of a function on an interval from xL to xR. The user must enter these quantities in the script:

function f
xL — the left interval endpoint
xR — the right interval endpoint
TOL — the stopping tolerance
Maxits — the maximum number of iterations to allow
In this demonstration we will set Digits to 16 to tell Maple to use 16 digit arithmetic. (By default Maple performs 10 digit arithmetic.)

> restart ;

> Digits := 16 ;    (enter this as an integer... no decimal point)

[Maple Math]

Enter f as a function here.

> f := x –> evalf( exp(-x) – cos(x) ) ;
   Note the –> is the minus followed by greater than without a space.
   The evalf command automatically converts the results to floating point (decimal) form any time function f is evaluated.

[Maple Math]

Notice that we did NOT enter function f as: f(x) := ...

Plot function f on appropriate intervals to determine where the zero might lie.

> plot( f(x), x = 0.0 .. 6.0, thickness = 3 ) ;

[Maple Plot]

Based on the plot, we observe that the first zero lies between x = 1 and x = 2. So we set the left and right endpoints accordingly:

> a := 1.0 ;    (enter this with a decimal point)

a := 1.0

> b := 2.0 ;    (enter this with a decimal point)

b := 2.0;

> xL := a ;    (This stores the current value of a in xL.)

[Maple Math]

> xR := b ;    (This stores the current value of b in xR.)

[Maple Math]

Calculate the y values at the interval endpoints.

> yL := f(xL) ;

[Maple Math]

> yR := f(xR) ;

[Maple Math]

Set the maximum iterations (as a safeguard to prevent infinite looping in case of human error) and the stopping tolerance. In fact, while debugging your code you should set Maxits to something smaller, like 4, for example. Make Maxits larger once you a sure your code is bug-free.

> Maxits := 50 ;    (enter this as an integer... no decimal point)

[Maple Math]

> TOL := 0.5 * 10^(–6) ;

[Maple Math]

The following line initially sets ym to a value greater than the tolerance. This is done once only and before the loop below is entered.

> ym := TOL + 1.0 ;

ym := 1.000000500000000

The following block (also called a loop) is the Bisection method. Notice that it continues iterating until either: 1) the stopping tolerance is satisfied or 2) the maximum number of iterations is exceeded.

In Maple, terminating a command with a colon (:) suppresses printing that result while terminating a command with a semicolon (;) allows printing that result. In our case, we are letting the lprint command do the printing.

> for i from 1 to Maxits while ( abs( xR – xL ) > TOL ) do   (after each line in this block, hit Shift-Enter)
         xm := ( xL + xR ) / 2.0 :
         ym := f(xm) :
         if ( yL * ym < 0 ) then   (This is the "sign test.")
              xR := xm :
              yR := ym :
         else
              xL := xm :
              yL := ym :
          fi :
          lprint( `iter =`, i, `xm =`, xm, `ym =`, ym, `|xR–xL| =`, abs(xR–xL) ) :
    od:
iter = 1 xm = 1.500000000000000 ym = .1523929584807269 |xR–xL| = .500000000000000
iter = 2 xm = 1.250000000000000 ym = –.288175655350786e-1 |xR–xL| = .250000000000000
iter = 3 xm = 1.375000000000000 ym = .582918878157593e-1 |xR–xL| = .125000000000000
iter = 4 xm = 1.312500000000000 ym = .137125818403722e-1 |xR–xL| = .62500000000000e-1
iter = 5 xm = 1.281250000000000 ym = –.78274951684297e-2 |xR–xL| = .31250000000000e-1
iter = 6 xm = 1.296875000000000 ym = .28761500885946e-2 |xR–xL| = .15625000000000e-1
iter = 7 xm = 1.289062500000000 ym = –.24925655603582e-2 |xR–xL| = .7812500000000e-2
iter = 8 xm = 1.292968750000000 ym = .1876058477670e-3 |xR–xL| = .3906250000000e-2
iter = 9 xm = 1.291015625000000 ym = –.11535310652437e-2 |xR–xL| = .1953125000000e-2
iter = 10 xm = 1.291992187500000 ym = –.4832248353680e-3 |xR–xL| = .976562500000e-3
iter = 11 xm = 1.292480468750000 ym = –.1478749785070e-3 |xR–xL| = .488281250000e-3
iter = 12 xm = 1.292724609375000 ym = .198490724473e-4 |xR–xL| = .244140625000e-3
iter = 13 xm = 1.292602539062500 ym = –.640170446997e-4 |xR–xL| = .122070312500e-3
iter = 14 xm = 1.292663574218750 ym = –.220850089032e-4 |xR–xL| = .61035156250e-4
iter = 15 xm = 1.292694091796875 ym = –.11182239046e-5 |xR–xL| = .30517578125e-4
iter = 16 xm = 1.292709350585938 ym = .93653603547e-5 |xR–xL| = .15258789063e-4
iter = 17 xm = 1.292701721191407 ym = .41235522459e-5 |xR–xL| = .7629394532e-5
iter = 18 xm = 1.292697906494141 ym = .15026601757e-5 |xR–xL| = .3814697266e-5
iter = 19 xm = 1.292695999145508 ym = .1922171368e-6 |xR–xL| = .1907348633e-5
iter = 20 xm = 1.292695045471192 ym = –.4630036333e-6 |xR–xL| = .953674316e-6
iter = 21 xm = 1.292695522308350 ym = –.1353933106e-6 |xR–xL| = .476837158e-6

NOTE: In the lprint command, use either the left quote ` or the double quote " to print a text string. Do NOT use the right quote '.

Let's now uses Maple's fsolve command to numerically obtain the zero of function f, having it look on the interval from x=1 to x=2.

> z := fsolve( f(x) = 0, x = 1.0 .. 2.0 ) ;

[Maple Math]

Question:   Does the last xm agree with z to at least 6 decimal places?

Comments:

To re-run the script, you must go up to the line where xL and xR are set, and either hit return or change their values and hit return. Then hit return on each subsequent command line to re-run the entire script or click on the !!! button at the top to run the entire worksheet.

Maple Notes:

     a) Maple is case sensitive.
         For example, xr, xR, Xr, and XR are treated as different quantities in Maple.

     b) Indentation and spacing are not necessary but greatly enhance readability.

     c) do must end with od or end do

     d) if must end with fi or end if

     e) If the sign test passes, then all commands between if and else are executed.
         If the sign test fails, then then all commands between else and fi are executed.

Copyright © 2002–2011 Kevin G. TeBeest

Return to the Bisection Assignment

Return to course web site