### Newton's Method

This is a method which, once you get started, quickly gives a very
good approximation to a root of polynomial (and other) equations. The
idea is that, if $x_o$ is *not* a root of a polynomial equation,
but is pretty close to a root, then *sliding down the tangent line
at $x_o$ to the graph of $f$ gives a good approximation to the actual
root*. The point is that this process can be repeated as much as
necessary to give as good an approximation as you want.

Let's derive the relevant formula: if our blind guess for a root of $f$ is $x_o$, then the tangent line is $$y-f(x_o)=f'(x_o)(x-x_o)$$ ‘Sliding down’ the tangent line to hit the $x$-axis means to find the intersection of this line with the $x$-axis: this is where $y=0$. Thus, we solve for $x$ in $$0-f(x_o)=f'(x_o)(x-x_o)$$ to find $$x=x_o-{f(x_o)\over f'(x_o)}$$

Well, let's call this *first serious guess* $x_1$. Then, repeating this
process, the *second serious guess* would be
$$x_2=x_1-{f(x_1)\over f'(x_1)}$$
and generally, if we have the $n$th guess $x_n$ then the $n+1$th guess
$x_{n+1}$ is
$$x_{n+1}=x_n-{f(x_n)\over f'(x_n)}$$

OK, that's the formula for *improving our guesses*. How do we
decide when to quit? Well, it depends upon to how many decimal places we
want our approximation to be good. Basically, if we want, for example,
$3$ decimal places accuracy, then as soon as $x_n$ and $x_{n+1}$ *agree* to three decimal places, we can presume that those are the *true* decimals of the true root of the equation. This will be
illustrated in the examples below.

It is important to realize that there is some uncertainty in Newton's method, both because it alone cannot assure that we have a root, and also because the idea just described for approximating roots to a given accuracy is not foolproof. But to worry about what could go wrong here is counter-productive.

#### Example 1

Approximate a root of $x^3-x+1=0$ using the intermediate value theorem to get started, and then Newton's method:

First let's see what happens if we are a little foolish here,
in terms of the ‘blind’ guess we start with. If we ignore the advice
about using the intermediate value theorem to *guarantee* a root
in some known interval, we'll waste time. Let's see: The
general formula $$x_{n+1}=x_n-{f(x_n)\over f'(x_n)}$$ becomes
$$x_{n+1}=x_n-{x^3-x+1\over 3x^2-1}$$ If we take $x_1=1$ as our
‘blind’ guess, then plugging into the formula gives
$$x_2=0.5$$
$$x_3=3$$
$$x_4=2.0384615384615383249$$
This is discouraging,
since the numbers are jumping around somewhat. But if we are stubborn
and can compute
quickly with a calculator (not by hand!), we'd see what happens:
$$\matrix{
x_5&=&1.3902821472167361527 \cr
x_6&=&0.9116118977179270555\cr
x_7&=&0.34502849674816926662 \cr
x_8&=&1.4277507040272707783\cr
x_9&=&0.94241791250948314662 \cr
x_{10}&=&0.40494935719938018881\cr
x_{11}&=&1.7069046451828553401 \cr
x_{12}&=&1.1557563610748160521\cr
x_{13}&=&0.69419181332954971175 \cr
x_{14}&=&-0.74249429872066285974\cr
x_{15}&=&-2.7812959406781381233 \cr
x_{16}&=&-1.9827252470441485421\cr
x_{17}&=&-1.5369273797584126484 \cr
x_{18}&=&-1.3572624831877750928\cr
x_{19}&=&-1.3256630944288703144 \cr
x_{20}&=&-1.324718788615257159\cr
x_{21}&=&-1.3247179572453899876
}$$

Well, after quite a few iterations of ‘sliding down the tangent’, the
last two numbers we got, $x_{20}$ and $x_{21}$, agree to $5$ decimal
places. This would make us think that the *true* root is *approximated to five decimal places* by $-1.32471$.

The stupid aspect of this little scenario was that our initial ‘blind’
guess was *too far from an actual root*, so that there was some
wacky jumping around of the numbers before things settled down. If we
had been computing by hand this would have been hopeless.

Let's try this example again using the Intermediate Value Theorem to
pin down a root with some degree of accuracy: First, $f(1)=1>0$. Then
$f(0)=+1>0$ also, so we might *doubt* that there is a root in
$[0,1]$. Continue: $f(-1)=1>0$ again, so we might *doubt* that
there is a root in $[-1,0]$, either. Continue: at last $f(-2)=-5 < 0$,
so since $f(-1)>0$ by the Intermediate Value Theorem we do indeed know
that there is a root between $-2$ and $-1$. Now to start using *Newton's Method*, we would reasonably guess
$$x_o=-1.5$$
since this is the midpoint of the interval on which we know there is a
root. Then computing by Newton's method gives:
$$
\matrix{
x_{1}&=&-1.3478260869565217295\cr
x_{2}&=&-1.3252003989509069104\cr
x_{3}&=&-1.324718173999053672\cr
x_{4}&=&-1.3247179572447898011
}$$
so right away we have what appears to be $5$ decimal places accuracy,
in $4$ steps rather than $21$. Getting off to a good start is important.

#### Example 2

Approximate *all three* roots of $x^3-3x+1=0$ using the
intermediate value theorem to get started, and then Newton's
method. Here you have to take a little care in choice of beginning
‘guess’ for Newton's method:

In this case, since we are *told* that there are three
roots, then we should certainly be wary about where we start:
presumably we have to start in different places in order to
successfully use Newton's method to find the different roots. So,
starting thinking in terms of the intermediate value theorem: letting
$f(x)=x^3-3x+1$, we have $f(2)=3>0$. Next, $f(1)=-1 < 0$, so we by the
Intermediate Value Theorem we know there is a root in $[1,2]$. Let's
try to approximate it pretty well before looking for the other roots:
The general formula for Newton's method becomes
$$x_{n+1}=x_n-{x^3-3x+1\over 3x^2-3}$$
Our initial ‘blind’ guess might reasonably be the midpoint of the
interval in which we know there is a root: take
$$x_o=1.5$$
Then we can compute
$$\matrix{
x_{1}&=&1.533333333333333437\cr
x_{2}&=&1.5320906432748537807\cr
x_{3}&=&1.5320888862414665521\cr
x_{4}&=&1.5320888862379560269\cr
x_{5}&=&1.5320888862379560269\cr
x_{6}&=&1.5320888862379560269
}$$
So it appears that we have quickly approximated a root in that
interval! To what looks like $19$ decimal places!

Continuing with this example: $f(0)=1>0$, so since $f(1) < 0$ we know by the intermediate value theorem that there is a root in $[0,1]$, since $f(1)=-1 < 0$. So as our blind gues let's use the midpoint of this interval to start Newton's Method: that is, now take $x_o=0.5$: $$\matrix{ x_{1}&=&0.33333333333333337034\cr x_{2}&=&0.3472222222222222654\cr x_{3}&=&0.34729635316386797683\cr x_{4}&=&0.34729635533386071788\cr x_{5}&=&0.34729635533386060686\cr x_{6}&=&0.34729635533386071788\cr x_{7}&=&0.34729635533386060686\cr x_{8}&=&0.34729635533386071788 }$$ so we have a root evidently approximated to $3$ decimal places after just $2$ applications of Newton's method. After $8$ applications, we have apparently $15$ correct decimal places.

#### Exercises

- Approximate a root of $x^3-x+1=0$ using the intermediate value theorem to get started, and then Newton's method.
- Approximate a root of $3x^4-16x^3+18x^2+1=0$ using the intermediate value theorem to get started, and then Newton's method. You might have to be sure to get sufficiently close to a root to start so that things don't ‘blow up’.
- Approximate
*all three*roots of $x^3-3x+1=0$ using the intermediate value theorem to get started, and then Newton's method. Here you have to take a little care in choice of beginning ‘guess’ for Newton's method. - Approximate the unique positive root of $\cos\,x=x$.
- Approximate a root of $e^x=2x$.
- Approximate a root of $\sin x=\ln x$. Watch out.

#### Thread navigation

##### Calculus Refresher

#### Similar pages

- Intermediate Value Theorem, location of roots
- Multivariable chain rule examples
- The multidimensional differentiability theorem
- Non-differentiable functions must have discontinuous partial derivatives
- A differentiable function with discontinuous partial derivatives
- Special cases of the multivariable chain rule
- The gradient vector
- The idea of the derivative of a function
- Derivatives of polynomials
- Derivatives of more general power functions
- More similar pages