Root Finding

Solve f(x) = 0 when algebra can't. Learn bisection, false position, fixed-point iteration, Newton–Raphson and the secant method — formulas, algorithms, preconditions, convergence rates, failure cases and stopping criteria — with Python implementations compared on the same equation.

Friction factors (Colebrook equation), operating points of non-linear circuits, pipe network flows, kinematic positions and equilibrium states all require solving non-linear equations numerically.

An analogy

Bisection is like guessing a number with 'higher/lower' hints — slow but sure. Newton's method is like sliding down the tangent — very fast if you start close.

Bracketing methods

Bisection and false position need f(a)f(b) < 0 (IVT) and always converge for continuous f. Bisection halves the interval each step (linear convergence).

Open methods

Newton uses the tangent — quadratic convergence near a simple root, but needs f′ and a good start. Secant replaces f′ with a finite difference. Fixed-point iteration converges only if |g′(x*)| < 1.

Stopping criteria

Stop when |xₙ₊₁ − xₙ| < tol, |f(xₙ)| < tol, or after a maximum iteration count — use more than one criterion.

Failure modes and hybrids

Newton fails near f′ = 0, can cycle or diverge, and slows at multiple roots. Brent's method (scipy.optimize.brentq) combines bisection safety with fast interpolation — the practical default.

Formulas

• Bisection: m = (a + b)/2; keep the half with a sign change; n ≥ log₂((b − a)/tol)
• False position: x = b − f(b)(b − a)/(f(b) − f(a))
• Fixed point: x = g(x): xₙ₊₁ = g(xₙ), converges if |g′| < 1
• Newton–Raphson: xₙ₊₁ = xₙ − f(xₙ)/f′(xₙ) (quadratic: eₙ₊₁ ≈ C eₙ²)
• Secant: xₙ₊₁ = xₙ − f(xₙ)(xₙ − xₙ₋₁)/(f(xₙ) − f(xₙ₋₁)) (order ≈ 1.618)

Worked example: Bisection iteration count

Given: [1, 2], tol 10⁻⁶

Find: Iterations.

• n ≥ log₂(1/10⁻⁶) − 1 ≈ 19

Answer: 19 halvings

Worked example: Newton for √2

Given: f = x² − 2

Find: Iteration formula.

• xₙ₊₁ = xₙ − (xₙ² − 2)/(2xₙ) = (xₙ + 2/xₙ)/2 (Babylonian method)

Answer: 1 → 1.5 → 1.41667 → 1.414216

Bisection, Newton and secant compared

import math

f  = lambda x: x**3 - x - 1          # root near 1.3247
df = lambda x: 3*x**2 - 1

def bisection(a, b, tol=1e-6):
    n = 0
    while (b - a) / 2 > tol:
        m = (a + b) / 2
        if f(a) * f(m) <= 0: b = m
        else:                a = m
        n += 1
    return (a + b) / 2, n

def newton(x, tol=1e-12, maxit=50):
    for n in range(1, maxit + 1):
        step = f(x) / df(x)
        x -= step
        if abs(step) < tol:
            return x, n
    raise RuntimeError("no convergence")

def secant(x0, x1, tol=1e-12):
    n = 0
    while abs(x1 - x0) > tol:
        x0, x1 = x1, x1 - f(x1) * (x1 - x0) / (f(x1) - f(x0))
        n += 1
    return x1, n

print("bisection: %.10f  (%d iterations)" % bisection(1, 2))
print("newton:    %.10f  (%d iterations)" % newton(1.5))
print("secant:    %.10f  (%d iterations)" % secant(1, 2))
# bisection: 1.3247175217  (19 iterations)
# newton:    1.3247179572  (5 iterations)
# secant:    1.3247179572  (8 iterations)

Bisection needs 19 steps for 10⁻⁶ accuracy; Newton reaches machine precision in 5 because the number of correct digits roughly doubles each step; secant is nearly as fast without needing f′.

Common mistakes

• Wrong: Starting Newton far from the root. — Right: Bracket first, or use a hybrid method.
• Wrong: Only checking |f(x)| small. — Right: Flat functions can have small f far from the root.

Applications

• Pipe flow: Colebrook friction factor.
• Circuits: Diode operating points.
• Mechanisms: Position analysis of linkages.

Key takeaways

• Bracketing = safe; open methods = fast.
• Newton: xₙ₊₁ = xₙ − f/f′.
• Use combined stopping criteria.
• Use hybrids (Brent) in practice.

Going further

• Brent's method: Robust hybrid root finder.
• Newton for systems: Jacobian-based multivariable solving.
• Polynomial roots: Companion-matrix eigenvalues.