Newton's Method

Newton's method is simply a way to solve equations you can't solve by algebra, like $\cos x = x$, by making better and better guesses. All we're really doing is: make a guess, replace the curve by its tangent line there (a line is easy to solve), and let the line's zero be the next guess. The formula has two pieces: $x_n$ (your current guess) and $\frac{f(x_n)}{f'(x_n)}$ (the correction: how far the tangent line slides sideways before it hits zero). New guess equals old guess minus the correction. Then you just do it again.

It's the linear approximation from two lessons ago, put to work. There we used the tangent line to estimate a value of $f$. Here we use it to estimate where $f$ is zero, and because the estimate is close but not exact, we repeat it from the new point.

Where it comes from. The tangent at $x_n$ is $y = f(x_n) + f'(x_n)(x - x_n)$. Setting $y = 0$ and solving for $x$ gives the formula.

How fast. Near a simple root the error roughly squares each step: $0.1 \to 0.01 \to 0.0001$. That's why the number of correct digits roughly doubles, and three or four steps are often enough.

When it fails:

• $f'(x_n) \approx 0$: the tangent is nearly flat and shoots far away.
• A bad start can cycle forever or converge to a different root.
• Near a double root it slows down a lot.

Stop when successive guesses agree to the precision you need.

Calculators compute square roots and reciprocals with Newton's method, GPS receivers solve their position equations with it, and optimizers use it on $f'$ to find minima.