Newton’s Method

What is Newton’s method?

Newton's method, also called the Newton–Raphson method, is a way to approximate a solution of f(x)=0 using tangent lines. A value of x where f is zero is a root of f and a solution of the equation. For a linear equation ax+b=0 and a quadratic ax^2+bx+c=0 there are formulas, but for most equations, such as x^3-x-1=0 or \cos x=x, there is none, and numbers are the only answer. The method is both fast and simple, and it is used in calculators, in software, and in engineering wherever a hard equation has to be solved.

The idea. Suppose x_0 is a rough guess of a root. Near x_0 the curve y=f(x) is almost its tangent line (this is the linearization of f), and a line is easy to solve. So take the point x_1 where the tangent at \left(x_0,f(x_0)\right) crosses the x-axis: it is usually closer to the root than x_0. Then do the same at x_1 to get x_2, and continue until the numbers stop changing.

The formula. The tangent line at \left(x_n,f(x_n)\right) is y=f(x_n)+f'(x_n) (x-x_n). It crosses the x-axis where y=0: 0=f(x_n)+f'(x_n)(x-x_n) ⇒ x=x_n-(f(x_n))/(f'(x_n))\qquadif f'(x_n)\ne0. This value is the next approximation: x_n+1=x_n-(f(x_n))/(f'(x_n)) Each step goes up (or down) from x_n to the curve and then follows the tangent line to the axis.

The procedure. 1. Guess a first approximation x_0, with the help of a graph, or of a sign change of f on an interval (the Intermediate Value Theorem). 2. Use the formula to get x_1, x_2, and so on. 3. Stop when the steps are smaller than the accuracy you need, and check that f(x_n) is close to zero.

An equation such as f(x)=g(x) is solved by applying the method to f(x)-g(x), and a question such as "where does the curve y=x^3-x cross the line y=1?" is the same as finding the roots of x^3-x-1.

How does Newton’s method work on real equations?

Three examples show the method at work: a square root, a cubic with a single real root, and an equation from astronomy.

Example 1: the square root of 2. Approximate the positive root of f(x)=x^2-2. With f'(x)=2x the formula becomes x_n+1=x_n-(x_n^2-2)/(2x_n)=(x_n)/(2)+\frac1x_n. From x_0=1 we get x_1=\frac32=1.5, then x_2=(17)/(12)≈1.41667 and x_3=(577)/(408)≈1.41422. The true value is √2=1.41421356…, so the errors are about 0.414, 0.086, 0.0025 and 0.000002, and the next step is correct to twelve decimals. Each step roughly doubles the number of correct digits.

Example 2: a cubic. Find the x-coordinate where the curve y=x^3-x crosses the line y=1. That is a root of f(x)=x^3-x-1. Since f(1)=-1 and f(2)=5, the Intermediate Value Theorem gives a root in (1,2). With f'(x)=3x^2-1, x_n+1=x_n-(x_n^3-x_n-1)/(3x_n^2-1). Starting at x_0=1 gives x_1=1.5, x_2=1.347826087, x_3=1.325200399, x_4=1.324718174 and x_5=1.324717957, and x_6 agrees with it to nine decimals: f(x_5) is zero up to the accuracy of the computation. The curve is concave up for x>0, since f''(x)=6x>0, so once an approximation is to the right of the root the tangents lie below the curve and the approximations fall steadily toward it. Starting much farther away, at x_0=3, still works, in seven steps; in fact any start to the right of \frac1√3 leads to this root.

Example 3: a planet. To calculate where a planet is, astronomers solve equations such as x=1+0.5\sin x (Kepler's equation, with x in radians). The function f(x)=x-1-0.5\sin x has f'(x)=1-0.5\cos x, and a graph suggests a root near 1.5. One step from x_0=1.5 gives x_1=1.5-(1.5-1-0.5\sin1.5)/(1-0.5\cos1.5)≈1.49870, which is already the root to five decimals.

Type a function and a starting value below, or choose one of the examples. The slider takes the steps one at a time, and the picture shows each tangent: up to the curve, then along the tangent to the axis.

How fast does Newton’s method converge?

Near a simple root Newton's method converges quadratically: the error is roughly squared at each step, so the number of correct digits roughly doubles. Write e_n=x_n-r for the error, where r is the root. If f has a continuous second derivative and f'(r)\ne0, then e_n+1=(f''(\xi))/(2f'(x_n)) e_n^2\qquadfor some \xi between x_n and r. Proof. Taylor's formula at x_n, evaluated at the root, gives 0=f(x_n)-f'(x_n)e_n+\frac12f''(\xi)e_n^2, that is f'(x_n)e_n-f(x_n)=\frac12f''(\xi)e_n^2. Then e_n+1=e_n-(f(x_n))/(f'(x_n))=(f'(x_n)e_n-f(x_n))/(f'(x_n))=(f''(\xi))/(2f'(x_n)) e_n^2. ∎ When x_n→ r this says (e_n+1)/(e_n^2)→(f''(r))/(2f'(r)). For √2 the constant is (2)/(2·2√2)≈0.354, and the table below shows the ratios close to it.

Comparison with bisection. The bisection method halves a bracket at each step, a gain of about 0.3 digits per step, so ten digits take about thirty-three steps. Newton's method needs four or five, but it needs the derivative, a good start, and no safety net.

It is a local result. The formula |e_n+1|\le M e_n^2, with M a bound for (|f''|)/(2|f'|) near the root, gives M|e_n|\le(M|e_0|)^2^n. So if the first error satisfies M|e_0|<1 the method converges, and very fast; if the start is farther away, nothing is promised.

Multiple roots. If f(x)=(x-r)^m g(x) with m>1 then f'(r)=0 and the argument above fails: the error shrinks only by the factor (m-1)/(m) at each step. For (x-1)^2 the error is halved, as in bisection; for (x-1)^6 only a sixth of the error is removed at each step. For f(x)=(x-1)^40 and x_0=2 the factor is (39)/(40), and after 100 steps the approximation is still about 1.08. Using x_n+1=x_n-m(f(x_n))/(f'(x_n)) restores quadratic convergence when m is known.

Stopping. For a simple root a tiny step |x_n+1-x_n| means the error is tinier still. Do not rely on |f(x_n)| alone: a flat curve such as (x-1)^40 has f(x) below 10^-15 while x is still 0.4 away from the root.

Choose a case below: the table gives the error, the correct digits and both ratios, with bisection beside it for the simple roots.

When does Newton’s method fail?

Newton's method does not always converge, and when it does, it may converge to a root you did not have in mind. If it converges, the limit is a root: when x_n→ L and f and f' are continuous with f'(L)\ne0, letting n→∞ in the formula gives (f(L))/(f'(L))=0. The trouble is whether it converges at all. The usual failures are these.

1. A horizontal tangent. If f'(x_n)=0 the tangent never meets the axis and the formula divides by zero; if f'(x_n) is merely tiny the next guess is thrown far away.
2. A cycle. For f(x)=x^3-2x+2 and x_0=0 the tangent at 0 meets the axis at 1, and the tangent at 1 meets it at 0: the approximations are 0,1,0,1,… forever, while the real root is near -1.77. In the textbook the function f(x)=√(x-r) for x\ge r and -√(r-x) for x<r swings between r-h and r+h in the same way.
3. Running off. For f(x)=x^(1/3) the root is 0, but x_n+1=x_n-3x_n=-2x_n, so the approximations are 1,-2,4,-8,… Another case is \arctan x: if |x_0| is greater than about 1.3917, where 2x=(1+x^2)\arctan x, each step lands farther out than the last.
4. The wrong root. \sin x has a root at every multiple of π, but from x_0=1.7 the tangent is nearly flat, the next guess is 9.40, and the sequence settles on 3π. If you start too far away, the method may miss the root you want.
5. A flat root. At a root of multiplicity m>1 the convergence is only linear, as above.

Basins of attraction. The set of starting values that lead to one root is its basin. The basins of different roots are usually separated by simple boundaries, but they can interleave in a fine pattern. For f(x)=x^3-x, with roots -1, 0 and 1, every start beyond \frac1√3≈0.577 goes to 1, every start between -\frac1√5 and \frac1√5 goes to 0, and between \frac1√5≈0.447 and \frac1√3 the roots reached change with every small move of the start. So a small change of x_0 can change the answer.

Safeguards. Graph the function first; start from a bracket [a,b] with f(a)f(b)<0 and fall back to a bisection step whenever Newton's step leaves the bracket; limit the number of steps; stop on both |x_n+1-x_n| and |f(x_n+1)|.

The first widget shows each failure with its steps, and the second colours the starting values by the root they reach.

Where is Newton’s method used?

Newton's method is behind the square root and the division of many calculators and programs, and behind any problem that comes down to solving one equation.

Square roots. For f(x)=x^2-a the formula is x_n+1=\frac12\left(x_n+\frac ax_n\right): replace the guess by the average of x_n and \frac ax_n, one of which is too small and one too large. For x^n-a the derivative disappears into x_n+1=((n-1) x_n+(a)/(x_n^ n-1))/(n). Division. For f(x)=\frac1x-a the root is \frac1a and the formula simplifies to x_n+1=x_n(2-a x_n), with no division at all: a computer can find a reciprocal with only multiplication and subtraction, as long as 0<x_0<\frac2a.

Optimization. The extreme values of g are at the roots of g' (see optimization problems), so Newton's method applied to f=g' gives x_n+1=x_n-(g'(x_n))/(g''(x_n)). In many variables the same idea, with the gradient and the second derivatives, is at the center of numerical optimization and of solving systems of equations.

Other equations. Where two curves intersect, where a planet is on its orbit, the closest approach of a submarine to a buoy, the equilibrium of a chemical mixture: each is an equation with no formula and a good first guess.

Try the two rules below. Change a, the root index and the start, and watch the correct digits.

How do you code Newton’s method?

In code, Newton's method is a loop of three lines; the care goes into the stopping rule. Stop when the step is small relative to x, give up after a fixed number of steps, and refuse to divide when the derivative is zero. SymPy can find f' for you, and without it a central difference (f(x+h)-f(x-h))/(2h) is a good replacement. The same loop run on x^3-2x+2 from 0 shows the cycle: the iterates are 0,1,0,1,…

import sympy as sp

x = sp.symbols('x')


def newton(f, x0, steps=6):
    """Newton's method for f(x) = 0, with f' found symbolically: the list of approximations."""
    g, dg = sp.lambdify(x, f), sp.lambdify(x, sp.diff(f, x))
    xs = [x0]
    for _ in range(steps):
        xs.append(xs[-1] - g(xs[-1]) / dg(xs[-1]))
    return xs


print([round(v, 10) for v in newton(x ** 2 - 2, 1.0)])
print([round(v, 10) for v in newton(x ** 3 - x - 1, 1.0)])
print([round(v, 10) for v in newton(x ** 3 - x - 1, 3.0, 8)])
print([round(v, 10) for v in newton(x ** 3 - 2 * x + 2, 0.0, 5)])
print(sp.nsolve(x ** 3 - x - 1, x, 1))
# [1.0, 1.5, 1.4166666667, 1.4142156863, 1.4142135624, 1.4142135624, 1.4142135624]
# [1.0, 1.5, 1.347826087, 1.325200399, 1.324718174, 1.3247179572, 1.3247179572]
# [3.0, 2.1153846154, 1.6042477584, 1.377421441, 1.3271331185, 1.3247233751, 1.3247179573, 1.3247179572, 1.3247179572]
# [0.0, 1.0, 0.0, 1.0, 0.0, 1.0]
# 1.32471795724475

// Newton's method with a central-difference derivative, a step limit and a flat-tangent check
const newton = (f, x0, { tol = 1e-12, max = 50 } = {}) => {
  let x = x0
  for (let n = 0; n < max; n++) {
    const h = 1e-6 * (1 + Math.abs(x))
    const d = (f(x + h) - f(x - h)) / (2 * h)
    if (d === 0 || !Number.isFinite(d)) return { x, n, status: 'flat' }
    const next = x - f(x) / d
    if (Math.abs(next - x) < tol * (1 + Math.abs(x))) return { x: next, n: n + 1, status: 'converged' }
    x = next
  }
  return { x, n: max, status: 'unfinished' }
}
const r1 = newton((x) => x ** 3 - x - 1, 1)
;[+r1.x.toFixed(10), r1.n, r1.status]                      // [1.3247179572, 6, 'converged']
const r2 = newton((x) => Math.cos(x) - x, 1)
;[+r2.x.toFixed(10), r2.n, r2.status]                      // [0.7390851332, 5, 'converged']: cos x = x
const r3 = newton((x) => x * x - 1, 0)
;[r3.x, r3.n, r3.status]                                    // [0, 0, 'flat']: the tangent at 0 is horizontal
const r4 = newton(Math.sin, 1.7)
;[+r4.x.toFixed(10), r4.n, r4.status]                      // [9.4247779608, 4, 'converged']: not the root 0 but 3 pi
newton((x) => x ** 3 - 2 * x + 2, 0, { max: 8 }).status    // 'unfinished': the iterates go 0, 1, 0, 1, ...

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;

int main() {
  double a = 2;
  double x = 1;                                          // the first guess
  for (int n = 0; n <= 5; n++) {
    printf("%d %.12f %.12f\n", n, x, fabs(x - sqrt(a)));
    x = (x + a / x) / 2;                                 // Newton's method for x*x - a = 0
  }
  return 0;
}

/* output:
0 1.000000000000 0.414213562373
1 1.500000000000 0.085786437627
2 1.416666666667 0.002453104294
3 1.414215686275 0.000002123901
4 1.414213562375 0.000000000002
5 1.414213562373 0.000000000000
*/

Who invented Newton’s method?

The idea of improving a guess for a root is four thousand years old, and the method carries the names of Newton and Raphson because of how they wrote it, not because they were the first to improve guesses.

• Babylon, about 1800–1600 BC. The clay tablet YBC 7289 gives √2 as 1;24,51,10 in base 60, which is 1.41421296…, correct to six decimals. Averaging a guess and the number divided by the guess, the rule of Example 1, is a likely way to get it.
• Heron of Alexandria, first century. Heron described the averaging rule for square roots, which is why the formula is also called Heron's method.
• Isaac Newton, 1669. In De analysi, written in 1669 and printed in 1711, Newton solved y^3-2y-5=0 by starting at 2, writing y=2+p, dropping the powers of p above the first, and repeating on the new polynomial. It was an algebraic process on the equation, not a formula for x_n+1.
• Joseph Raphson, 1690. Raphson published a way of repeating a single formula for polynomials, without rewriting the equation each time, which is the shape of the method we use.
• Thomas Simpson, 1740. Simpson described the method with derivatives, the form x-(f(x))/(f'(x)), for any equation and even for two equations at once.
• Fourier and Cauchy, 1820s. Joseph Fourier and Augustin-Louis Cauchy studied when the method converges.
• Cayley, 1879. Arthur Cayley asked which root Newton's method reaches from a start in the complex plane. For a quadratic the plane splits along a line; for a cubic the boundaries became the fractals later studied by Julia and Fatou.
• Kantorovich, 1948. Leonid Kantorovich proved a convergence theorem that needs conditions only at the starting point, and that works for systems of equations.

What mistakes do people make with Newton’s method?

The most common mistakes with Newton's method are the nine below, each with the correct statement.

Practice: test your understanding

These questions mix everything above. A wrong answer costs nothing here: read the hint and try again.

Summary: Newton’s method at a glance

• The formula: x_n+1=x_n-(f(x_n))/(f'(x_n)), the zero of the tangent line at x_n; it needs f'(x_n)\ne0.
• How to use it: write the equation as f(x)=0, choose x_0 from a graph or a sign change, iterate, and stop when the step and f(x_n) are both small.
• Speed: quadratic at a simple root, e_n+1=(f''(\xi))/(2f'(x_n))e_n^2; linear, with ratio (m-1)/(m), at a root of multiplicity m.
• Failures: a horizontal tangent, a cycle (x^3-2x+2 from 0), running off (x^(1/3), \arctan x far out), the wrong root (\sin x from 1.7).
• Basins: the starts that reach each root; the boundaries between them can be fine.
• By hand: \frac12\left(x+\frac ax\right) for √ a and x(2-ax) for \frac1a.
• Safeguards: a bracket and bisection as a fallback, a step limit, and a check of both the step and |f|.
• Next: antiderivatives, the reverse of differentiation.
• Code: a loop with a stopping rule; SymPy lambdify and diff, or a central difference.

Glossary: key terms

Root

A number r where a function is zero, f(r) = 0, and so a solution of the equation f(x) = 0.

Newton’s method

An iteration that replaces each approximation of a root by the point where the tangent line of the function crosses the x-axis.

Iteration

Repeating the same formula, each time on the result of the last step, to produce a sequence of approximations.

Quadratic convergence

A rate at which the error is roughly squared at each step, so the number of correct digits doubles.

Multiple root

A root where the derivative is also zero, so that the function has a factor (x − r) raised to a power m greater than one.

Basin of attraction

The set of starting values from which an iteration converges to a given root.

Bisection method

A root-finding method that halves a bracket where the function changes sign; it is slower than Newton’s method but cannot fail inside the bracket.

Frequently asked questions

References

1. Joel Hass, Christopher Heil, Maurice D. Weir et al. (2023). Thomas' Calculus: Early Transcendentals in SI Units (15th ed.), Section 4.7: Newton's Method. Pearson.
2. James Stewart (2015). Calculus (8th ed.), section 4.8: Newton’s Method. Cengage Learning.
3. Joseph Raphson (1690). Analysis aequationum universalis. London.
4. Thomas Simpson (1740). Essay on the Several Parts of the Doctrine of Fluxions, Section on the Resolution of Equations. London.

Related articles

• Linearization and Differentials: Linearization and differentials: the tangent-line approximation L(x) = f(a) + f′(a)(x − a), df = f′(x) dx, estimates, errors, percentage change and code.
• Applied Optimization: Applied optimization with derivatives: the four steps for max and min word problems, geometry, Snell’s law, marginal cost and inventory, with examples and code.
• Concavity and Curve Sketching: Concavity and curve sketching: the second derivative, points of inflection, the Second Derivative Test and seven steps to sketch a graph, with examples and code.
• The Mean Value Theorem: The Mean Value Theorem and Rolle’s Theorem: statements, proofs, how to find c, speed and rates, and the corollaries about constant functions, with examples and code.