Quadrature formulas for monotone functions

Novak, Erich

doi:10.1090/S0002-9939-1992-1086337-X

Quadrature formulas for monotone functions
HTML articles powered by AMS MathViewer

by Erich Novak PDF

Proc. Amer. Math. Soc. 115 (1992), 59-68 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

11

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

Elementary theory of numbers

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

On the power of adaptive information for functions with singularities

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