Quadrature formulas for monotone functions

Author:
Erich Novak

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

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.

**[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)**

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

DOI:
https://doi.org/10.1090/S0002-9939-1992-1086337-X

Article copyright:
© Copyright 1992
American Mathematical Society