{VERSION 3 0 "IBM INTEL NT" "3.0" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 1 0 0 0 0 }{PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "Helvetica" 1 12 0 0 0 1 2 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "T itle" 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 }{PSTYLE "Author" 0 19 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }3 0 0 -1 8 8 0 0 0 0 0 0 -1 0 } {PSTYLE "R3 Font 0" -1 256 1 {CSTYLE "" -1 -1 "MS Sans Serif" 1 10 0 0 255 1 2 2 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R 3 Font 2" -1 257 1 {CSTYLE "" -1 -1 "MS Sans Serif" 1 12 255 0 0 1 2 2 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }} {SECT 0 {EXCHG {PARA 18 "" 0 "" {TEXT -1 62 "NUMERICAL METHODS FOR NON -LINEAR EQUATIONS AND NEWTON'S METHOD" }}{PARA 0 "" 0 "" {TEXT -1 0 " " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 19 "" 0 "" {TEXT -1 41 "G. K eady, University of Western Australia" }}{PARA 0 "" 0 "" {TEXT -1 0 " " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 3 "AIM" } }{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 244 "The mai n aim of this Worksheet is to investigate Newton's method of finding t he roots of single non-linear equations. (In a subsequent Worksheet we give the generalisation to Newton's method for finding roots of syste ms of nonlinear equations.)" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 44 "However we begin by reminding students that " } }{PARA 0 "" 0 "" {TEXT -1 59 "(1) there are other methods of solving n onlinear equations;" }}{PARA 0 "" 0 "" {TEXT -1 183 "(2) many of these methods, including Newton's are in-built into packages like Matlab or Maple where fsolve is the relevant function, or available in numerica l libraries such as NAG's;" }}{PARA 0 "" 0 "" {TEXT -1 170 "(3) there \+ are some common-sense guidelines for practical solution, one of which \+ is \"have a look at a plot of the function to get an idea of where roo ts are likely to be\"." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 80 "OVERVIEW OF SOME OF \+ THE ISSUES CONCERNING NUMERICAL METHODS USED TO SOLVE f(x)=0" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 178 "The methods used to solve f(x)=0 are iterative; tha t is, they define a sequence of points x0, x1, x2, ... which hopefully converge to a zero, X, of f. Issues which arise include:" }}{PARA 0 " " 0 "" {TEXT -1 34 "(i) When will the method converge?" }}{PARA 0 "" 0 "" {TEXT -1 39 "(ii) How fast does the method converge?" }}{PARA 0 " " 0 "" {TEXT -1 66 "(iii) What stopping criteria should be used to sto p the iteration?" }}{PARA 0 "" 0 "" {TEXT -1 53 "In connection with it em (ii) we define the following." }}{PARA 0 "" 0 "" {TEXT -1 40 "A con vergent iteration is said to be of " }}{PARA 0 "" 0 "" {TEXT -1 5 "ord er" }}{PARA 0 "" 0 "" {TEXT -1 125 " p if there exists a C>0 such tha t, for k sufficiently large, abs(X-x.(k+1) ) <= C*(abs(X-x.k))^p" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 272 "We will return to these issues later. However we begi n with the easy-to-use fsolve function in Maple. A point-of-view conce rning the subsequent treatment of methods for solving nonlinear equati ons is that it is methods like these which underpin the code that is i n fsolve." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 54 "MAPLE's fsolve: EXAMPLES AND WHY WE NEED TO LEARN MORE" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 " " {TEXT -1 66 "Maple has its own inbuilt fsolve function. Here are som e examples:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "fsolve(x^2-3=0,x);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 27 "fsolve(x^3 - x + 1 = 0, x);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 36 "fsolve(2*x = tan(x),x, 1.0 .. 1.57);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 158 "This last example is one where there are infinitely many solutions if one does not restrict the range. Plot th e function to see this. Here is another solution" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 37 "fsolve(2*x = tan(x) ,x, 4.14 .. 4.71);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 " " {TEXT -1 720 "Here is a reason WHY WE NEED TO LEARN MORE. The real u ses of Maple's fsolve function will be for small problems where time i s not crucial, and for problems where the greater accuracy obtainable \+ changing Digits is useful. However, sometimes nonlinear equation solvi ng is nested within loops and computer time is important: for this com piled Fortran/C - with libraries such as NAG's - remains important. To understand the documentation requires some knowledge of the methods a vailable and the terminology to describe them. See numerical analysis \+ texts when you need this. The remainder of this Worksheet can be consi dered as an introductory treatment which would help you get started on the relevant sections of the texts." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 1 " " }} {PARA 0 "" 0 "" {TEXT -1 16 "BISECTION METHOD" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 421 "In the bisection method to find a zero X of a continuous f, on e starts with an interval [a,b] with f(a)*f(b)<0, and then evaluates f ((a+b)/2). Next one finds on which half of the original interval f cha nges sign, and then updates the interval [a,b] to this. It is easy to \+ code the bisection method in any language. Here are the questions we \+ asked at the beginning of this Worksheet, and answers for the bisectio n method." }}{PARA 0 "" 0 "" {TEXT -1 69 "(i) When will the method con verge? Always: it is globally convergent." }}{PARA 0 "" 0 "" {TEXT -1 124 "(ii) How fast does the method converge? Slowly, and we get only o ne bit more accuracy each step: the method is first order. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 33 "Here is Maple c ode for bisection:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 " " {MPLTEXT 1 0 26 "bisect := proc(f, a, b, N)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 45 " local epsilon, fa, fb, n, an, bn, pn, fp;" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 39 " epsilon := evalf( 10^(-Digits/2 ) );" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 24 " fa := evalf( f(a) );" } }{PARA 0 "> " 0 "" {MPLTEXT 1 0 24 " fb := evalf( f(b) );" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 25 " if (fa * fb) > 0 then" }}{PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 59 " ERROR(`f fails to take opposite signs \+ at a and b.`)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 7 " fi:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 19 " an := evalf(a);" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 19 " bn := evalf(b);" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 24 " for n from 0 to N do" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 30 " \+ pn := ( an + bn ) / 2;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 29 " \+ fp := evalf( f(pn) );" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 33 " \+ print(n, an, pn, bn, fp);" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 33 " \+ if fa * fp > epsilon then" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 21 " an := pn;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 21 " \+ fa := fp;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 36 " elif fa * fp < -epsilon then" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 21 " bn \+ := pn;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 21 " fb := fp;" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 " else" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 17 " break" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 10 " fi" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 7 " od;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 7 " pn;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 4 "end:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 32 "f:= x -> x^2-3: bisect(f,1,2,4);" }}}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 239 "Well this is not very accur ate: the bisection method is slow. Newton's method is much more rapidl y convergent. We will soon get the flavour of the fact that the bisect ion method is only first-order, whereas Newton's method is second-orde r." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 15 "NEWTON'S METHOD" }}{PARA 0 "" 0 " " {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 1 " " }}{PARA 0 "" 0 "" {TEXT -1 508 "Here is Maple code for single-variable Newton iteration. (Remember that this is for pedagogical reasons only. In practice with any real nonlinear equation worked in Maple, I recommend you use Mapl e's fsolve. The code here is only to illustrate the method: it is not \+ for production use.) By setting Digits to prescribed accuracy, high ac curacy can be obtained for the solution. The variable diff1f is the fi rst derivative of f w.r.t. x: it is better to work it out just once, o utside the for-loop (and itern)." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 7 "f:=' f':" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "itern:= proc(xo)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 24 " global \+ x, f, diff1f:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 28 " xo - subs(x=xo ,f/diff1f)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 6 " end:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 17 "# A test example " }}{PARA 0 "" 0 "" {TEXT -1 70 "# Run this code if you can't predict the general form of the resul ts. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 40 "f:=x^2-3: diff1f:=diff(f,x): x1:=2.0: " }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 22 " for j from 1 to 4 do" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 24 " x.(j+1):=itern(x.j);" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 7 " od;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 16 " ev alf(sqrt(3));" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 19 " # Check the ans wer" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" } }{PARA 0 "" 0 "" {TEXT -1 163 " For more complicated functions f, you \+ could CHECK your answers against the output from Maple's fsolve, whic h is best for real use in solving nonlinear equations." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 353 "Newton iteration is second-order: the number of correct decimal places approximately doub les on each iteration. (Compare this with the slow, first-order, rate \+ of convergence we saw with the bisection method.) As an EXERCISE set D igits:=100, and re-run the code above this time for 8 iterative steps: you will see the number of correct digits increasing." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 288 "This page is a theo retical aside. Newton iteration can be applied exactly too. Use an exa ct (rational) x0 in the above Maple code. We could apply this to find \+ a sequence of rational numbers approximating sqrt(3). However we choos e to use a number related to sqrt(5). Consider the function" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 16 " f:= x^2 \+ - x -1;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 39 "If m is given and the \+ starting guess is" }}{PARA 0 "" 0 "" {TEXT -1 34 " x0:= fibonacci(m+1) /fibonacci(m);" }}{PARA 0 "" 0 "" {TEXT -1 95 "then subsequent Newton \+ iterations x.k have a similar form. The following code illustrates thi s." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 50 "itern:= proc(xo) xo - subs(x=xo,f /diff1f) end:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 38 "f:=x^2-x -1: diff1f:=diff(f,x): xo:=2:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 56 "x0:=xo: for j from 0 to 4 do x.(j+1):=itern(x.j); od;" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" } }{PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "evalf((1+sqrt(5))/2);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "evalf(x5);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 18 "SOME MORE EXAMPLES" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 " " {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 52 "p:= 3*x^11 + 5*x^9 - 15*x^5 - 8*x^4 + 5*x^2 - x + 6: " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "factor(p); " }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 50 "# from which we see that p has no \+ rational factors" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "plot(p,x = -5/4 .. 5/4); " }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 41 "# to get a rough id ea where the zeros are" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "fsolve(p= 0,x); " }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 46 "# just to compare again st the Newton iteration" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 33 "f:=p: di ff1f:=diff(p,x): xo:=0.9:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 56 "x0:=xo: for j from 0 to 3 do x.(j+1):=itern(x.j); od;" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 34 "ANOTHER EXAMPLE OF NEWTON'S METHOD " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 31 "Assig n the function f(x) to be:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "f:= x -> tan(x)-2*x;" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 " " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 39 "plot(f(x), x = 0 .. 1.5 7, y= -2 .. 10);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 297 "We could tre at this exactly as in the preceding example. However, we choose to giv e the picture of what is happenning in the iteration by using some Map le graphics. This is only to reinforce the message of how Newton itera tion works. You are not expected in this course to program Maple like \+ this." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 " " }}{PARA 0 "" 0 "" {TEXT -1 34 "SOME FANCIER GRAPHICS IN THE MAPLE" } }{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 90 "The Newt on method is based on the following formula for the next value in the \+ interation: " }}{PARA 0 "" 0 "" {TEXT -1 33 "x.(k+1) = x.k - f(x.k)/f' (x.k). " }}{PARA 0 "" 0 "" {TEXT -1 76 "The following procedure compu tes the formula for a given function f(x) in x." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 44 "newtonStep := proc( f,x) x - f/diff(f,x) end:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 54 "Appl ying the Newton routine to f(x) we get the formula" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "g:= newtonStep(f(x) ,x);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "g := unapply(g,x);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 72 "Choose \+ an initial of x0 = 1 and then approximate the zero of f(x) using:" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "eva lf(g(1));" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "evalf(g(%));" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 49 " and so on to obtain a zero value at x = 1.165561." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 43 "for n from 1 to 10 \+ do evalf(g(%)) od: %;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 110 "Each iteration of the Newton procedure can be represented graphically by \+ using in the following procedure nr." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 49 " nr:=proc(f,initial,number,left,r ight,bottom,top)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 18 " local t,n,N ,g:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 14 " N:=number:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 0 " " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 12 " t:=NULL:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 54 " g := una pply(newtonStep(f(x),x),x); x.1:= initial:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 26 " for n from 1 to N do:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 30 " t:=t,(x.n,0,x.n,f(x.n)):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 28 " x.(n+1):=e valf(g(x.n)):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 8 " od:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 35 " print(`Zero at x= `,evalf(x.(n)));" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 61 " plot(\{[t], f(x) \}, x= left..righ t, bottom..top, style=LINE);" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 4 "end:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 25 "Call the procedure using:" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 32 "nr( f, 1.0, 5, 0.9, 1.32, -1, 2);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 184 "The graphics from proc nr illustrates Newton i teration: drawing tangents to the curve at one approximation of x give s the next approximation where this tangent intersects the x axis. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 51 "In the OV ERVIEW section we presented the questions:" }}{PARA 0 "" 0 "" {TEXT -1 34 "(i) When will the method converge?" }}{PARA 0 "" 0 "" {TEXT -1 39 "(ii) How fast does the method converge?" }}{PARA 0 "" 0 "" {TEXT -1 396 "We have already answered (ii): when the method converges its s peed of convergence is very good and in usual circumstances is second- order. However, caution is needed for item (i): typically Newton's met hod will converge only when the starting guess is sufficiently close t o the zero we are seeking. The code with the graphics can be applied i n other, harder, examples to illustrate the following." }}{PARA 0 "" 0 "" {TEXT -1 149 "1. The zero found may not be the closest to our st arting value. To obtain the closest root the initial value may need to be very close to the root. " }}{PARA 0 "" 0 "" {TEXT -1 237 "2. One \+ example where Newton's method will fail is if the initial approximatio n is selected at a stationary point. As we see in other contexts, we \+ need to know the general behaviour of the function before applying a n umerical technique." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 " " {TEXT -1 0 "" }}}}{MARK "54" 0 }{VIEWOPTS 1 1 0 1 1 1803 }