Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



Quadrature formulas for monotone functions

Author: Erich Novak
Journal: Proc. Amer. Math. Soc. 115 (1992), 59-68
MSC: Primary 41A55; Secondary 65C05, 65D32
MathSciNet review: 1086337
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] N. S. Bakhvalov, On approximate computation of integrals, Vestnik Moscow State University Ser. Mat. Mekh. Astronom. Phys. Chem. 4 (1959), 3-18 (Russian) MR 0115275 (22:6077)
  • [2] -, On the optimality of linear methods for operator approximation in convex classes of functions, USSR Comput. Math. and Math. Phys. 11 (1971), 244-249.
  • [3] I. A. Glinkin and A. G. Sukharev, Efficiency analysis of some algorithms of numerical integration and their applications to the solution of extremal problems in Models and Methods of Global Optimizatin (V. V. Fedorov, ed.) Voprosy Kibernet. (Moscow) 122 (1985), 23-37 (Russian) MR 814090 (87c:65074)
  • [4] S. Graf, R. D. Mauldin, and S. C. Williams, Random homeomorphisms, Adv. in Math. 60 (1986), 239-359 MR 848153 (87k:60010)
  • [5] S. Graf and E. Novak, The average error of quadrature formulas for functions of bounded variation, Rocky Mountain J. Math. 20 (1990), 707-716. MR 1073718 (91m:65070)
  • [6] S. Haber, Numerical evaluation of multiple integrals, SIAM Review 12 (1970), 481-526. MR 0285119 (44:2342)
  • [7] J. Kiefer, Optimum sequential search and approximation methods under minimum regularity assumptions, J. Soc. Indust. Appl. Math. 5 (1957), 105-136. MR 0092326 (19:1097d)
  • [8] D. Lee and G. Wasilkowski, Approximation of linear functionals on a Banach space with Gaussian measure, J. Complexity 2 (1986), 12-43. MR 925342 (88m:65088)
  • [9] E. Novak, Deterministic and stochastic error bounds in numerical analysis, Lecture Notes in Math., vol. 1349, 1988. MR 971255 (90a:65004)
  • [10] E. W. Packel, The algorithm designer versus nature: a game-theoretic approach to information-based complexity, J. Complexity 3 (1987), 244-257. MR 919675 (89j:68070)
  • [11] W. Sierpiński, Elementary theory of numbers, Warszawa, 1964.
  • [12] A. G. Sukharev, On the existence of optimal affine methods for approximating linear functionals, J. Complexity 2 (1986), 317-322. MR 923025 (89b:65150)
  • [13] -, The concept of sequential optimality for problems in numerical analysis, J. Complexity 3, (1987), 347-357. MR 919681 (88k:65040)
  • [14] A. V. Suldin, Wiener measure and its application to approximation methods. I, II, Izv. Vyssh. Uchebn. Zaved. Mat. 13, 145-158; 18, 165-179. MR 0157489 (28:722)
  • [15] J. F. Traub, G. W. Wasilkowski, and H. Woźniakowski, Information-based complexity, Academic Press, Toronto, Sidney, Tokyo, Boston, San Diego, New York, Berkely, London 1988. MR 958691 (90f:68085)
  • [16] G. W. Wasilkowski and F. Gao, On the power of adaptive information for functions with singularities. Technical Report, University of Kentucky, 1989.
  • [17] S. Zubrzycki, Some approximate integration formulas of statistical interest, Collog. Math. 11 (1963), 123-136. MR 0161474 (28:4678)
  • [18] D. Zwick Optimal quadrature for convex functions and generalizations, Numerical Integration III' (H. Braß, G. Hämmerlin, eds.), Birkhäuser, Basel, Boston, Berlin. 85 (1988), 310-315. MR 1021545 (90k:65085)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC: 41A55, 65C05, 65D32

Retrieve articles in all journals with MSC: 41A55, 65C05, 65D32

Additional Information

Article copyright: © Copyright 1992 American Mathematical Society

American Mathematical Society