A generalized discrepancy and quadrature error bound

Hickernell, Fred

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

A Generalized Discrepancy and
Quadrature Error Bound

Author: Fred J. Hickernell
Journal: Math. Comp. 67 (1998), 299-322
MSC (1991): Primary 65D30, 65D32
DOI: https://doi.org/10.1090/S0025-5718-98-00894-1
MathSciNet review: 1433265
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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.

[AS64] Milton Abramowitz and Irene A. Stegun, Handbook of mathematical functions with formulas, graphs, and mathematical tables, National Bureau of Standards Applied Mathematics Series, vol. 55, For sale by the Superintendent of Documents, U.S. Government Printing Office, Washington, D.C., 1964. MR 0167642
[DR84] 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
[FH95] K. T. Fang and F. J. Hickernell, The uniform design and its applications, Bulletin of the International Statistical Institute, $50^{\textup{th}}$ Session, Book 1 (Beijing), 1995, pp. 333-349.
[FW94] 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
[Hei96] S. Heinrich, Efficient algorithms for computing the 𝐿₂-discrepancy, Math. Comp. 65 (1996), no. 216, 1621–1633. MR 1351202, https://doi.org/10.1090/S0025-5718-96-00756-9
[Hic95] 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.
[Hic96] F. J. Hickernell, Quadrature error bounds with applications to lattice rules, SIAM J. Numer. Anal. 33 (1996), 1995-2016. CMP 97:02
[MC94] 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, https://doi.org/10.1137/0915077
[Nie92] 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
[Owe92] Art B. Owen, Orthogonal arrays for computer experiments, integration and visualization, Statist. Sinica 2 (1992), no. 2, 439–452. MR 1187952
[Owe95] 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.
[SJ94] I. H. Sloan and S. Joe, Lattice methods for multiple integration, Oxford University Press, Oxford, 1994.
[Sob69] I. M. Tsobol′, Mnogomernye kvadraturnye formuly i funktsii Khaara, Izdat. “Nauka”, Moscow, 1969 (Russian). MR 0422968
[War72] Tony T. Warnock, Computational investigations of low-discrepancy point sets, Applications of number theory to numerical analysis (Proc. Sympos., Univ. Montreal, Montreal, Que., 1971) Academic Press, New York, 1972, pp. 319–343. MR 0351035
[Wo\'{z}91] H. Woźniakowski, Average case complexity of multivariate integration, Bull. Amer. Math. Soc. (N.S.) 24 (1991), no. 1, 185–194. MR 1072015, https://doi.org/10.1090/S0273-0979-1991-15985-9
[Zar68] S. C. Zaremba, Some applications of multidimensional integration by parts, Ann. Polon. Math. 21 (1968), 85–96. MR 235731, https://doi.org/10.4064/ap-21-1-85-96