Quadrature formulas for monotone functions
HTML articles powered by AMS MathViewer
- by Erich Novak
- Proc. Amer. Math. Soc. 115 (1992), 59-68
- DOI: https://doi.org/10.1090/S0002-9939-1992-1086337-X
- PDF | Request permission
Abstract:
We prove that adaptive quadrature formulas for the class of monotone functions are much better than nonadaptive ones if the average error is considered. Up to now it was only known that adaptive methods are not better in the worst case (for this and many other classes of functions) or in various average case settings. We also prove that adaptive Monte Carlo methods are much better than nonadaptive ones. This also contrasts with analogous results for other classes (Sobolev classes, Hölder classes) where adaptive methods are only slightly better than nonadaptive ones.References
- N. S. Bahvalov, Approximate computation of multiple integrals, Vestnik Moskov. Univ. Ser. Mat. Meh. Astr. Fiz. Him. 1959 (1959), no. 4, 3–18 (Russian). MR 0115275 —, On the optimality of linear methods for operator approximation in convex classes of functions, USSR Comput. Math. and Math. Phys. 11 (1971), 244-249.
- I. A. Glinkin and A. G. Sukharev, Investigation of the efficiency of some algorithms for numerical integration and their application for solution of extremal problems, Voprosy Kibernet. (Moscow) 122 (1985), 23–37 (Russian). MR 814090
- S. Graf, R. Daniel Mauldin, and S. C. Williams, Random homeomorphisms, Adv. in Math. 60 (1986), no. 3, 239–359. MR 848153, DOI 10.1016/S0001-8708(86)80001-9
- S. Graf and E. Novak, The average error of quadrature formulas for functions of bounded variation, Rocky Mountain J. Math. 20 (1990), no. 3, 707–716. MR 1073718, DOI 10.1216/rmjm/1181073094
- Seymour Haber, Numerical evaluation of multiple integrals, SIAM Rev. 12 (1970), 481–526. MR 285119, DOI 10.1137/1012102
- J. Kiefer, Optimum sequential search and approximation methods under minimum regularity assumptions, J. Soc. Indust. Appl. Math. 5 (1957), 105–136. MR 92326
- D. Lee and G. W. Wasilkowski, Approximation of linear functionals on a Banach space with a Gaussian measure, J. Complexity 2 (1986), no. 1, 12–43. MR 925342, DOI 10.1016/0885-064X(86)90021-X
- Erich Novak, Deterministic and stochastic error bounds in numerical analysis, Lecture Notes in Mathematics, vol. 1349, Springer-Verlag, Berlin, 1988. MR 971255, DOI 10.1007/BFb0079792
- Edward W. Packel, The algorithm designer versus nature: a game-theoretic approach to information-based complexity, J. Complexity 3 (1987), no. 3, 244–257. MR 919675, DOI 10.1016/0885-064X(87)90014-8 W. Sierpiński, Elementary theory of numbers, Warszawa, 1964.
- Aleksei G. Sukharev, On the existence of optimal affine methods for approximating linear functionals, J. Complexity 2 (1986), no. 4, 317–322. MR 923025, DOI 10.1016/0885-064X(86)90009-9
- Aleksei G. Sukharev, The concept of sequential optimality for problems in numerical analysis, J. Complexity 3 (1987), no. 3, 347–357. MR 919681, DOI 10.1016/0885-064X(87)90020-3
- A. V. Sul′din, Wiener measure and its applications to approximation methods. I, Izv. Vysš. Učebn. Zaved. Matematika 1959 (1959), no. 6 (13), 145–158 (Russian). MR 0157489
- J. F. Traub, G. W. Wasilkowski, and H. Woźniakowski, Information-based complexity, Computer Science and Scientific Computing, Academic Press, Inc., Boston, MA, 1988. With contributions by A. G. Werschulz and T. Boult. MR 958691 G. W. Wasilkowski and F. Gao, On the power of adaptive information for functions with singularities. Technical Report, University of Kentucky, 1989.
- S. Zubrzycki, Some approximate integration formulas of statistical interest, Colloq. Math. 11 (1963), 123–136. MR 161474, DOI 10.4064/cm-11-1-123-136
- D. Zwick, Optimal quadrature for convex functions and generalizations, Numerical integration, III (Oberwolfach, 1987) Internat. Schriftenreihe Numer. Math., vol. 85, Birkhäuser, Basel, 1988, pp. 310–315. MR 1021545
Bibliographic Information
- © Copyright 1992 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 115 (1992), 59-68
- MSC: Primary 41A55; Secondary 65C05, 65D32
- DOI: https://doi.org/10.1090/S0002-9939-1992-1086337-X
- MathSciNet review: 1086337