Newton’s Method

1 Jim LambersMAT 419/519 Summer Session 2011-12 Lecture 9 NotesThese notes correspond to Section in the s MethodFinding the minimum of the functionf(x), wheref:D Rn R, requires finding its criticalpoints, at which f(x) =0. In general, however, solving this system of equations can be quitedifficult. Therefore, it is often necessary to usenumerical methodsthat compute anapproximatesolution. We now present one such Method , known asNewton s Methodor :D Rn Rnbe a function that is differentiable onD. As it is a vector-valued function,it has component functionsgi(x),i= 1,2, .. , n, and thus we haveg(x) = g1(x)g2(x) gn(x) ,x s Method is aniterativemethod that computes an approximate solution to the systemof equationsg(x) =0. The Method requires an initial guessx(0)as input.

2 It then computessubsequent iteratesx(1),x(2),..that, hopefully, will converge to a solutionx ofg(x) = idea behind newton s Method is to approximateg(x) near the current iteratex(k)by afunctiongk(x) for which the system of equationsgk(x) is easy to solve, and then use the solutionas the next iteratex(k+1), after which this process is repeated. A suitable choice forgk(x) is thelinear approximationofg(x) atx(k), whose graph is thetangent spacetog(x) atx(k):gk(x) =g(x(k)) +Jg(x(k))(x x(k)),whereJg(x) is theJacobian matrixofg(x), defined by[Jg(x)]ij= gi(x) is,Jg(x) is the matrix of first partial derivatives of the component functions ofg(x).ExampleLetg(x, y, z) = g1(x, y, z)g2(x, y, z) gn(x, y, z) = x2+y2+z2 3x2+y2 z 1x+y+z 3 .1 ThenJg(x, y, z) = g1 x g1 y g1 z g2 x g2 y g2 z g3 x g3 y g3 z = 2x2y2z2x2y 1111.

3 2 Now, we solve the equationgk(x(k+1)) =0for the next iteratex(k+1). Settinggk(x) =0in thedefinition ofgk(x) yields the system of equations0=g(x(k)) +Jg(x(k))(x(k+1) x(k)).Rearranging yieldsx(k+1)=x(k) [Jg(x(k))] 1g(x(k)).This is the process by which each new iteratex(k+1)is obtained from the previous iteratex(k), fork= 0,1, ..In practice, one does not computex(k+1)by explicitly computing [Jg(x(k))] 1and then multi-plying byg(x(k)), because this is computationally inefficient. Instead, it is more practical to solvethe system of linear equationsJg(x(k))s(k)= g(x(k))for the unknowns(k), using a Method such as Gaussian elimination, and then settingx(k+1)=x(k)+s(k).For a single-variable functiong(x), newton s Method reduces tox(k+1)=x(k) g(x(k))g (x(k)), k= 0,1.

4 Note that it is necessary thatg (x(k))6= 0; otherwise, the sequence of newton iterates is , in the multi-variable case, whenJg(x(k)) is not an invertible matrix, the solutions(k)may not exist, in which case the sequence of newton iterates is also now illustrate the use of newton s Method in the single-variable case with some will use of newton s Method in computing 2. This number satisfies the equationf(x) = 0 wheref(x) =x2 (x) = 2x,it follows that in newton s Method , we can obtain the next iteratex(n+1)fromthe previous iteratex(n)byx(n+1)=x(n) f(x(n))f (x(n))=x(n) [x(n)]2 22x(n)=x(n) [x(n)]22x(n)+22x(n)=x(n)2+1x(n).2We choose our starting iteratex0= 1, and compute the next several iterates as follows:x1=12+11= + the fourth and fifth iterates agree in to eight decimal places, we assume that is acorrect solution tof(x) = 0, to at least eight decimal places.

5 The first two iterations are illustratedin Figure 1: newton s Method applied tof(x) =x2 2. The bold curve is the graph off. Theinitial iteratex0is chosen to be 1. The tangent line off(x) at the point (x0, f(x0)) is used toapproximatef(x), and it crosses thex-axis atx1= , which is much closer to the exact solutionthanx0. Then, the tangent line at (x1, f(x1)) is used to approximatef(x), and it crosses thex-axisatx2= 6, which is already very close to the exact s Method can be used to compute the reciprocal of a numberawithout perform-3ing any divisions. The solution, 1/a, satisfies the equationf(x) = 0,wheref(x) =a (x) =1x2,it follows that in newton s Method , we can obtain the next iteratex(n+1)from the previous iteratex(n)byx(n+1)=x(n) a 1/x(n)1/[x(n)]2=x(n) a1/x(n)2+1/x(n)1/[x(n)]2= 2x(n) a[x(n)] that no divisions are necessary to obtainx(n+1)fromx(n).

6 This iteration was actually usedon older IBM computers to implement division in use this iteration to compute the reciprocal ofa= 12. Choosing our starting iterate to , we compute the next several iterates as follows:x1= 2( ) 12( )2= 2( ) 12( )2= conclude that is an accurate approximation to the correct , suppose we repeat this process, but with an initial iterate ofx0= 1. Then, we havex1= 2(1) 12(1)2= 10x2= 2( 6) 12( 6)2= 1220x3= 2( 300) 12( 300)2= 17863240It is clear that this sequence of iterates is not going to converge to the correct solution. In general,for this iteration to converge to the reciprocal ofa, the initial iteratex0must be chosen so that0< x0<2/a. This condition guarantees that the next iteratex1will at least be positive.

7 Thecontrast between the two choices ofx0are illustrated in Figure examples demonstrate that on the one hand, newton s Method can converge to a solutionvery rapidly. On the other hand, it may not converge at all, if the initial guessx(0)is not chosensufficiently close to the solutionx .ExampleWe consider the system of equationsg(x) =0, whereg(x, y, z) = x2+y2+z2 3x2+y2 z 1x+y+z 3 .4 Figure 2: newton s Method used to compute the reciprocal of 8 by solving the equationf(x) =8 1/x= 0. Whenx0= , the tangent line off(x) at (x0, f(x0)) crosses thex-axis atx1= ,which is close to the exact solution. Whenx0= 1, the tangent line crosses thex-axis atx1= 6,which causes searcing to continue on the wrong portion of the graph, so the sequence of iteratesdoes not converge to the correct will begin to use newton s Method to solve this system of equations, with initial guessx(0)=(x(0), y(0), z(0)) = (1,0,1).

8 As computed in a previous example,Jg(x, y, z) = 2x2y2z2x2y 1111 .Therefore, each newton iteratex(k+1)is obtained by solving the system of equationsJg(x(k), y(k), z(k))(x(k+1) x(k)) = g(x(k), y(k), z(k)),or 2x(k)2y(k)2z(k)2x(k)2y(k) 1111 x(k+1) x(k)y(k+1) y(k)z(k+1) z(k) = (x(k))2+ (y(k))2+ (z(k))2 3(x(k))2+ (y(k))2 z(k) 1x(k)+y(k)+z(k) 3 .5 Settingk= 0 and substituting (x(0), y(0), z(0)) = (1,0,1) yields the system 2 022 0 11 11 x(1) 1y(1)z(1) 1 = 111 ,which has the solutionx(1)= (32,12,1). Repeating this process withk= 1 yields the system 3 123 1 11 11 x(2) 32y(2) 12z(2) 1 = 12 120 ,which has the solutionx(2)= (54,34,1). A similar process yields the next iteratex(3)=(98,78,1).It can be seen that these iterates are converging to (1,1,1), which is the exact solution.

9 However,if we instead use the initial guessx(0)= (0,0,0), then we obtainJg(0,0,0) = 0 000 0 11 11 ,which is not invertible. The systemJg(0,0,0)s(0)= g(0,0,0) does not have a solution, andtherefore newton s Method , suppose that we wish to minimize a functionf(x), and therefore need to solve the systemof equations f(x) =0. Then,g(x) = f(x), andJg(x) =Hf(x). Therefore, the newton sMethod step takes the formx(k+1)=x(k) [Hf(x(k))] 1 f(x(k)).Effectively, when used for minimization, newton s Method approximatesf(x) by itsquadraticapproximationnearx(k),fk(x) =f(x(k)) + f(x(k)) (x x(k)) +12(x x(k)) Hf(x(k))(x x(k))and then computing the unique critical point offk(x), which is the unique solution of fk(x) = that fk(x) = f(x(k)), andHfk(x) =Hf(x(k)).

10 IfHf(x(k)is positive definite, then this critical point is also guaranteed to be the unique strictglobal minimizer offk(x). For quadratic functions in general, we have this useful ann nsymmetric positive definite matrix, letb Rn, and leta R. Thenthe quadratic functionf(x) =a+b x+12x Ax6is strictly convex and has a unique strict global minimizerx , whereAx = any initial guessx(0), newton s Method applied tof(x) converges tox in one step; that is,x(1)=x .Iff(x) is not a quadratic function, then newton s Method will generally not compute a min-imizer off(x) in one step, even if its HessianHf(x) is positive definite. However, in this case, newton s Method is guaranteed to make progress, as the following theorem {x(k)} k=0be the sequence of newton iterates for the functionf(x).)