Average-case optimality of a hybrid secant-bisection method

Abstract:

We present an average-case complexity analysis for the zerofinding problem for functions from ${C^r}([0,1]),r \geq 2$, which change sign at the endpoints. This class of functions is equipped with a conditional r-folded Wiener measure. We prove that the average-case complexity of computing an $\varepsilon$-approximation is of order $\log \log (1/\varepsilon )$, and that a hybrid secant-bisection method with a suitable adaptive stopping rule is almost optimal. This method uses only function evaluations. We stress that the adaptive stopping rule is crucial. If one uses a nonadaptive stopping rule, then the cost has to be of order $\log (1/\varepsilon )$. Hence, the adaptive stopping rule is exponentially more powerful than arbitrary nonadaptive stopping rules. Our algorithm is a slightly simplified version of the hyrbrid methods proposed by Dekker in 1969 and Bus and Dekker in 1975. These algorithms are still considered as "the best algorithms for zerofinding" by Kahaner, Moler, and Nash in their book on numerical methods.