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.

**[1]**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****[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,*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****[4]**S. Graf, R. Daniel Mauldin, and S. C. Williams,*Random homeomorphisms*, Adv. in Math.**60**(1986), no. 3, 239–359. MR**848153**, 10.1016/S0001-8708(86)80001-9**[5]**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**, 10.1216/rmjm/1181073094**[6]**Seymour Haber,*Numerical evaluation of multiple integrals*, SIAM Rev.**12**(1970), 481–526. MR**0285119****[7]**J. Kiefer,*Optimum sequential search and approximation methods under minimum regularity assumptions*, J. Soc. Indust. Appl. Math.**5**(1957), 105–136. MR**0092326****[8]**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**, 10.1016/0885-064X(86)90021-X**[9]**Erich Novak,*Deterministic and stochastic error bounds in numerical analysis*, Lecture Notes in Mathematics, vol. 1349, Springer-Verlag, Berlin, 1988. MR**971255****[10]**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**, 10.1016/0885-064X(87)90014-8**[11]**W. Sierpiński,*Elementary theory of numbers*, Warszawa, 1964.**[12]**Aleksei G. Sukharev,*On the existence of optimal affine methods for approximating linear functionals*, J. Complexity**2**(1986), no. 4, 317–322. MR**923025**, 10.1016/0885-064X(86)90009-9**[13]**Aleksei G. Sukharev,*The concept of sequential optimality for problems in numerical analysis*, J. Complexity**3**(1987), no. 3, 347–357. MR**919681**, 10.1016/0885-064X(87)90020-3**[14]**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****[15]**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****[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*, Colloq. Math.**11**(1963), 123–136. MR**0161474****[18]**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**

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:
http://dx.doi.org/10.1090/S0002-9939-1992-1086337-X

Article copyright:
© Copyright 1992
American Mathematical Society