APEX Newton’s Method

Section 4.1 Newton’s Method

Solving equations is one of the most important things we do in mathematics, yet we are surprisingly limited in what we can solve analytically. For instance, equations as simple as

x^{5} + x + 1 = 0

\cos (x) = x

cannot be solved by algebraic methods in terms of familiar functions. Fortunately, there are methods that can give us approximate solutions to equations like these. These methods can usually give an approximation correct to as many decimal places as we like. In Section 1.5 we learned about the Bisection Method. This section focuses on another technique (which generally works faster), called Newton’s Method.

🔗

Newton’s Method is built around tangent lines. The main idea is that if

x

is sufficiently close to a root of

f (x),

then the tangent line to the graph at

(x, f (x))

will cross the

x

-axis at a point closer to the root than

x .

🔗

We start Newton’s Method with an initial guess about roughly where the root is. Call this

x_{0} .

(See Figure 4.1.1.(a).) Draw the tangent line to the graph at

(x_{0}, f (x_{0}))

and see where it meets the

x

-axis. Call this point

x_{1} .

Then repeat the process — draw the tangent line to the graph at

(x_{1}, f (x_{1}))

and see where it meets the

x

-axis. (See Figure 4.1.1.(b).) Call this point

x_{2} .

Repeat the process again to get

x_{3},

x_{4},

etc. This sequence of points will often converge rather quickly to a root of

f .

A tangent line is drawn to the graph at (x_0,f(x_0)) and and meets on the x-axis at point x_1. — (a)

A tangent line is drawn to the graph at (x_1,f(x_1)) and and meets on the x-axis at point x_2. — (a)

🔗

We can use this geometric process to create an algebraic process. Let’s look at how we found

x_{1} .

We started with the tangent line to the graph at

(x_{0}, f (x_{0})) .

The slope of this tangent line is

f^{'} (x_{0})

and the equation of the line is

y = f^{'} (x_{0}) (x - x_{0}) + f (x_{0}) .

🔗

This line crosses the

x

-axis when

y = 0,

and the

x

-value where it crosses is what we called

x_{1} .

So let

y = 0

and replace

x

with

x_{1},

giving the equation:

0 = f^{'} (x_{0}) (x_{1} - x_{0}) + f (x_{0}) .

🔗

Now solve for

x_{1} :

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

🔗

Since we repeat the same geometric process to find

x_{2}

from

x_{1},

we have

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

🔗

In general, given an approximation

x_{n},

we can find the next approximation,

x_{n + 1}

as follows:

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

🔗

We summarize this process as follows.

🔗

Key Idea 4.1.2. Newton’s Method.

🔗

Let

f

be a differentiable function on an interval

I

with a root in

I .

To approximate the value of the root, accurate to

d

decimal places:

🔗

Choose a value $x_{0}$ as an initial approximation of the root. (This is often done by looking at a graph of $f .$ )
Create successive approximations iteratively; given an approximation $x_{n},$ compute the next approximation $x_{n + 1}$ as

$x_{n + 1} = x_{n} - \frac{f (x_{n})}{f^{'} (x_{n})} .$
Stop the iterations when successive approximations do not differ in the first $d$ places after the decimal point.

🔗

Let’s practice Newton’s Method with a concrete example.

🔗

Example 4.1.3. Using Newton’s Method.

🔗

Approximate the real root of

x^{3} - x^{2} - 1 = 0,

accurate to the first three places after the decimal, using Newton’s Method and an initial approximation of

x_{0} = 1 .

Solution.

To begin, we compute

f^{'} (x) = 3 x^{2} - 2 x .

Then we apply the Newton’s Method algorithm, outlined in Key Idea 4.1.2.

$\begin{aligned} x_{1} & = 1 - \frac{f (1)}{f^{'} (1)} \\ = 1 - \frac{1^{3} - 1^{2} - 1}{3 \cdot 1^{2} - 2 \cdot 1} \\ = 2 \end{aligned}$
$\begin{aligned} x_{2} & = 2 - \frac{f (2)}{f^{'} (2)} \\ = 2 - \frac{2^{3} - 2^{2} - 1}{3 \cdot 2^{2} - 2 \cdot 2} \\ = 1.625 \end{aligned}$
$\begin{aligned} x_{3} & = 1.625 - \frac{f (1.625)}{f^{'} (1.625)} \\ = 1.625 - \frac{{1.625}^{3} - {1.625}^{2} - 1}{3 \cdot {1.625}^{2} - 2 \cdot 1.625} \\ \approx 1.48579 \end{aligned}$
$\begin{aligned} x_{4} & = 1.48579 - \frac{f (1.48579)}{f^{'} (1.48579)} \\ \approx 1.46596 \end{aligned}$
$\begin{aligned} x_{5} & = 1.46596 - \frac{f (1.46596)}{f^{'} (1.46596)} \\ \approx 1.46557 \end{aligned}$

We performed five iterations of Newton’s Method to find a root accurate to the first three places after the decimal; our final approximation is

1.465 .

The exact value of the root, to six decimal places, is

1.465571;

It turns out that our

x_{5}

is accurate to more than just three decimal places.

A graph of

f (x)

is given in Figure 4.1.4. We can see from the graph that our initial approximation of

x_{0} = 1

was not particularly accurate; a closer guess would have been

x_{0} = 1.5 .

Our choice was based on ease of initial calculation, and shows that Newton’s Method can be robust enough that we do not have to make a very accurate initial approximation.

A cubic graph features a curve with two turning points. — Figure 4.1.4. A graph of $f (x) = x^{3} - x^{2} - 1$ in Example 4.1.3

🔗

We can automate this process on a calculator that has an ANS key that returns the result of the previous calculation. Start by pressing 1 and then Enter. (We have just entered our initial guess,

x_{0} = 1 .

) Now compute

ANS - \frac{f (ANS)}{f^{'} (ANS)}

🔗

by entering the following and repeatedly press the Enter key.

ANS-(ANS^3-ANS^2-1)/(3*ANS^2-2*ANS)

🔗

Each time we press the Enter key, we are finding the successive approximations,

x_{1},

x_{2},

…, and each one is getting closer to the root. In fact, once we get past around

x_{7}

or so, the approximations don’t appear to be changing. They actually are changing, but the change is far enough to the right of the decimal point that it doesn’t show up on the calculator’s display. When this happens, we can be pretty confident that we have found an accurate approximation.

🔗

Using a calculator in this manner makes the calculations simple; many iterations can be computed very quickly.

🔗

Example 4.1.5. Using Newton’s Method to find where functions intersect.

🔗

Use Newton’s Method to approximate a solution to

\cos (x) = x,

accurate to five places after the decimal.

Solution.

Newton’s Method provides a method of solving

f (x) = 0;

it is not (directly) a method for solving equations like

f (x) = g (x) .

However, this is not a problem; we can rewrite the latter equation as

f (x) - g (x) = 0

and then use Newton’s Method.

So we rewrite

\cos (x) = x

\cos (x) - x = 0 .

Written this way, we are finding a root of

f (x) = \cos (x) - x .

We compute

f^{'} (x) = - \sin (x) - 1 .

Next we need a starting value,

x_{0} .

Consider Figure 4.1.6, where

f (x) = \cos (x) - x

is graphed. It seems that

x_{0} = 0.75

is pretty close to the root, so we will use that as our

x_{0} .

(The figure also shows the graphs of

y = \cos (x)

and

y = x .

Note how they intersect at the same

x

value as when

f (x) = 0 .

)

A graph of f(x) = cos x - x used to find an initial approximation of its root. — Figure 4.1.6. A graph of $f (x) = \cos (x) - x$ used to find an initial approximation of its root

We now compute

x_{1},

x_{2},

etc. The formula for

x_{1}

\begin{aligned} x_{1} & = 0.75 - \frac{\cos (0.75) - 0.75}{- \sin (0.75) - 1} \\ \approx 0.7391111388 . \end{aligned}

Apply Newton’s Method again to find

x_{2} :

\begin{aligned} x_{2} & = 0.7391111388 - \frac{\cos (0.7391111388) - 0.7391111388}{- \sin (0.7391111388) - 1} \\ \approx 0.7390851334 . \end{aligned}

We can continue this way, but it is really best to automate this process. On a calculator with an ANS key, we would start by entering 0.75, then Enter, inputting our initial approximation. We then enter:

ANS - (cos(ANS)-ANS)/(-sin(ANS)-1)

Repeatedly pressing the Enter key gives successive approximations. We quickly find:

\begin{aligned} x_{3} & = 0.7390851332 \\ x_{4} & = 0.7390851332 . \end{aligned}

Our approximations

x_{2}

and

x_{3}

did not differ for at least the first five places after the decimal, so we could have stopped. However, using our calculator in the manner described is easy, so finding

x_{4}

was not hard. It is interesting to see how we found an approximation, accurate to as many decimal places as our calculator displays, in just four iterations.

🔗

If you know how to program, you can translate the following pseudocode into your favorite language to perform the computation in this problem.

x = 0.75
while true
    oldx = x
    x = x - (cos(x)-x)/(-sin(x)-1)
    print x
    if abs(x-oldx) < 0.0000000001
        break

🔗

This code calculates

x_{1},

x_{2},

etc., storing each result in the variable x. The previous approximation is stored in the variable oldx. We continue looping until the difference between two successive approximations, abs(x-oldx), is less than some small tolerance, in this case, 0.0000000001.

🔗

Convergence of Newton’s Method.

🔗

What should one use for the initial guess,

x_{0} ?

Generally, the closer to the actual root the initial guess is, the better. However, some initial guesses should be avoided. For instance, consider Example 4.1.3 where we sought the root to

f (x) = x^{3} - x^{2} - 1 .

Choosing

x_{0} = 0

would have been a particularly poor choice. Consider Figure 4.1.7, where

f (x)

is graphed along with its tangent line at

x = 0 .

Since

f^{'} (0) = 0,

the tangent line is horizontal and does not intersect the

x

-axis. Graphically, we see that Newton’s Method fails.

A cubic graph features an "S" shaped curve with two turning points. — 🔗
Figure 4.1.7. A graph of $f (x) = x^{3} - x^{2} - 1,$ showing why an initial approximation of $x_{0} = 0$ with Newton’s Method fails

🔗

We can also see analytically that it fails. Since

x_{1} = 0 - \frac{f (0)}{f^{'} (0)}

🔗

and

f^{'} (0) = 0,

we see that

x_{1}

is not well defined.

🔗

This problem can also occur if, for instance, it turns out that

f^{'} (x_{5}) = 0 .

Adjusting the initial approximation

x_{0}

by a very small amount will likely fix the problem.

🔗

It is also possible for Newton’s Method to not converge while each successive approximation is well defined. Consider

f (x) = x^{1 / 3},

as shown in Figure 4.1.8. It is clear that the root is

x = 0,

but let’s approximate this with

x_{0} = 0.1 .

Figure 4.1.8.(a) shows graphically the calculation of

x_{1};

notice how it is farther from the root than

x_{0} .

Figure 4.1.8.(b) and Figure 4.1.8.(c) show the calculation of

x_{2}

and

x_{3},

which are even farther away; our successive approximations are getting worse. (It turns out that in this particular example, each successive approximation is twice as far from the true answer as the previous approximation.)

The graph illustrates the cube root function with initial guess x_0 as 0.1 — (a)

The graph illustrates the cube root function with point x_1 — (a)

🔗

There is no “fix” to this problem; Newton’s Method simply will not work and another method must be used. (In this case the particular reason Newton’s Method fails is that the tangent line is vertical at the root).

🔗

While Newton’s Method does not always work, it does work “most of the time,” and it is generally very fast. Once the approximations get close to the root, Newton’s Method can as much as double the number of correct decimal places with each successive approximation. A course in Numerical Analysis will introduce the reader to more iterative root finding methods, as well as give greater detail about the strengths and weaknesses of Newton’s Method.

🔗

True
False

🔗

Given a function

f (x),

Newton’s Method produces an exact solution to

f (x) = 0 .

🔗

2.

🔗

True
False

🔗

In order to get a solution to

f (x) = 0

accurate to

d

places after the decimal, at least

d + 1

iterations of Newton’s Method must be used.

🔗

Problems

🔗

Exercise Group.

🔗

The roots of the function

f (x)

are known or are easily found. Use five iterations of Newton’s Method with the given initial approximation to approximate the root. Compare it to the known value of the root.

🔗

3.

🔗

f (x) = \cos (x),

x_{0} = 1.5

🔗

4.

🔗

f (x) = \sin (x),

x_{0} = 1

🔗

5.

🔗

f (x) = x^{2} + x - 2,

x_{0} = 0

🔗

6.

🔗

f (x) = x^{2} - 2,

x_{0} = 1.5

🔗

7.

🔗

f (x) = \ln (x),

x_{0} = 2

🔗

8.

🔗

f (x) = x^{3} - x^{2} + x - 1,

x_{0} = 2

🔗

Exercise Group.

🔗

Use Newton’s Method to approximate all roots of the given function accurate to three places after the decimal. If an interval is given, find only the roots that lie within that interval. Use technology to obtain good initial approximations.

🔗

9.

🔗

f (x) = x^{3} + 5 x^{2} - x - 1

🔗

10.

🔗

f (x) = x^{4} + 2 x^{3} - 7 x^{2} - x + 5

🔗

11.

🔗

f (x) = x^{17} - 2 x^{13} - 10 x^{8} + 10

(- 2, 2)

🔗

12.

🔗

f (x) = x^{2} \cos (x) + (x - 1) \sin (x)

(- 3, 3)

🔗

Exercise Group.

🔗

Use Newton’s Method to approximate when the given functions are equal, accurate to 3 places after the decimal. Use technology to obtain good initial approximations.

🔗

13.

🔗

f (x) = x^{2},

g (x) = \cos (x)

🔗

14.

🔗

f (x) = x^{2} - 1,

g (x) = \sin (x)

🔗

15.

🔗

f (x) = e^{x^{2}},

g (x) = \cos (x)

🔗

16.

🔗

f (x) = x,

g (x) = \tan (x)

[- 6, 6]

🔗

17.

🔗

Why does Newton’s Method fail in finding a root of

f (x) = x^{3} - 3 x^{2} + x + 3

when

x_{0} = 1 ?

🔗

18.

🔗

Why does Newton’s Method fail in finding a root of

f (x) = - 17 x^{4} + 130 x^{3} - 301 x^{2} + 156 x + 156

when

x_{0} = 1 ?

Prev Top Next

Section 4.1 Newton’s Method

Key Idea 4.1.2. Newton’s Method.

Example 4.1.3. Using Newton’s Method.

Example 4.1.5. Using Newton’s Method to find where functions intersect.

Convergence of Newton’s Method.

Exercises Exercises

Terms and Concepts

1.

2.

Problems

Exercise Group.

3.

4.

5.

6.

7.

8.

Exercise Group.

9.

10.

11.

12.

Exercise Group.

13.

14.

15.

16.

17.

18.