Newton's Method, Continued

Newton's algorithm is widely used because, it is more rapidly convergent than any of the methods discussed so far. Quadratically convergent
The error of each step approaches a constant K times the square of the error of the previous step.
The number of decimal places of accuracy nearly doubles at each iteration.
When Newton's method is applied to , if we begin with :

$\begin{displaymath} x_1=x_0-\frac{f(x_0)}{f^{'}(x_0)}=0.0-\frac{-1.0}{3.0}=0.33333 \end{displaymath}$

$\begin{displaymath} x_2=0.36017 \end{displaymath}$

$\begin{displaymath} x_3=0.3604217 \end{displaymath}$
After three iterations, the root is correct to seven digits (.3604217029603
2440136932951583028); 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.

There is the need for two functions evaluations at each step, and and we must obtain the derivative function at the start.
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's method always uses two per iteration whereas the others take only one.
An algorithm for the Newton's method :

$\fbox{\parbox{9cm}{ To determine a root of $f(x) = 0$, given $x_0$\ reasonably c... ...lerance~value1)$\ Or If $\vert f(x_0)\vert < tolerance~value2)$\\ End If.\\ }}$

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 (Fig. 1).

**Figure 1:** Graphical illustration of the case that Newton's Method will not converge.
$\includegraphics[scale=0.4]{figures/1-14}$

Starting with , one never reaches the root because 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.

Example: Apply Newton's method to $x-x^{1/3}-2=0$ .
(http://siber.cankaya.edu.tr/ozdogan/NumericalComputations/mfiles/chapter1/demoNewton.m m-file: demoNewton.m.
Example: A general implementation of Newton's method.
(http://siber.cankaya.edu.tr/ozdogan/NumericalComputations/mfiles/chapter1/newton.m m-files: newton.m),(http://siber.cankaya.edu.tr/ozdogan/NumericalComputations/mfiles/chapter1/fx3n.m fx3n.m).

Cem Ozdogan 2010-10-13