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.
Featured Image
Photo by Volkan Olmez on Unsplash
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
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.
Ivo Oliveira
Universidade Federal dos Vales do Jequitinhonha e Mucuri
Read the Original
This page is a summary of: An Enhancement of the Bisection Method Average Performance Preserving Minmax Optimality, ACM Transactions on Mathematical Software, March 2021, ACM (Association for Computing Machinery),
DOI: 10.1145/3423597.
You can read the full text:
Contributors
The following have contributed to this page
