6
$\begingroup$

We know that the bisection method for root finding is slow (linear convergence), but has the advantage of always working for a continuous function, if we start with a interval which brackets the root. However, the arithmetic is very simple, no derivatives are required, and only one new function evaluation is needed each iteration.

However, in practice, and with modern computer speeds and processing power, computing, say, 30 iterates of bisection can be done in a fraction of a second. Irrespective of the theory, solving a single root-finding problem would seem to take hardly any more computing time than a better method.

All books say: bisection - works but slow; Newton-Raphson/Secant etc: sometimes fails but much faster. And in the days of hand computation the time differences would have been considerable. I wonder, though, with modern computational tools, and with practical precision requirements (does anybody really need 100 decimal place accuracy?), if the bisection method is really as slow as all the texts seem to indicate?

$\endgroup$
4
  • 2
    $\begingroup$ In most problems we care in practice involve finding the root of a function of several variables. As the number of variables increases speed becomes more important. $\endgroup$ Commented Dec 15, 2013 at 9:22
  • 1
    $\begingroup$ Additionally, while Newton may be overkill for solving a single root finding problem, things may be very different if you have to do it billions of times, as may be the case in some large scale simulations. $\endgroup$ Commented Dec 15, 2013 at 9:27
  • $\begingroup$ @HaraldHanche-Olsen. Same numbers at the same time with the same concerns ! Cheers. $\endgroup$ Commented Dec 15, 2013 at 9:55
  • $\begingroup$ Sometimes (in practical applications) a function may be very expensive to evaluate even with modern computational resources, so a few iterations less may matter. $\endgroup$
    – Roger V.
    Commented Sep 15, 2021 at 12:49

3 Answers 3

3
$\begingroup$

The problem is very context dependent. If you have a single equation to solve in a known range, use bisection. There are methods which are faster for this kind of situations (for example : use a Newton step; ,if it keeps you in the interval, continue with Newton; if not, use bisection).
Where the problem starts to be different is when you have billions (trillions) of times an equation to be solved (for example : dynamic simulation of chemical processes, oil and gas reservoir simulations, ...). In such cases, even very marginal savings in CPU time have a lot of impact.

$\endgroup$
1
3
$\begingroup$

Another possibility is that $f(x)$ may be very expensive to compute. For example, it may involve solving a PDE numerically, where $x$ is some parameter and $f(x)$ is some statistic based on the solution of the PDE. Once you have a numeric PDE solver, it is usually quite easy and relatively inexpensive to add code to compute the derivatives with respect to some parameters (sometimes called the sensitivity of the solution wrt said parameters), so computing $f(x)$ and $f'(x)$ together may be less costly than two evaluations of $f(x)$, say. Now the savings of Newton's method become significant once more.

To illustrate this, consider the simpler case of an ODE: Say $\dot y=g(t,y,x)$, where $x$ is some independent parameter. So the solution will be a function of $t$ and $x$. Write $y_x$ for the partial derivative of the solution wrt $x$. Then $y_x$ satisifies the linear ODE $\dot y_x=g_x(t,y,x)+g_y(t,y,x)y_x$, which is easy to solve numerically as soon as you know $y$.

$\endgroup$
2
$\begingroup$

There is no reason to use the bisection method when the Regula falsi variants, the most simple one the Illinois variation, provide faster superlinear convergence with almost no more computational or coding effort and the same safety features of a bracketing method as the bisection method.

The Dekker and Brent methods are almost as fast as, resp. in nice cases faster than a secant iteration while preserving the safety of a bracketing method, but have more code complexity.

$\endgroup$
1
  • $\begingroup$ The initial claim is somewhat false, the Illinois variants tend to be (in my experience) less robust if the root cannot be properly estimated by a secant line, is somewhat more sensitive to the initial bracket, and also suffers tragically from an inability to give a guaranteed bound on how long it takes to find the root, which are the main advantages of bisection and that which the methods by Dekker and Brent mentioned take advantage of. $\endgroup$ Commented Sep 27, 2020 at 3:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .