Newton's Method for Finding Roots

Read this section. Work through practice problems 1-6.

What Can Go Wrong?

When Newton's method works, it usually works very well and the values of the $\mathrm{x}_{\mathrm{n}}$ approach a root of $\mathrm{f}$ very quickly, often doubling the number of correct digits with each iteration. There are, however, several things which can go wrong.

One obvious problem with Newton's method is that $\mathrm{f}^{\prime}\left(\mathrm{x}_{\mathrm{n}}\right)$ can be 0. Then we are trying to divide by 0 and $x_{n+1}$ is undefined. Geometrically, if $f^{\prime}\left(x_{n}\right)=0$, then the tangent line to the graph of $f$ at $x_{n}$ is horizontal and does not intersect the $\mathrm{x}$-axis at one point (Fig. 12). If $\mathrm{f}^{\prime}\left(\mathrm{x}_{\mathrm{n}}\right)=0$, just pick another starting value $\mathrm{x}_{0}$ and begin again. In practice, a second or third choice of $\mathrm{x}_{0}$ usually succeeds.

There are two other less obvious difficulties that are not as easy to overcome - the values of the iterates $\mathrm{x}_{\mathrm{n}}$ may become locked into an infinitely repeating loop (Fig. 13), or they may actually move farther away from a root (Fig. 14).

Example 3: Put $x_{0}=1$ and use Newton's method to find the first two iterates, $\mathrm{x}_{1}$ and $\mathrm{x}_{2}$, for the function $\mathrm{f}(\mathrm{x})$ $=x^{3}-3 x^{2}+x-1$.

Solution: This is the same function as in the previous Practice problem, but we are using a different starting value for $x_{0}. f^{\prime}(x)=3 x^{2}-6 x+1$ so

$\mathrm{x}_{1}=\mathrm{x}_{0}-\frac{\mathrm{f}\left(\mathrm{x}_{0}\right)}{\mathrm{f}^{\prime}\left(\mathrm{x}_{0}\right)}=1-\frac{\mathrm{f}(1)}{\mathrm{f}^{\prime}(1)}=1-\frac{-2}{-2}=0$ and $\mathrm{x}_{2} = \mathrm{x}_{1}-\frac{\mathrm{f}\left(\mathrm{x}_{1}\right)}{\mathrm{f}^{\prime}\left(\mathrm{x}_{1}\right)}=0-\frac{\mathrm{f}(0)}{\mathrm{f}^{\prime}(0)}=0-\frac{-1}{1}=1$

which is the same as $\mathrm{x}_{0}$, so $\mathrm{x}_{3}=\mathrm{x}_{1}=0$ and $\mathrm{x}_{4}=\mathrm{x}_{2}=1$. The values of $\mathrm{x}_{\mathrm{n}}$ alternate between 1 and 0 and do not approach a root.

Newton's method behaves badly at only a few starting points for this particular function. For most starting points Newton's method converges to the root of this function.

There are some functions which defeat Newton's method for almost every starting point.

Practice 5: For $\mathrm{f}(\mathrm{x})=\sqrt[3]{\mathrm{x}}=\mathrm{x}^{1 / 3}$ and $\mathrm{x}_{0}=1$, verify that $\mathrm{x}_{1}=-2, \mathrm{x}_{2}=4, \mathrm{x}_{3}=-8$. Also try $\mathrm{x}_{0}=-3$, and verify that the same pattern holds: $\mathrm{x}_{\mathrm{n}+1}=-2 \mathrm{x}_{\mathrm{n}}$. Graph $\mathrm{f}$ and explain why the Newton's method iterates get farther and farther away from the root at $\mathrm{0}$.

Newton's method is powerful and quick and very easy to program on a calculator or computer. It usually works so well that many people routinely use it as the first method they apply. If Newton's method fails for their particular function, they simply try some other method.