Newton’s method is motivated by the problem of finding roots of equations. Given some function f(x), we want to find the roots, or solutions, of the equation
f(x) = 0
The method consists of the following steps:
One of the simplest applications of Newton’s method is finding square roots. Suppose we wanted to compute . We would need to create a function that has as one of its roots. One such equation is
As a starting point for the method, we make a crude guess that the root we want is somewhere close to x = 1. To compute the equation of the tangent line at x = 1 we first compute the derivative, which tells us the slope of the tangent line.
At x = 1 the tangent has slope .
The tangent line touches the curve at a point (1,f(1)) = (1,12 - 2) = (1,-1).
Thus the equation of the tangent line is
or
To determine where this tangent crosses the x-axis we can substitute 0 for y and solve for x.
The graph below shows the tangent line and the crossing point.
We now use the crossing point of the tangent line, x = 3/2, as the basis for our next guess. The point on the curve that corresponds to x = 3/2 is
The slope of the tangent at that point is
Once again,we are trying to find a line with equation
or
This second tangent line crosses the x axis when y = 0:
or
x - 3/2 = -1/12
x = 17/12
This lands very close to the actual value of . Numerically, 17/12 is approximately
while is approximately
1.4142135623730951
After only two iterations of the method we have found an approximate solution that is equal to the actual solution to two decimal places.
Although the calculations above are easy enough to follow, they are a little tedious. Instead of redoing the tangent line calculation over and over again for specific cases, it would be nice if we could solve the tangent line problem once and for all. The result will be a general formula for Newton’s method that will be valid regardless of the original function.
The general problem is to find solutions to
We pick a point
(1) |
on the curve and find the equation of the tangent line at that point. The slope of the tangent line at that point is
(2) |
The tangent line has general form
This line intersects the x-axis when y = 0.
We call that new point x1 and then repeat the process starting from that point. The result will be a new point
This now is Newton’s method. Pick a starting guess, x0, and compute a sequence of approximations. Each successive term in the sequence gets computed from the term that came before it via the formula
(3) |
Let us see how this works using the example from above. The function is
Substituting this f into the general formula (3) gives
which simplifies to
You can now use this formula to create a sequence of approximations for the root.
n | xn |
---|---|
0 | 1 |
1 | 1.5 |
2 | 1.4166666666666665 |
3 | 1.4142156862745097 |
4 | 1.4142135623746899 |
Here is a more complicated polynomial.
The graph shows that there is a root somewhere in the neighborhood of x = -1.5.
Substituting the function into the formula
gives
Here is the sequence of terms in the iteration of the method.
n | xn |
---|---|
0 | -1.5 |
1 | -1.767195767195767 |
2 | -1.6940073649495915 |
3 | -1.6845061344302743 |
4 | -1.6843577264032357 |
The values of xn generated by the method appear to be converging to a limit. We can get a sense for how good the approximation is after four iterations by plugging the final value back into the function. If we are very close to the root, we should have a function value close to 0. That is indeed the case:
The examples above show that Newton's method does a spectacular job in some cases. Unfortunately, it does not always work perfectly. Here is an example designed to show the flaw in the method.
Consider the equation
x = tan x
If you make a plot of both y = x and y = tan x, you will see that these curves intersect in many places.
In particular, let us go looking for the intersection that happens near x = 4.
Before we can apply Newton’s method, we have to rewrite the problem
x = tan x
in the form
tan x - x = 0
We introduce the function
f(x) = tan x - x
and apply the formula
to get
We are looking for a root near x = 4, so let us use that as our initial guess.
n | xn |
---|---|
0 | 4 |
1 | 6.1201584866543381 |
2 | 238.40427645407496 |
3 | 1957.2641956952848 |
4 | 725239.8209342995 |
The results are disastrous. Rather than converge to a reasonable answer, the sequence of xn terms blows up.
Why did this happen? A plot of the function tan x - x near x = 4 shows the problem.
Thanks to the shape of the curve near x = 4, the tangent line we draw at that point sends us way off target. In fact, the point where that tangent crosses is so far away that we have crossed over to the next period of the tangent function. From there things only get worse.
The solution to this problem is also clear from the picture. What we need to do is to pick a starting point closer to the actual root. From the plot we can see that x = 4.5 is probably a good guess. Starting from that point we get the following sequence
n | xn |
---|---|
0 | 4.5 |
1 | 4.4936139027432027 |
2 | 4.4934096550132478 |
3 | 4.4934094579092472 |
4 | 4.4934094579090642 |
If you compare the final x value in the sequence
4.4934094579090642
with its tangent
tan 4.4934094579090642 = 4.4934094579090651
you can see that the result is very good, matching out to 14 decimal places.
Section 4.9: 6, 7, 18, 30, 33