{VERSION 2 3 "DEC ALPHA UNIX" "2.3" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 1 0 0 0 0 }{CSTYLE "2D Math" -1 2 "Times" 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 }{CSTYLE "Hyperlink" -1 17 "" 0 1 0 128 128 1 0 0 1 0 0 0 0 0 0 } {CSTYLE "2D Comment" 2 18 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE " " -1 256 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" 18 257 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 258 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" 18 259 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 260 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Text Output" -1 2 1 {CSTYLE "" -1 -1 "Courier" 1 10 0 0 255 1 0 0 0 0 0 1 3 0 0 }1 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 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 }0 0 0 -1 4 4 0 0 0 0 0 0 -1 0 }{PSTYLE "Warning" 2 7 1 {CSTYLE "" -1 -1 "" 0 1 0 0 255 1 0 0 0 0 0 0 1 0 0 }0 0 0 -1 -1 -1 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 }3 0 0 -1 12 12 0 0 0 0 0 0 19 0 }} {SECT 0 {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 18 "" 0 "" {TEXT -1 23 " Lab #2: Newton's Method" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 28 "Updated: September \+ 10, 1999" }}{PARA 0 "" 0 "" {TEXT -1 29 "Author: Arthur C. Heinricher " }}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 12 "Introduction" }}{PARA 0 "" 0 "" {TEXT -1 170 "The purpose of this lab is to help you learn more abo ut Newton's method and some of the strange things that can happen when you are solving relatively simple equations. " }}{PARA 0 "" 0 "" {TEXT -1 1 " " }}{PARA 0 "" 0 "" {TEXT -1 242 "The following command i s sometimes useful. It simply tells Maple to forget any work done in \+ the past and start with a clean memory. Execute it when you start ne w work or when you are in the middle of some work and you have lost yo ur way. " }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "restart;" }}} {PARA 0 "" 0 "" {TEXT -1 186 "Many of the times that students (or calc ulus teachers) have problems with Maple, it is simply because Maple is using old variables and old assignments that the user has long forgot ten. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 13 "Basic Toolbox" }}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 16 "Newton's Method " }}{PARA 0 "" 0 "" {TEXT -1 51 "The method is used to solve equations of the form " } {XPPEDIT 18 0 "f(x)=0" "/-%\"fG6#%\"xG\"\"!" }{TEXT -1 173 ". It is a n iterative scheme that builds a sequence of approximations for the so lution. In a sense, the method is just an application for the defini tion of the derivative." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 29 "Start with the approximation " }{XPPEDIT 18 0 "D(f)( x0) = (f(x1)-f(x0))/(x1-x0)" "/--%\"DG6#%\"fG6#%#x0G*&,&-F'6#%#x1G\"\" \"-F'6#F)!\"\"F/,&F.F/F)F2F2" }{TEXT -1 16 " and solves fo " } {XPPEDIT 18 0 "x1" "I#x1G6\"" }{TEXT -1 34 ". The \"trick\" is to ass ume tahat " }{XPPEDIT 18 0 "x1" "I#x1G6\"" }{TEXT -1 44 " is the solut ion you are looking for and so " }{XPPEDIT 18 0 "f(x1) = 0" "/-%\"fG6# %#x1G\"\"!" }{TEXT -1 70 " (or it is at least close). This leads you to the recursive formula:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 11 " " }{XPPEDIT 18 0 "x[n+1] = x[n] - (f(x [n])/D(f)(x[n])" "/&%\"xG6#,&%\"nG\"\"\"\"\"\"F(,&&F$6#F'F(*&-%\"fG6#& F$6#F'F(--%\"DG6#F/6#&F$6#F'!\"\"F:" }{TEXT -1 2 ". " }}{PARA 0 "" 0 " " {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 112 "You now have a simple \+ way to build a sequence that (you hope) will converge to the solution \+ (or a solution) for " }{XPPEDIT 18 0 "f(x) = 0" "/-%\"fG6#%\"xG\"\"!" }{TEXT -1 1 "." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 0 7 "Remark:" }{TEXT -1 193 " In the work below, note the use t he arrow notation for functions (instead of the simple expression appr oach from the first two labs). Notice also that the command for diffe rentiation is not " }{HYPERLNK 17 "diff" 2 "diff" "" }{TEXT -1 28 ", i s is a plain old capitol " }{HYPERLNK 17 "D" 2 "D" "" }{TEXT -1 79 " . This keeps everything a function and so you can evaluate without usi ng the " }{HYPERLNK 17 "subs" 2 "subs" "" }{TEXT -1 10 " command. " }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 258 10 "Example# 1:" }{TEXT -1 135 " Approximate the square root of 2 using Newton's m ethod. Just define the function, compute the derivative, and then sta rt iterating. " }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "f := x-> x ^2-2;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "df := x -> D(f)(x) ;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "x0 := 3;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "x1 := x0 - f(x0)/df(x0);" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "evalf(\");" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "x2 := x1 - f(x1)/df(x1);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "evalf(\");" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "x3 := x2 - f(x2)/df(x2);" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 9 "evalf(\");" }}}{PARA 0 "" 0 "" {TEXT -1 115 "If you want to compute a different square root, what would you change? \+ Try it and re-execute the commands above. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 246 "You could keep going this way, cutting and pasting, and build an even better solution. But cutting a nd pasting gets boring, so automate it. The following block of code w ill do five steps of Newton's method for approximating the square root of 2." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "x[0] := 1.5;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "f := x-> x^2-2 ;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "d f := x-> D(f)(x);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 76 "for n \+ from 0 to 5 do \n x[n+1] := evalf(x[n] - f(x[n])/df(x[n]),30);\n o d;" }}}{PARA 0 "" 0 "" {TEXT -1 173 "Does the method really double the number of correct digits with each iteration? Note that you can \"ch eck\" the answer by asking Maple for 30 digits of the square root of 2 : " }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "evalf(sqrt(2),30);" }} }{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 98 "Now you \+ can use this same set of commands to run Newton's method for any funct ion. Just redefine " }{XPPEDIT 18 0 "f(x)" "-%\"fG6#%\"xG" }{TEXT -1 37 ", choose an starting point, and go. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 50 "Domains of Attraction: Where Does Newton Converge?" }}{PARA 0 " " 0 "" {TEXT -1 201 "When a function has more than one zero (or root), then the solution that Newton's method finds depends on the initial g uess. The set of initial points that converge to a particular zero is called the " }{TEXT 259 20 "domain of attraction" }{TEXT -1 71 " for \+ that zero. Your job here is to describe a domains of attraction. " }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 201 "The foll owing is an example that provides a pretty simple way to generate a pi cture for the domains of convergence. The example also shows that th e domain of convergence can be a pretty complex set! " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 23 "Start with a picture. \+ " }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "with(plots):" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "f := x-> x*(x+1)*(x-1);" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 63 "plot(f(x),x=-2..2,view=[-2.. 2,-1.2..1.2],\ntitle=`Three Roots`);" }}}{PARA 0 "" 0 "" {TEXT -1 101 "It is \"obvious\" that initial guesses larger than 1 will lead to 1. \+ Similarly, if you start close to " }{XPPEDIT 18 0 "x=0" "/%\"xG\"\"! " }{TEXT -1 23 ", you will converge to " }{XPPEDIT 18 0 "x=0" "/%\"xG \"\"!" }{TEXT -1 161 ". The question is: What happens in between? I s there a simple switching point where you change from convergence to \+ 1 to convergence to 0? (The answer is no.)" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 313 "The following block of code ta kes a bunch of initial points and keeps track of where Newton's method will converge. At the end, it puts a red dot at -1, 0, or +1 for eac h initial point. For example, a red dot at the point (1.6,1) indicat es that when Newton's method started at 1.6, it converges to the root \+ at " }{XPPEDIT 18 0 "x" "I\"xG6\"" }{TEXT -1 67 " = 1. A red dot at ( 0.3,0) indicates that the method converges to " }{XPPEDIT 18 0 "x" "I \"xG6\"" }{TEXT -1 29 " = 0 when it starts at 0.3. " }}{PARA 0 "" 0 " " {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "df := D(f) ;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 147 "for m from -50 to 100 do x[0] := m/50;\n for n from 0 to 20 do\n x[n+1] := x[n] - e valf(f(x[n])/df(x[n])):\n od:\n z[m] := x[21]: od:" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 112 "pointplot(\{seq([m/50,z[m]] ,m=-50..100)\},\nsymbol=circle,thickness=3,color=red,\ntitle=`Domains \+ of Attraction #1`);" }}}{PARA 0 "" 0 "" {TEXT -1 312 "As expected, if \+ you start close to +1, the iterations converge to +1. If you start cl ose to 0, the iterations converge to zero. But there seems to be s ome strange behavior near 0.5, so look more closely around that point. The following block takes initial points at 0.50+ m/100 for m betwee n -50 and +50. " }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 154 "for m f rom -50 to 50 do x[0] := 0.50 + m/100;\n for n from 0 to 20 do\n \+ x[n+1] := x[n] - evalf(f(x[n])/df(x[n])):\n od:\n z[m] := x[21]: od:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 103 "pointplot(\{seq([0. 50+m/100,z[m]],m=-50..50)\},\nsymbol=circle,color=red,title=`Domain of Attraction #2`);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{PARA 0 "" 0 "" {TEXT -1 67 "You can change the code to focus more closely on the behavior n ear " }{XPPEDIT 18 0 "x" "I\"xG6\"" }{TEXT -1 69 " = 0.44, but I'll le ave that to you (and your report for next week.) " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{PARA 7 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 8 "Problems" }}{PARA 0 "" 0 "" {TEXT -1 263 "You and your \+ lab partner should produce a report addressing the following questions . You should provide a brief introduction to the report (in your own \+ words) and a brief summary at the end of the report including any obse rvations or conclusions that you make. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 145 "The report is due next Monday in \+ lecture. As before, there will be three bonus points awarded if you h and in your report on Friday in lecture. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 0 5 "Note:" }{TEXT -1 94 " Your repor t must be your own work. Please do not hand in text copied from this \+ worksheet. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 256 11 "Problem #1:" }{TEXT -1 120 " \+ One of your recent homework problems asked you to explain why Newton's method would not converge to the solutions of " }{XPPEDIT 18 0 "f(x) = 0" "/-%\"fG6#%\"xG\"\"!" }{TEXT -1 6 " when " }{XPPEDIT 18 0 "f(x) \+ = x^(1/3)" "/-%\"fG6#%\"xG)F&*&\"\"\"\"\"\"\"\"$!\"\"" }{TEXT -1 109 " . Use the tools available in Maple to illustrate the problems that t his function causes Newton's method. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 260 11 "Problem #2:" }{TEXT -1 65 " Study \+ Newton's method for solving the (really simple) equation " }{XPPEDIT 18 0 "x^2 = 0" "/*$%\"xG\"\"#\"\"!" }{TEXT -1 177 ". Does the method converge to the solution? If it does converge, how fast (or slow) i s the convergence? Explain why this equation presents a problem for N ewton's method. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 257 11 "Problem #3:" }{TEXT -1 2 " " }}{PARA 0 "" 0 "" {TEXT -1 135 "Continue the example introduced in the background section on d omains of attraction. Look more closely at the \"strange behavior\" \+ near " }{XPPEDIT 18 0 "x" "I\"xG6\"" }{TEXT -1 107 " = 0.44. Is there a pattern in the domain of attraction? Can you explain why this part icular area of the " }{XPPEDIT 18 0 "x" "I\"xG6\"" }{TEXT -1 44 " axis causes problems for Newton's method? " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}}{MARK "10 14 0" 0 }{VIEWOPTS 1 1 0 1 1 1803 }