Bisection Method

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

This is NOT a project (programming assignment) to be turned in for grading. You should have this completed BEFORE I post the first Program (Coding) Assignment.
This Maple script uses the bisection method to approximate the zero of a function on an interval from x = a to x = b.

Do NOT copy and paste these commands into a Maple session. Doing so WILL introduce errors. Instead, manually type them into a Maple session. Learn from your mistakes.

The user must enter the following quantities in the script:

function f
a — the left interval endpoint
b — the right interval endpoint
TOL — the stopping tolerance
Maxits — the maximum number of iterations to allow


In this demonstration we will set Digits (Maple's precision) to 16 to tell Maple to perform 16 digit arithmetic. (By default Maple performs 10 digit arithmetic.)

> restart ;    (Start EVERY code with restart. You should put that in the first line in every code.)

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

[Maple Math]

Enter f as a function (not as an expression).

> f := x -> evalf( exp(-x) – cos(x) ) ;
   The evalf command automatically converts the results to floating point (decimal) form whenever function f is evaluated.

[Maple Math]

Notice that we did NOT enter function f as:   f := evalf( exp(-x) – cos(x) ) ;

Plot function f on appropriate intervals to determine where the zero might be.
size specifies the desired width and height of the plot in pixels.

> plot( f(x), x = 0.0 .. 6.0, thickness = 4, size = [450, 345] ) ;

[Maple Plot]

Based on the plot, we observe that the first positive zero is 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 (like 50) once you are 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 workhorse of the Bisection method that performs the iterations. 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 displaying that result, while terminating a command with a semicolon (;) allows that result to be displayed on screen. 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) ) :   (lprint — the first character is the letter ell, NOT the number one.)
    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 the double quote " to print a text string.
Furthermore, lprint is one word, and the first letter is ell, not the number 1.
Notice how ugly the output is. We will learn a VASTLY SUPERIOR print command that displays results in nice readable table format with proper column alignment, etc.


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. Alternatively, after making any changes to the code, 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 all commands between else and fi are executed.


Copyright © 2002–2023 Dr. Kevin G. TeBeest

Return to the Bisection Assignment

Return to course web site