Three Ways to Corner a Root, and the Speed They Cost

One equation, three hunters

You have a function and you want to know where it crosses zero. There is no formula for most equations worth asking about, so you do the only thing left: guess, measure how wrong you are, and guess better. Every root-finder ever written is a rule for that second step. Three classic ones have survived because each makes a different bargain with risk, and the interactive above races all three on the same equation so you can watch the bargain play out.

The default equation is x³ − 2x − 5 = 0. That is not a random cubic. It is the exact equation Isaac Newton wrote down in 1669 to demonstrate his method, and its only real root, near x = 2.0945514815, has been a numerical-analysis test case ever since. Two more are on the dial: cos x − x (whose root, 0.7390851332…, is the Dottie number, the value your calculator drifts to if you press cosine over and over) and x·eˣ − 1 (whose root is the omega constant, 0.5671432904…). Every digit of every root on this page is recomputed in your browser as it loads; nothing is looked up.

Here are the three hunters.

• Bisection. Start with two points where the function has opposite signs, so a root is trapped between them. Cut the interval in half, keep whichever half still straddles zero, repeat. It needs almost nothing (only that you can tell a positive value from a negative one) and it cannot fail: the root is always inside the shrinking bracket. Its price is that each step buys you exactly one more bit of the answer.
• The secant method. Forget the bracket. Take your last two guesses, draw the straight line through them, and jump to where that line hits the axis. It uses the shape of the function, not just its sign, so it closes in faster, but it can wander outside any bracket and miss.
• Newton. If you can also compute the function's slope, stand at your guess, slide down the tangent line to the axis, and start again. This is the fastest of the three when it works, doubling your correct digits every step, and the subject of an earlier drop about how brittle that speed is.

Step them in lockstep and the gap is not subtle. To pin Newton's cubic root to twelve correct digits, bisection needs about 37 steps, the secant 6, and Newton 5.

The slopes tell you everything

Counting steps is crude. The honest way to compare root-finders is to plot how many correct digits you have against how many steps you have taken, which is the second console above. Three curves come out, and their shapes are the whole story.

Bisection is a straight line. Halving the interval multiplies the error by exactly one half every step, so the number of correct digits grows by log₁₀(2) ≈ 0.301 each time: a little over three steps per decimal digit, forever, no matter how close you get. Steady, unglamorous, unbreakable.

The secant curve bends upward: each step's gain is bigger than the last. Newton's bends upward harder. They are not just faster than bisection by a constant factor; they accelerate, because each good guess makes the next guess disproportionately better. A method whose digit count is a straight line is called linear; the two that curve up are superlinear. But "superlinear" hides a sharp distinction, and to see it you have to measure the curve itself.

Order: the exponent hiding in the error

Convergence has a precise gear number. If eₙ is your error at step n, a method has order p when the next error behaves like the current one raised to the power p:

eₙ₊₁ ≈ C · eₙᵖ

Order p = 1 (with a constant C < 1) is linear: the error is multiplied by a fixed fraction, which is bisection with C = ½. Order p = 2 is quadratic: square the error each step, so 0.01 becomes 0.0001 becomes 0.00000001, the digit-doubling that makes Newton famous. The way to read p off real data is to take logarithms, because log eₙ₊₁ ≈ p · log eₙ + log C is a straight line whose slope is the order. That is the third console: each method's consecutive errors, plotted log against log, and the line they fall on.

• Bisection lies on a slope-1 line. Order exactly 1.
• Newton lies on a slope-2 line. Order exactly 2.
• The secant lands on a slope of about 1.618, the golden ratio φ.

That the secant's order is φ is one of the quietly beautiful facts in numerical analysis. It falls out because the method reuses information: each new guess leans on the previous two errors, and the exponent that balances the recurrence is the root of p² = p + 1, which is the defining equation of the golden ratio. The same number that governs sunflower spirals and Fibonacci nim sets the exact speed of a 350-year-old root-finder. The secant pays nothing for derivatives and still gets most of the way to Newton's quadratic speed; that φ-order efficiency is why it, not Newton, is the engine inside many production solvers.

Fast is also how you fall

Speed has a bill, and the fourth console sends it. Switch the equation to arctan x, whose only root is at zero, and start all three from a wide bracket. Bisection does not care that the function is strange; it keeps halving and closes in. Newton detonates. From a starting guess of x = 8, the tangent line is so flat that it flings the next guess to −86, then to 11,500, then past 10²⁷² and out of the number system entirely. The secant, with no bracket to hold it, follows Newton off the cliff.

This is the trade in one screen. Bisection has the worst order of the three and is the only one that cannot diverge. Newton has the best order and the least mercy: no bracket, needs a derivative, and a bad start or a flat spot throws it to infinity. The secant sits between them on both axes, φ-fast and almost as reckless. There is no free lunch; there is a spectrum, and where you sit on it is a choice about how much you trust your starting guess.

Which is why almost no library makes you choose. The function under scipy.optimize.brentq, under MATLAB's fzero, under most of the world's actual root-finding is Brent's method (Richard Brent, 1973): keep a guaranteed bracket like bisection, but each step try the fast superlinear jump (a secant or an inverse-quadratic guess) and take it only if it stays inside the bracket and actually helps; otherwise fall back to a safe bisection. It keeps bisection's ironclad guarantee and steals the secant's φ-order speed, spending a bisection step only in the freak weather where the fast move would have bolted. It is the same lesson the Newton relaxation dial taught with one knob, now built into a single algorithm: take the greedy step when it is safe, shrink back to the timid one when it is not.

What is computed here

Every trace, error, and slope on this page is produced live from the three iteration rules running in your browser, measured against a high-precision root computed on load. I verified the engine offline before building it (all checks passing): to twelve digits the cubic root takes bisection 37 steps, the secant 6, and Newton 5; the measured convergence order lands on 1.00 for bisection, 1.62 (the golden ratio) for the secant, and 2.00 for Newton across all three equations; bisection gains exactly log₁₀(2) digits per step; and on arctan x a Newton step from x = 8 diverges (8 → −86 → 1.15×10⁴ → … → 1.3×10²⁷²) while bisection on the same bracket keeps converging.

Sources

• Newton's method and the x³ − 2x − 5 example: Newton's method, Wikipedia
• The secant method and its golden-ratio order of convergence: Secant method, Wikipedia
• Brent's hybrid method, the production default: Brent's method, Wikipedia and scipy.optimize.brentq
• The named roots on the dial: Dottie number and Omega constant