Newton’s Method 1 Construction Suppose we want to ﬁnd a root of F , that is solution of F (x) = 0. For most functions we can’t algebraically solve the equations and must use numerical techniques. One method for doing this, that you may have seen in calculus, is the NewtonRaphson method. Given an initial guess, x0 , draw the tangent to the graph of F at (x0 , F (x0 )). Unless we have had the bad luck of picking a critical point of F , this line intersects the xaxis at a new point, x1 , this point is out new guess. Algebraically we get x1 = x0 − F (x0 ) . F � (x0 ) Newton’s method consists of iterating this procedure. Hence we deﬁne the Newton iteration function associated to F to be F (x) N (x) = x − � . F (x) 2 Convergence We must ﬁrst deﬁne the multiplicity of a root. Deﬁnition. A root x0 of F has multiplicity k, if F [k−1] (x0 ) = 0, but F [k] (x0 ) = � 0. Here F [k] th is the k derivative of F . If x0 is a root of F with multiplicity k, F can be written in the form F (x) = (x − x0 )k G(x) where G doesn’t have a root at x0 . Note, however, that the multiplicity of a root can be inﬁnite. 1 Newton’s Fixed Point Theorem. Suppose F is a (suﬃciently diﬀerentiable) function and N is its associated Newton iteration function. Then, assuming all roots of F have ﬁnite multiplicity, x0 is a root of multiplicity k if and only if x0 is a ﬁxed point of N . Moreover, such a ﬁxed point is always attracting. Proof. Suppose ﬁrst that x0 has multiplicity 1, i.e., F (x0 ) = 0, but F � (x0 ) = � 0. Then it is clear that N (x0 ) = x0 . Conversely, N (x0 ) = x0 implies F (x0 ) = 0. Next, we compute N � (x) = F (x)F �� (x) (F � (x))2 using the quotient rule. Hence if x0 has multiplicity 1, N � (x0 ) = 0 so x0 is indeed attracting. For the general case, see text. Despite the above theorem, Newton’s method doesn’t always converge. One problem is that F might not be diﬀerentiable. For example, if F (x) = x1/3 , then N (x) = −2x which has a repelling ﬁxed point at 0, the root of F . Even if F is diﬀerentiable, there may still be problems with cycles. Let F (x) = x3 − 5x. Then we see x3 − 5x N (x) = x − 2 . 3x − 5 This has a cycle since N (1) = −1 and N (−1) = 1. Therefore if we had made the initial guess x0 = 1, Newton’s method would have gotten stuck. In this case the cycle is repelling and so most initial guesses converge to a root. This is not always the case. Consider F (x) = (x2 − 1)(x2 + A). From the proof of Newton’s ﬁxed point theorem, N has critical points at the places where F �� vanishes. Hence the points � 1−A c± = ± 6 √ are critical for N . If we set A = (29 − 720)/11, the points c± lie on a 2cycle, which is therefore attracting. 2

Lecture 10 (Part I): Newton’s Method

Related Documents

Recommended Documents

Description

Related Documents

Free up your schedule!

Take 5 seconds to unlock