So far when you've encountered a function, finding the roots analytically (by hand) involved figuring out first what kind of function it was (polynomial, rational, &c. ...), then trying one or more of several methods, including:
But what if there are no rational roots? Then we need some way to numerically estimate what the roots are. After all, it may still be important to find them.
Newton's method works well for a good number of cases, and it's pretty easy to understand. It's all about tangent lines and the derivative.
In the first panel (left) of the figure below we have a function, f(x) (purple curve), with a root we couldn't find using one of the methods above. We first make a guess at the root, say at x1. Then we find the line tangent to f(x) at that point and find where that tangent line intersects the x-axis. Obviously this will involve finding the equation of the tangent line from a point (x1, f(x1)) and the slope, f'(x1). You can see that we've "walked" closer to the actual root.
The point where our first tangent crosses the x-axis is our new "guess," x2. We find the equation of the line tangent to f(x) at x2 and take the x-intercept of that tangent as our new best guess at the root.
Repeating the process gets us even closer to the actual root. In fact, in a case like this, we can get as close as we'd like to the actual root, depending on what kind of precision we require. The error – the difference between our guess and the real value of the root – gets smaller and smaller.
← Here's a blowup of that last step. You can see that where the root of the tangent to the curve at x3 is x4, which is much closer to our elusive actual root (yellow) of f(x). We track our progress by noting that the step size along the x-axis decreases and that f(xn), the value of the function at the nth step, gets smaller.
I'm going to work through one round of Newton's method in this example, then automate the process below with a spreadsheet. Notice that for this quadratic function, we already know the two roots, x = -2, 3. That will make our exploration of the method more meaningful because we know what the answer should be.
First we'll make an initial guess at the root on the left, say x = -4. Now we'll need to calculate f(x) and f'(x):
OK, so remember that we're looking for the equation of the tangent line at x = -4 for the purpose of finding where it crosses the x-axis. That will be our refined "guess" at the root. We have a point and a slope:
So the y-intercept and equation of the line are:
Setting y = 0, we find the x-intercept and our refined root estimate:
Now it remains to keep doing that until the estimates converge
Here's what that first cycle looks like on the graph. The initial guess at the root is x = -4, which generates a second guess of -2.44 on the way to an actual root of x = 2.
Now let's automate this procedure with a spreadsheet. In the table below are the four rounds of Newton's method that converged very nicely to the value of the root. The top row is the initial guess of x = -4.0, and successive rows are refinements of that guess using Newton's method.
| x | f(x) | f'(x) | y=mx+b | x-int. |
| -4.00 | 14.000 | -9.000 | -22.000 | -2.444 |
| -2.44 | 2.4197 | -5.889 | -11.975 | -2.034 |
| -2.03 | 0.169 | -5.067 | -10.135 | -2.000 |
| -2.00 | 0.001 | -5.001 | -10.001 |
Below are similar calculations of the x = -2 and x = 3 roots beginning from different starting guesses, including one that's quite far away, at x = 25.
Notice that in the case of the parabola, we have to make our guess on the correct side of the vertex to get a result. This is important because it means that Newton's method won't always, at least for a given initial guess, converge to a root of the function.
| x | f(x) | f'(x) | y=mx+b | x-int. |
| 2.00 | 4.000 | 3.000 | -10.000 | 3.333 |
| 3.33 | -1.778 | 5.667 | -17.11 | 3.019 |
| 3.02 | -0.098 | 5.039 | -15.11 | 3.000 |
| 3.00 | -0.001 | 5.000 | -15.00 | 3.000 |
| 3.00 | 0.000 | 5.000 | -15.00 | 3.000 |
Notice that it takes a few more iterations to get to the root when our starting guess is so far away, but the method still works.
| x | f(x) | f'(x) | y=mx+b | x-int. |
| 25.00 | 594.0 | 49.00 | -631.0 | 12.878 |
| 12.88 | 146.9 | 24.76 | -171.8 | 6.941 |
| 6.94 | 35.2 | 12.88 | -54.18 | 4.206 |
| 4.21 | 7.48 | 7.412 | -23.69 | 3.196 |
| 3.20 | 1.02 | 5.392 | -16.22 | 3.007 |
| 3.01 | 0.036 | 5.014 | -15.04 | 3.001 |
| 3.00 | 0.000 | 5.000 | -15.000 | 3.000 |
Once in a while, you'll encounter a function in which Newton's method, for one reason or another, doesn't work. One such example is shown here →
The problem in this example, f(x) = ln(x), is that the function is convex on the side of the tangent and the domain is restricted on the left. Thus the first tangent line intersects the x-axis outside the domain of the function and the method is dead. Always be on the lookout for situations like this.
Also notice that if your first guess was between 0 and 1 (x = 1 is the actual root of the log function), the method would work.
| 1. |
f(x) = x3 + 5x + 2 near x = 0 (one root)
|
| 2. |
f(x) = x4 - 2x3 + 5x2 - 5 in [1, 2] (one root)
|
| 3. |
Use Newton's method to find, correct to six digits, the 6th root of 4, i.e. solve x6 = 4.
|
| 4. |
Find the positive root of sin(x) = x2
|
xaktly.com by Dr. Jeff Cruzan is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License. © 2012, Jeff Cruzan. All text and images on this website not specifically attributed to another source were created by me and I reserve all rights as to their use. Any opinions expressed on this website are entirely mine, and do not necessarily reflect the views of any of my employers. Please feel free to send any questions or comments to jeff.cruzan@verizon.net.
