Newton's Method

Figure 4: Graphical illustration of the Newton's Method.

• One of the most widely used methods of solving equations is Newton's method (Newton did not publish an extensive discussion of this method, but he solved a cubic polynomial in Principia (l687). The version given here is considerably improved over his original example).
• Like the previous ones, this method is also based on a linear approximation of the function, but does so using a tangent to the curve. Figure 4 gives a graphical description
• Starting from a single initial estimate, $x_0$, that is not too far from a root, we move along the tangent to its intersection with the x-axis, and take that as the next approximation.
• This is continued until either the successive x-values are sufficiently close or the value of the function is sufficiently near zero.
• The calculation scheme follows immediately from the right triangle shown in Fig. 4.
  
  $$tan\theta=f^{'}(x_0)=\frac{f(x_0)}{x_0-x_1}\Rightarrow x_1=x_0-\frac{f(x_0)}{f^{'}(x_0)}$$
  
  
  and the general term is:
  
  $$x_{n+1}=x_{n}-\frac{f(x_n)}{f^{'}(x_n)},n ~0,1,2,\ldots$$
  
  

• Newton's algorithm is widely used because, it is more rapidly convergent than any of the methods discussed so far.
• The method is quadratically convergent, by which we mean that the error of each step approaches a constant K times the square of the error of the previous step.
• The net result of this is, that the number of decimal places of accuracy nearly doubles at each iteration.
• When Newton's method is applied to $f(x) = 3x + sin x - e^x= ~0$, if we begin with $x_0=0.0$:
  
  $$x_1=x_0-\frac{f(x_0)}{f^{'}(x_0)}=0.0-\frac{-1.0}{3.0}=0.33333$$
  
  
  
  
  $$x_2=0.36017$$
  
  
  
  
  $$x_3=0.3604217$$
  
  

• After three iterations, the root is correct to seven digits; convergence is much more rapid than any previous method. In fact, the error after an iteration is about one-third of the square of the previous error.
• If a difficult problem requires many iterations to converge, the number of function evaluations with Newton's method may be many more than with linear iteration methods because Newton always uses two per iteration whereas the others take only one (after the first step that takes two).

Figure 5: Graphical illustration of the case that Newton's Method will not converge.

An algorithm for the Newton's method :

• The method may converge to a root different from the expected one or diverge if the starting value is not close enough to the root.
• In some cases Newton's method will not converge. Figure 5 illustrates this situation.
• Starting with $x_0$, one never reaches the root $r$ because $x_6=x_1$ and we are in an endless loop.
• Observe also that if we should ever reach the minimum or maximum of the curve, we will fly off to infinity.