
\chapter{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.  \index{Newton's method} 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.  \index{Iterative procedures} Iterative procedures like
Newton's method are well suited to programming for a computer.

\smallskip

Here are the steps:
\begin{enumerate}
\item We start with a rough guess, which we call $x_0$.
\item Starting at the
point $x_0$ on the $x$-axis, we go up to the curve, hitting it at the
point $(x_0,f(x_0))$.
\item Now we slide down the {\bf tangent line to the curve
at} $(x_0,f(x_0))$, and take the point where this tangent line hits the
$x$-axis as our improved estimate for the desired $x$-value. Call this 
value $x_1$. (See the diagram below.)

The tangent line has slope $f'(x_0)$ and passes through the points
$(x_0,f(x_0))$ and $(x_1,0)$. This gives the equation:
$$f'(x_0)= \disp\frac{f(x_0)-0}{x_0-x_1} \mbox{~or~solving~}
x_1 = x_0 - \disp\frac{f(x_0)}{f'(x_0)}$$

\item Replace $x_0$ by $x_1$ and repeat as often as needed.
Thus we will produce a sequence of guesses $x_0,x_1,x_2,\dots$ and 
hopefully these will get closer and closer to a root.
\end{enumerate}

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. $f(x_0)=0$, then $x_1=x_0$ and thus, we can quit if 
we have $x_1=x_0$. In general, it makes sense to keep track of 
the difference between $x_1$ and $x_0$ 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 $f'(x_0)$ is small
and this causes $x_1$ to be far away from $x_0$. In an extreme case,
we could have $f'(x_0)=0$ and $x_1$ running off to infinity! It is also possible to create situations where $x_2=x_0$ and so we get into an infinite loop! This is easy to avoid, since a slight change in $x_0$ 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.

%%%% To update! Add example of bad situations for Newton's method.

\medskip

%--- figure QA (Newton's method)--------------------
%
\begin{psfigure}{3.25in}{2.0in}{figQA.ps}
%%
\puttext{-40, -10}{\Small root}
\put(-35,-15){\vector(1,-2){7}}
\puttext{10,-15}{\Small $x_{1}$}
\put(8,-18){\vector(-1,-1){11}}
\puttext{55., 35}{\Small slope = $f'(x_{0})$}
\puttext{5, 18}{\Small $(x_{0},f(x_{0}))$}
\puttext{6,-42}{\Small $\Delta x$}
\puttext{42,-12}{\Small $\Delta y$}
\end{psfigure}
%------------------------------

\medskip

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

\[
   x_1=x_0-\frac{f(x_0)}{ f'(x_0)},\;
   x_2=x_1-\frac{f(x_1)}{ f'(x_1)},\;
   x_3=x_2-\frac{f(x_2)}{ f'(x_2)},\;
   x_4=x_3-\frac{f(x_3)}{ f'(x_3)},\;
\text{ etc.}
\]

\medskip

How do we know when we are close enough?  Two things happen:
(1) when we plug our approximate value $x_n$ into $f(x)$ we get
something very near zero, and (2) our successive approximations
$x_{n-1}$ and $x_n$ 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 $x_1$, ``two
iterations'' means finding $x_2$, and so on.  If, on the other hand, the
directions specify the desired accuracy (``three decimal places,'' for
example), then just keep \index{iterating Newton's method} iterating Newton's method until the only changes
in your value from one iteration to the next occur beyond the decimal places
needed.


% Example 1
\begin{example}

Find $\sqrt{102}$ without using the square-root function on a calculator.
Use Newton's method with 3 iterations.

\smallskip

The first step is to set up the function we want to equal zero.  We set
$f(x)=x^2-102$, since $\sqrt{102}$ is a root of that function.  Since we
know $\sqrt{100}=10$, we can make a rough guess of $x_0=10$.  We are now
ready to apply the formula for Newton's method.  Here $f'(x)$ is, of
course, $2x$.  We obtain:
\[
   x_1=10-\frac{f(10)}{ f'(10)}=10-\frac{10^2-102}{ 2\cdot 10}=10.1.
\]
Actually, $x_1$ 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$\approx\sqrt{102}$.  That is, we successively compute:
\begin{align*}
x_2&=10.1-\frac{f(10.1)}{ f'(10.1)}=10.1-\frac{0.01}{ 20.2}=10.09950495;\\
x_3&=10.09950495-\frac{f(10.09950495)}{ f'(10.09950495)}=10.09950495-
\frac{0.0000002}{ 20.199}=10.09950494.
\end{align*}
Thus, $\sqrt{102}=10.09950494\cdots$.  If we computed $x_4$, $x_5$, etc.,
we would get the same as $x_3$ out to 8 places past the decimal point.

\end{example}


\bigskip
\noindent
{\bf STEPS IN A NEWTON METHOD STORY PROBLEM:}

\medskip

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

\medskip

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

\medskip

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

\medskip

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


% Example 2
\begin{example} 

Suppose that the material you are using to manufacture marbles costs
$1.0$ cent/in${}^3$, and the coating that is painted on the surface costs
$0.15$ cent/in${}^2$.  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.

\smallskip

We first write out the condition on the total cost, using the formulas
$\frac{4}{ 3}\pi r^3$ for the volume and $4\pi r^2$ for the surface area of a
marble: $1.0\cdot\frac{4}{ 3}\pi r^3+0.15\cdot 4\pi r^2=0.3$.  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 $r^3$, thereby obtaining: $f(r)=r^3+0.45r^2-\frac{0.225}{\pi}=0$.  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 $r_0=0.3$.  Here $f'(r)=3r^2+0.9r$.  We obtain:
\[
  r_1=r_0-\frac{f(r_0)}{ f'(r_0)}
     =0.3-\frac{0.027+0.45\cdot 0.09-0.07162}{
    3\cdot 0.09+0.9\cdot 0.3}=0.3076~\text{inch}.
\]
\end{example}



%
%<---------------Changed reference Example 10 below to Example 1 (Feb 24, 1993)
%
% Example 3
\begin{example}

Recall the example of the path of a baton's tip (Example 11.1).  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.)

\smallskip

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=\frac{d}{ dt}\Bigl(-16t^2+14t+5+\cos(6\pi t)\Bigr)=-32t+14-6\pi\,\sin(6\pi
t).
\]
We take $t_0=0.35$ as our first approximate value, and apply Newton's
method with $f(t)$ taken to be the vertical velocity function
$f(t)=-32t+14-6\pi\,\sin(6\pi t)$.  Then $f'(t)=-32-36\pi^2\cos(6\pi t)$
(this function is actually the vertical component of the acceleration of
the tip of the baton).  So Newton's method gives:
\begin{align*}
   t_1&= t_0-\frac{f(t_0)}{ f'(t_0)}=0.35-\frac{-32\cdot0.35+14
        -6\pi\,\sin(6\pi\cdot 0.35)
}{-32-36\pi^2\cos(6\pi\cdot 0.35)}=0.341823;\\
   t_2&=t_1-\frac{f(t_1)}{ f'(t_1)}=\cdots=0.341989;\qquad
   t_3=\cdots=0.341975;\qquad t_4=\cdots=0.341975.
\end{align*}
So $t_3$ 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
$y=-16t^2+14t+5+\cos(6\pi t)$.  We obtain 8.90326 ft.
 
\end{example}



%Example 4.
\begin{example}

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 $\alpha$ 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.

\smallskip

To solve this, we first write the parameterized equations for the plane
\[
x_{\text{plane}}(t)=1.5+500t,\qquad y_{\text{plane}}(t)=2, 
\] 
and for the missile 
\[
 x_{\text{missile}}(t)=(2000\cos\alpha)t,\qquad
y_{\text{missile}}(t)=(2000\sin\alpha)t.  
\]
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:
$1.5+500t=(2000\cos\alpha)t$, i.e., $t=1.5/(2000\cos\alpha - 500)$; and in
the vertical direction $2=(2000\sin\alpha)t$.  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:
$2(2000\cos\alpha-500)-(2000\sin\alpha)1.5=0$.  Dividing through by 1000
for convenience, we arrive at the equation: $f(\alpha)=4\cos\alpha -1
-3\sin\alpha=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 $\pi/4$ radians, it makes sense to take
$\alpha_0=\pi/4$.  Here we have $f'(\alpha)=-4\sin\alpha-3\cos\alpha$, so
Newton's method gives:
\begin{align*}
   \alpha_1&=\frac{\pi}{ 4}-\frac{f(\pi/4)}{ f'(\pi/4)}
            =0.785398-\frac{-0.29289}{-4.94975}=0.726225;\\
   \alpha_2&=\cdots=0.725937;\qquad\alpha_3
            = \cdots=0.725937\text{~rad}=41.5931^\circ.
\end{align*}

\smallskip

Finally, if we want to take gravity into account, we must add the term
$-\frac{1}{ 2}gt^2$ to $y_{\text{missile}}(t)$, where the gravitational
constant $g$ is converted from $9.80665$ m/sec${}^2$ to $78980$
mi/hr${}^2$ (using the fact that 1 mi = 1609.3 m, and 1 hr =3600 sec).
Since nothing changes in the horizontal direction, we still have
$t=1.5/(2000\cos\alpha-500)$.  As before, we equate the $y$-coordinates of
the plane and the missile and clear denominators, which now means
multiplying through by $(2000\cos\alpha-500)^2$.  We divide through by
1000000 (for convenience), and bring everything over to the left.  The
result is:
\[
  8\cos^2\alpha-4\cos\alpha-6\sin\alpha\cos\alpha+1.5\sin\alpha+0.58885=0.
\]
This is what we use for our $f(\alpha)$ in Newton's method.

\end{example}

\bigskip

