{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 "2D Output" 2 20 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 256 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 257 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 258 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 259 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 260 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 } {PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }1 1 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Heading 1" -1 3 1 {CSTYLE "" -1 -1 "Times" 1 18 0 0 0 1 2 1 2 2 2 2 1 1 1 1 }1 1 0 0 8 4 1 0 1 0 2 2 0 1 }{PSTYLE "Maple Output" -1 11 1 {CSTYLE "" -1 -1 "Ti mes" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }3 3 0 0 0 0 1 0 1 0 2 2 0 1 } {PSTYLE "Maple Plot" -1 13 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }3 1 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Title" -1 18 1 {CSTYLE "" -1 -1 "Times" 1 18 0 0 0 1 2 1 1 2 2 2 1 1 1 1 }3 1 0 0 12 12 1 0 1 0 2 2 19 1 }{PSTYLE "Heading 2" -1 256 1 {CSTYLE "" -1 -1 "Times" 1 14 0 0 0 1 2 1 2 2 2 2 1 1 1 1 }3 1 0 0 8 2 1 0 1 0 2 2 0 1 }} {SECT 0 {EXCHG {PARA 18 "" 0 "" {TEXT -1 10 "Calculus I" }}{PARA 256 " " 0 "" {TEXT -1 76 "Lesson 22: Solving Equations Numerically with Bis ection and Newton's Method" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 106 "In this worksheet, we will investigate m ethods for finding approximate solutions to equations of the form " } {XPPEDIT 18 0 "f(x) = 0;" "6#/-%\"fG6#%\"xG\"\"!" }{TEXT -1 43 " . We will look at two important methods: " }{TEXT 257 19 "repeated bisecti on," }{TEXT -1 103 " which is based on the Intermediate Value Theorem, and a method based on linear approximation known as " }{TEXT 256 16 " Newton's method." }}}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 18 "Repeated Bis ection" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 87 "The idea behind the repe ated bisection method is very simple: if a continuous function " } {XPPEDIT 18 0 "f;" "6#%\"fG" }{TEXT -1 147 " is negative somewhere and positive somewhere else, it must have a zero in between. The traditi onal first example of the method is to approximate " }{XPPEDIT 18 0 "s qrt(2);" "6#-%%sqrtG6#\"\"#" }{TEXT -1 25 " by solving the equation " }{XPPEDIT 18 0 "x^2-2 = 0;" "6#/,&*$%\"xG\"\"#\"\"\"F'!\"\"\"\"!" } {TEXT -1 2 " ." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "restart;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "f := x -> x^2 - 2;" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"fGR6#%\"xG6\"6$%)operatorG%&arrowG F(,&*$)9$\"\"#\"\"\"F1F0!\"\"F(F(F(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "plot(f, 0..4);" }}{PARA 13 "" 1 "" {GLPLOT2D 400 300 300 {PLOTDATA 2 "6%-%'CURVESG6$7S7$$\"\"!F)$!\"#F)7$$\"3Hmmmm;')=()!#> $!37`P7X\")R#*>!#<7$$\"3RLLLe'40j\"!#=$!3E<3a#Q9M(>F27$$\"3mmmm;6m$[#F 6$!3\"3evXF9$Q>F27$$\"3fmmm;yYULF6$!3ova%*)3z#))=F27$$\"3%HLL$eF>(>%F6 $!3CUR\\Hd$Q#=F27$$\"3Qmmm\">K'*)\\F6$!31P)=fqN5v\"F27$$\"3P*****\\Kd, \"eF6$!3k)[(e=2Ui;F27$$\"3-mmm\"fX(emF6$!3a(fa926mb\"F27$$\"3.*****\\U 7Y](F6$!3Nc`]Bz!oV\"F27$$\"3'QLLLV!pu$)F6$!3S^$e9gX')H\"F27$$\"3xmmm;c 0T\"*F6$!3'y1I@-6W;\"F27$$\"3#*******H,Q+5F2$!3UK=,bfR#***F67$$\"3)*** ****\\*3q3\"F2$!3eu*)>Ea6%=)F67$$\"3)*******p=\\q6F2$!3gJ!RE#y[*H'F67$ $\"3mmm;fBIY7F2$!3Q4gN&H/tY%F67$$\"3GLLLj$[kL\"F2$!3/[lV@x0R@F67$$\"3? LLL`Q\"GT\"F2$!35v)=%He,dR!#?7$$\"3!*****\\s]k,:F2$\"3%3INwBz$\\DF67$$ \"39LLL`dF!e\"F2$\"3iMBtlXrs\\F67$$\"33++]sgam;F2$\"3sc9iq$z0\"F27$$\"3QLLLe/TM=F2$\"355FkH<1l8F27$$\"3 JLL$eDBJ\">F2$\"3gL.,#fS+m\"F27$$\"3immmTc-)*>F2$\"3'[\\dZY1@*>F27$$\" 3Mmm;f`@'3#F2$\"3-.H#[_%H_BF27$$\"3y****\\nZ)H;#F2$\"3)z-PW5.&yEF27$$ \"3YmmmJy*eC#F2$\"3DM]Gqq0WIF27$$\"3')******R^bJBF2$\"3;>/'3P\\hV$F27$ $\"3f*****\\5a`T#F2$\"3i[.a_a$R$QF27$$\"3o****\\7RV'\\#F2$\"3)e0![zA=K UF27$$\"3k*****\\@fke#F2$\"3E9%e3Fr(*o%F27$$\"3/LLL`4NnEF2$\"3ES#[#36w 9^F27$$\"3#*******\\,s`FF2$\"3'=-;XmuHe&F27$$\"3[mm;zM)>$GF2$\"3$p$HFE /8?gF27$$\"3$*******pfa&R,)F27$$\"3#)****\\7yh]KF2$\"3o$GUH;;lc)F27$$\"3xmmm')fdLLF2$\"35 S1))e)GF6*F27$$\"3bmmm,FT=MF2$\"3I)*f\"*)RXbo*F27$$\"3FLL$e#pa-NF2$\"3 S`kw'\\$yE5!#;7$$\"3!*******Rv&)zNF2$\"3-&[p1+Q:3\"F\\y7$$\"3ILLLGUYoO F2$\"3!y7c%zHwX6F\\y7$$\"3_mmm1^rZPF2$\"3OaP2_o`/7F\\y7$$\"34++]sI@KQF 2$\"37*)RI.deo7F\\y7$$\"34++]2%)38RF2$\"3h)3\"\\)3E7L\"F\\y7$$\"\"%F)$ \"#9F)-%'COLOURG6&%$RGBG$\"#5!\"\"F(F(-%+AXESLABELSG6$Q!6\"Fe[l-%%VIEW G6$;F(Fgz%(DEFAULTG" 1 2 0 1 10 0 2 9 1 4 2 1.000000 45.000000 45.000000 0 0 "Curve 1" }}}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 37 "It see ms clear from the picture that " }{XPPEDIT 18 0 "f;" "6#%\"fG" }{TEXT -1 88 " has a zero somewhere in the interval (1,2). We can quickly co nfirm this by evaluating " }{XPPEDIT 18 0 "f;" "6#%\"fG" }{TEXT -1 21 " at these two points:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "f (1); f(2);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#!\"\"" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#\"\"#" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 221 "The fu nction changes sign on the interval [1,2]; since it is a polynomial, a nd therefore continuous, it must have a zero in the open interval (1,2 ). We can obviously locate this zero more accurately by testing value s of " }{XPPEDIT 18 0 "f;" "6#%\"fG" }{TEXT -1 302 " at the endpoints \+ of shorter intervals, but the trick is to do this in the most efficien t manner possible. It turns out that it is not possible, in general, \+ to do any better than halving the length of the interval at each stage , so we bisect the interval in which we have found the zero, and evalu ate " }{XPPEDIT 18 0 "f;" "6#%\"fG" }{TEXT -1 269 " at the midpoint. \+ Since there was a sign-change over the whole interval, there must be o ne over one of the half-intervals, and we have the zero located in a s horter interval than before. We can repeat this process as often as n ecesary to obtain the required accuracy." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "m1 := (1 +2)/2; f(m1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#m1G#\"\"$\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6##\"\"\"\"\" %" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 58 "The sign change is between 1 and 3/2, so we know that 1 < " }{XPPEDIT 18 0 "sqrt(2);" "6#-%%sqrtG6 #\"\"#" }{TEXT -1 76 " < 1.5 . We now repeat the procedure, starting \+ withe the interval [1, 3/2]." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "m2 := (1 + m1)/2; f(m2);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#m 2G#\"\"&\"\"%" }}{PARA 11 "" 1 "" {XPPMATH 20 "6##!\"(\"#;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "m3 := (m2 + m1)/2; f(m3);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#m3G#\"#6\"\")" }}{PARA 11 "" 1 "" {XPPMATH 20 "6##!\"(\"#k" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "m4 := (m3 + m1)/2; f(m4);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#m4G# \"#B\"#;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6##\"#<\"$c#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "evalf([m3,m4]);" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#7$$\"++++v8!\"*$\"+++]P9F&" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "m5 := (m3 + m4)/2; f(m5);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#m5G#\"#X\"#K" }}{PARA 11 "" 1 "" {XPPMATH 20 "6##!#B \"%C5" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "m6 := (m5 + m4)/2; f(m6);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#m6G#\"#\"*\"#k" }}{PARA 11 "" 1 "" {XPPMATH 20 "6##\"#*)\"%'4%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "evalf([m5,m6]);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7$ $\"+++D19!\"*$\"++](=U\"F&" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 6 "Sinc e " }{XPPEDIT 18 0 "f;" "6#%\"fG" }{TEXT -1 76 " changes sign on the i nterval [m5, m6], and is continuous, we now know that " }{XPPEDIT 18 0 "sqrt(2);" "6#-%%sqrtG6#\"\"#" }{TEXT -1 32 " = 1.4 to 2 significant figures." }}{PARA 0 "" 0 "" {TEXT -1 129 "(Guaranteed!) It may seem \+ as though we have done a lot of work for a small result, but you migh t remember the following points:" }}{PARA 0 "" 0 "" {TEXT -1 108 " 1) We are illustrating a very general method, which can be used to solv e much more complicated equations." }}{PARA 0 "" 0 "" {TEXT -1 70 " 2 ) In principle, the method can be used to get any desired accuracy." } }{PARA 0 "" 0 "" {TEXT -1 39 " 3) Most importantly, the accuracy is \+ " }{TEXT 258 11 "guaranteed:" }{TEXT -1 148 " we not only get an appro ximation to the zero, but we get upper and lower bounds. That is, the zero is guaranteed to lie within a certain interval." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 287 "You should also obser ve that the method is highly repetitious, and is therefore a good cand idate for programming. Here is a crude implementation, which takes a \+ function and an initial interval, checks to see whether the function c hanges sign on the interval, and then iterates 10 times." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 40 "bisect10 := proc(f,a,b) local a1,b1 ,m,j:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 45 " if (evalf(f( a)*f(b)) >= 0) then" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 60 " \+ RETURN(`No sign change detected on ` (a,b)):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 18 " else" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 33 " a1 := a: b1 := b:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 37 " for j from 1 to 10 do" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 35 " m := (a1 + b1)/2:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 51 " if (f(a1)*f(m) < 0) then b1 := m:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 31 " else a1 := m:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 21 " fi:" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 " od:" }}{PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 17 " fi:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 78 " print(`There is a zero in ` (evalf(a1), evalf(b1)) ): " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 16 " \+ end:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "bisect10(f,2, 3);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-% " 0 "" {MPLTEXT 1 0 16 "bisect10(f, 1,2);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%4There~is~a~zero~in~G6$$\"+ +D199!\"*$\"+i!R]T\"F(" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 32 "Can you explain the next result?" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "bisect10(sin,-1,4);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-% " 0 "" {MPLTEXT 1 0 0 "" }}}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}} {SECT 0 {PARA 3 "" 0 "" {TEXT -1 15 "Newton's Method" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "restart;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 235 "Despite the advantages of repeated bisection listed towards th e end of the last section, it can be slow if you need a highly accurat e approximation, especially if you are doing the computations by hand. If we assume that our function " }{XPPEDIT 18 0 "f;" "6#%\"fG" } {TEXT -1 195 " is not only continuous, but differentiable, we can use \+ the idea of linear approximation: as you can see from the picture bel ow, if we have somehow managed to find an approximation to a zero of \+ " }{XPPEDIT 18 0 "f;" "6#%\"fG" }{TEXT -1 62 ", the intersection of th e tangent line at that point with the " }{XPPEDIT 18 0 "x;" "6#%\"xG" }{TEXT -1 102 "-axis might be expected to be a better approximation. \+ (In the picture, the original approximation is " }{XPPEDIT 18 0 "x = 1 ;" "6#/%\"xG\"\"\"" }{TEXT -1 2 ".)" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "f := x -> x^2 - 2;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6 #>%\"fGR6#%\"xG6\"6$%)operatorG%&arrowGF(,&*$)9$\"\"#\"\"\"F1F0!\"\"F( F(F(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "x0 := 1;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#x0G\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 35 "t1 := x -> f(x0) + D(f)(x0)*(x-x0);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#t1GR6#%\"xG6\"6$%)operatorG%&arrowGF(,&-%\"fG6#%# x0G\"\"\"*&--%\"DG6#F.F/F1,&9$F1F0!\"\"F1F1F(F(F(" }}}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 19 "plot(\{f,t1\}, 0..3);" }}{PARA 13 "" 1 "" {GLPLOT2D 400 300 300 {PLOTDATA 2 "6&-%'CURVESG6$7S7$$\"\"!F)$!\"#F)7$ $\"3s******\\i9Rl!#>$!3+6@jcRs&*>!#<7$$\"3/++vVA)GA\"!#=$!3o4#z,fX])>F 27$$\"3+++]Peui=F6$!3;k([%zF27$$\"3A++]i3&o]#F6$!3'*H=`()p:P>F27$$ \"3%)***\\(oX*y9$F6$!3ZU.%yf24!>F27$$\"3z***\\P9CAu$F6$!3!fMzXed*f=F27 $$\"3!)***\\P*zhdVF6$!3Fia?a;65=F27$$\"31++v$>fS*\\F6$!356KpFPf]\")*H:F27$$\"3`+++v4&G](F6$!3Q:%pCFsqV\"F27 $$\"3!)*****\\7nD:)F6$!3]#pBF\\c`L\"F27$$\"3[+++D!*oy()F6$!3ZXM-!>Y$H7 F27$$\"3))***\\PpnsM*F6$!3hvPhmeGE6F27$$\"3,++]siL-5F2$!3+e!3$o*>K&**F 67$$\"3-+++!R5'f5F2$!37y//9#eAx)F67$$\"3)***\\P/QBE6F2$!3XU,$)yT(fJ(F6 7$$\"3!******\\\"o?&=\"F2$!3Gfbxc![G&fF67$$\"31+]Pa&4*\\7F2$!37()3#)e5 ExVF67$$\"33+]7j=_68F2$!3m'G^a-/\"*z#F67$$\"33++vVy!eP\"F2$!3e_(f2xF:2 \"F67$$\"34+](=WU[V\"F2$\"35/8e+LGxeF/7$$\"3)****\\7B>&)\\\"F2$\"3M34E k))fbCF67$$\"3)***\\P>:mk:F2$\"3QL)G@qc;[%F67$$\"3'***\\iv&QAi\"F2$\"3 M'GeC'*zlJ'F67$$\"31++vtLU%o\"F2$\"3mALN?5#GP)F67$$\"3!******\\Nm'[F2$\"3)*ey&)Rj*Hw\"F27$$\" 3z*****\\@80+#F2$\"3[N'*QBJ0-?F27$$\"31++]7,Hl?F2$\"3Cj-z[KUlAF27$$\"3 ()**\\P4w)R7#F2$\"3OF&yZOB8^#F27$$\"3;++]x%f\")=#F2$\"3atI(*)*=/)y#F27 $$\"3!)**\\P/-a[AF2$\"3#ew!p]I$f0$F27$$\"3/+](=Yb;J#F2$\"3\"*>lTu4vVLF 27$$\"3')****\\i@OtBF2$\"3TvmQaz%Gj$F27$$\"3')**\\PfL'zV#F2$\"38N]lT`m VRF27$$\"3>+++!*>=+DF2$\"3=h.7$)*44D%F27$$\"3-++DE&4Qc#F2$\"3]\\-*oG>J d%F27$$\"3=+]P%>5pi#F2$\"3!3I6$prl+\\F27$$\"39+++bJ*[o#F2$\"39bew`7l3_ F27$$\"33++Dr\"[8v#F2$\"3=?2Wfn\"*pbF27$$\"3++++Ijy5GF2$\"3%*o[\"Hz>0! fF27$$\"31+]P/)fT(GF2$\"3-R\\3\"e%zgiF27$$\"31+]i0j\"[$HF2$\"3KtBwZn98 mF27$$\"\"$F)$\"\"(F)-%'COLOURG6&%$RGBG$\"#5!\"\"F(F(-F$6$7S7$F)$!\"$F )7$$\"+]i9Rl!#6$!+vq@pG!\"*7$$\"+WA)GA\"!#5$!+^NUbFF\\\\l7$$\"+Qeui=F` \\l$!+K3XFEF\\\\l7$$\"+i3&o]#F`\\l$!+G)H')\\#F\\\\l7$$\"+pX*y9$F`\\l$! +'3@/P#F\\\\l7$$\"+WTAUPF`\\l$!+r^b^AF\\\\l7$$\"+%*zhdVF`\\l$!+,kZG@F \\\\l7$$\"+%>fS*\\F`\\l$!+h\")=,?F\\\\l7$$\"+>$f%GcF`\\l$!+O\"3V(=F\\ \\l7$$\"+Dy,\"G'F`\\l$!+NkzViUC\"F\\\\l7$$\"+%pnsM*F`\\l$!+hkaI6F\\\\l7$$\"+siL-5 F\\\\l$!*cuK&**F\\\\l7$$\"+!R5'f5F\\\\l$!*?#z2))F\\\\l7$$\"+/QBE6F\\\\ l$!*#RKvuF\\\\l7$$\"+:o?&=\"F\\\\l$!*qjeH'F\\\\l7$$\"+a&4*\\7F\\\\l$!* #*3=+&F\\\\l7$$\"+j=_68F\\\\l$!*ui&pPF\\\\l7$$\"+Wy!eP\"F\\\\l$!*7VQ[# F\\\\l7$$\"+UC%[V\"F\\\\l$!*;^JI\"F\\\\l7$$\"+J#>&)\\\"F\\\\l$!(Q:'HF \\\\l7$$\"+>:mk:F\\\\l$\"*QIKH\"F\\\\l7$$\"+w&QAi\"F\\\\l$\"*_rZW#F\\ \\l7$$\"+uLU%o\"F\\\\l$\"*[n%)o$F\\\\l7$$\"+bjm[F\\\\l$\"*A))oz)F\\\\l7$$\"+:K^+?F\\\\l$\"+Ik-,5F\\\\l7$$\"+7,H l?F\\\\l$\"+C-eI6F\\\\l7$$\"+4w)R7#F\\\\l$\"+=_(zC\"F\\\\l7$$\"+y%f\") =#F\\\\l$\"+c*=jP\"F\\\\l7$$\"+/-a[AF\\\\l$\"+3/3(\\\"F\\\\l7$$\"+ial6 BF\\\\l$\"+C4JB;F\\\\l7$$\"+i@OtBF\\\\l$\"+CVsY=+DF\\\\l$\"+!)RO+?F\\\\l7$$\"+E&4Qc#F\\\\ l$\"+_!>w7#F\\\\l7$$\"+%>5pi#F\\\\l$\"+)Q?QD#F\\\\l7$$\"+bJ*[o#F\\\\l$ \"+5jypBF\\\\l7$$\"+r\"[8v#F\\\\l$\"+Ujp-DF\\\\l7$$\"+Ijy5GF\\\\l$\"+g Ed@EF\\\\l7$$\"+/)fT(GF\\\\l$\"+3'>$[FF\\\\l7$$\"+1j\"[$HF\\\\l$\"+7Ej pGF\\\\l7$FfzFez-Fjz6&F\\[lF(F][lF(-%+AXESLABELSG6$Q!6\"Fjjl-%%VIEWG6$ ;F(Fez%(DEFAULTG" 1 2 0 1 10 0 2 9 1 4 2 1.000000 45.000000 45.000000 0 0 "Curve 1" "Curve 2" }}}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 70 "Now, o f course, we repeat: we find where the tangent line crosses the " } {XPPEDIT 18 0 "x;" "6#%\"xG" }{TEXT -1 111 "-axis. This is our new ap proximation to the zero, so we find the tangent line at this new point and see where " }{TEXT 259 2 "it" }{TEXT -1 118 " crosses the axis. \+ Hopefully, by repeating the procedure as often as necessary, we can ob tain any accuracy we desire." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "x1 := solve(t1(x) = 0, x);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>% #x1G#\"\"$\"\"#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 35 "t2 := x \+ -> f(x1) + D(f)(x1)*(x-x1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#t2GR 6#%\"xG6\"6$%)operatorG%&arrowGF(,&-%\"fG6#%#x1G\"\"\"*&--%\"DG6#F.F/F 1,&9$F1F0!\"\"F1F1F(F(F(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "plot(\{f,t2\}, 0..3);" }}{PARA 13 "" 1 "" {GLPLOT2D 400 300 300 {PLOTDATA 2 "6&-%'CURVESG6$7S7$\"\"!$!++++]U!\"*7$$\"+]i9Rl!#6$!+9c#Q0 %F+7$$\"+WA)GA\"!#5$!+G`8$)QF+7$$\"+Qeui=F5$!+[i<\"p$F+7$$\"+i3&o]#F5$ !+UZ%z\\$F+7$$\"+pX*y9$F5$!+H;j0LF+7$$\"+WTAUPF5$!+eFLFJF+7$$\"+%*zhdV F5$!+.YrUHF+7$$\"+%>fS*\\F5$!+VAy^FF+7$$\"+>$f%GcF5$!+/AYhDF+7$$\"+Dy, \"G'F5$!+_YplBF+7$$\"+7#F+7$$\"+v4&G](F5$!+3Z9**>F+7$$\" +Drc_\")F5$!+i)HU!=F+7$$\"+D!*oy()F5$!+#H$R;;F+7$$\"+%pnsM*F5$!+#p>eW \"F+7$$\"+siL-5F+$!+%=\"*HC\"F+7$$\"+!R5'f5F+$!+I)o62\"F+7$$\"+/QBE6F+ $!+!)e)Hr)F57$$\"+:o?&=\"F+$!+]bzVpF57$$\"+a&4*\\7F+$!+!Q8F+&F57$$\"+j =_68F+$!+5TMaJF57$$\"+Wy!eP\"F+$!+!okdA\"F57$$\"+UC%[V\"F+$\"*gKFX&F57 $$\"+J#>&)\\\"F+$\"+IpdbCF57$$\"+>:mk:F+$\"+qb%)RWF57$$\"+w&QAi\"F+$\" +!Gdr;'F57$$\"+uLU%o\"F+$\"+?7qK!)F57$$\"+bjm[F+$\"+LK`p:F+7 $$\"+:K^+?F+$\"+X'R:v\"F+7$$\"+7,Hl?F+$\"+O.(e%>F+7$$\"+4w)R7#F+$\"+FG '>7#F+7$$\"+y%f\")=#F+$\"+M%yWJ#F+7$$\"+/-a[AF+$\"+71i&\\#F+7$$\"+ial6 BF+$\"+'Qm\\o#F+7$$\"+i@OtBF+$\"+'['3qGF+7$$\"+fL'zV#F+$\"+x+*Q1$F+7$$ \"+!*>=+DF+$\"+qfa]KF+7$$\"+E&4Qc#F+$\"+y&G9W$F+7$$\"+%>5pi#F+$\"+#eI2 j$F+7$$\"+bJ*[o#F+$\"+l%zY!QF+7$$\"+r\"[8v#F+$\"+8X//SF+7$$\"+Ijy5GF+$ \"+!**eB=%F+7$$\"+/)fT(GF+$\"+7%zCP%F+7$$\"+1j\"[$HF+$\"+=*[Wb%F+7$\" \"$$\"++++]ZF+-%'COLOURG6&%$RGBG$\"#5!\"\"$F(F(F^[l-F$6$7S7$F^[l$!\"#F (7$$\"3s******\\i9Rl!#>$!3+6@jcRs&*>!#<7$$\"3/++vVA)GA\"!#=$!3o4#z,fX] )>F[\\l7$$\"3+++]Peui=F_\\l$!3;k([%zF[\\l7$$\"3A++]i3&o]#F_\\l$!3' *H=`()p:P>F[\\l7$$\"3%)***\\(oX*y9$F_\\l$!3ZU.%yf24!>F[\\l7$$\"3z***\\ P9CAu$F_\\l$!3!fMzXed*f=F[\\l7$$\"3!)***\\P*zhdVF_\\l$!3Fia?a;65=F[\\l 7$$\"31++v$>fS*\\F_\\l$!356KpFPf]\")*H:F[\\l7$$\"3`+++v4&G](F_\\l$!3Q:%pCFsqV\"F[\\l7$$\" 3!)*****\\7nD:)F_\\l$!3]#pBF\\c`L\"F[\\l7$$\"3[+++D!*oy()F_\\l$!3ZXM-! >Y$H7F[\\l7$$\"3))***\\PpnsM*F_\\l$!3hvPhmeGE6F[\\l7$$\"3,++]siL-5F[\\ l$!3+e!3$o*>K&**F_\\l7$$\"3-+++!R5'f5F[\\l$!37y//9#eAx)F_\\l7$$\"3)*** \\P/QBE6F[\\l$!3XU,$)yT(fJ(F_\\l7$$\"3!******\\\"o?&=\"F[\\l$!3Gfbxc![ G&fF_\\l7$$\"31+]Pa&4*\\7F[\\l$!37()3#)e5ExVF_\\l7$$\"33+]7j=_68F[\\l$ !3m'G^a-/\"*z#F_\\l7$$\"33++vVy!eP\"F[\\l$!3e_(f2xF:2\"F_\\l7$$\"34+]( =WU[V\"F[\\l$\"35/8e+LGxeFh[l7$$\"3)****\\7B>&)\\\"F[\\l$\"3M34Ek))fbC F_\\l7$$\"3)***\\P>:mk:F[\\l$\"3QL)G@qc;[%F_\\l7$$\"3'***\\iv&QAi\"F[ \\l$\"3M'GeC'*zlJ'F_\\l7$$\"31++vtLU%o\"F[\\l$\"3mALN?5#GP)F_\\l7$$\"3 !******\\Nm'[F[\\l$\"3)*ey&)Rj*Hw\"F[\\l7$$\"3z*****\\@80+#F[\\l$\"3[N'*QBJ 0-?F[\\l7$$\"31++]7,Hl?F[\\l$\"3Cj-z[KUlAF[\\l7$$\"3()**\\P4w)R7#F[\\l $\"3OF&yZOB8^#F[\\l7$$\"3;++]x%f\")=#F[\\l$\"3atI(*)*=/)y#F[\\l7$$\"3! )**\\P/-a[AF[\\l$\"3#ew!p]I$f0$F[\\l7$$\"3/+](=Yb;J#F[\\l$\"3\"*>lTu4v VLF[\\l7$$\"3')****\\i@OtBF[\\l$\"3TvmQaz%Gj$F[\\l7$$\"3')**\\PfL'zV#F [\\l$\"38N]lT`mVRF[\\l7$$\"3>+++!*>=+DF[\\l$\"3=h.7$)*44D%F[\\l7$$\"3- ++DE&4Qc#F[\\l$\"3]\\-*oG>Jd%F[\\l7$$\"3=+]P%>5pi#F[\\l$\"3!3I6$prl+\\ F[\\l7$$\"39+++bJ*[o#F[\\l$\"39bew`7l3_F[\\l7$$\"33++Dr\"[8v#F[\\l$\"3 =?2Wfn\"*pbF[\\l7$$\"3++++Ijy5GF[\\l$\"3%*o[\"Hz>0!fF[\\l7$$\"31+]P/)f T(GF[\\l$\"3-R\\3\"e%zgiF[\\l7$$\"31+]i0j\"[$HF[\\l$\"3KtBwZn98mF[\\l7 $$FdzF($\"\"(F(-Fhz6&FjzF^[lF[[lF^[l-%+AXESLABELSG6$Q!6\"F\\[m-%%VIEWG 6$;F^[lFdjl%(DEFAULTG" 1 2 0 1 10 0 2 9 1 4 2 1.000000 45.000000 45.000000 0 0 "Curve 1" "Curve 2" }}}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 108 "Note that even after one iteration, we will need to zoom in to se e the difference between the true zero of " }{XPPEDIT 18 0 "f;" "6#% \"fG" }{TEXT -1 51 " and the intersection of the tangent line with the " }{XPPEDIT 18 0 "x;" "6#%\"xG" }{TEXT -1 6 "-axis." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 36 "x2 := solve(t2(x) = 0, x); evalf(%);" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%#x2G#\"#<\"#7" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#$\"+nmm;9!\"*" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 20 "R epeat if necessary:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 37 "t3 : = x -> f(x2) + D(f)(x2)*(x - x2);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#> %#t3GR6#%\"xG6\"6$%)operatorG%&arrowGF(,&-%\"fG6#%#x2G\"\"\"*&--%\"DG6 #F.F/F1,&9$F1F0!\"\"F1F1F(F(F(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 36 "x3 := solve(t3(x) = 0, x); evalf(%);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#x3G#\"$x&\"$3%" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#$ \"+'o:UT\"!\"*" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 25 "As a comparison , here is " }{TEXT 260 7 "Maple's" }{TEXT -1 15 " evaluation of " } {XPPEDIT 18 0 "sqrt(2);" "6#-%%sqrtG6#\"\"#" }{TEXT -1 16 " (to 10 dig its):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "evalf(sqrt(2));" } }{PARA 11 "" 1 "" {XPPMATH 20 "6#$\"+iN@99!\"*" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 127 "It is clear that Newton's method is extermely fast- --at least in this example. Can you think of any disadvantages it may have?" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{MARK "0 2 0" 0 }{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }