Newton–Raphson Solver
Solve f(x) = 0 by Newton–Raphson, the secant method, bisection or false position, with the full iteration table.
f(x) = 8.88e-16 there
the fair cost comparison — Newton needs three per step to get a numerical derivative
measured from the run, not assumed (theory: 2)
x from 1.34y from -5.77 to 9.89to 2.76
The dashed line is y = 0. Hollow dots are the first few iterates, dropping towards it. The two axes carry different quantities, so they are scaled independently.
| n | xₙ | f(xₙ) | |xₙ − xₙ₋₁| |
|---|---|---|---|
| 1 | 2.100000000003 | 6.100e-2 | 1.00e-1 |
| 2 | 2.094568121105 | 1.857e-4 | 5.43e-3 |
| 3 | 2.094551481698 | 1.740e-9 | 1.66e-5 |
| 4 | 2.094551481542 | -8.882e-16 | 1.56e-10 |
| 5 | 2.094551481542 | -8.882e-16 | 0 |
Scanning from -4 to 9 finds 1 sign change, so at least that many roots lie in range: [2.067, 2.11]. A scan cannot see a root the curve only touches.
Newton–Raphson replaces the curve with its tangent line and jumps to where that line crosses zero: x₁ = x₀ − f(x₀) ÷ f′(x₀), repeated. It roughly doubles the number of correct digits each step, but only once it is close enough, and it can fail outright.
Four methods, and what each one buys
Most equations worth solving have no formula for their roots. x⁵ − x − 1 = 0 is the standard example: it has a perfectly ordinary real root near 1.167, and Abel’s theorem says no expression in radicals can write it down. So you iterate instead, and the choice of method is a trade between speed and safety.
Bisection is the safe one. Given an interval where f changes sign, a root must lie inside, and halving the interval keeps that true forever. It cannot fail and it cannot be hurried: each step buys exactly one bit, so about 3.3 steps per decimal digit regardless of the function. Newton is the fast one. Near a simple root the error squares each step — three correct digits become six, then twelve — but it needs a derivative, it needs a decent starting point, and given a bad one it can cycle forever or shoot off to infinity.
Why the function-call count is the honest comparison
Counting iterations flatters Newton. Each Newton step here needs three evaluations of f — one for the value and two more for the numerical derivative — while bisection and the secant method need one apiece. On x³ − 2x − 5 from a sensible start, Newton reaches machine precision in 6 steps but 18 evaluations; the secant method takes 7 steps and 9 evaluations. If evaluating f is the expensive part, which it usually is, the secant method wins despite converging more slowly per step.
the tangent at xₙ crosses the axis at xₙ₊₁ — that is the whole method
- 1 Put the equation in the form f(x) = 0. Move everything to one side. To solve cos x = x, enter cos(x) − x.
- 2 Find a starting point near the root. Sketch the function, or scan for a sign change. Newton converges to whichever root its tangent happens to lead to, not necessarily the nearest one.
- 3 Take the step x − f(x) ÷ f′(x). Geometrically: follow the tangent line down to the axis, and start again from there.
- 4 Stop when the step stops changing anything. Either |xₙ − xₙ₋₁| falls below your tolerance or f(xₙ) is as close to zero as the arithmetic allows.
- 5 Check the answer in the original equation. A small residual is the evidence. An iteration that converged neatly to the wrong thing is still wrong.
How the four methods compare
Order p means the error behaves like eₙ₊₁ ≈ C·eₙᵖ. Higher is faster, once it is converging at all.
| Method | Needs | Order | Can it fail? | f evaluations per step |
|---|---|---|---|---|
| Bisection | A bracket with a sign change | 1 (halves each step) | No — guaranteed once bracketed | 1 |
| False position | A bracket with a sign change | Between 1 and 1.618 | No, but one end can stick and it crawls | 1 |
| Secant | Two starting points, no bracket | ≈ 1.618 | Yes — can diverge or go flat | 1 |
| Newton–Raphson | One starting point and f′ | 2 | Yes — can cycle or run to infinity | 1 with a formula, 3 with a numerical derivative |
When Newton fails, and how to tell
Three failures are common enough to recognise. If f′ is zero at your starting point the tangent is horizontal and never meets the axis — try x² + 1 from x = 0 and the method stops on the first step. If the curve has the wrong shape between your guess and the root, the iteration can settle into a cycle: x³ − 2x + 2 started from 0 sends you to 1, then back to 0, forever, and this page reports it as hitting the iteration limit rather than quietly returning the last value.
The third is subtler. At a repeated root — where f and f′ vanish together, as at x = 2 in (x − 2)² — Newton still converges, but linearly rather than quadratically, halving the error each step like bisection. The iteration table gives this away: the observed order shown above the table is measured from the run itself rather than assumed, so a value near 1 where you expected 2 is telling you the root is repeated.
False position deserves a warning of its own. It looks strictly better than bisection — it uses the actual function values rather than just their signs — but on a curve that keeps its convexity across the bracket, one endpoint never moves. The bracket stops shrinking, and convergence slows to a crawl: on x⁵ − x − 1 the same end stays put for 74 steps running. The Illinois variant fixes this by halving the stuck function value, which is why textbooks that teach regula falsi usually teach Illinois straight afterwards.