A Generalized Discrepancy and Quadrature Error Bound
Author:
Fred J. Hickernell
Journal:
Math. Comp. 67 (1998), 299322
MSC (1991):
Primary 65D30, 65D32
MathSciNet review:
1433265
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: An error bound for multidimensional quadrature is derived that includes the KoksmaHlawka 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 star discrepancy and 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
(29 #4914)
 [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 (86d:65004)
 [FH95]
K. T. Fang and F. J. Hickernell, The uniform design and its applications, Bulletin of the International Statistical Institute, Session, Book 1 (Beijing), 1995, pp. 333349.
 [FW94]
K.T.
Fang and Y.
Wang, Numbertheoretic methods in statistics, Monographs on
Statistics and Applied Probability, vol. 51, Chapman & Hall,
London, 1994. MR
1284470 (95g:65189)
 [Hei96]
S.
Heinrich, Efficient algorithms for computing the
𝐿₂discrepancy, Math. Comp.
65 (1996), no. 216, 1621–1633. MR 1351202
(97a:65024), http://dx.doi.org/10.1090/S0025571896007569
 [Hic95]
F. J. Hickernell, A comparison of random and quasirandom points for multidimensional quadrature, Monte Carlo and QuasiMonte Carlo Methods in Scientific Computing (H. Niederreiter and P. J.S. Shiue, eds.), Lecture Notes in Statistics, vol. 106, SpringerVerlag, New York, 1995, pp. 213227.
 [Hic96]
F. J. Hickernell, Quadrature error bounds with applications to lattice rules, SIAM J. Numer. Anal. 33 (1996), 19952016. CMP 97:02
 [MC94]
William
J. Morokoff and Russel
E. Caflisch, Quasirandom sequences and their discrepancies,
SIAM J. Sci. Comput. 15 (1994), no. 6,
1251–1279. MR 1298614
(95e:65009), http://dx.doi.org/10.1137/0915077
 [Nie92]
Harald
Niederreiter, Random number generation and quasiMonte Carlo
methods, CBMSNSF Regional Conference Series in Applied Mathematics,
vol. 63, Society for Industrial and Applied Mathematics (SIAM),
Philadelphia, PA, 1992. MR 1172997
(93h:65008)
 [Owe92]
Art
B. Owen, Orthogonal arrays for computer experiments, integration
and visualization, Statist. Sinica 2 (1992),
no. 2, 439–452. MR 1187952
(93h:62135)
 [Owe95]
A. B. Owen, Equidistributed Latin hypercube samples, Monte Carlo and QuasiMonte Carlo Methods in Scientific Computing (H. Niederreiter and P. J.S. Shiue, eds.), Lecture Notes in Statistics, vol. 106, SpringerVerlag, New York, 1995, pp. 299317.
 [SJ94]
I. H. Sloan and S. Joe, Lattice methods for multiple integration, Oxford University Press, Oxford, 1994.
 [Sob69]
I.
M. \cyr{T}sobol′, Mnogomernye kvadraturnye formuly i funktsii
Khaara, Izdat. “Nauka”, Moscow, 1969 (Russian). MR 0422968
(54 #10952)
 [War72]
Tony
T. Warnock, Computational investigations of lowdiscrepancy 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
(50 #3526)
 [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
(91i:65224), http://dx.doi.org/10.1090/S027309791991159859
 [Zar68]
S.
C. Zaremba, Some applications of multidimensional integration by
parts, Ann. Polon. Math. 21 (1968), 85–96. MR 0235731
(38 #4034)
 [AS64]
 M. Abramowitz and I. A. Stegun (eds.), Handbook of mathematical functions with formulas, graphs and mathematical tables, U. S. Government Printing Office, Washington, DC, 1964. MR 29:4914
 [DR84]
 P. J. Davis and P. Rabinowitz, Methods of numerical integration, Academic Press, Orlando, Florida, 1984. MR 86d:65004
 [FH95]
 K. T. Fang and F. J. Hickernell, The uniform design and its applications, Bulletin of the International Statistical Institute, Session, Book 1 (Beijing), 1995, pp. 333349.
 [FW94]
 K. T. Fang and Y. Wang, Number theoretic methods in statistics, Chapman and Hall, New York, 1994. MR 95g:65189
 [Hei96]
 S. Heinrich, Efficient algorithms for computing the discrepancy, Math. Comp. 65 (1996), 16211633. MR 97a:65024
 [Hic95]
 F. J. Hickernell, A comparison of random and quasirandom points for multidimensional quadrature, Monte Carlo and QuasiMonte Carlo Methods in Scientific Computing (H. Niederreiter and P. J.S. Shiue, eds.), Lecture Notes in Statistics, vol. 106, SpringerVerlag, New York, 1995, pp. 213227.
 [Hic96]
 F. J. Hickernell, Quadrature error bounds with applications to lattice rules, SIAM J. Numer. Anal. 33 (1996), 19952016. CMP 97:02
 [MC94]
 W. J. Morokoff and R. E. Caflisch, Quasirandom sequences and their discrepancies, SIAM J. Sci. Comput. 15 (1994), 12511279. MR 95e:65009
 [Nie92]
 H. Niederreiter, Random number generation and quasiMonte Carlo methods, SIAM, Philadelphia, 1992. MR 93h:65008
 [Owe92]
 A. B. Owen, Orthogonal arrays for computer experiments, integration and visualization, Statist. Sinica 2 (1992), 439452. MR 93h:62135
 [Owe95]
 A. B. Owen, Equidistributed Latin hypercube samples, Monte Carlo and QuasiMonte Carlo Methods in Scientific Computing (H. Niederreiter and P. J.S. Shiue, eds.), Lecture Notes in Statistics, vol. 106, SpringerVerlag, New York, 1995, pp. 299317.
 [SJ94]
 I. H. Sloan and S. Joe, Lattice methods for multiple integration, Oxford University Press, Oxford, 1994.
 [Sob69]
 I. M. Sobol', Multidimensional quadrature formulas and Haar functions (in Russian), Izdat. ``Nauka'', Moscow, 1969. MR 54:10952
 [War72]
 T. T. Warnock, Computational investigations of low discrepancy point sets, Applications of Number Theory to Numerical Analysis (S. K. Zaremba, ed.), Academic Press, New York, 1972, pp. 319343. MR 50:3526
 [Wo\'{z}91]
 H. Wo\'{z}niakowski, Average case complexity of multivariate integration, Bull. Amer. Math. Soc. 24 (1991), 185194. MR 91i:65224
 [Zar68]
 S. K. Zaremba, Some applications of multidimensional integration by parts, Ann. Polon. Math. 21 (1968), 8596. MR 38:4034
Similar Articles
Retrieve articles in Mathematics of Computation of the American Mathematical Society
with MSC (1991):
65D30,
65D32
Retrieve articles in all journals
with MSC (1991):
65D30,
65D32
Additional Information
Fred J. Hickernell
Affiliation:
Department of Mathematics, Hong Kong Baptist University, Kowloon Tong, Hong Kong
Email:
fred@hkbu.edu.hk
DOI:
http://dx.doi.org/10.1090/S0025571898008941
PII:
S 00255718(98)008941
Keywords:
Figure of merit,
multidimensional integration,
numbertheoretic nets and sequences,
quasirandom sets,
variation
Received by editor(s):
April 5, 1996
Received by editor(s) in revised form:
September 4, 1996
Additional Notes:
This research was supported by a Hong Kong RGC grant 9495/38 and HKBU FRG grant 9596/II01
Article copyright:
© Copyright 1998 American Mathematical Society
