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)
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.
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] ) ;
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.)
> xR := b ; (This stores the current value of b in xR.)
Calculate the y values at the interval endpoints.
> yL := f(xL) ;
> yR := f(xR) ;
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)
> TOL := 0.5 * 10^(–6) ;
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
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 ) ;
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.
Return to the Bisection Assignment