A generalized discrepancy and quadrature error bound

Hickernell, Fred

doi:10.1090/S0025-5718-98-00894-1

A generalized discrepancy and quadrature error bound
HTML articles powered by AMS MathViewer

by Fred J. Hickernell PDF

Math. Comp. 67 (1998), 299-322 Request permission

Abstract:

An error bound for multidimensional quadrature is derived that includes the Koksma-Hlawka inequality as a special case. This error bound takes the form of a product of two terms. One term, which depends only on the integrand, is defined as a generalized variation. The other term, which depends only on the quadrature rule, is defined as a generalized discrepancy. The generalized discrepancy is a figure of merit for quadrature rules and includes as special cases the ${\mathcal L}^p$-star discrepancy and $P_\alpha$ that arises in the study of lattice rules.

References

Milton Abramowitz and Irene A. Stegun, Handbook of mathematical functions with formulas, graphs, and mathematical tables, National Bureau of Standards Applied Mathematics Series, No. 55, U. S. Government Printing Office, Washington, D.C., 1964. For sale by the Superintendent of Documents. MR 0167642
Philip J. Davis and Philip Rabinowitz, Methods of numerical integration, 2nd ed., Computer Science and Applied Mathematics, Academic Press, Inc., Orlando, FL, 1984. MR 760629
K. T. Fang and F. J. Hickernell, The uniform design and its applications, Bulletin of the International Statistical Institute, 50th Session, Book 1 (Beijing), 1995, pp. 333–349.
K.-T. Fang and Y. Wang, Number-theoretic methods in statistics, Monographs on Statistics and Applied Probability, vol. 51, Chapman & Hall, London, 1994. MR 1284470, DOI 10.1007/978-1-4899-3095-8
S. Heinrich, Efficient algorithms for computing the $L_2$-discrepancy, Math. Comp. 65 (1996), no. 216, 1621–1633. MR 1351202, DOI 10.1090/S0025-5718-96-00756-9
F. J. Hickernell, A comparison of random and quasirandom points for multidimensional quadrature, Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing (H. Niederreiter and P. J.-S. Shiue, eds.), Lecture Notes in Statistics, vol. 106, Springer-Verlag, New York, 1995, pp. 213–227.
F. J. Hickernell, Quadrature error bounds with applications to lattice rules, SIAM J. Numer. Anal. 33 (1996), 1995–2016.
William J. Morokoff and Russel E. Caflisch, Quasi-random sequences and their discrepancies, SIAM J. Sci. Comput. 15 (1994), no. 6, 1251–1279. MR 1298614, DOI 10.1137/0915077
Harald Niederreiter, Random number generation and quasi-Monte Carlo methods, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 63, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1992. MR 1172997, DOI 10.1137/1.9781611970081
Art B. Owen, Orthogonal arrays for computer experiments, integration and visualization, Statist. Sinica 2 (1992), no. 2, 439–452. MR 1187952
A. B. Owen, Equidistributed Latin hypercube samples, Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing (H. Niederreiter and P. J.-S. Shiue, eds.), Lecture Notes in Statistics, vol. 106, Springer-Verlag, New York, 1995, pp. 299–317.
I. H. Sloan and S. Joe, Lattice methods for multiple integration, Oxford University Press, Oxford, 1994.
I. M. Tsobol′, Mnogomernye kvadraturnye formuly i funktsii Khaara, Izdat. “Nauka”, Moscow, 1969 (Russian). MR 0422968
Tony T. Warnock, Computational investigations of low-discrepancy point sets, Applications of number theory to numerical analysis (Proc. Sympos., Univ. Montréal, Montreal, Que., 1971) Academic Press, New York, 1972, pp. 319–343. MR 0351035
H. Woźniakowski, Average case complexity of multivariate integration, Bull. Amer. Math. Soc. (N.S.) 24 (1991), no. 1, 185–194. MR 1072015, DOI 10.1090/S0273-0979-1991-15985-9
S. C. Zaremba, Some applications of multidimensional integration by parts, Ann. Polon. Math. 21 (1968), 85–96. MR 235731, DOI 10.4064/ap-21-1-85-96