ITP method

The ITP method, short for Interpolate, Truncate and Project, is a root-finding algorithm from numerical analysis that finds a point where a continuous function crosses zero inside an interval whose end values have opposite signs. It was designed to combine two properties that earlier methods offered separately: the superlinear convergence of the secant method on well-behaved functions, and the guaranteed worst-case number of evaluations of the bisection method on badly behaved ones. Each iteration computes a regula falsi estimate, nudges it toward the interval midpoint in a truncation step, and then projects it into a neighbourhood of the midpoint sized so that the total number of function evaluations never exceeds the bisection bound plus a chosen slack. The user sets three hyper-parameters that control how far the estimate is truncated and how much slack is allowed. The article reports that with no slack the method is guaranteed never to need more iterations than bisection, and it cites an example polynomial where it took less than half as many iterations as bisection. An implementation is available as a package for the R language.