**Chapter 15: Newton's Method**

Suppose you have a function f(x), and you want to find as accurately as possible where it crosses the x-axis; in other words, you want to solve f(x) = 0. Suppose you know of no way to find an exact solution by any algebraic procedure. Newton's method is a way to find a solution to the equation to as many decimal places as you want. It is what is called an " iterative procedure ", meaning that it can be repeated again and again to get an answer of greater and greater accuracy. Iterative procedures like Newton's method are well suited to programming for a computer.

**The Steps in Newton's Method**

1. We start with a rough guess, which we call
.

2. Starting at the point
on the x-axis, we go up to the curve, hitting it at the point (
).

3.Now we slide down the
**tangent line**
to the curve at (
), and take the point where this tangent line hits the x-axis as our improved estimate for the desired x-value. Call this value
. (See the diagram below.)

The tangent line has slope
and passes through the points (
) and (
). This gives the equation:

=
or solving
=

4. Replace
by
and repeat as often as needed.

Thus we will produce a sequence of guesses
, ... and

hopefully these will get closer and closer to a root.

The main questions are how often do we need to do this and will it actually give the right answer. First note that if we land on a root, i.e.
, then
and thus, we can quit if we have
. In general, it makes sense to keep track of the difference between
and
and quit when the difference gets smaller than the desired accuracy.

If our function has several roots and if we start close to a root, then the Newton's Method can lead us astray and take us to some other root. Usually this happens because the denominator in our formula
is small and this causes
to be far away from
. In an extreme case, we could have
and
running off to infinity! It is also possible to create situations where
and so we get into an infinite loop! This is easy to avoid, since a slight change in
will usually get us out of this situation. We will illustrate these peculiarities in the exercises below. In general, Newton's method is reliable when the derivative is well defined and does not become too small in the region of interest.

**code for Newton method diagram**

A less wordy description of the process is to use the formulas:

;

;

,

,

... etc.

How do we know when we are close enough? Two things happen: (1) when we plug our approximate value into f(x) we get something very near zero, and (2) our successive approximations and are very close together. For example, if we want three decimal places of accuracy, then once we have two successive approximations which agree out to three decimal places, we need go no further. In the homework and exam problems, you will usually be told how many iterations to perform: "one iteration" means finding , "two iterations" means finding , and so on. If, on the other hand, the directions specify the desired accuracy ("three decimal places," for example), then just keep iterating Newton's method until the only changes in your value from one iteration to the next occur beyond the decimal places needed.

The first step is to set up the function we want to equal zero. We set , since is a root of that function. Since we know , we can make a rough guess of . We are now ready to apply the formula for Newton's method. Here is, of course, . We obtain:

= .

Actually, is the same value we would have obtained using the tangent line approximation. But with the tangent line approximation, if our approximate value isn't good enough, there is nothing further we can do. However, with Newton's method we can improve this approximate value 10.1 to . That is, we successively compute:

=
;

=
.

Thus,
.... If we computed
, etc., we would get the same as
out to 8 places past the decimal point.

**STEPS IN A NEWTON METHOD STORY PROBLEM**

1. Decide what equation you want to solve, and what variable is playing the role of x.

2. Simplify algebraically if you can (dividing out constants, clearing denominators).

3. Bring everything to one side of the = , so you have f(x) = 0.

4. Apply Newton's method for the required number of iterations.

**Example 2:**
Suppose that the material you are using to manufacture marbles costs 1.0 cent/
, and the coating that is painted on the surface costs 0.15 cent/
. Find the radius of the
marbles
if you want to spend 0.3 cent per marble on the material and coating. Use Newton's method with one iteration, and take 0.3 inch as a rough guess for the radius.

We first write out the condition on the total cost, using the formulas 4/ 3 for the volume and for the surface area of a marble: . In Newton's method we need our equation in the form f(x) = 0 (rather, f(r) = 0 in this problem), and this means bringing everything over to the left of the equal sign. In addition, for convenience we'll divide through by the coefficient of , thereby obtaining: f(r) = . Notice that this is a third degree equation. A third degree equation can be solved algebraically, but the formula is much more complicated than the quadratic formula. If you want an approximate answer, then Newton's method is much faster. We use the Newton's method formula with x replaced by r, and with . Here . We obtain:

= = 0.3076 inch.

**Example 3:**
Recall the example of the path of a
baton
's tip. From the

picture of the trajectory it's clear that the tip reaches its highest point at roughly 7/20 = 0.35 sec. Find to several more decimal places the time when this peak is reached, and find what the maximum height is. (Note: In reality, of course, it is pointless to find something like this to such a great accuracy, since our model for the physical situation has some important sources of error --- the neglect of air resistance, for example --- and our measurement of the constants given in the problem was probably fairly inaccurate.)

In this example we want to find the maximum value of y(t). We do this by setting the vertical component of velocity dy/dt equal to zero:

0 = .

We take as our first approximate value, and apply Newton's method with f(t) taken to be the vertical velocity function . Then (this function is actually the vertical component of the acceleration of the tip of the baton). So Newton's method gives:

= 0.35 -
;

= ... = 0.341989; = ... = 0.341975; = ... = 0.341975.

So
is accurate to 6 decimal places (the last digit could conceivably be off by 1 due to rounding). Thus, the baton's tip reaches its maximum height at t = 0.341975 sec. Finally, to find the maximum height reached, we substitute this value of t into the height function
. We obtain 8.90326 ft.

**Example 4:**
Recall Problem 15 of the max/min homework. Suppose that the Pilot was daydreaming, did not notice the missile passing a half-mile away, and so the next day takes the plane again on the exact same route. The
terrorist
is waiting, and this time he decides to adjust the angle at which he shoots the missile (aiming at a point roughly a half-mile ahead of the plane). Again suppose that the missile travels at 2000 mph, and neglect both air resistance and gravity. Find the angle
above the horizontal at which the terrorist should fire the missile in order to hit the plane. Use Newton's method with three iterations. Also determine how the function in Newton's method would be affected if you took gravity into account in the motion of the missile.

To solve this, we first write the parameterized equations for the plane

,
,

and for the missile

,

.

At the time t when the
missile
hits the plane, the coordinates of the missile must be equal to the corresponding coordinates of the plane. This means that in the horizontal direction we have:

, i.e.,
;

and in the vertical direction

.

We substitute the value for t (determined from the horizontal motion) into the last equation, clear denominators, and move everything to the left of the equal sign:

. Dividing through by 1000 for convenience, we arrive at the equation:
= 0. Since the problem mentioned that a rough guess would be to aim the missile at the point (2,2) (a half-mile in front of the plane), which means an angle of
radians, it makes sense to take
. Here we have
, so Newton's method gives:

= /4 - f( )/( ( ) = 0.785398- (-0.29289)/(-4.94975) = 0.726225;

= ... = 0.725937; = ... 0.725937 rad = .

Finally, if we want to take gravity into account, we must add the term - to , where the gravitational constant g is converted from 9.80665 m/ to 78980 mi/ (using the fact that 1 mi = 1609.3 m, and 1 hr = 3600 sec).

Since nothing changes in the horizontal direction, we still have ). As before, we equate the y-coordinates of the plane and the missile and clear denominators, which now means multiplying through by . We divide through by 1000000 (for convenience), and bring everything over to the left. The result is:

.

This is what we use for our in Newton's method.