In this paper we study multivariate integration for a weighted Korobov space for which the Fourier coefficients of the functions decay exponentially fast. This implies that the functions of this space are infinitely times differentiable. Weights of the Korobov space monitor the influence of each variable and each group of variables. We show that there are numerical integration rules which achieve an exponential convergence of the worst-case integration error. We also investigate the dependence of the worst-case error on the number of variables s s , and show various tractability results under certain conditions on weights of the Korobov space. Tractability means that the dependence on s s is never exponential, and sometimes the dependence on s s is polynomial or there is no dependence on s s at all.
We study multivariate
L2-approximation for a weighted Korobov space of analytic periodic functions for which the Fourier coefficients decay exponentially fast. The weights are defined, in particular, in terms of two sequences
a={aj} and
b={bj} of numbers no less than one. Let
eL2−app,Λ(n,s) be the minimal worst-case error of all algorithms that use
n information functionals from the class
Λ in the
s-variate case. We consider two classes
Λ: the class
Λall consists of all linear functionals and the class
Λstd consists of only function valuations. We study (EXP) exponential convergence. This means that
eL2−app,Λ(n,s)≤C(s)q(n/C1(s))p(s)foralln,s∈N where
q∈(0,1), and
C,C1,p:N→(0,∞). If we can take
p(s)=p>0 for all
s then we speak of (UEXP) uniform exponential convergence. We also study EXP and UEXP with (WT) weak, (PT) polynomial and (SPT) strong polynomial tractability. These concepts are defined as follows. Let $n(\e,s)$ be the minimal
n for which $e^{L_2-\mathrm{app},Λ}(n,s)\le \e$. Then WT holds iff $\lim_{s+\log\,\e^{-1}\to\infty}(\log n(\e,s))/(s+\log\,\e^{-1})=0$, PT holds iff there are
c,τ1,τ2 such that $n(\e,s)\le cs^{τ_1}(1+\log\,\e^{-1})^{τ_2}$ for all
s and $\e\in(0,1)$, and finally SPT holds iff the last estimate holds for
τ1=0. The infimum of
τ2 for which SPT holds is called the exponent
τ∗ of SPT. We prove that the results are the same for both classes
Λ, and obtain conditions for WT, PT, SPT with and without EXP and UEXP.
We study multivariate
L∞-approximation for a weighted Korobov space of periodic functions for which the Fourier coefficients decay exponentially fast. The weights are defined, in particular, in terms of two sequences
a={aj} and
b={bj} of positive real numbers bounded away from zero. We study the minimal worst-case error
eL∞−app,Λ(n,s) of all algorithms that use
n information evaluations from a class
Λ in the
s-variate case. We consider two classes
Λ in this paper: the class
Λall of all linear functionals and the class
Λstd of only function evaluations. We study exponential convergence of the minimal worst-case error, which means that
eL∞−app,Λ(n,s) converges to zero exponentially fast with increasing
n. Furthermore, we consider how the error depends on the dimension
s. To this end, we define the notions of
κ-EC-weak, EC-polynomial and EC-strong polynomial tractability, where EC stands for "exponential convergence". In particular, EC-polynomial tractability means that we need a polynomial number of information evaluations in
s and
1+logε−1 to compute an
ε-approximation. We derive necessary and sufficient conditions on the sequences
a and
b for obtaining exponential error convergence, and also for obtaining the various notions of tractability. The results are the same for both classes
Λ.
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 a = { a i } \mathbf {a}=\{a_i\} and b = { b i } \mathbf {b}=\{b_i\} of numbers no less than one and a parameter ω ∈ ( 0 , 1 ) \omega \in (0,1) . Let e ( n , s ) e(n,s) be the minimal worst-case error of all algorithms that use n n function values in the s s -variate case. We would like to check conditions on a \mathbf {a} , b \mathbf {b} and ω \omega such that e ( n , s ) e(n,s) decays exponentially fast, i.e., for some q ∈ ( 0 , 1 ) q\in (0,1) and p > 0 p>0 we have
This paper studies the multivariate approximation of functions in weighted Korobov spaces using multiple rank-1 lattice rules. It has been shown by Kämmerer and Volkmer (2019) that algorithms based on multiple rank-1 lattices achieve the optimal convergence rate for the
L∞ error in Wiener-type spaces, up to logarithmic factors. While this result was translated to weighted Korobov spaces in the recent monograph by Dick, Kritzer, and Pillichshammer (2022), the analysis requires the smoothness parameter
α to be greater than
1 and is restricted to product weights. In this paper, we extend this result for multiple rank-1 lattice-based algorithms to the case where
1/2<α≤1 and for general weights, covering a broader range of periodic functions with low smoothness and general relative importance of variables. We also provide a summability condition on the weights to ensure strong polynomial tractability for any
α>1/2. Furthermore, by incorporating random shifts into multiple rank-1 lattice-based algorithms, we prove that the resulting randomized algorithm achieves a nearly optimal convergence rate in terms of the worst-case root mean squared
L2 error, while retaining the same tractability property.
QMC rules are equal weight quadrature rules for approximating integrals over
[0,1]s. One line of research studies the integration error of functions in the unit ball of so-called Korobov spaces, which are Hilbert spaces of periodic functions on
[0,1]s with square integrable partial mixed derivatives of order
α. Using Parseval's identity, this smoothness can be defined for all real numbers
α>1/2. This condition is necessary as otherwise the Korobov space contains discontinuous functions for which function evaluation is not well defined. This paper is concerned with more precise endpoint estimates of the integration error using QMC rules for Korobov spaces with
α arbitrarily close to
1/2. To obtain such estimates we introduce a
log-scale for functions with smoothness close to
1/2, which we call
log-Korobov spaces. We show that lattice rules can be used to obtain an integration error of order
O(N−1/2(logN)−μ(1−λ)/2) for any
1/μ<λ≤1, where
μ>1 is a power in the
log-scale. We also consider tractability of numerical integration for weighted Korobov spaces with product weights
(γj)j∈N. It is known that if
∑j=1∞γjτ<∞ for some
1/(2α)<τ≤1 one can obtain error bounds which are independent of the dimension. In this paper we give a more refined estimate for the case where
τ is close to
1/(2α), namely we show dimension independent error bounds under the condition that
∑j=1∞γjmax{1,logγj−1}μ(1−λ)<∞ for some
1/μ<λ≤1. The essential tool in our analysis is a
log-scale Jensen's inequality. The results described above also apply to integration in
log-cosine spaces using tent-transformed lattice rules.