4. Newton's Method

The methods we saw so far, the Bisection Method and Regula Falsi, both had the same principle in common: they both started with an interval which was then improved in each iteration. Newton's Method, however, works different. First, we now suppose that our function f is not just continuous, but also differentiable. Then we begin with a starting point, not an interval. Let's call this point $x_0$. We know calculate $f(x_0)$ and $f'(x_0)$, and think to ourselves: ``OK, we know that the graph of $f$ is not a straight line, but suppose it was. Then we could find the root by drawing a straight line through the point $(x_0, f(x_0))$ with slope $f'(x_0)$, and calculating the place where this line intersects the x-axis.'' So, just like Regula Falsi, we hope that our function $f$ is more or less a straight line, so that we can get a good approximation by using the root of the tangent line in $(x_0, f(x_0))$. Of course, we can do this several times, which leads to the formula:

$$x_{n+1} = x_n - {f(x_n) \over f'(x_n) }.$$

Let's put Newton to the test. Here is the applet "Newton", that shows the method: If you tried Newton a few times for some , you might have noticed that it is much faster than the other methods we encountered so far. Indeed, Newton's Method generally produces accurate results within a few iterations. To see this, suppose the real root of $f$ lies in the point $x$, and we started with an approximation $x_0 = x + h$. Then we find, using the Taylor series:

$$f(x+h) = f(x) + h f'(x) + O(h^2) = h f'(x) + O(h^2).$$

So for our next approximation x1, we have:

$$x_1 = x_0 - { f(x_0) \over f'(x0) } = x + h - { h f'(x) + O(h^2) \over f'(x) + O(h) } = x + O(h^2).$$

So, our first approximation $x_0$ had an error $h$, but our second iteration only has an error of $O(h^2)$. So if we started with an approximation that had 3 significant digits, we have, after just one iteration, an approximation with 6 significant digits! You can see this behaviour by looking at the table of numbers generated by the applet on the Java Console. Compare this with the Bisection Method, which only doubles the precision each iteration. So Bisection needs at least 3 iterations to get one more significant digit!