Root finding

@ac-kit/math-analysisPortable

import { bisect } from "@ac-kit/math-analysis";

Where you meet it. Solving for a break-even price, an interest rate that produces a given yield, the temperature at which two curves meet, or — inside this very package — the value at a given percentile, where the quantile has no closed form. Any time you can compute f(x) but cannot rearrange f(x) = 0 to get x on its own.

What it guarantees

bisect() requires a bracket: two points where f has opposite signs. That requirement is the whole strength of the method. The intermediate value theorem then guarantees a root inside the bracket, and bisection can never leave it — so it cannot fail, cannot diverge, and cannot return something wildly wrong.

If the signs match, there is no such guarantee and it throws rather than guessing.

Each step halves the interval, so the error after n steps is at most (upper − lower) / 2ⁿ. One bit of accuracy per step, forever.

EvidenceThe error after n steps never exceeds the bracket-halving bound (upper − lower) / 2ⁿ.

Bisection converges one bit per iteration

Each step halves the bracket, so the error after n steps is at most (upper − lower) / 2ⁿ. On a logarithmic axis that is a straight line, and its slope is the whole character of the method: linear convergence, but unconditionally reliable. The intermediate value theorem guarantees a root inside a sign-changing bracket, and bisection can never leave it — which is why it is the default here despite Newton's method being asymptotically faster and capable of diverging.

const { f, lower, upper, root } = FUNCTIONS[target];

const iterations: number[] = [];
const errors: number[] = [];
const bound: number[] = [];

for (let n = 1; n <= steps; n++) {
  const estimate = bisect(f, lower, upper, {
    maxIterations: n,
    tolerance: 0,
  });
  iterations.push(n);
  // Floored at one ulp: an exact hit has no logarithm to plot.
  errors.push(Math.max(Math.abs(estimate - root), Number.MIN_VALUE));
  bound.push((upper - lower) / 2 ** n);
}

const frame = curveFrame(
  iterations,
  [
    { name: "measured error", values: errors },
    { name: "(b − a) / 2ⁿ", values: bound },
  ],
  { x: "iteration", y: "error", series: "quantity" },
);

Why not Newton’s method?

Newton’s method converges much faster — roughly doubling the number of correct digits each step rather than adding one bit. But it needs the derivative, and it has no bracket to stay inside: from a poor starting point it can shoot off and never come back, with nothing in the output to say so.

Reliability wins by default here. A method that is slow is an inconvenience; a method that silently returns a wrong answer is a bug you ship.

Root finding

What it guarantees

Why not Newton’s method?

Further reading