Newton's method

A much faster, but less certain, root-finder is Newton's method. Suppose you make one initial guess at the root, $x_1$. You'd like to find $x_2$ such that $f(x_2)$ $=$ 0. If you take the first two terms of the Taylor series for $f$ around $x_1$, then you have:

$$0 = f(x_2) \approx f(x_1) + f'(x_1)(x_2 - x_1).$$

Re-arranging things, and assuming that $f'(x_1)$ is non-zero, you get:

$$x_2 \approx x_1 - \frac{f(x_1)}{f'(x_1)}.$$

You decide you have to live with the approximation for $x_2$, and you plug it back into the formula to get $x_3$, and so on. So long as this method converges, it does so at a quadratic rate: $e_{k+1}$ $\leq$ $\alpha e_k^2$ (Course readings, p. 217). How can you tell whether it converges. A picture gives some intuition, since approximating $f$ by its tangent is risky when the slope is near zero. Another pictorial method comes to us from chaos theory. If we call $x - (f(x))/f'(x))$ $g(x)$, convergence means that $g(g(x))$ is getting closer to our root. If we draw the function $g(x)$ and the diagonal $y=x$ through the root, we can see that $g(x)$ is a contraction (i.e. gets closer), if $g'(x)$ has magnitude less than 1, or

$$1 > \vert g'(x)\vert = \left\vert\frac{f(x) f''(x)}{[f'(x)]^2}\right\vert \Longrightarrow [f'(x)]^2 > \vert f(x) f''(x)\vert.$$

If this holds true near the root, then Newton's method will converge at a quadratic rate.