## Newton's Method for Finding Roots

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

### The Algorithm for Newton's Method

Rather than deal with each particular function and starting point, let's find a pattern for a general function $\mathrm{f}$. For the starting point $\mathrm{x}_{0}$, the slope of the tangent line at the point $\left(\mathrm{x}_{0}, \mathrm{f}\left(\mathrm{x}_{0}\right)\right)$ is $\mathrm{f}^{\prime}\left(\mathrm{x}_{0}\right)$ so the equation of the tangent line is $y-f\left(x_{0}\right)=f^{\prime}\left(x_{0}\right)\left(x-x_{0}\right)$. This line intersects the $x$-axis when $y=0$, so

is $y-f\left(x_{0}\right)=f^{\prime}\left(x_{0}\right)\left(x-x_{0}\right)$. This line intersects the $x$-axis when $y=0$, so $0-\mathrm{f}\left(\mathrm{x}_{0}\right)=\mathrm{f}^{\prime}\left(\mathrm{x}_{0}\right)\left(\mathrm{x}-\mathrm{x}_{0}\right)$ and $\mathrm{x}_{1}=\mathrm{x}=\mathrm{x}_{0}-\frac{\mathrm{f}\left(\mathrm{x}_{0}\right)}{\mathrm{f}^{\prime}\left(\mathrm{x}_{0}\right)}$. Starting with $\mathrm{x}_{1}$ and repeating this process we have $\mathrm{x}_{2}$ $=x_{1}-\frac{f\left(x_{1}\right)}{f^{\prime}\left(x_{1}\right)}$; starting with $x_{2}$, we get $x_{3}=x_{2}-\frac{f\left(x_{2}\right)}{f^{\prime}\left(x_{2}\right)} ;$ and so on.

In general, if we start with $x_{n}$, the line tangent to the graph of $f$ at the point $\left(x_{n}, f\left(x_{n}\right)\right)$ intersects the $x$-axis at the point $x_{n+1}=x_{n}-\frac{f\left(x_{n}\right)}{f^{\prime}\left(x_{n}\right)}$, our new estimate for the root of $f$.

##### Algorithm for Newton's Method:

(1) Pick a starting value $\mathrm{x}_{0}$ (preferably close to a root of $\mathrm{f}$).

(2) For each estimate $\mathrm{x}_{\mathrm{n}}$, calculate a new estimate $\mathrm{x}_{\mathrm{n}+1}=\mathrm{x}_{\mathrm{n}}-\frac{\mathrm{f}\left(\mathrm{x}_{\mathrm{n}}\right)}{\mathrm{f}^{\prime}\left(\mathrm{x}_{\mathrm{n}}\right)}$.

(3) Repeat step (2) until the estimates are "close enough" to a root or until the method "fails".

When the algorithm for Newton's method is used with $\mathrm{f}(\mathrm{x})=\mathrm{x}^{2}-5$, the function at the beginning of this section, we have $\mathrm{f}^{\prime}(\mathrm{x})=2 \mathrm{x}$ so

\begin{aligned} x_{n+1} &=x_{n}-\frac{f\left(x_{n}\right)}{f^{\prime}\left(x_{n}\right)}=x_{n}-\frac{x_{n}^{2}-5}{2 x_{n}}=\frac{2 x_{n}^{2}-\left(x_{n}^{2}-5\right)}{2 x_{n}} \\ &=\frac{x_{n}^{2}+5}{2 x_{n}}=\frac{1}{2}\left\{x_{n}+\frac{5}{x_{n}}\right\} \end{aligned}

The new approximation, $x_{n+1}$, is the average of the previous approximation, $x_{n}$, and $\mathrm{5}$ divided by the previous approximation, $5 / \mathrm{x}_{\mathrm{n}}$. Problem 16 asks you to show that this pattern, called Heron's method, approximates the square root of any positive number. Just replace the "$\mathrm{5}$" with the number whose square root you want.

Example 1: Use Newton's method to approximate the root(s) of $\mathrm{f}(\mathrm{x})=2 \mathrm{x}+\mathrm{x} \sin (\mathrm{x}+3)-5$. Solution: $\mathrm{f}^{\prime}(\mathrm{x})=2+\mathrm{x} \cos (\mathrm{x}+3)+\sin (\mathrm{x}+3)$ so

$x_{n+1}=x_{n}-\frac{f\left(x_{n}\right)}{f^{\prime}\left(x_{n}\right)}=x_{n}-\frac{2 x_{n}+x_{n} \sin \left(x_{n}+3\right)-5}{2+x_{n} \cos \left(x_{n}+3\right)+\sin \left(x_{n}+3\right)}$

The graph of $\mathrm{f}(\mathrm{x})$ for $-4 \leq \mathrm{x} \leq 6$ (Fig. 8) indicates only one root of $\mathrm{f}$, and that root is near $\mathrm{x}=3$ so pick $\mathrm{x}_{0}=3.$ Then Newton's method yields the values $\mathrm{x}_{0}=3, \mathrm{x}_{1}=\underline{2.96484457}$ $\mathrm{x}_{2}=\underline{2.96446277}, \mathrm{x}_{3}=\underline{2.96446273} \quad$ (the underlined digits agree with the exact root).

If we had picked $\mathrm{x}_{0}=4$, Newton's method would have required $\mathrm{4}$ iterations to get $\mathrm{9}$ digits of accuracy. If $\mathrm{x}_{0}=5$, then $\mathrm{7}$ iterations are needed to get $\mathrm{9}$ digits of accuracy. If we pick $x_{0}=5.1$, then the values of $x_{n}$ are not close to the actual root after even $\mathrm{100}$ iterations, $\mathrm{x}_{100} \approx \, -49.183$. Picking a good value for $\mathrm{x}_{0}$ can result in values of $\mathrm{x}_{\mathrm{n}}$ which get close to the root quickly. Picking a poor value for $\mathrm{x}_{0}$ can result in $\mathrm{x}_{\mathrm{n}}$ values which take longer to get close to the root or which don't approach the root at all.

Note: An examination of the graph of the function can help you pick a "good" $\mathbf{x}_{0}$.

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

Example 2: The function in Fig. 9 has roots at $\mathrm{x}=3$ and $x=7$. If we pick $x_{0}=1$ and apply Newton's method, which root do the iterates, the $\mathrm{x}_{\mathrm{n}}$, approach?

Solution: The iterates of $\mathrm{x}_{0}=1$ are labeled in Fig. 10. They are approaching the root at $\mathrm{7}$.

Practice 4: For the function in Fig. 11, which root do the iterates of Newton's method approach if (a) $x_{0}=2?$

(b) $\mathrm{x}_{0}=3$?

(c) $\mathrm{x}_{0}=5$?