{VERSION 4 0 "IBM INTEL NT" "4.0" }
{USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0
1 0 0 0 0 1 }{CSTYLE "2D Math" -1 2 "Times" 0 1 0 0 0 0 0 0 2 0 0 0 0
0 0 1 }{CSTYLE "2D Comment" 2 18 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }
{CSTYLE "" -1 256 "" 1 14 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1
257 "" 1 14 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 258 "" 1 14 0
0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 259 "" 1 14 0 0 0 0 0 1 0 0
0 0 0 0 0 1 }{CSTYLE "" -1 260 "" 1 14 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }
{CSTYLE "" -1 261 "" 1 14 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1
262 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 263 "" 0 1 0 0
0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 264 "" 1 14 0 0 0 0 0 1 0 0 0
0 0 0 0 1 }{CSTYLE "" -1 265 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 }
{PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0
0 0 1 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Heading 1" 0 3 1
{CSTYLE "" -1 -1 "" 1 18 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }1 0 0 0 6 6 0 0
0 0 0 0 -1 0 }{PSTYLE "Heading 2" 3 4 1 {CSTYLE "" -1 -1 "" 1 14 0 0
0 0 0 0 0 0 0 0 0 0 0 1 }0 0 0 -1 4 4 0 0 0 0 0 0 -1 0 }{PSTYLE "Title
" 0 18 1 {CSTYLE "" -1 -1 "" 1 18 0 0 0 0 0 1 1 0 0 0 0 0 0 1 }3 0 0
-1 12 12 0 0 0 0 0 0 19 0 }{PSTYLE "" 18 256 1 {CSTYLE "" -1 -1 "" 0
1 0 0 0 0 0 0 2 0 0 0 0 0 0 1 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }
{PSTYLE "" 4 257 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
1 }3 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 4 258 1 {CSTYLE "" -1
-1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }3 0 0 -1 -1 -1 0 0 0 0 0 0 -1
0 }{PSTYLE "" 4 259 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0
0 1 }3 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 4 260 1 {CSTYLE ""
-1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }3 0 0 -1 -1 -1 0 0 0 0 0 0
-1 0 }{PSTYLE "" 4 261 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0
0 0 0 1 }3 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 4 262 1 {CSTYLE "
" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }3 0 0 -1 -1 -1 0 0 0 0 0
0 -1 0 }{PSTYLE "" 0 263 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 1 0 0 0
0 0 0 0 1 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 264 1
{CSTYLE "" -1 -1 "" 1 14 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }0 0 0 -1 -1 -1
0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 265 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0
0 0 1 0 0 0 0 0 0 1 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }}
{SECT 0 {PARA 256 "" 0 "" {TEXT -1 41 "Solving f(a) = b: The Method of
Bisection" }}{PARA 257 "" 0 "" {TEXT -1 9 "Jim Herod" }}{PARA 258 ""
0 "" {TEXT -1 22 "School of Mathematics " }}{PARA 259 "" 0 "" {TEXT
-1 12 "Georgia Tech" }}{PARA 260 "" 0 "" {TEXT -1 22 "Atlanta, Ga 3033
2 0160" }}{PARA 261 "" 0 "" {TEXT -1 3 "USA" }}{PARA 262 "" 0 ""
{TEXT -1 21 "herod@math.gatech.edu" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}
{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 256 12 "Backgrou
nd: " }{TEXT -1 1 " " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 263 ""
0 "" {TEXT -1 31 "The Intermediate Value Theorem." }}{PARA 0 "" 0 ""
{TEXT -1 183 "Suppose that f is continuous on the closed interval [a,b
], and f(a) f(b). If c is a number between f(a) and f(b), then there
is a number x in the interval (a, b) such that f(x) = c." }}{PARA 0 "
" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "
" {TEXT 257 27 "Explanation of the Problem:" }}{PARA 0 "" 0 "" {TEXT
-1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 55 "Consider the graph of tan(x) on
the interval [-2,, 2]. " }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 50 "
plot(tan(x),x=-2*Pi..2*Pi,y=-10..10,discont=true);" }}}{PARA 0 "" 0 "
" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 237 " It is clear from t
his graph that there is an infinity of numbers x such that tan(x) + x \+
= 0. Three of them are visible in this graph. As an aid for approximat
ing the values for such x's, we superimpose the graph of tan(x) and of
- x." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 55 "plot(\{tan(x),-x\},
x=-2*Pi..2*Pi,y=-10..10,discont=true);" }}}{PARA 0 "" 0 "" {TEXT -1 0
"" }}{PARA 0 "" 0 "" {TEXT -1 65 " We wish to know the first posit
ive x such that tan(x) = - x." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}
{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 258 27 "Illustra
tion of the Method:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "
" {TEXT -1 306 " We define a function f for which we will find a z
ero. In this case, we take f(x) to be tan(x) + x. Thus, we seek x so t
hat f(x) = 0. From looking at the previous graph, we see that a zero o
f this function should lie between 1.8 and 2.2. In fact, here is a gra
ph of this f over the interval [1.8, 2.2]." }}{EXCHG {PARA 0 "> " 0 "
" {MPLTEXT 1 0 15 "f:=x->tan(x)+x;" }}}{EXCHG {PARA 0 "> " 0 ""
{MPLTEXT 1 0 43 "plot(f(x),x=1.8..2.2,y=-5..5,discont=true);" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{PARA 0 "" 0 "" {TEXT
-1 1 " " }}{PARA 0 "" 0 "" {TEXT -1 223 " When setting an upper and
lower bound for the zero of f, it is a good idea to draw a graph over
that interval as we just did above. Such a graph can serve as a check
that there is a zero in the interval we have chosen. " }}{PARA 0 ""
0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 181 " We now make a \+
routine for which we can input the left end point, the right endpoint,
and error tolerance for the accuracy we allow. The scheme will determ
ine if the values of f" }}{PARA 0 "" 0 "" {TEXT -1 74 " \+
at a and at " }
{XPPEDIT 18 0 "(a+b)/2" "6#*&,&%\"aG\"\"\"%\"bGF&F&\"\"#!\"\"" }{TEXT
-1 1 " " }}{PARA 0 "" 0 "" {TEXT -1 334 "have opposite signs. If they \+
do, a new interval is made from a to this midpoint. If not, a new inte
rval is made from this midpoint to b. In either case, according to the
Intermediate Value Theorem, a zero for f will lie in the new interval
. We continue this process until the endpoints of the intervals are wi
thin the error tolerance." }}{PARA 0 "" 0 "" {TEXT -1 146 " The sc
heme is built as a procedure with input the function f, the left and r
ight endpoints for the initial interval, and the error tolerance." }}
{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0
199 "bisect:=proc(f,left,right, err)\n\011local mid,a,b;\n\011a:=left;
\n\011b:=right;\n\011while b - a > 2*err do\n\011\011mid:=(a+b)/2:\n
\011\011if evalf(f(a)*f(mid)) < 0 then\n\011\011\011b:=mid\n\011\011el
se\n\011\011\011a:=mid\n\011\011fi;\n\011od;\n\011RETURN(mid);\n\011en
d:" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 56 " \+
Here are the choices for the input in this example." }}{EXCHG
{PARA 0 "> " 0 "" {MPLTEXT 1 0 35 "left:=1.7; right:=5/2; err:=0.0007;
" }}}{PARA 0 "" 0 "" {TEXT -1 1 " " }}{PARA 0 "" 0 "" {TEXT -1 99 " \+
We call the routine and expect as output an approximation for x whic
h satisfies tan(x) = - x. " }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0
31 "ans:=bisect(f,left,right,err); " }}}{PARA 0 "" 0 "" {TEXT -1 0 ""
}}{PARA 0 "" 0 "" {TEXT -1 57 " It seems appropriate to see how cl
ose the answer is." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "evalf(
f(ans));" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{PARA 0 ""
0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 259 27 "Exercise 1 for the
reader:" }}{PARA 0 "" 0 "" {TEXT -1 56 "Find the second positive numb
er x such that tan(x) = -x." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA
264 "" 0 "" {TEXT -1 20 "Rate of convergence:" }}{PARA 0 "" 0 ""
{TEXT -1 171 "If we consider the most recently computed midpoint as an
approximation of the root, one may say that the approximation error i
s halved at each besection iteration. Because" }}{PARA 0 "" 0 ""
{TEXT -1 16 " " }{XPPEDIT 18 0 "1/2^4" "6#*&\"\"\"F$*$
\"\"#\"\"%!\"\"" }{TEXT -1 5 " < " }{XPPEDIT 18 0 "1/10" "6#*&\"\"\"
F$\"#5!\"\"" }{TEXT -1 4 " < " }{XPPEDIT 18 0 "1/2^3" "6#*&\"\"\"F$*$
\"\"#\"\"$!\"\"" }{TEXT -1 1 "," }}{PARA 0 "" 0 "" {TEXT -1 91 "we mig
ht say that one significant decimal place in three or four interations
is determined." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 ""
{TEXT 260 21 "Pathological Example:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }
}{PARA 265 "" 0 "" {TEXT -1 11 "Pathology 1" }}{PARA 0 "" 0 "" {TEXT
-1 389 "The method of bisection is but one of a collection of methods \+
for finding zeros of a function -- that is, for finding solutions x fo
r an equation of the form f(x) = 0. In the above illustration, if f(x)
= tan(x) + x, then we found zeros for the equation f(x) = 0. This me
thod does not work if a zero is a local maximum or minimum for the fun
ction f. For example, consider solutions x for " }{XPPEDIT 18 0 "exp(2
*x)=3*x+3/2*(1-ln(3/2)" "6#/-%$expG6#*&\"\"#\"\"\"%\"xGF),&*&\"\"$F)F*
F)F)*(F-F)F(!\"\",&F)F)-%#lnG6#*&F-F)F(F/F/F)F)" }{TEXT -1 111 ". A lo
ok at the following graph suggests why this method will not work for f
inding solutions for this equation." }}{EXCHG {PARA 0 "> " 0 ""
{MPLTEXT 1 0 42 "plot(exp(2*x)-3*x-3/2*(1-ln(3/2)),x=0..1);" }}}{PARA
0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 265 12 "Pathology 2."
}{TEXT -1 1 " " }}{PARA 0 "" 0 "" {TEXT -1 171 "The method of bisectio
n can fail to work if the function is not continuous within the interv
al of the initial guess. For example, Check tan(x) + x at x = 1, and a
t x = 2. " }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 58 "evalf(subs(x=1,
tan(x) + x)); \nevalf(subs(x=2,tan(x) + x));" }}}{PARA 0 "" 0 ""
{TEXT -1 147 "The naive, unsuspecting pupil will think there should be
a number x between one and two for which tan(x) + x = 0. The student \+
knows this is not so." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0
"" {TEXT 264 27 "Exercise 2 for the reader:" }}{PARA 0 "" 0 "" {TEXT
-1 53 "Draw the graph of tan(x) + x on the interval [ 1, 2]." }}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "
" {MPLTEXT 1 0 0 "" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "
" {TEXT 261 19 "Reference Material:" }}{PARA 0 "" 0 "" {TEXT -1 87 "(1
) A statement of the Intermediate-Value Theorem is on page 119 of Stan
ley Grossman's " }{TEXT 262 8 "Calculus" }{TEXT -1 17 " (Fifth Edition
)." }}{PARA 0 "" 0 "" {TEXT -1 64 "(2) A proof of the Intermediate-Val
ue Theorem is on page 153 on " }{TEXT 263 29 "The Elements of Real Ana
lysis" }{TEXT -1 62 " (Second Edition), Robert G. Bartle, John WIley &
Sons (1976)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{MARK "0 0" 0 }
{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }