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

DOI10.1007/S00211-015-0765-YzbMATH Open1358.65004arXiv1501.01800OpenAlexW3106016933MaRDI QIDQ304528FDOQ304528

Aicke Hinrichs, Tino Ullrich, Lev Markhasin, Jens Oettershagen

Publication date: 25 August 2016

Published in: Numerische Mathematik (Search for Journal in Brave)

Abstract: We investigate quasi-Monte Carlo rules for the numerical integration of multivariate periodic functions from Besov spaces $S_{p,q}^{r}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}(logN{)}^{(d-1)(1-1/q)}$. The logarithmic term does not depend on $r$ and hence improves the known bound provided by J. Dick for the special case of Sobolev spaces $H_{extmix}^r(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 higher order digital nets. Moreover, we provide numerical computations which indicate that this bound also holds for the case $r=2$.

Full work available at URL: https://arxiv.org/abs/1501.01800

Recommendations

• Explicit Constructions of Quasi-Monte Carlo Rules for the Numerical Integration of High-Dimensional Periodic Functions
• An explicit construction of optimal order quasi-Monte Carlo rules for smooth integrands
• Quasi–Monte Carlo Numerical Integration on $\mathbb{R}^s$: Digital Nets and Worst-Case Error
• Optimal order quasi-Monte Carlo integration in weighted Sobolev spaces of arbitrary smoothness
• Optimal cubature in Besov spaces with dominating mixed smoothness on the unit square

zbMATH Keywords

numerical examplesdigital \((t,n,d)\)-netsFaber baseHaar baseperiodic Besov spaceQMC-optimal worst-case errorquasi Monte Carlo method

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Sobolev spaces and other spaces of ``smooth functions, embedding theorems, trace theorems (46E35) Pseudo-random numbers; Monte Carlo methods (11K45)

Cites Work

• Theory of Reproducing Kernels
• Smoothing noisy data with spline functions
• Sparse grids
• Low-discrepancy sequences and global function fields with many rational places
• Title not available (Why is that?)
• Title not available (Why is that?)
• Discrepancy bounds for infinite-dimensional order two digital sequences over \(\mathbb F_2\)
• Optimal \(\mathcal {L}_{2}\) discrepancy bounds for higher order digital sequences over the finite field \(\mathbb {F}_{2}\)
• Title not available (Why is that?)
• Explicit constructions of point sets and sequences with low discrepancy
• Explicit Constructions of Quasi-Monte Carlo Rules for the Numerical Integration of High-Dimensional Periodic Functions
• Walsh Spaces Containing Smooth Functions and Quasi–Monte Carlo Rules of Arbitrary High Order
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Geometric discrepancy. An illustrated guide
• Discrepancy of Hammersley points in Besov spaces of dominating mixed smoothness
• Tractability of multivariate problems. Volume II: Standard information for functionals.
• On Roth's orthogonal function method in discrepancy theory
• Higher Order QMC Petrov--Galerkin Discretization for Affine Parametric Operator Equations with Random Field Inputs
• Lower bounds for the integration error for multivariate functions with mixed smoothness and optimal Fibonacci cubature for functions on the square
• Title not available (Why is that?)
• B-spline quasi-interpolant representations and sampling recovery of functions with mixed smoothness
• Bases in function spaces, sampling, discrepancy, numerical integration
• Point sets and sequences with small discrepancy
• Reconstruction of periodic functions of several variables with respect to the values in the nodes of number-theoretic nets
• Cubature formulas, discrepancy, and nonlinear approximation
• Change of variable in spaces of mixed smoothness and numerical integration of multivariate functions on the unit cube
• Quasi-Monte Carlo methods for integration of functions with dominating mixed smoothness in arbitrary dimension
• Optimal cubature in Besov spaces with dominating mixed smoothness on the unit square
• The role of Frolov's cubature formula for functions with bounded mixed derivative
• Higher Order Quasi Monte-Carlo Integration in Uncertainty Quantification
• Discrepancy, Integration and Tractability
• Optimal Point Sets for Quasi-Monte Carlo Integration of Bivariate Periodic Functions with Bounded Mixed Derivatives
• Title not available (Why is that?)
• Title not available (Why is that?)
• Duality theory and propagation rules for generalized digital nets
• CUBATURE FORMULAS FOR CLASSES OF FUNCTIONS WITH BOUNDED MIXED DIFFERENCE
• Title not available (Why is that?)
• Cubature formulae for Besov classes
• Title not available (Why is that?)
• A construction of low-discrepancy sequences using global function fields
• L_p- and S_p,q^rB-discrepancy of (order 2) digital nets
• Discrepancy Theory and Quasi-Monte Carlo Integration
• Discrepancy and integration in function spaces with dominating mixed smoothness
• Discrepancy of generalized Hammersley type point sets in Besov spaces of dominating mixed smoothness
• Faber systems and their use in sampling, discrepancy, numerical integration
• Zur angenäherten Berechnung mehrfacher Integrale
• On the exact \(t\)-value of Niederreiter and Sobol' sequences

Cited In (21)

• Approximation of multivariate periodic functions based on sampling along multiple rank-1 lattices
• On “Upper Error Bounds for Quadrature Formulas on Function Classes” by K.K. Frolov
• Optimal Monte Carlo integration on closed manifolds
• Bypassing the quadrature exactness assumption of hyperinterpolation on the sphere
• Some Results on the Complexity of Numerical Integration
• Approximation of functions with small mixed smoothness in the uniform norm
• Quasi–Monte Carlo Numerical Integration on $\mathbb{R}^s$: Digital Nets and Worst-Case Error
• Numerical performance of optimized Frolov lattices in tensor product reproducing kernel Sobolev spaces
• An explicit construction of optimal order quasi-Monte Carlo rules for smooth integrands
• Point sets with optimal order of extreme and periodic discrepancy
• A representer theorem for deep kernel learning
• A higher order Faber spline basis for sampling discretization of functions
• Title not available (Why is that?)
• Optimal periodic \(L_2\)-discrepancy and diaphony bounds for higher order digital sequences
• Change of variable in spaces of mixed smoothness and numerical integration of multivariate functions on the unit cube
• Tight error bounds for rank-1 lattice sampling in spaces of hybrid mixed smoothness
• Multiple rank-1 lattices as sampling schemes for multivariate trigonometric polynomials
• The role of Frolov's cubature formula for functions with bounded mixed derivative
• Equivalence between Sobolev spaces of first-order dominating mixed smoothness and unanchored ANOVA spaces on ℝ^{𝕕}
• Optimal Point Sets for Quasi-Monte Carlo Integration of Bivariate Periodic Functions with Bounded Mixed Derivatives
• Optimal order quadrature error bounds for infinite-dimensional higher-order digital sequences

Uses Software

• rhalton
• Algorithm 247

This page was built for publication: Optimal quasi-Monte Carlo rules on order 2 digital nets for the numerical integration of multivariate periodic functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q304528)