# Math Insight

### 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

1. Approximate a root of $x^3-x+1=0$ using the intermediate value theorem to get started, and then Newton's method.
2. 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’.
3. 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.
4. Approximate the unique positive root of $\cos\,x=x$.
5. Approximate a root of $e^x=2x$.
6. Approximate a root of $\sin x=\ln x$. Watch out.