Newton’s Method and Other Applications

Lecture 13 18.01 Fall 2006 Lecture 13: Newton’s Method and Other Applications Newton’s Method Newton’s method is a powerful tool for solving equations of the form f (x) = 0. Example 1. f√ (x) = x2 − 3. In other words, solve x2 − 3 = 0. We already know that the solution to this is x = 3. Newton’s method, gives a good numerical approximation to the answer. The method uses tangent lines (see Fig. 1). y = x2 -3 x0=1 x1 (1,-2) Figure 1: Illustration of Newton’s Method, Example 1. The goal is to find where the graph crosses the x-axis. We start with a guess of x0 = 1. Plugging that back into the equation for y, we get y0 = 12 − 3 = −2, which isn’t very close to 0. Our next guess is x1 , where the tangent line to the function at x0 crosses the x-axis. The equation for the tangent line is: y − y0 = m(x − x0 ) When the tangent line intercepts the x-axis, y = 0, so −y0 y0 − m = m(x1 − x0 ) = x1 − x0 x1 = x0 − y0 m Remember: m is the slope of the tangent line to y = f (x) at the point (x0 , y0 ). 1 Lecture 13 18.01 Fall 2006 In terms of f : y0 = m = f (x0 ) f � (x0 ) Therefore, x1 = x0 − f (x0 ) f � (x0 ) x0 Figure 2: x2 x1 Illustration of Newton’s Method, Example 1. In our example, f (x) = x2 − 3, f � (x) = 2x. Thus, x1 = x1 = (x20 − 3) 1 3 = x0 − x0 + 2 2x0 2x 1 3 x0 + 2 2x0 x0 − The main idea is to repeat (iterate) this process: x2 = x3 = and so on. The procedure approximates √ 1 x1 + 2 1 x2 + 2 3 2x1 3 2x2 3 extremely well. 2 Lecture 13 18.01 Fall 2006 accuracy: |y − x x0 x1 y 1 2 x2 7 4 x3 7 8 x4 18,817 10,864 √ 3| 3 × 10−1 2 × 10−2 10−4 6 7 + 3 × 10−9 Notice that the number of digits of accuracy doubles with each iteration. Summary Newton’s Method is illustrated in Fig. 3 and can be summarized as follows: xk+1 = xk − f (xk ) f � (xk ) y=f(x) (xk, yk) xk+1 xk = kth iterate Figure 3: Illustration of Newton’s Method. Example 1 considered the particular case of x2 − 3 f (xk ) 1 3 = xk − � = ... = xk + f (xk ) 2 2xk f (x) = xk+1 Now, we define x = lim xk k→∞ (xk → x as k → ∞) To evaluate x in Example 1, take the limit as k → ∞ in the equation xk+1 = 1 3 xk + 2 2xk 3 Lecture 13 18.01 Fall 2006 This yields 1 3 1 3 1 3 x̄ + =⇒ x − x = =⇒ x = =⇒ x2 = 3 2 2x̄ 2x 2x 2 2 √ which is just what we hoped: x = 3. x̄ = Warning 1. Newton’s Method can find√an unexpected √ root. Example: if you take x0 = −1, then xk → − 3 instead of + 3. This convergence to an unexpected root is illustrated in Fig. 4 y = x2-3 x1 x0 tangent to curve at x = x0 Figure 4: Newton’s method converging to an unexpected root. Warning 2. Newton’s Method can fail completely. This failure is illustrated in Fig. 5. In this case, x2 = x0 , x3 = x1 , and so forth. It repeats in a cycle, and never converges to a single value. (x1, y1) x0 x1 (x0, y0) Figure 5: Newton’s method converging to an unexpected root. 4 Lecture 13 18.01 Fall 2006 Ring on a String Consider a ring on a string 1 held fixed at two ends at (0, 0) and (a, b) (see Fig. 6). The ring is free to slide to any point. Find the position (x, y) of the string. a-x (0, 0) (a, b) x α √ (x2 +y2) √ [(a-x)2 +(b-y2)] β α=β (x, y) Figure 6: Illustration of the Ring on a String problem. Physical Principle The ring settles at the lowest height (lowest potential energy), so the prob­ lem is to minimize y subject to the constraint that (x, y) is on the string. Constraint The length L of the string is fixed: � � x2 + y 2 + (x − a)2 + (y − b)2 = L The function y = y(x) is determined implicitly by the constraint equation above. We traced the constraint curve (possible positions of the ring) on the blackboard. This curve is an ellipse with foci at (0, 0) and (a, b), but knowing that the curve is an ellipse does not help us find the lowest point. Experiments with the hanging ring show that the lowest point is somewhere in the middle. Since the ends of the constraint curve are higher than the middle, the lowest point is a critical point (a point where y � (x) = 0). In class we also gave a physical demonstration of this by drawing the horizontal tangent at the lowest point. To find the critical point, differentiate the constraint equation implicitly with respect to x, x + yy � x − a + (y − b)y � � +� =0 (x − a)2 + (y − b)2 x2 + y 2 Since y � = 0 a the critical point, the equation can be rewritten as x � 1� c 1999 x2 + y2 a−x =� (x − a)2 + (y − b)2 c and �2007 David Jerison 5 Lecture 13 18.01 Fall 2006 From Fig. 6, we see that the last equation can be interpreted geometrically as saying that sin α = sin β where α and β are the angles the left and right portions of the string make with the vertical. Physical and geometric conclusions The angles α and β are equal. Using vectors to compute the force exerted by gravity on the two halves of the string, one finds that there is equal tension in the two halves of the string - a physical equilibrium. (From another point of view, the equal angle property expresses a geometric property of ellipses: Suppose that the ellipse is a mirror. A ray of light from the focus (0, 0) reflects off the mirror according to the rule angle of incidence equals angle of reflection, and therefore the ray goes directly to the other focus at (a, b).) Formulae for x and y We did not yet find the location of (x, y). We will now show that � � � � a b 1� 1− √ b − L2 − a 2 x= , y= 2 2 L2 − a2 Because α = β, � � x = x2 + y 2 sin α; a − x = (x − a)2 + (y − b)2 sin α Adding these two equations, �� � � a a= x2 + y 2 + (x − a)2 + (y − b)2 sin α = L sin α =⇒ sin α = L The equations for the vertical legs of the right triangles are (note that y < 0): � � −y = x2 + y 2 cos α; b − y = (x − a)2 + (y − b)2 cos β Adding these two equations, and using α = β, �� � � 1 b − 2y = x2 + y 2 + (x − a)2 + (y − b)2 cos α = L cos α =⇒ y = (b − L cos α) 2 � √ a 2 2 2 Use the relation sin α = to write L cos α = L 1 − sin α = L − a . Then the formula for y is L � � 1� y= b − L2 − a2 2 Finally, to find the formula for x, use the similar right triangles x a−x tan α = = =⇒ x(b − y) = (−y)(a − x) =⇒ (b − 2y)x = −ay −y b−y Therefore, � � −ay a b = 1− √ b − 2y 2 L2 − a2 Thus we have formulae for x and y in terms of a, b and L. x= I omitted the derivation of the formulae for x and y in lecture because it is long and because we got all of our physical intuition and understanding out of the problem from the balance condition that was the immediate consequence of the critical point computation. Final Remark. In 18.02, you will learn to treat constrained max/min problems in any number of variables using a method called Lagrange multipliers. 6