Newton's Method Simulation

About this experiment

Most equations cannot be solved with a formula, yet a calculator finds √2 or the root of cos x = x in an instant. Newton's method is one reason: from a guess, follow the tangent line down to the x-axis and use that crossing as the next guess. Close to a simple root the number of correct digits roughly doubles every step. Watch it work, then break it: double roots, horizontal tangents, cycles, divergence, and the fractal basins of attraction it draws in the complex plane.

Learning goals

Derive the Newton iteration from the equation of the tangent line
Recognise quadratic convergence in a table of errors
Explain why convergence becomes linear at a multiple root
Give examples where Newton fails: horizontal tangents, cycles and divergence
Describe basins of attraction and why their boundaries in the complex plane are fractal

How to use it

1With x² − 2 and x₀ = 3, step through the method and watch the digits column. Roughly how does the number of correct digits grow?
2Show that for f(x) = x² − a the iteration becomes x_{n+1} = (x_n + a/x_n)/2, the Babylonian method.
3Choose (x − 1)²(x + 2) and start at 2.5. Compare the errors from one step to the next with the simple root case. What is the ratio?
4Choose x³ − 2x + 2 and start at exactly 0. What happens? Now start at 0.1 or −0.5.
5Choose arctan x. Find, to two decimal places, the largest start that still converges.
6Switch to the complex plane with z³ − 1. Zoom in mentally on a boundary between two colours: why are there always points of the third colour there?

The model

y = f (x_{n}) + f^{'} (x_{n}) (x - x_{n}) = 0 \Rightarrow x_{n + 1} = x_{n} - \frac{f ( x _{n} )}{f ^{'} ( x _{n} )}

The next guess is where the tangent crosses the x-axis

e_{n + 1} \approx \frac{f ^{''} ( r )}{2 f ^{'} ( r )} e_{n}^{2}

Quadratic convergence near a simple root r

e_{n + 1} \approx \frac{m - 1}{m} e_{n}

Linear convergence near a root of multiplicity m

p \approx \frac{ln ( e _{n + 1} / e _{n} )}{ln ( e _{n} / e _{n - 1} )}

Estimated order of convergence from three errors

Assumptions

Calculations use double precision, about 16 significant digits, so the error stops falling near 10^−16.
The error is the distance from the nearest exact root, which is known for every function shown.
The method stops when the tangent is horizontal, when |x| exceeds 10^6, or after 40 steps.
In the complex plane a start is coloured by the root it reaches within 50 steps, darker when it needs more steps. Points that never arrive are drawn almost black.

Try this in class

Q1Use two Newton steps from x₀ = 2 to estimate the cube root of 10.
Q2Why must f′(x) be non-zero near the root for Newton to work well?
Q3Find the Newton iteration for f(x) = 1/x − a. Why is it useful for computers that cannot divide?
Q4For f(x) = x^(1/3), show that x_{n+1} = −2x_n. What does this mean for every start?
Q5Compare Newton with bisection: which needs fewer steps to reach 10 correct digits, and which is guaranteed to work?

Frequently asked questions

Why is it called the Newton-Raphson method?

Isaac Newton described a version for polynomials in 1669 that rewrote the polynomial at each step. Joseph Raphson published the simpler iterative form in 1690, and Thomas Simpson gave the general calculus version in 1740.

How do practical solvers avoid the failures shown here?

They combine Newton with a safe method such as bisection (as in Brent's method), shorten the step when it would make the function larger (damped Newton or line search), or start from a good estimate found another way.

Where is Newton's method used?

In computing square roots and reciprocals in hardware, solving nonlinear equations in engineering and physics, implicit time stepping of differential equations, and optimisation, where Newton is applied to the gradient to find minima.