Skip to main content
SpringerLink
Log in

Optimal quasi-Monte Carlo rules on order 2 digital nets for the numerical integration of multivariate periodic functions

  • Published:
Numerische Mathematik Aims and scope Submit manuscript

Abstract

We investigate quasi-Monte Carlo rules for the numerical integration of multivariate periodic functions from Besov spaces \(S^r_{p,q}B(\mathbb {T}^d)\) with dominating mixed smoothness \(1/p<r<2\). We show that order 2 digital nets achieve the optimal rate of convergence \(N^{-r} (\log N)^{(d-1)(1-1/q)}\). The logarithmic term does not depend on r and hence improves the known bound of Dick (SIAM J Numer Anal 45:2141–2176, 2007) for the special case of Sobolev spaces \(H^r_{\text {mix}}(\mathbb {T}^d)\). Secondly, the rate of convergence is independent of the integrability p of the Besov space, which allows for sacrificing integrability in order to gain Besov regularity. Our method combines characterizations of periodic Besov spaces with dominating mixed smoothness via Faber bases with sharp estimates of Haar coefficients for the discrepancy function of order 2 digital nets. Moreover, we provide numerical computations which indicate that this bound also holds for the case \(r=2\).

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5

Similar content being viewed by others

Notes

  1. These spaces are sometimes also referred to as Korobov spaces.

References

  1. Amanov, T.I.: Spaces of Differentiable Functions with Dominating Mixed Derivatives. Nauka Kaz SSR, Alma-Ata (1976)

    Google Scholar 

  2. Aronszajn, N.: Theory of reproducing kernels. Trans. Am. Math. Soc. 68, 337–404 (1950)

    Article  MathSciNet  MATH  Google Scholar 

  3. Bakhvalov, N.S.: Optimal convergence bounds for quadrature processes and integration methods of Monte Carlo type for classes of functions. Zh. Vychisl. Mat. Mat. Fiz. 4(4), 5–63 (1963)

    MathSciNet  Google Scholar 

  4. Bilyk, D.: On Roth’s orthogonal function method in discrepancy theory. Unif. Distrib. Theory 6, 143–184 (2011)

    MathSciNet  MATH  Google Scholar 

  5. Bungartz, H.-J., Griebel, M.: Sparse grids. Acta Numer. 13, 1–123 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  6. Dick, J.: Explicit constructions of quasi-Monte Carlo rules for the numerical integration of high-dimensional periodic functions. SIAM J. Numer. Anal. 45, 2141–2176 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  7. Dick, J.: Walsh spaces containing smooth functions and quasi-Monte Carlo rules of arbitrary high order. SIAM J. Numer. Anal. 46, 1519–1553 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  8. Dick, J.: Discrepancy bounds for infinite-dimensional order two digital sequences over \(\mathbb{F}_2\). J. Number Theory 136, 204–232 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  9. Dick, J., Kritzer, P.: Duality theory and propagation rules for generalized digital nets. Math. Comput. 79, 993–1017 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  10. Dick, J., Kuo, F., Thong Le Gia, Q., Schwab, C.: Multi-level higher order QMC Galerkin discretization for affine parametric operator equations (2014) (arXiv e-prints)

  11. Dick, J., Le Gia, Q.T., Schwab, C.: Higher order quasi-monte carlo integration for holomorphic, parametric operator equations (2014) (arXiv e-prints)

  12. Dick, J., Niederreiter, H.: On the exact \(t\)-value of Niederreiter and Sobol sequences. J. Complex. 24(56), 572–581 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  13. Dick, J., Pillichshammer, F.: Digital Nets and Sequences. Discrepancy Theory and Quasi-Monte Carlo Integration. Cambridge University Press, Cambridge (2010)

    Book  MATH  Google Scholar 

  14. Dick, J., Pillichshammer, F.: Discrepancy theory and quasi-Monte Carlo integration. In: Panorama in Discrepancy Theory. Springer, Berlin (2013)

  15. Dick, J., Pillichshammer, F.: Explicit constructions of point sets and sequences with low discrepancy. In: Uniform Distribution and Quasi-Monte Carlo Methods—Discrepancy, Integration and Applications, pp. 63–86 (2014)

  16. Dick, J., Pillichshammer, F.: Optimal \(L_2\)-discrepancy bounds for higher order digital sequences over the finite field \(\mathbb{F}_2\). Acta Arith. 162(1), 65–99 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  17. Dubinin, V.V.: Cubature formulas for classes of functions with bounded mixed difference. Mat. USSR Sb. 76, 283–292 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  18. Dubinin, V.V.: Cubature formulae for Besov classes. Iz. Math. 61(2), 259–283 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  19. Dũng, D.: B-spline quasi-interpolant representations and sampling recovery of functions with mixed smoothness. J. Complex. 27(6), 541–567 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  20. Dũng, D., Ullrich, T.: Lower bounds for the integration error for multivariate functions with mixed smoothness and optimal Fibonacci cubature for functions on the square. Math. Nachr. doi:10.1002/mana.201400048

  21. Faber, G.: Über stetige Funktionen. Math. Ann. 66, 81–94 (1909)

    Article  MathSciNet  MATH  Google Scholar 

  22. Glasserman, P.: Monte Carlo Methods in Financial Engineering. Applications of Mathematics: Stochastic Modelling and Applied Probability. Springer, Berlin (2004)

  23. Halton, J.H.: Algorithm 247: radical-inverse quasi-random point sequence. Commun. ACM 7(12), 701–702 (1964)

    Article  Google Scholar 

  24. Hinrichs, A.: Discrepancy of Hammersley points in Besov spaces of dominating mixed smoothness. Math. Nachr. 283(3), 478–488 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  25. Hinrichs, A.: Discrepancy, integration and tractability. In: Dick, J., Kuo, F.Y., Peters, G.W., Sloan, I.H. (eds.) Monte Carlo and Quasi-Monte Carlo. Methods, vol. 2012 (2014)

  26. Hinrichs, A., Oettershagen, J.: Optimal point sets for quasi-Monte Carlo integration of bivariate periodic functions with bounded mixed derivatives. In: Proceedings of the Conference MCQMC, Leuven (2014) (to appear)

  27. Hlawka, E.: Zur angenäherten Berechnung mehrfacher Integrale. Monatsh. Math. 66, 140–151 (1962)

    Article  MathSciNet  MATH  Google Scholar 

  28. Korobov, N.M.: Approximate evaluation of repeated integrals. Dokl. Akad. Nauk SSSR 124, 1207–1210 (1959)

    MathSciNet  MATH  Google Scholar 

  29. Kuipers, H.N.L.: Uniform Distribution of Sequences. Wiley, New York (1974)

    MATH  Google Scholar 

  30. Markhasin, L.: Discrepancy and integration in function spaces with dominating mixed smoothness. Dissert. Math. 494, 1–81 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  31. Markhasin, L.: Discrepancy of generalized Hammersley type point sets in Besov spaces with dominating mixed smoothness. Unif. Distrib. Theory 8(1), 135–164 (2013)

    MathSciNet  MATH  Google Scholar 

  32. Markhasin, L.: Quasi-Monte Carlo methods for integration of functions with dominating mixed smoothness in arbitrary dimension. J. Complex. 29(5), 370–388 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  33. Markhasin, L.: \({L}_2\)- and \({S}^r_{p, q}{B}\)-discrepancy of (order 2) digital nets. Acta Arith. 168(2), 139–160 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  34. Matoušek, J.: Geometric Discrepancy. An Illustrated Guide. Springer, Berlin (1999)

    Book  MATH  Google Scholar 

  35. Nguyen, V.K., Ullrich, M., Ullrich, T.: Boundedness of pointwise multiplication and change of variable and applications to numerical integration (2015) (preprint)

  36. Niederreiter, H.: Point sets and sequences with small discrepancy. Monatsh. Math. 104, 273–337 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  37. Niederreiter, H., Xing, C.: A construction of low-discrepancy sequences using global function fields. Acta Arith. 73(1), 87–102 (1995)

    MathSciNet  MATH  Google Scholar 

  38. Niederreiter, H., Xing, C.: Low-discrepancy sequences and global function fields with many rational places. Finite Fields Appl. 2(3), 241–273 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  39. Nikol’skij, S.M.: Approximation of Functions of Several Variables and Embedding Theorems. Nauka, Moskva (1977)

  40. Novak, E.: Some results on the complexity of numerical integration. In: Monte Carlo and Quasi-Monte Carlo Methods. Proceedings of the Conference MCQMC, Leuven (2014) (to appear)

  41. Novak, E., Woźniakowski, H.: Tractability of multivariate problems. Standard information for functionals, vol. II. In: EMS Tracts in Mathematics, vol. 12. European Mathematical Society (EMS), Zürich (2010)

  42. Pirsic, G.: A software implementation of Niederreiter–Xing sequences. In: Monte Carlo and Quasi-Monte Carlo Methods, vol. 2000. Springer, Berlin (2002)

  43. Schmeisser, H.-J., Triebel, H.: Topics in Fourier Analysis and Function Spaces. A Wiley-Interscience Publication. Wiley, Chichester (1987)

    Google Scholar 

  44. Skriganov, M.M.: Constructions of uniform distributions in terms of geometry of numbers. J. Complex. 6, 200–230 (1994)

    MathSciNet  MATH  Google Scholar 

  45. Smolyak, S.: Quadrature and interpolation formulas for tensor products of certain classes of functions. Dokl. Akad. Nauk SSSR 4, 240–243 (1963)

    MATH  Google Scholar 

  46. Temlyakov, V.N.: On reconstruction of multivariate periodic functions based on their values at the knots of number-theoretical nets. Anal. Math. 12, 287–305 (1986)

    Article  MathSciNet  MATH  Google Scholar 

  47. Temlyakov, V.N.: On a way of obtaining lower estimates for the errors of quadrature formulas. Mat. Sb. 181(10), 1403–1413 (1990)

    Google Scholar 

  48. Temlyakov, V.N.: Error estimates for Fibonacci quadrature formulas for classes of functions with a bounded mixed derivative. Trudy Mat. Inst. Steklov 200, 327–335 (1991)

    MathSciNet  MATH  Google Scholar 

  49. Temlyakov, V.N.: Approximation of Periodic Functions. Computational Mathematics and Analysis Series. Nova Science, Commack (1993)

    MATH  Google Scholar 

  50. Temlyakov, V.N.: Cubature formulas, discrepancy, and nonlinear approximation. J. Complex. 19(3), 352–391 (2003) (numerical integration and its complexity, Oberwolfach, 2001)

  51. Triebel, H.: Bases in Function Spaces, Sampling, Discrepancy, Numerical Integration. In: EMS Tracts in Mathematics, vol. 11. European Mathematical Society (EMS), Zürich (2010)

  52. Triebel, H.: EMS Series of Lectures in Mathematics. Faber systems and their use in sampling, discrepancy, numerical integration. European Mathematical Society (EMS), Zürich (2012)

    Google Scholar 

  53. Ullrich, M., Ullrich, T.: The role of Frolov’s cubature formula for functions with bounded mixed derivative (2015). arXiv:1503.08846 [math.NA] (arXiv e-prints)

  54. Ullrich, T.: Function spaces with dominating mixed smoothness; characterization by differences. Jenaer Schriften Math. Inf. (2006) (Math/Inf/05/06)

  55. Ullrich, T.: Smolyak’s algorithm, sampling on sparse grids and Sobolev spaces of dominating mixed smoothness. East J. Approx. 14(1), 1–38 (2008)

    MathSciNet  MATH  Google Scholar 

  56. Ullrich, T.: Optimal cubature in Besov spaces with dominating mixed smoothness on the unit square. J. Complex. 30, 72–94 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  57. Wahba, G.: Smoothing noisy data with spline functions. Numer. Math. 24(5), 383–393 (1975)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgments

The authors would like to thank the HCM Bonn and the organizers of the HCM-workshop Discrepancy, Numerical Integration, and Hyperbolic Cross Approximation where this work has been initiated. In addition, they would like to thank the organizers of the semester program High-Dimensional Approximation at ICERM, Brown University, for providing a pleasant and fruitful working atmosphere. Finally, they would like to thank Dinh Dũng, Michael Griebel, Winfried Sickel and Vladimir Temlyakov for several helpful remarks on earlier versions of this manuscript.

Author information

Authors and Affiliations

  1. Institute for Analysis, Johannes Kepler University, 4040, Linz, Austria

    Aicke Hinrichs

  2. Institute for Stochastics and Applications, University of Stuttgart, 70569, Stuttgart, Germany

    Lev Markhasin

  3. Institute for Numerical Simulation, University of Bonn, 53115, Bonn, Germany

    Jens Oettershagen & Tino Ullrich

Authors
  1. Aicke Hinrichs
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Lev Markhasin
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Jens Oettershagen
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Tino Ullrich
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Tino Ullrich.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Hinrichs, A., Markhasin, L., Oettershagen, J. et al. Optimal quasi-Monte Carlo rules on order 2 digital nets for the numerical integration of multivariate periodic functions. Numer. Math. 134, 163–196 (2016). https://doi.org/10.1007/s00211-015-0765-y

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00211-015-0765-y

Mathematics Subject Classification

Search

Navigation