Bisection Method Simulator — Root Finding by Interval Bracketing
Visualize the bisection iteration c=(a+b)/2 on f(x)=x^3-2x-5. Watch the bracket shrink by half each step, plot the log10 bracket-width decay, and tune the interval, tolerance, and max iterations.
Stop criterion and required iterations. For tolerance epsilon = 1e^-n, N is about log2((b0-a0)/epsilon). Linear convergence (error halves each step).
What is the Bisection Method
Given a continuous function with opposite signs at the two endpoints of a bracket, bisection chops the interval in half at each step and keeps the half that still contains the sign change. It is the most classical and the most robust root finder - the one method that absolutely cannot diverge.
🙋
How is this different from Newton-Raphson? I heard Newton is much faster.
🎓
Newton is faster on speed alone - quadratic convergence, so the error roughly squares each iteration. Bisection is linear: each step only halves the bracket. Reaching 1e-6 from a unit interval takes about log2(2/1e-6) which is about 21 iterations. The bisection win is it can never diverge. As long as f(a)*f(b)<0 holds, the intermediate-value theorem guarantees a root inside, and bisection grinds straight to it. Production codes use both: bisection to localize, then Newton or Brent's method to polish quickly.
🙋
What if both endpoints come out positive (or both negative)?
🎓
Then the hypothesis fails. Try a=1, b=2 in the simulator - f(1)=-6, f(2)=-1, both negative, and you'll see "same-sign error". The intermediate-value theorem only proves a root exists when the function changes sign; if it doesn't, there may be zero, two, or any even number of roots inside, and bisection cannot find them. The fix is to either move an endpoint until you see a sign change, or to plot f(x) once to pick a good initial bracket. Real bisection libraries always check f(a)*f(b)<0 before they start iterating.
🙋
If I tighten the tolerance to 1e-12, do I have to double the iterations?
🎓
Yes, roughly. Linear convergence means tightening from 1e-6 to 1e-12 costs another log2(10^6) which is about 20 iterations - way worse than Newton, where the same upgrade is one or two extra steps. The hard wall is double-precision machine epsilon at about 2.2e-16, beyond which arithmetic cancellation in computing (a+b)/2 can actually make things worse. In practice engineers use bisection up to about 1e-6 and switch to Newton or secant for anything tighter.
Physical Model and Key Equations
The bisection method is a direct translation of the intermediate-value theorem (IVT) into an algorithm: if f(a)*f(b)<0, then at least one root lies in (a, b).
$$c_n = \frac{a_n + b_n}{2}$$
Compute the midpoint, then pick the half whose endpoints still bracket the sign change:
One iteration gains about log10(2) which is about 0.301 decimal digits - slow compared to Newton's "digit doubling" but utterly reliable.
Real-World Applications
Nonlinear solver safety net (CAE): Abaqus and ANSYS fall back to a bisection-style bracket reduction when Newton-Raphson diverges in a load step. The arc-length (Riks) method also bisects the path-following constraint when its inner iteration cannot find a sign change.
Equation-of-state inversion (CFD, thermal): The pressure-from-density-and-temperature inversion of a real-gas EOS rarely has a closed-form inverse. SUPG, PISO, and SIMPLE pressure-velocity coupling all rely on bisection or Brent's method inside their sub-iterations.
Contact time-of-impact in explicit dynamics: When a node penetrates a contact surface during a step, bisection finds the exact instant t* where the penetration is zero, so the step can be redone with the correct contact pair active.
Line search in optimization: Gradient descent and Newton-type optimizers need a step length alpha that satisfies the Wolfe conditions. A bisection search (or golden-section, Armijo back-tracking) brackets the acceptable alpha and zeroes in on it.
Common Misconceptions and Pitfalls
The first myth is "linear convergence is so slow that bisection is useless". The iteration count is high, but each step only costs one evaluation of f(x). Newton requires both f and f' (or the full Jacobian in CAE), and assembling the tangent stiffness can dwarf the function cost. Per-iteration, bisection is often the cheapest choice.
Second, "the IVT guarantees one root" is wrong. It only guarantees an odd number of roots in the bracket. There could be three roots; bisection will still converge to one of them, but which one depends on where the midpoint sequence lands. Setting a=-2, b=3 in the simulator on a function with multiple roots shows this nicely.
Third, the discontinuity trap. The intermediate-value theorem requires continuity. Functions like 1/x flip sign at x=0 without passing through zero, and bisection will happily converge to that discontinuity as if it were a root. Always check the function's continuity, or visualize it before bracketing.
Frequently Asked Questions
Three common ones: (1) bracket width |b-a| < epsilon (positional accuracy), (2) residual |f(c)| < epsilon, (3) maximum iteration count. Production code typically combines (1) with (3); this simulator stops when either triggers. Residual-only criteria can terminate early near a root with very small f'(x*), so they should be used cautiously or together with a width bound.
The secant method uses the line through (a, f(a)) and (b, f(b)), giving super-linear convergence (order phi which is about 1.618) - faster than bisection but not always bracket-preserving. Brent's method combines bisection, secant, and inverse-quadratic interpolation with automatic switching; it is the standard root finder behind SciPy's brentq and MATLAB's fzero. If you do not need extreme speed, plain bisection is still the gold standard for robustness.
Pure bisection is one-dimensional. Higher-dimensional analogues exist - interval analysis, the Krawczyk operator, and box-subdivision algorithms - but they are far more complex. In practical CAE the multidimensional nonlinear solver is almost always Newton-Raphson with a Jacobian (or a quasi-Newton variant), and bisection appears only inside auxiliary one-dimensional sub-problems.
Run a coarse grid search first - sample f(x) at 10 to 100 points across the search range and locate sign changes between adjacent samples. Then refine each sign-change interval with bisection. Physical constraints (temperatures above absolute zero, positive pressures, etc.) frequently give natural bounds. For the cubic in this tool, any wide bracket such as [-5, 10] is guaranteed to contain the real root.