Skip to content
Tutorials Center
My learning

Topics

Lesson 11 of 37 ยท Root Finding

Newton-Raphson Method

Derive Newton's method from the tangent line, implement it in Python, see quadratic convergence, learn why it fails and how multiple roots slow it down.

Bisection is dependable but slow. Newton's method (also called Newton-Raphson) is the opposite: when it works it is astonishingly fast, doubling the number of correct digits at every step. It is the workhorse behind square-root routines, optimization, and solving large nonlinear systems.

The price is that it needs the derivative of f and a starting guess that is reasonably close to a root. This lesson derives the method, tests its speed, and then shows the situations where it misbehaves so you know what to watch for.

The idea: follow the tangent

At a guess x_k, replace the curve by its tangent line, which is a good local approximation. The tangent crosses the x axis at a new point, and that point is usually closer to the root.

The tangent at x_k is y = f(x_k) + f'(x_k)(x - x_k). Setting y = 0 and solving for x gives the Newton iteration:

x_(k+1) = x_k - f(x_k) / f'(x_k)

This is the same formula as the Babylonian square root: for f(x) = xยฒ - a we get x - (xยฒ - a)/(2x) = (x + a/x)/2.

flowchart LR
    A["Guess x_k"] --> B["Draw tangent at x_k"]
    B --> C["Tangent hits the axis at x_k+1"]
    C --> D{"|x_k+1 - x_k| small?"}
    D -->|"no"| A
    D -->|"yes"| E["Done"]

Each step trades the curve for its tangent line and moves to where that line is zero.

Implementation

Python Newton's method from scratch

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Bisection needed about 33 steps for this equation; Newton finishes in 3 or 4. The residual f(x) collapses from 1e-1 to 1e-3 to 1e-7 to 1e-15: quadratic convergence.

Why it converges quadratically

Let e_k = x_k - r. Expanding f and f' in Taylor series about the root r (where f(r) = 0) gives

e_(k+1) โ‰ˆ (f''(r) / (2 f'(r))) e_kยฒ

So the new error is proportional to the square of the old one, provided f'(r) โ‰  0. If the error is 1e-3 now, it is about 1e-6 next, then 1e-12. Check it numerically:

Python Watch e_(k+1) / e_k^2 settle

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The last column approaches a constant, |f''(r) / (2 f'(r))| โ‰ˆ 0.22, which confirms the error recurrence. This is how you verify second-order convergence in practice.

When Newton's method fails

Newton's method has no guarantee. It can fail in these ways:

Problem Why
f'(x_k) = 0 The tangent is horizontal and never meets the axis: division by zero
Bad starting point The tangent may send you far away, to another root or to infinity
Cycling Iterates bounce between two points forever
Multiple root Convergence drops from quadratic to linear
Non-smooth f The derivative may not exist or be wrong
Python Divergence and cycling

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For arctan, starting near the root works (it converges to 0), but starting at x0 = 2 the tangent overshoots further each time and the iterates grow. For xยณ - 2x + 2 the sequence 0, 1, 0, 1, ... never converges. The fix in both cases is a better starting value, often obtained from a few bisection steps or a plot.

Multiple roots

If r is a root of multiplicity m > 1 (e.g. f(x) = (x - 1)ยฒ) then f'(r) = 0 too. Newton still converges, but only linearly, with ratio (m - 1)/m: for a double root the error halves each step.

Python Double root: quadratic speed is lost

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

If you know the multiplicity m, the modified iteration x - m f(x)/f'(x) restores quadratic convergence. When you do not know m, apply Newton to u(x) = f(x)/f'(x), which has the same roots, all simple.

Derivatives in practice

You must supply f'. Options:

  • By hand when it is easy, as above.
  • Numerically: replace f'(x) by (f(x + h) - f(x)) / h. This is nearly the secant method, next lesson.
  • Automatic differentiation libraries (such as JAX), or symbolic tools (SymPy).

A common safeguard is a damped or safeguarded Newton step: if |f| does not decrease after a step, halve the step length. Production solvers also fall back on bisection when Newton jumps outside a known bracket.

Always stop on both a step tolerance and max_iter, and check f'(x) != 0. A Newton loop with no iteration cap can spin forever on a cycling problem.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What is the Newton iteration for f(x) = 0?

    It is where the tangent line at x meets the x axis.
  2. 2. What convergence does Newton's method have at a simple root?

    The new error is proportional to the square of the old error when f'(r) is not zero.
  3. 3. What happens at a double root?

    Because f'(r) = 0, the quadratic convergence argument fails and the rate falls to (m-1)/m.
  4. 4. Which is a typical way to recover when Newton's method diverges?

    A good start (often from bracketing) or a safeguarded step cures most failures.
  5. 5. Why is Newton's square-root iteration the same as the Babylonian method?

    x - (x^2 - a)/(2x) simplifies to (x + a/x)/2.

Summary

  • Newton: x_(k+1) = x_k - f(x_k)/f'(x_k), the zero of the tangent line.
  • Converges quadratically near a simple root: digits double each step.
  • It needs f', a good starting point and f'(x) โ‰  0; it can diverge or cycle.
  • Multiple roots reduce it to linear convergence; use m f/f' or f/f' to fix.
  • Safeguard with iteration limits and, in serious code, a bracketing fallback.

Next: Secant and False-Position Methods