An improved bisection method
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.
The following have contributed to this page: Dr. Ricardo H. C. Takahashi and Ivo Oliveira