Adding TOMS748 Algorithm for 1-d root-solving.
Hi all, I propose adding Algorithm 748 of Alefeld, Potro and Shi [APS1995] for root-finding in 1 dimension. The algorithm is also referred to as TOMS748. TOMS748 uses a mixture of inverse cubic interpolation and newton-quadratic steps to find a root of a function inside an interval. For functions with 4 continuous derivatives, the asymptotic efficiency index is about 1.65, making it converge more quickly than Brent’s method, and it may even converge in situations where Brent’s method has difficulty. This would be a new function toms748(f, a, b, ...) in scipy.optimize, sitting alongside optimize.{bisect,brentq,brenth,ridder,newton} External to SciPy, this algorithm is used by Boost as its default 1-d root finding algorithm. (See https://www.boost.org/doc/libs/1_63_0/libs/math/doc/html/math_toolkit/roots/... <https://www.boost.org/doc/libs/1_63_0/libs/math/doc/html/math_toolkit/roots/...>) The relevant PR is https://github.com/scipy/scipy/pull/8876 <https://github.com/scipy/scipy/pull/8876>, which also includes the addition of 15 test families used in the APS1993 paper, and two additional test families defined on the complex plane. Reference .. [APS1995] Alefeld, G. E. and Potra, F. A. and Shi, Yixun, *Algorithm 748: Enclosing Zeros of Continuous Functions*, ACM Trans. Math. Softw. Volume 221(1995) doi = {10.1145/210089.210111} -Paul
participants (1)
-
Paul van Mulbregt