Multivariate integration of infinitely many times differentiable functions in weighted Korobov spaces

Abstract:

We study multivariate integration for a weighted Korobov space of periodic infinitely many times differentiable functions for which the Fourier coefficients decay exponentially fast. The weights are defined in terms of two non-decreasing sequences $\mathbf {a}=\{a_i\}$ and $\mathbf {b}=\{b_i\}$ of numbers no less than one and a parameter $\omega \in (0,1)$. Let $e(n,s)$ be the minimal worst-case error of all algorithms that use $n$ function values in the $s$-variate case. We would like to check conditions on $\mathbf {a}$, $\mathbf {b}$ and $\omega$ such that $e(n,s)$ decays exponentially fast, i.e., for some $q\in (0,1)$ and $p>0$ we have $e(n,s)=\mathcal {O}(q^{ n^{ p}})$ as $n$ goes to infinity. The factor in the $\mathcal {O}$ notation may depend on $s$ in an arbitrary way. We prove that exponential convergence holds iff $B:=\sum _{i=1}^\infty 1/b_i<\infty$ independently of $\mathbf {a}$ and $\omega$. Furthermore, the largest $p$ of exponential convergence is $1/B$. We also study exponential convergence with weak, polynomial and strong polynomial tractability. This means that $e(n,s)\le C(s) q^{ n^{ p}}$ for all $n$ and $s$ and with $\log C(s)=\exp (o(s))$ for weak tractability, with a polynomial bound on $\log C(s)$ for polynomial tractability, and with uniformly bounded $C(s)$ for strong polynomial tractability. We prove that the notions of weak, polynomial and strong polynomial tractability are equivalent, and hold iff $B<\infty$ and $a_i$ are exponentially growing with $i$. We also prove that the largest (or the supremum of) $p$ for exponential convergence with strong polynomial tractability belongs to $[1/(2B),1/B]$.