# Newton's Method for Finding Roots

Site: | Saylor Academy |

Course: | MA005: Calculus I |

Book: | Newton's Method for Finding Roots |

Printed by: | Guest user |

Date: | Tuesday, September 10, 2024, 10:37 PM |

## Description

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

## Newton's Method for Finding Roots

Newton's method is a process which can find roots of functions whose graphs cross or just kiss the x–axis. Although this method is a bit harder to apply than the Bisection Algorithm, it often finds roots that the Bisection Algorithm misses, and it usually
finds them faster.

Source: Dale Hoffman, https://s3.amazonaws.com/saylordotorg-resources/wwwresources/site/wp-content/uploads/2012/12/MA005-3.8-Newtons-Method.pdf

This work is licensed under a Creative Commons Attribution 3.0 License.

## Off on a Tangent

The basic idea of Newton's Method is remarkably simple and graphic (Fig. 1):

at a point on the graph of , the tangent line to the graph of "points toward" a root of , a place where the graph touches the -axis.

If we want to find a root of , all we need to do is pick a starting value , go up or down to the point on the graph of , build a tangent line there, and follow the tangent line to where it crosses the -axis, say at .

If is a root of , then we are done. If is not a root of , then is usually closer to the root than was, and we can repeat the process, using as our new starting point. Newton's method is an **iterative procedure**, that is, the output from one application of the method becomes the starting point for the next application.

Let's start with a differentiable function , (Fig. 2) whose roots we already know, , and illustrate how Newton's method works. First we pick some value for , say for this example, and move to the point on the graph of .

At , the graph of "points to" a location on the -axis which is closer to the root of (Fig. 3). We can calculate this location on the -axis by finding the equation of the line tangent to the graph of at the point and then finding where this tangent line intersects the -axis:

At the point , the line tangent to has slope , so the equation of the tangent line is . Setting , we can find where the tangent line crosses the -axis:

The point is closer to the actual root, but it certainly does not equal the actual root. If Newton's method stopped after one step with the estimate of , it would not be very useful. Instead, we can use this new value for , to repeat the procedure (Fig. 4:

(i) move to the point on the graph,

(ii) find the equation of the tangent line at the point :

(iii) find the new value where the tangent line intersects the -axis and call it

When we continue repeating this process, (Fig. 5) using each new estimate for the root of as the beginning point for calculating the next estimate, we get:

It only took 4 iterations to get an approximation of which is within of the exact value. One more iteration gives an approximation which has 16 correct digits. If we start with (or any negative number), then the values of approach

Fig. 6 shows the process for Newton's Method, starting with and graphically finding the locations on the -axis of , and .

**Practice 1: **Find where the tangent line to at intersects the -axis.

**Practice 2: **A starting point and a graph of are given in Fig. 7. Label the approximate locations of the next two points on the -axis which are found by Newton's method.

## 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 . For the starting point , the slope of the tangent line at the point is so the equation of the tangent line is . This line intersects the -axis when , so

is . This line intersects the -axis when , so and . Starting with and repeating this process we have ; starting with , we get and so on.

In general, if we start with , the line tangent to the graph of at the point intersects the -axis at the point , our new estimate for the root of .

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

(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 , the function at the beginning of this section, we have so

The new approximation, , is the average of the previous approximation, , and divided by the previous approximation, . Problem 16 asks you to show that this pattern, called Heron's method, approximates the square root of any positive number. Just replace the "" with the number whose square root you want.

**Example 1: **Use Newton's method to approximate the root(s) of . Solution: so

The graph of for (Fig. 8) indicates only one root of , and that root is near so pick Then Newton's method yields the values (the underlined digits agree with the exact root).

If we had picked , Newton's method would have required iterations to get digits of accuracy. If , then iterations are needed to get digits of accuracy. If we pick , then the values of are not close to the actual root after even iterations, . Picking a good value for can result in values of which get close to the root quickly. Picking a poor value for can result in 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" .**

**Practice 3: **Put and use Newton's method to find the first two iterates, and , for the function

**Example 2: **The function in Fig. 9 has roots at and . If we pick and apply Newton's method, which root do the iterates, the , approach?

Solution: The iterates of are labeled in Fig. 10. They are approaching the root at .

**Practice 4: **For the function in Fig. 11, which root do the iterates of Newton's method approach if (a)

## What Can Go Wrong?

When Newton's method works, it usually works very well and the values of the approach a root of 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 can be 0. Then we are trying to divide by 0 and is undefined. Geometrically, if , then the tangent line to the graph of at is horizontal and does not intersect the -axis at one point (Fig. 12). If , just pick another starting value and begin again. In practice, a second or third choice of usually succeeds.

There are two other less obvious difficulties that are not as easy to overcome - the values of the iterates 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 and use Newton's method to find the first two iterates, and , for the function .

Solution: This is the same function as in the previous Practice problem, but we are using a different starting value for so

which is the same as , so and . The values of 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 and , verify that . Also try , and verify that the same pattern holds: . Graph and explain why the Newton's method iterates get farther and farther away from the root at .

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.

## Chaotic Behavior and Newton's Method

An algorithm leads to chaotic behavior if two starting points which are close together generate iterates which are sometimes far apart and sometimes close together: is small but is large for lots (infinitely many) of values of and is small for lots of values of .

The iterates of the next simple algorithm exhibit chaotic behavior.

**A Simple Chaotic Algorithm: **Starting with any number between and , double the number and keep the fractional part of the result: is the fractional part of is the fractional part of , and in general, .

If , then the iterates of the algorithm are (= fractional part of The iterates for two other starting values close to are given below as well as the iterates of and :

There are starting values as close together as we want whose iterates are far apart infinitely often. Many physical, biological, and business phenomena exhibit chaotic behavior. Atoms can start out within inches of each other and several weeks later be hundreds of miles apart. The idea that small initial differences can lead to

dramatically diverse outcomes is sometimes called the "Butterfly Effect" from the title of a talk ("Predictability: Does the Flap of a Butterfly's Wings in Brazil Set Off a Tornado in Texas?") given by Edward Lorenz, one of the first

people to investigate chaos. The "butterfly effect" has important implications about the possibility, or rather the impossibility, of accurate long–range weather forecasting. Chaotic behavior is also an important aspect of studying turbulent air and water flows, the incidence and spread of diseases, and even the fluctuating behavior of the stock market.

Newton's method often exhibits chaotic behavior, and, since it is a relatively easy to study, is often used as a model to study the properties of chaotic behavior. If we use Newton's method to approximate the roots of (with roots and ), then starting points which are very close together can have iterates which converge to different roots. The iterates of and converge to the roots and , respectively. The iterates of the middle point converge to the root , and the iterates of another nearby point, , simply cycle between and and do not converge at all.

**Practice 6: **Find the first 4 Newton's method iterates of and for . Try two other starting values very close to (but not equal to ) and find their first iterates. Use the graph of to explain how starting points so close together can quickly have iterates so far apart.

## Practice Problem Answers

**Practice 1:** so and the slope of the tangent line at the point is . Using the point-slope form for the equation of a line, the equation of the tangent line is or .

The -coordinate of a point on the -axis is 0 so we need to put and solve the linear equation for so .

The line tangent to the graph of at the point intersects the -axis at the point .

**Practice 2: **The approximate locations of and are shown in Fig. 20.

**Practice 4: **Fig. 21 shows the first iteration of Newton's Method for , and .

If , the iterates approach the root at .

If , the iterates approach the root at .

If , the iterates approach the root at .

The graph of the cube root has a shape similar to Fig. 14, and the behavior of the iterates is similar to the pattern in that figure. Unless (the only root of ) the iterates alternate in sign and double in magnitude with each iteration: they get progressively farther from the root with each iteration.