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
- G. Alefeld, F. A. Potra, and Yixun Shi, On enclosing simple roots of nonlinear equations, Math. Comp. 61 (1993), no. 204, 733–744. MR 1192965, DOI 10.1090/S0025-5718-1993-1192965-2
- J. C. P. Bus and T. J. Dekker, Two efficient algorithms with guaranteed convergence for finding a zero of a function, ACM Trans. Math. Software 1 (1975), no. 4, 330–345. MR 386254, DOI 10.1145/355656.355659
- T. J. Dekker, Finding a zero by means of successive linear interpolation, Constructive Aspects of the Fundamental Theorem of Algebra (Proc. Sympos., Zürich-Rüschlikon, 1967) Wiley-Interscience, New York, 1969, pp. 37–48. MR 0256551 D. Kahaner, C. Moler, and S. Nash, Numerical methods and software, Prentice-Hall, Englewood Cliffs, NJ, 1989.
- L. V. Kantorovič, Functional analysis and applied mathematics, Uspehi Matem. Nauk (N.S.) 3 (1948), no. 6(28), 89–185 (Russian). MR 0027947
- Michel Ledoux and Michel Talagrand, Probability in Banach spaces, Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)], vol. 23, Springer-Verlag, Berlin, 1991. Isoperimetry and processes. MR 1102015, DOI 10.1007/978-3-642-20212-4
- Erich Novak and Klaus Ritter, Some complexity results for zero finding for univariate functions, J. Complexity 9 (1993), no. 1, 15–40. Festschrift for Joseph F. Traub, Part I. MR 1213485, DOI 10.1006/jcom.1993.1003
- J. M. Ortega and W. C. Rheinboldt, Iterative solution of nonlinear equations in several variables, Academic Press, New York-London, 1970. MR 0273810
- A. M. Ostrowski, Solution of equations in Euclidean and Banach spaces, Pure and Applied Mathematics, Vol. 9, Academic Press [Harcourt Brace Jovanovich, Publishers], New York-London, 1973. Third edition of Solution of equations and systems of equations. MR 0359306
- Klaus Ritter, Average errors for zero finding: lower bounds for smooth or monotone functions, Aequationes Math. 48 (1994), no. 2-3, 194–219. MR 1295091, DOI 10.1007/BF01832985
- Jerome Sacks and Donald Ylvisaker, Designs for regression problems with correlated errors. III, Ann. Math. Statist. 41 (1970), 2057–2074. MR 270530, DOI 10.1214/aoms/1177696705 K. Sikorski, Optimal solution for nonlinear equations, J. Complexity 1 (1985), 197-209.
- J. F. Traub, Iterative methods for the solution of equations, Prentice-Hall Series in Automatic Computation, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1964. MR 0169356
- G. W. Wasilkowski, Information of varying cardinality, J. Complexity 2 (1986), no. 3, 204–228. MR 922813, DOI 10.1016/0885-064X(86)90002-6
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