Super-polynomial convergence and tractability of multivariate integration for infinitely times differentiable functions

Abstract

We investigate multivariate integration for a space of infinitely times differentiable functions ${\mathcal{F}}_{s,\mathbf{u}}:=\{f\in C^{\infty }[0,1{]}^s\mid \Vert f{\Vert }_{{\mathcal{F}}_{s,\mathbf{u}}}<\infty \}$, where $\Vert f{\Vert }_{{\mathcal{F}}_{s,\mathbf{u}}}:={\sup }_{\mathbf{\alpha }=({\alpha }_1,\dots ,{\alpha }_s)\in {\mathbb{N}}_0^s}\Vert f^{(\mathbf{\alpha })}{\Vert }_{L^1}/{\prod }_{j=1}^s{u}_j^{{\alpha }_j}$, $f^{(\mathbf{\alpha })}:=\frac{{\partial }^{|\mathbf{\alpha }|}}{\partial x_1^{{\alpha }_1}\cdots \partial x_s^{{\alpha }_s}}f$ and $\mathbf{u}=\{u_j{\}}_{j\ge 1}$ is a sequence of positive decreasing weights. Let $e(n,s)$ be the minimal worst-case error of all algorithms that use $n$ function values in the $s$-variate case. We prove that for any $\mathbf{u}$ and $s$ considered $e(n,s)\le C(s)\exp (-c(s)(\log n{)}^2)$ holds for all $n$, where $C(s)$ and $c(s)$ are constants which may depend on $s$. Further we show that if the weights $\mathbf{u}$ decay sufficiently fast then there exist some $1<p<2$ and absolute constants $C$ and $c$ such that $e(n,s)\le C\exp (-c(\log n{)}^p)$ holds for all $s$ and $n$. These bounds are attained by quasi-Monte Carlo integration using digital nets. These convergence and tractability results come from those for the Walsh space into which ${\mathcal{F}}_{s,\mathbf{u}}$ is embedded.

References in corpus (3)

• WAFOM on abelian groups for quasi-Monte Carlo point sets
• Formulas for the Walsh coefficients of smooth functions and their application to bounds on the Walsh coefficients
• Quasi-Monte Carlo point sets with small $t$-values and WAFOM

Cited by in corpus (4)

• A universal median quasi-Monte Carlo integration
• Recent advances in higher order quasi-Monte Carlo methods
• Construction of interlaced polynomial lattice rules for infinitely differentiable functions
• The median trick does not help for fully nested scrambling