Mathematics.

root finding

Newton's Method

Numerical Analysis25 minDifficulty4 out of 10

You should know: derivative, numerical methods

Overview

Newton's method (also called the Newton–Raphson method) is an iterative algorithm for finding a root of a differentiable function f(x) = 0. Starting from an initial guess x₀, it repeatedly replaces the function by its tangent line at the current estimate and moves to where that tangent crosses the x-axis. Near a simple root, and given a sufficiently good starting point, the method converges quadratically — the number of correct decimal digits roughly doubles with each iteration. This speed makes it the default root finder in most numerical software, though it requires the derivative f′(x) and can fail to converge if f′ is near zero or the initial guess is poor.

Intuition

Picture standing on the curve y = f(x) at your current guess xₙ and looking at the tangent line there. That line is the best straight-line approximation to the curve near xₙ, so wherever it crosses the x-axis is a good guess for where the curve itself crosses zero. Sliding down the tangent to its intercept gives xₙ₊₁, and repeating this — draw a tangent, slide to its zero, repeat — homes in on the root remarkably fast whenever the curve is well-approximated by its tangent near the root, which is exactly what quadratic convergence captures.

Formal Definition

Definition

Given a differentiable function f and a current estimate xₙ, the next estimate is the x-intercept of the tangent line to f at xₙ:

xn+1=xn−f(xn)f′(xn)x_{n+1} = x_n - \dfrac{f(x_n)}{f'(x_n)}
Newton's iteration
f(x)≈f(xn)+f′(xn)(x−xn)f(x) \approx f(x_n) + f'(x_n)(x - x_n)
Tangent-line approximation used to derive the iteration
en+1≈f′′(r)2f′(r) en2,en=xn−re_{n+1} \approx \dfrac{f''(r)}{2f'(r)}\,e_n^2, \quad e_n = x_n - r
Quadratic convergence near a simple root r

Worked Examples

  1. f(x) = x² − 2, f′(x) = 2x, so the iteration simplifies to the classic Babylonian average form.

    xn+1=xn−xn2−22xn=xn2+1xnx_{n+1} = x_n - \dfrac{x_n^2-2}{2x_n} = \dfrac{x_n}{2} + \dfrac{1}{x_n}

  2. Step 1 from x₀ = 1.

    x1=12+11=0.5+1=1.5x_1 = \dfrac{1}{2} + \dfrac{1}{1} = 0.5 + 1 = 1.5

  3. Step 2 from x₁ = 1.5.

    x2=1.52+11.5=0.75+0.6666‾=1.416‾x_2 = \dfrac{1.5}{2} + \dfrac{1}{1.5} = 0.75 + 0.666\overline{6} = 1.41\overline{6}

  4. Step 3 from x₂ = 1.416666....

    x3=1.4166‾2+11.4166‾=0.708333+0.705882=1.414216x_3 = \dfrac{1.416\overline{6}}{2} + \dfrac{1}{1.416\overline{6}} = 0.708333 + 0.705882 = 1.414216

  5. Compare to the true value.

    2=1.414214…\sqrt{2} = 1.414214\ldots

Answer: x₃ ≈ 1.414216, matching √2 = 1.414214… to 5 decimal places after just 3 iterations.

Practice Problems

Difficulty 3/10

Starting from x₀ = 2, compute one Newton's-method step for f(x) = x² − 5.

Difficulty 5/10

A machinist needs the root of f(x) = cos(x) − x = 0 (where a line meets the cosine curve). Starting from x₀ = 0.75, and given f′(x) = −sin(x) − 1, compute x₁.

Difficulty 4/10

Which condition most commonly causes Newton's method to fail to converge or diverge?

Quiz

Newton's method updates the estimate using:
Near a simple root with a good starting guess, Newton's method converges:
What does Newton's method require that the bisection method does not?

Summary

  • Newton's method iterates x_{n+1} = x_n − f(x_n)/f′(x_n), following the tangent line to its x-intercept.
  • Convergence is quadratic near a simple root with a good initial guess — correct digits roughly double each step.
  • It can diverge if f′ is near zero or the starting guess is poor, unlike guaranteed-but-slower bracketing methods.

References

  1. WebsiteWikipedia — Newton's method