Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society since 1960 (published as Mathematical Tables and other Aids to Computation 1943-1959), Mathematics of Computation is devoted to research articles of the highest quality in computational mathematics.

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

The 2020 MCQ for Mathematics of Computation is 1.78.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.


Average-case optimality of a hybrid secant-bisection method
HTML articles powered by AMS MathViewer

by Erich Novak, Klaus Ritter and Henryk Woźniakowski PDF
Math. Comp. 64 (1995), 1517-1539 Request permission


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.
Similar Articles
  • Retrieve articles in Mathematics of Computation with MSC: 65H05
  • Retrieve articles in all journals with MSC: 65H05
Additional Information
  • © Copyright 1995 American Mathematical Society
  • Journal: Math. Comp. 64 (1995), 1517-1539
  • MSC: Primary 65H05
  • DOI:
  • MathSciNet review: 1312098