Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society, the Mathematics of Computation (MCOM) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

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

The 2020 MCQ for Mathematics of Computation is 1.98.

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

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
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: https://doi.org/10.1090/S0025-5718-1995-1312098-3
  • MathSciNet review: 1312098