Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Average-case optimality of a hybrid secant-bisection method

Authors: Erich Novak, Klaus Ritter and Henryk Woźniakowski
Journal: Math. Comp. 64 (1995), 1517-1539
MSC: Primary 65H05
MathSciNet review: 1312098
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65H05

Retrieve articles in all journals with MSC: 65H05

Additional Information

Keywords: Zerofinding, hybrid secant-bisection method, hybrid Newton-bisection method, average-case complexity
Article copyright: © Copyright 1995 American Mathematical Society

American Mathematical Society