Newton's method

What you will be able to do

After this lesson you can

• explain Newton's method with a picture of a tangent,
• write it as a short loop and use it to solve an equation,
• compare its speed with bisection, and
• say when it fails.

A better guess from a straight line

Bisection is safe but slow: it gains about one digit every three steps. Newton's method is much quicker. It uses what you learned in calculus: close to a point, a curve looks like its tangent line.

You have a guess $x_0$ for the root. At that point, the curve has the value $f(x_0)$ and the slope $f'(x_0)$. The tangent line is a straight line, and you can find where a straight line meets the axis. That place is much closer to the root than $x_0$ was, if the curve is not too wild. Take it as the next guess, $x_1$, and repeat.

The tangent at $(x_0, f(x_0))$ has the equation $y = f(x_0) + f'(x_0)(x - x_0)$. It meets the axis where $y = 0$:

In general, the step is $x_{n+1} = x_n - \dfrac{f(x_n)}{f'(x_n)}$.

Square root of 2

For $f(x) = x^2 - 2$, the derivative is $f'(x) = 2x$. Start with $x_0 = 1$.

Predict first. The error of the first guess is 0.41. How large will it be after 3 steps? Then run it.

Newton against bisection

Start far away and the first steps are big. Once close, each step about squares the error: 0.01 becomes 0.0001.

When Newton goes wrong

Newton's method has no guarantee, because the tangent can point anywhere.

More ways to fail: a start far from the root can send the guess to a distant part of the graph. A root where the slope is nearly zero makes the method slow. A function with a sharp bend can throw the guess far away.

A good plan is the one that professional programs use: bracket first (find the interval with a change of sign), and then use a method that is quick but cannot leave the bracket. The function brentq of SciPy, which you meet in lesson 5, is exactly such a mixture of bisection and faster methods.

Where does the derivative come from?

You can write it by hand, as we did. If the formula is hard, use a numerical derivative: $f'(x) \approx \dfrac{f(x + h) - f(x)}{h}$ for a small $h$, such as $10^{-6}$. It is slightly less accurate, but it needs no work. (Chapter 4 explains derivatives by numbers in detail.)

Common mistakes

• A wrong derivative. The method then converges badly or not at all. Test your derivative with a number.
• A start that is far from the root. Look at the graph first.
• Not checking the slope. If it is zero, stop.
• Forgetting the limit on the number of steps. A loop can run for ever, as in the cycle.
• Trusting the last number without a check. Put it in the equation.

Practice

Start with two quick questions. Each New numbers gives you a fresh one, so you can practise as long as you like.

Then the labs and the problems:

1. Warm-up. Open the lab Newton's method. You write the method with a limit of steps and a check for the zero slope.
2. Build. Open the problem Square roots by Newton and the problem When Newton fails.

Remember these

• Newton's step is $x_{n+1} = x_n - f(x_n) / f'(x_n)$: the tangent meets the axis.
• Near a simple root, the number of correct digits doubles at every step.
• It needs the derivative, and has no guarantee: cycles, zero slope and a far start are the ways to fail.
• Put a limit on the number of steps, and check the answer.

Check yourself

Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.

1. For $f(x) = x^2 - 9$ and $x_0 = 4$, what is $x_1$?

2. What does "quadratic convergence" mean?

3. Why does Newton fail at $x_0 = 0$ for $f(x) = x^2 + 1$?

4. Why is Newton quicker than bisection, and what does it cost?