[Intermediate] — Solving when there’s no formula, and why Newton’s method is everywhere despite being unreliable.

The problem

Enormously more general than it looks, because any equation rearranges into this form. becomes .

Where it shows up in this vault:

  • Inverse kinematics — find joint angles where the pose error is zero
  • Root locus — roots of the characteristic equation
  • Implicit ODE solvers — each step solves a nonlinear equation → ODEs
  • Optimisation — minimising means finding a root of
  • Internal rate of return, equilibrium points, break-even analysis

Bisection

The one that always works.

Requires a bracket: and with opposite signs. By the intermediate value theorem, a root lies between them.

while (b - a) > tol:
    c = (a + b) / 2
    if sign(f(c)) == sign(f(a)):  a = c
    else:                          b = c

Each iteration halves the interval. Error after steps: .

Guaranteed convergence, linear rate. To reach from an interval of 1 takes ~50 iterations.

Goodcannot fail if bracketed; needs only sign evaluations; no derivative
Badslow; needs a bracket; can’t find even-multiplicity roots (no sign change); doesn’t generalise to higher dimensions

Use c = a + (b-a)/2, not (a+b)/2. The second can overflow for large values and is less accurate. Same bug as binary search — and it’s the same fix.

Newton’s method

The one everybody uses.

The geometry: follow the tangent line at down to the -axis. That’s your next guess.

        │    ╱ f(x)
        │   ╱
        │  ╱ ●  ← x_n
        │ ╱ ╱ tangent
   ─────┼────●──────  x_{n+1}
        │

Quadratic convergence near a simple root:

Digits double every iteration. — four steps from a rough guess to machine precision, which is why it dominates.

And why it fails, which matters just as much:

Bad initial guess → divergence, or convergence to a different root than you wanted.

→ the tangent is nearly flat, the step is enormous, and you’re thrown across the number line.

Cycling — from oscillates between 0 and 1 forever.

Multiple roots degrade it to linear convergence. (Fixable: if you know the multiplicity .)

Needs — analytically, or by automatic differentiation, or approximated.

Newton is fast and unreliable. Bisection is slow and certain. That trade is the whole design space, and the practical answer is to combine them — which is what every production root-finder does.

Newton’s fractal is the vivid demonstration: colour each starting point in the complex plane by which root it converges to, and you get a fractal boundary. Arbitrarily close starting points converge to different roots. Sensitivity to the initial guess isn’t a rough edge; it’s structural.

Secant method

Newton without the derivative — approximate it from the last two points:

Superlinear convergence, order — the golden ratio, which is a pleasing bit of trivia and follows from the error recurrence.

One function evaluation per step instead of two (Newton needs and ), so in evaluations-per-digit it often beats Newton when derivatives are expensive.

Watch for cancellation in the denominator as the points converge — is exactly the near-equal subtraction from note 02.

Hybrid methods — what to actually use

Brent’s method is the answer for one-dimensional root finding. It maintains a bracket (so it cannot diverge), and uses inverse quadratic interpolation or the secant method when they’re behaving, falling back to bisection when they aren’t.

Superlinear convergence with a guarantee. This is what scipy.optimize.brentq, MATLAB’s fzero, and Boost’s toms748 implement, and you should call one of them rather than writing your own.

Ridders’ method is a simpler alternative with similar behaviour and is easier to implement if you must.

The general principle worth carrying beyond this note: a fast method that can fail, wrapped in a slow method that can’t, gives you both. The same pattern appears in robust control and in optimisation line searches.

Systems of equations

In dimensions, , Newton becomes:

with the Jacobian. Note you solve a linear system each iteration — you don’t invert . → Linear Systems

Everything gets harder:

No bracketing exists in dimensions. The intermediate value theorem doesn’t generalise, so there’s no safety net — this is the fundamental reason multidimensional root finding is harder than 1-D.

The Jacobian is evaluations if approximated by finite differences.

Near-singular — the same problem as singularities in robotics, and the same fix: damped least squares / Levenberg–Marquardt, adding to keep the step bounded.

The practical variants:

Line search — take the Newton direction but a shorter step: , choosing so the residual actually decreases. Turns divergent Newton into convergent Newton, and costs almost nothing.

Trust region — restrict the step to a region where the linear model is believed, adapting the radius based on how well it predicted.

Broyden’s method — the multidimensional secant: update an approximate Jacobian rather than recomputing it. Much cheaper per step, superlinear.

Continuation / homotopy — solve an easy problem and deform it into the hard one, tracking the solution. Genuinely useful when you have no good initial guess, and it’s how hard nonlinear systems in engineering get solved.

Practical notes

Bracket if you possibly can. A guaranteed method is worth a lot, and in 1-D you usually can — plot the function, or scan a grid for sign changes.

Plot it first. Ten seconds of plotting reveals multiple roots, flat regions, discontinuities and asymptotes — all things that break solvers silently.

Set a sensible convergence test. Three options, and they’re not equivalent:

  • — the residual. Meaningless if is badly scaled
  • — the step. Can trigger early if convergence stalls
  • Both, with relative tolerances. What production solvers do

Always cap the iterations, and return a status. A solver that silently returns garbage on failure is worse than one that errors.

Scale your variables so they’re . A solver working on a variable of magnitude and one of simultaneously will have tolerance problems.

Watch for multiple roots — convergence degrades to linear and the achievable accuracy drops to about , because the function is flat near the root. You cannot do better; the problem is ill-conditioned. → Conditioning

Use the library. brentq for bracketed 1-D, newton when you have a derivative and a good guess, fsolve/root for systems, least_squares for over-determined problems.


↑ Back to Numerical Methods