4 Applications of Derivatives 4.6 Applied Optimization Problems 4.8 Antiderivatives

4.7 Newton’s Method

Coming Concepts

•

Describe the steps of Newton’s method.
•

Explain what an iterative process means.
•

Recognize when Newton’s method does not work.
•

Apply iterative processes to various situations.

In many areas of pure and applied mathematics, we are interested in finding solutions to an equation of the form $\displaystyle f(x)=0$ . For most functions, however, it is difficult—if not impossible—to calculate their zeroes explicitly. In this section, we take a look at a technique that provides a very efficient way of approximating the zeroes of functions. This technique makes use of tangent line approximations and is behind the method used often by calculators and computers to find zeroes.

4.7.1 Describing Newton’s Method

Consider the task of finding the solutions of $\displaystyle f(x)=0$ . If $\displaystyle f$ is the first-degree polynomial $\displaystyle f(x)=ax+b$ , then the solution of $\displaystyle f(x)=0$ is given by the formula $\displaystyle x=-\frac{b}{a}$ . If $\displaystyle f$ is the second-degree polynomial $\displaystyle f(x)=ax^{2}+bx+c$ , the solutions of $\displaystyle f(x)=0$ can be found by using the quadratic formula. However, for polynomials of degree $\displaystyle 3$ or more, finding roots of $\displaystyle f$ becomes more complicated. Although formulas exist for third- and fourth-degree polynomials, they are quite complicated. Also, if $\displaystyle f$ is a polynomial of degree $\displaystyle 5$ or greater, it is known that no such formulas exist. For example, consider the function

\displaystyle f(x)=x^{5}+8x^{4}+4x^{3}-2x-7.

No formula exists that allows us to find the solutions of $\displaystyle f(x)=0$ . Similar difficulties exist for nonpolynomial functions. For example, consider the task of finding solutions of $\displaystyle\tan(x)-x=0$ . No simple formula exists for the solutions of this equation. In cases such as these, we can use Newton’s method to approximate the roots.

Newton’s method makes use of the following idea to approximate the solutions of $\displaystyle f(x)=0$ . By sketching a graph of $\displaystyle f$ , we can estimate a root of $\displaystyle f(x)=0$ . Let’s call this estimate $\displaystyle x_{0}$ . We then draw the tangent line to $\displaystyle f$ at $\displaystyle x_{0}$ . If $\displaystyle f^{\prime}(x_{0})\neq 0$ , this tangent line intersects the $\displaystyle x$ -axis at some point $\displaystyle(x_{1},0)$ . Now let $\displaystyle x_{1}$ be the next approximation to the actual root. Typically, $\displaystyle x_{1}$ is closer than $\displaystyle x_{0}$ to an actual root. Next we draw the tangent line to $\displaystyle f$ at $\displaystyle x_{1}$ . If $\displaystyle f^{\prime}(x_{1})\neq 0$ , this tangent line also intersects the $\displaystyle x$ -axis, producing another approximation, $\displaystyle x_{2}$ . We continue in this way, deriving a list of approximations: $\displaystyle x_{0},x_{1},x_{2},\ldots$ . Typically, the numbers $\displaystyle x_{0},x_{1},x_{2},\ldots$ quickly approach an actual root $\displaystyle x*$ , as shown in the following figure.

Figure 4.48: The approximations

\displaystyle x_{0},x_{1},x_{2},\ldots

approach the actual root

\displaystyle x*

. The approximations are derived by looking at tangent lines to the graph of

\displaystyle f

Now let’s look at how to calculate the approximations $\displaystyle x_{0},x_{1},x_{2},\ldots$ . If $\displaystyle x_{0}$ is our first approximation, the approximation $\displaystyle x_{1}$ is defined by letting $\displaystyle(x_{1},0)$ be the $\displaystyle x$ -intercept of the tangent line to $\displaystyle f$ at $\displaystyle x_{0}$ . The equation of this tangent line is given by

\displaystyle y=f(x_{0})+f^{\prime}(x_{0})(x-x_{0}).

Therefore, $\displaystyle x_{1}$ must satisfy

\displaystyle f(x_{0})+f^{\prime}(x_{0})(x_{1}-x_{0})=0.

Solving this equation for $\displaystyle x_{1}$ , we conclude that

\displaystyle x_{1}=x_{0}-\frac{f(x_{0})}{f^{\prime}(x_{0})}.

Similarly, the point $\displaystyle(x_{2},0)$ is the $\displaystyle x$ -intercept of the tangent line to $\displaystyle f$ at $\displaystyle x_{1}$ . Therefore, $\displaystyle x_{2}$ satisfies the equation

\displaystyle x_{2}=x_{1}-\frac{f(x_{1})}{f^{\prime}(x_{1})}.

In general, for $\displaystyle n>0,x_{n}$ satisfies

x_{n}=x_{n-1}-\frac{f(x_{n-1})}{f^{\prime}(x_{n-1})}.

(4.5)

Next we see how to make use of this technique to approximate the root of the polynomial $\displaystyle f(x)=x^{3}-3x+1$ .

Example 4.7.1 (Finding a Root of a Polynomial).

Use Newton’s method to approximate a root of $\displaystyle f(x)=x^{3}-3x+1$ in the interval $\displaystyle[1,2]$ . Let $\displaystyle x_{0}=2$ and find $\displaystyle x_{1},x_{2},x_{3},x_{4}$ , and $\displaystyle x_{5}$ .

Solution: From Figure 4.49, we see that $\displaystyle f$ has one root over the interval $\displaystyle(1,2)$ . Therefore $\displaystyle x_{0}=2$ seems like a reasonable first approximation. To find the next approximation, we use Equation 4.5. Since $\displaystyle f(x)=x^{3}-3x+1$ , the derivative is $\displaystyle f^{\prime}(x)=3x^{2}-3$ . Using Equation 4.5 with $\displaystyle n=1$ (and a calculator that displays $\displaystyle 10$ digits), we obtain

\displaystyle x_{1}=x_{0}-\frac{f(x_{0})}{f^{\prime}(x_{0})}=2-\frac{f(2)}{f^{% \prime}(2)}=2-\frac{3}{9}\approx 1.666666667.

To find the next approximation, $\displaystyle x_{2}$ , we use Equation 4.5 with $\displaystyle n=2$ and the value of $\displaystyle x_{1}$ stored on the calculator. We find that

\displaystyle x_{2}=x_{1}=\frac{f(x_{1})}{f^{\prime}(x_{1})}\approx 1.548611111.

Continuing in this way, we obtain the following results:

	$\displaystyle x_{1}\approx 1.666666667$
	$\displaystyle x_{2}\approx 1.548611111$
	$\displaystyle x_{3}\approx 1.532390162$
	$\displaystyle x_{4}\approx 1.532088989$
	$\displaystyle x_{5}\approx 1.532088886$
	$\displaystyle x_{6}\approx 1.532088886.$

We note that we obtained the same value for $\displaystyle x_{5}$ and $\displaystyle x_{6}$ . Therefore, any subsequent application of Newton’s method will most likely give the same value for $\displaystyle x_{n}$ .

Figure 4.49: The function

\displaystyle f(x)=x^{3}-3x+1

has one root over the interval

\displaystyle[1,2]

Checkpoint 4.7.1.

Letting $\displaystyle x_{0}=0$ , let’s use Newton’s method to approximate the root of $\displaystyle f(x)=x^{3}-3x+1$ over the interval $\displaystyle[0,1]$ by calculating $\displaystyle x_{1}$ and $\displaystyle x_{2}$ .

Hint: Use Equation 4.5.

Newton’s method can also be used to approximate square roots. Here we show how to approximate $\displaystyle\sqrt{2}$ . This method can be modified to approximate the square root of any positive number.

Example 4.7.2 (Finding a Square Root).

Use Newton’s method to approximate $\displaystyle\sqrt{2}$ (Figure 4.50). Let $\displaystyle f(x)=x^{2}-2$ , let $\displaystyle x_{0}=2$ , and calculate $\displaystyle x_{1},x_{2},x_{3},x_{4},x_{5}$ . (We note that since $\displaystyle f(x)=x^{2}-2$ has a zero at $\displaystyle\sqrt{2}$ , the initial value $\displaystyle x_{0}=2$ is a reasonable choice to approximate $\displaystyle\sqrt{2}$ .)

Solution: For $\displaystyle f(x)=x^{2}-2,f^{\prime}(x)=2x$ . From Equation 4.5, we know that

	$\displaystyle x_{n}$	$\displaystyle=x_{n-1}-\frac{f(x_{n-1})}{f^{\prime}(x_{n-1})}$
		$\displaystyle=x_{n-1}-\frac{x^{2}_{n-1}-2}{2x_{n-1}}$
		$\displaystyle=\frac{1}{2}x_{n-1}+\frac{1}{x_{n-1}}$
		$\displaystyle=\frac{1}{2}\left(x_{n-1}+\frac{2}{x_{n-1}}\right).$

Therefore,

	$\displaystyle x_{1}=\frac{1}{2}\left(x_{0}+\frac{2}{x_{0}}\right)=\frac{1}{2}% \left(2+\frac{2}{2}\right)=1.5$
	$\displaystyle x_{2}=\frac{1}{2}\left(x_{1}+\frac{2}{x_{1}}\right)=\frac{1}{2}% \left(1.5+\frac{2}{1.5}\right)\approx 1.416666667.$

Continuing in this way, we find that

	$\displaystyle x_{1}=1.5$
	$\displaystyle x_{2}\approx 1.416666667$
	$\displaystyle x_{3}\approx 1.414215686$
	$\displaystyle x_{4}\approx 1.414213562$
	$\displaystyle x_{5}\approx 1.414213562.$

Since we obtained the same value for $\displaystyle x_{4}$ and $\displaystyle x_{5}$ , it is unlikely that the value $\displaystyle x_{n}$ will change on any subsequent application of Newton’s method. We conclude that $\displaystyle\sqrt{2}\approx 1.414213562$ .

Figure 4.50: We can use Newton’s method to find

\displaystyle\sqrt{2}

Checkpoint 4.7.2.

Use Newton’s method to approximate $\displaystyle\sqrt{3}$ by letting $\displaystyle f(x)=x^{2}-3$ and $\displaystyle x_{0}=3$ . Find $\displaystyle x_{1}$ and $\displaystyle x_{2}$ .

Hint: For $\displaystyle f(x)=x^{2}-3$ , Equation 4.5 reduces to $\displaystyle x_{n}=\frac{x_{n-1}}{2}+\frac{3}{2x_{n-1}}$ .

When using Newton’s method, each approximation after the initial guess is defined in terms of the previous approximation by using the same formula. In particular, by defining the function

\displaystyle F(x)=x-\left[\frac{f(x)}{f^{\prime}(x)}\right],

we can rewrite Equation 4.5 as $\displaystyle x_{n}=F(x_{n-1})$ . This type of process, where each $\displaystyle x_{n}$ is defined in terms of $\displaystyle x_{n-1}$ by repeating the same function, is an example of an iterative process. Shortly, we examine other iterative processes. First, let’s look at the reasons why Newton’s method could fail to find a root.

4.7.2 Failures of Newton’s Method

Typically, Newton’s method is used to find roots fairly quickly. However, things can go wrong. Some reasons why Newton’s method might fail include the following:

(a)

At one of the approximations $\displaystyle x_{n}$ , the derivative $\displaystyle f^{\prime}$ is zero at $\displaystyle x_{n}$ , but $\displaystyle f(x_{n})\neq 0$ . As a result, the tangent line of $\displaystyle f$ at $\displaystyle x_{n}$ does not intersect the $\displaystyle x$ -axis. Therefore, we cannot continue the iterative process.
(b)

The approximations $\displaystyle x_{0},x_{1},x_{2},\ldots$ may approach a different root. If the function $\displaystyle f$ has more than one root, it is possible that our approximations do not approach the one for which we are looking, but approach a different root (see Figure 4.51). This event most often occurs when we do not choose the approximation $\displaystyle x_{0}$ close enough to the desired root.
(c)

The approximations may fail to approach a root entirely. In Example 4.7.3, we provide an example of a function and an initial guess $\displaystyle x_{0}$ such that the successive approximations never approach a root because the successive approximations continue to alternate back and forth between two values.

Figure 4.51: If the initial guess

\displaystyle x_{0}

is too far from the root sought, it may lead to approximations that approach a different root.

Example 4.7.3 (When Newton’s Method Fails).

Consider the function $\displaystyle f(x)=x^{3}-2x+2$ . Let $\displaystyle x_{0}=0$ . Show that the sequence $\displaystyle x_{1},x_{2},\ldots$ fails to approach a root of $\displaystyle f$ .

Solution: For $\displaystyle f(x)=x^{3}-2x+2$ , the derivative is $\displaystyle f^{\prime}(x)=3x^{2}-2$ . Therefore,

\displaystyle x_{1}=x_{0}-\frac{f(x_{0})}{f^{\prime}(x_{0})}=0-\frac{f(0)}{f^{% \prime}(0)}=-\frac{2}{-2}=1.

In the next step,

\displaystyle x_{2}=x_{1}-\frac{f(x_{1})}{f^{\prime}(x_{1})}=1-\frac{f(1)}{f^{% \prime}(1)}=1-\frac{1}{1}=0.

Consequently, the numbers $\displaystyle x_{0},x_{1},x_{2},\ldots$ continue to bounce back and forth between $\displaystyle 0$ and $\displaystyle 1$ and never get closer to the root of $\displaystyle f$ which is over the interval $\displaystyle[-2,-1]$ (see Figure 4.52). Fortunately, if we choose an initial approximation $\displaystyle x_{0}$ closer to the actual root, we can avoid this situation.

Figure 4.52: The approximations continue to alternate between

\displaystyle 0

and

\displaystyle 1

and never approach the root of

\displaystyle f

Checkpoint 4.7.3.

For $\displaystyle f(x)=x^{3}-2x+2$ , let $\displaystyle x_{0}=-1.5$ and find $\displaystyle x_{1}$ and $\displaystyle x_{2}$ .

Hint: Use Equation 4.5.

From Example 4.7.3, we see that Newton’s method does not always work. However, when it does work, the sequence of approximations approaches the root very quickly. Discussions of how quickly the sequence of approximations approach a root found using Newton’s method are included in texts on numerical analysis.

4.7.3 Other Iterative Processes

As mentioned earlier, Newton’s method is a type of iterative process. We now look at an example of a different type of iterative process.

Consider a function $\displaystyle F$ and an initial number $\displaystyle x_{0}$ . Define the subsequent numbers $\displaystyle x_{n}$ by the formula $\displaystyle x_{n}=F(x_{n-1})$ . This process is an iterative process that creates a list of numbers $\displaystyle x_{0},x_{1},x_{2},\ldots,x_{n},\ldots$ . This list of numbers may approach a finite number $\displaystyle x*$ as $\displaystyle n$ gets larger, or it may not. In Example 4.7.4, we see an example of a function $\displaystyle F$ and an initial guess $\displaystyle x_{0}$ such that the resulting list of numbers approaches a finite value.

Example 4.7.4 (Finding a Limit for an Iterative Process).

Let $\displaystyle F(x)=\frac{1}{2}x+4$ and let $\displaystyle x_{0}=0$ . For all $\displaystyle n\geq 1$ , let $\displaystyle x_{n}=F(x_{n-1})$ . Find the values $\displaystyle x_{1},x_{2},x_{3},x_{4},x_{5}$ . Make a conjecture about what happens to this list of numbers $\displaystyle x_{1},x_{2},x_{3}\ldots,x_{n},\ldots$ as $\displaystyle n\to\infty$ . If the list of numbers $\displaystyle x_{1},x_{2},x_{3},\ldots$ approaches a finite number $\displaystyle x*$ , then $\displaystyle x*$ satisfies $\displaystyle x*=F(x*)$ , and $\displaystyle x*$ is called a fixed point of $\displaystyle F$ .

Solution: If $\displaystyle x_{0}=0$ , then

	$\displaystyle x_{1}=\frac{1}{2}(0)+4=4$
	$\displaystyle x_{2}=\frac{1}{2}(4)+4=6$
	$\displaystyle x_{3}=\frac{1}{2}(6)+4=7$
	$\displaystyle x_{4}=\frac{1}{2}(7)+4=7.5$
	$\displaystyle x_{5}=\frac{1}{2}(7.5)+4=7.75$
	$\displaystyle x_{6}=\frac{1}{2}(7.75)+4=7.875$
	$\displaystyle x_{7}=\frac{1}{2}\left(7.875\right)+4=7.9375$
	$\displaystyle x_{8}=\frac{1}{2}(7.9375)+4=7.96875$
	$\displaystyle x_{9}=\frac{1}{2}\left(7.96875\right)+4=7.984375.$

From this list, we conjecture that the values $\displaystyle x_{n}$ approach $\displaystyle 8$ .

Figure 4.53 provides a graphical argument that the values approach $\displaystyle 8$ as $\displaystyle n\to\infty$ . Starting at the point $\displaystyle(x_{0},x_{0})$ , we draw a vertical line to the point $\displaystyle(x_{0},F(x_{0}))$ . The next number in our list is $\displaystyle x_{1}=F(x_{0})$ . We use $\displaystyle x_{1}$ to calculate $\displaystyle x_{2}$ . Therefore, we draw a horizontal line connecting $\displaystyle(x_{0},x_{1})$ to the point $\displaystyle(x_{1},x_{1})$ on the line $\displaystyle y=x$ , and then draw a vertical line connecting $\displaystyle(x_{1},x_{1})$ to the point $\displaystyle(x_{1},F(x_{1}))$ . The output $\displaystyle F(x_{1})$ becomes $\displaystyle x_{2}$ . Continuing in this way, we could create an infinite number of line segments. These line segments are trapped between the lines $\displaystyle F(x)=\frac{x}{2}+4$ and $\displaystyle y=x$ . The line segments get closer to the intersection point of these two lines, which occurs when $\displaystyle x=F(x)$ . Solving the equation $\displaystyle x=\frac{x}{2}+4$ , we conclude they intersect at $\displaystyle x=8$ . Therefore, our graphical evidence agrees with our numerical evidence that the list of numbers $\displaystyle x_{0},x_{1},x_{2},\ldots$ approaches $\displaystyle x*=8$ as $\displaystyle n\to\infty$ .

Figure 4.53: This iterative process approaches the value

\displaystyle x*=8

Checkpoint 4.7.4.

Consider the function $\displaystyle F(x)=\frac{1}{3}x+6$ . Let $\displaystyle x_{0}=0$ and let $\displaystyle x_{n}=F(x_{n-1})$ for $\displaystyle n\geq 2$ . Find $\displaystyle x_{1},x_{2},x_{3},x_{4},x_{5}$ . Make a conjecture about what happens to the list of numbers $\displaystyle x_{1},x_{2},x_{3},\ldots x_{n},\ldots$ as $\displaystyle n\to\infty$ .

Hint: Consider the point where the lines $\displaystyle y=x$ and $\displaystyle y=F(x)$ intersect.

Key Concepts

•

Newton’s method approximates roots of $\displaystyle f(x)=0$ by starting with an initial approximation $\displaystyle x_{0}$ , then uses tangent lines to the graph of $\displaystyle f$ to create a sequence of approximations $\displaystyle x_{1},x_{2},x_{3},\ldots$ .
•

Typically, Newton’s method is an efficient method for finding a particular root. In certain cases, Newton’s method fails to work because the list of numbers $\displaystyle x_{0},x_{1},x_{2},\ldots$ does not approach a finite value or it approaches a value other than the root sought.
•

Any process in which a list of numbers $\displaystyle x_{0},x_{1},x_{2},\ldots$ is generated by defining an initial number $\displaystyle x_{0}$ and defining the subsequent numbers by the equation $\displaystyle x_{n}=F(x_{n-1})$ for some function $\displaystyle F$ is an iterative process. Newton’s method is an example of an iterative process, where the function $\displaystyle F(x)=x-\left[\frac{f(x)}{f^{\prime}(x)}\right]$ for a given function $\displaystyle f$ .

Glossary

iterative process: process in which a list of numbers $\displaystyle x_{0},x_{1},x_{2},x_{3}\ldots$ is generated by starting with a number $\displaystyle x_{0}$ and defining $\displaystyle x_{n}=F(x_{n-1})$ for $\displaystyle n\geq 1$
Newton’s method: method for approximating roots of $\displaystyle f(x)=0;$ using an initial guess $\displaystyle x_{0};$ each subsequent approximation is defined by the equation $\displaystyle x_{n}=x_{n-1}-\frac{f(x_{n-1})}{f^{\prime}(x_{n-1})}$