An Enhancement of the Bisection Method Average Performance Preserving Minmax Optimality

  • I. F. D. Oliveira, R. H. C. Takahashi
  • ACM Transactions on Mathematical Software, December 2020, ACM (Association for Computing Machinery)
  • DOI: 10.1145/3423597

An improved bisection method

Photo by Volkan Olmez on Unsplash

Photo by Volkan Olmez on Unsplash

What is it about?

When solving an equation numerically, a common misconception is that you have to chose between reliable methods such as the bisection method and fast methods such as the secant method. In this paper we show how to solve numerical equations with the worst case guarantees of the bisection method and the asymptotic guarantees of the secant method with zero trade-offs. Our simple yet novel technique, which we call the ITP method standing for "Interpolate, Truncate and Project", is the main tool we offer in this paper. We show that it not only outperforms the thus-farr-unbeaten bisection method but also, much of the current state of the art in numerical root solving.

Why is it important?

Our techniques have the potential to significantly speed-up numerical softwares without giving up on reliability. One of the somewhat surprising implications of our findings is that standard off-the-shelf solutions found in virtually every numerical software suffers either from ineficient minmax performance or a lacking asymptotic convergence; both of which are avoidable with the a proper use of the ITP method.

Perspectives

Ivo Oliveira
Universidade Federal dos Vales do Jequitinhonha e Mucuri

I hope that the ITP method finds it's way into both numerical softwares (matlab, mathematica amongst others) as well as numerical text-books (such as numerical analysis undergrad courses, optimization theory etc.). This way both practitioners and academics can benefit of the improvements here identified. But, perhaps more importantly, that future developers will keep in mind that worst-case and asymptotic performance need not be traded-off, but rather, that both metrics can often be simultaneously optimized with careful software craftsmanship.

Read Publication

http://dx.doi.org/10.1145/3423597

The following have contributed to this page: Dr. Ricardo H. C. Takahashi and Ivo Oliveira