Transcription of The Newton-Raphson Method
1 The Newton-Raphson Method1 IntroductionThe Newton-Raphson Method , or newton Method , is a powerful techniquefor solving equations numerically. Like so much of the di erential calculus,it is based on the simple idea of linear approximation. The newton Method ,properly used, usually homes in on a root with devastating e essential part of these notes is Section , where the basic formulais derived, Section , where the procedure is interpreted geometrically,and|of course|Section 6, where the problems are. Peripheral but perhapsinteresting is Section 3, where the birth of the newton Method is Using Linear Approximations to Solve Equa-tionsLetf(x) be a well-behaved function, and letrbe a root of the equationf(x) = 0. We start with an , we produce animproved|we hope| , we produce a new , we produce a new estimatex3.
2 We go on until we are `closeenough' tor|or until it becomes clear that we are getting above general style of proceeding is the many it-erative root- nding procedures, the Newton-Raphson Method , with its com-bination of simplicity and power, is the most widely used. Section de-scribes another iterative root- nding procedure, theSecant initial estimate is sometimes calledx1, but most mathe-maticians prefer to start counting at the initial estimate is called a \guess." The newton Methodis usually very very good ifx0is close tor, \guess"x0should be chosen with The Newton-Raphson IterationLetx0be a good estimate ofrand letr=x0+h. Sincethetruerootisr,andh=r x0,thenumberhmeasures how far the estimatex0is from `small,' we can use the linear (tangent line) approximation toconclude that0=f(r)=f(x0+h) f(x0)+hf0(x0);and therefore, unlessf0(x0)iscloseto0,h f(x0)f0(x0):It follows thatr=x0+h x0 f(x0)f0(x0):Our new improved (?)
3 Estimatex1ofris therefore given byx1=x0 f(x0)f0(x0):The next estimatex2is obtained fromx1in exactly the same way asx1wasobtained fromx0:x2=x1 f(x1)f0(x1):Continue in this way. Ifxnis the current estimate, then the next estimatexn+1is given byxn+1=xn f(xn)f0(xn)(1) A Geometric Interpretation of the Newton-Raphson It-erationIn the picture below, the curvey=f(x) meets thex-axis thecurrent estimate ofr. The tangent line toy=f(x)atthepoint(a;f(a))has equationy=f(a)+(x a)f0(a):Letbbe thex-intercept of the tangent line. Thenb=a f(a)f0(a):2abrCompare with Equation 1:bis just the `next' Newton-Raphson estimate ofr. The new estimatebis obtained by drawing the tangent line atx=a,andthen sliding to thex-axis along this tangent line. Now draw the tangent lineat (b;f(b)) and ride the new tangent line to thex-axis to get a new estimatec.
4 Can use the geometric interpretation to design functions and startingpoints for which the newton Method runs into trouble. For example, byputting a little bump on the curve atx=awe can makebfly far away fromr. When a newton Method calculation is going badly, a picture can help usdiagnose the problem and x would be wrong to think of the newton Method simply in termsof tangent lines. The newton Method is used to nd complex roots ofpolynomials, and roots of systems of equations in several variables, wherethe geometry is far less clear, but linear approximation still makes The Convergence of the newton MethodThe argument that led to Equation 1 used the informal and imprecise symbol . We probe this argument for numerical procedure works forallequations.
5 For example, letf(x)=x2+17 ifx6=1,andletf(1) = 0. The behaviour off(x)near1givesnoclue to the fact thatf(1) = 0. Thus no Method of successive approximationcan arrive at the solution off(x) = 0. To make progress in the analysis, weneed to assume thatf(x) is in some sense smooth. We will suppose thatf00(x) (exists and) is continuous tangent line approximation is|an 's try to geta handle on the error. Imagine a particle travelling in a straight line, andletf(x) be its position at (x) is the velocity at acceleration of the particle were always 0, then thechangein positionfrom timex0to timex0+hwould behf0(x0). So the position at timex0+h3would bef(x0)+hf0(x0)|note that this is the tangent line approximation,which we can also think of as the zero-acceleration the velocityvariesin the time fromx0tox0+h, that is, if the ac-celeration is not 0, then in general the tangent line approximation will notcorrectly predict the displacement at timex0+h.
6 And the bigger the accel-eration, the bigger the error. It can be shown that iffis twice di erentiablethen the error in the tangent line approximation is (1=2)h2f00(c)forsomecbetweenx0andx0+h. In particular, ifjf00(x)jis large betweenx0andx0+h, then the error in the tangent line approximation is large. Thus wecan expectlarge second derivativesto be bad for the newton Method . Thisis what goes wrong in Problem 7(b).In the argument for Equation 1, from 0 f(x0)+hf0(x0)weconcludedthath f(x0)=f0(x0). This can be quite wrong iff0(x0)iscloseto0:note that 3:01 is close to 3, but 3:01=10 8isnotatallcloseto3=10 can expect rst derivatives close to0 to be bad for the newton is what goes wrong in Problems 7(a) and informal considerations can be turned into positivetheoremsaboutthe behaviour of the error in the newton Method .
7 For example, ifjf00(x)=f0(x)jis not too large nearr,andwestartwithanx0close enough tor,theNew-ton Method converges very fast tor. (Naturally, the theorem gives \not toolarge," \close enough," and \very fast" precise meanings.)The study of the behaviour of the newton Method is part of a large andimportant area of mathematics calledNumerical The Secant MethodThe Secant Method is the most popular of the many variants of the NewtonMethod. We start withtwoestimates of the root,x0andx1. The iterativeformula, forn 1isxn+1=xn f(xn)Q(xn 1;xn);whereQ(xn 1;xn)=f(xn 1) f(xn)xn 1 xn:Note that ifxnis close toxn 1,thenQ(xn 1;xn)isclosetof0(xn), andthe two methods do not di er by much. We can also compare the methodsgeometrically. Instead of sliding along the tangent line, the Secant Methodslides along a nearby secant Secant Method has some advantages over the newton Method .
8 Itis more stable, less subject to the wild gyrations that can a ict the NewtonMethod. (The di erences are not great, since the geometry is nearly thesame.) To use the Secant Method , we do not need the derivative, which4can be expensive to calculate. The Secant Method , when it is working well,which is most of the time, is fast. Usually we need about 45 percent moreiterations than with the newton Method to get the same accuracy, but eachiteration is cheaper. Your mileage may newton 's newton MethodNature and Nature's laws lay hid in night:God said, Let newton be! And all was Pope, 1727It didn't quite happen that way with the newton Method . newton hadno great interest in the numerical solution of equations|his only numericalexample is a cubic. And there was a long history of e cient numericalsolution of cubics, going back at least to Leonardo of Pisa (\Fibonacci,"early thirteenth century).
9 At rst sight, the Method newton uses doesn't look like the NewtonMethod we know. The derivative is not even mentioned, even though thesame manuscript develops the Newtonian version of the derivative! newton 's version of the Method is mainly a pedagogical device to explainsomething quite di erent. Newtonreal lywanted to show how to solve thefollowing `algebraic' problem: given an equationF(x;y) = 0, expressyas aseries in powers before discussing his novelsymboliccalculations, newton tried tomotivate the idea by doing an analogous calculation withnumbers,usingthe equationy3 2y 5=0:We describe, quoting (in translation) from newton 'sDe Methodis Serierumet Fluxionum,how he deals with the equation. Like any calculation, New-ton's should be followed with pencil in hand.
10 \Let the equationy3 2y 5 = 0 be proposed for solution and letthe number 2 be found, one way or another, which di ers fromthe required root by less than its tenth part. I then set 2 +p=yand in place ofyin the equation I substitute 2 + arises the new equationp3+6p2+10p 1=0:whose rootpis to be sought for addition to the quotient. Speci -cally, (whenp3+6p2is neglected because of its smallness) we have510p 1 = 0, orp=0:1 narrowly approximates the truth. Ac-cordingly, I write in the quotient and, supposing 0:1+q=p,I substitute this ctitious value for it as before. There resultsq3+6:3q2+11:23q+0:061 = 0:And since 11:23q+0:061 = 0 closely approaches the truth, inother words very nearlyq= 0:0054 .." newton puts 0:0054 +rforqinq3+6:3q2+11:23q+0:061 = 0,Neglecting the terms inr3andr2, he concludes thatr 0:00004852.
