We study lower bounds on the worst-case error of numerical integration in tensor product spaces. As reference we use the
N-th minimal error of linear rules that use
N function values. The information complexity is the minimal number
N of function evaluations that is necessary such that the
N-th minimal error is less than a factor
ε times the initial error. We are interested to which extent the information complexity depends on the number
d of variables of the integrands. If the information complexity grows exponentially fast in
d, then the integration problem is said to suffer from the curse of dimensionality. Under the assumption of the existence of a worst-case function for the uni-variate problem we present two methods for providing good lower bounds on the information complexity. The first method is based on a suitable decomposition of the worst-case function. This method can be seen as a generalization of the method of decomposable reproducing kernels, that is often successfully applied when integration in Hilbert spaces with a reproducing kernel is studied. The second method, although only applicable for positive quadrature rules, has the advantage, that it does not require a suitable decomposition of the worst-case function. Rather, it is based on a spline approximation of the worst-case function and can be used for analytic functions. The methods presented can be applied to problems beyond the Hilbert space setting. For demonstration purposes we apply them to several examples, notably to uniform integration over the unit-cube, weighted integration over the whole space, and integration of infinitely smooth functions over the cube. Some of these results have interesting consequences in discrepancy theory.
We prove lower bounds on the worst-case error of numerical integration in tensor product spaces. The information complexity is the minimal number N of function evaluations that is necessary such that the N -th minimal error is less than a factor ε times the initial error, i.e., the error for N = 0 , where ε belongs to ( 0 , 1 ) . We are interested to which extent the information complexity depends on the number d of variables of the integrands. If the information complexity grows exponentially fast in d , then the integration problem is said to suffer from the curse of dimensionality. Under the assumption of the existence of a worst-case function for the uni-variate problem, we present two methods for providing lower bounds on the information complexity. The first method is based on a suitable decomposition of the worst-case function and can be seen as a generalization of the method of decomposable reproducing kernels. The second method, although only applicable for positive quadrature rules, does not require a suitable decomposition of the worst-case function. Rather, it is based on a spline approximation of the worst-case function and can be used for analytic functions. Several applications of both methods are presented.
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 numerical integration for a weighted Korobov space of analytic periodic functions for which the Fourier coefficients decay exponentially fast. In particular, we are interested in how the error depends on the dimension d. Many recent papers deal with this problem or similar problems and provide matching necessary and sufficient conditions for various notions of tractability. In most cases even simple algorithms are known which allow to achieve these notions of tractability. However, there is a gap in the literature: while for the notion of exponential-weak tractability one knows matching necessary and sufficient conditions, so far no explicit algorithm has been known which yields the desired result. In this paper we close this gap and prove that Korobov lattice rules are suitable algorithms in order to achieve exponential-weak tractability for integration in weighted Korobov spaces of analytic periodic functions.
This note is devoted to discussing multivariate approximation of continuous functions on
[0,1]d with analytic Korobov kernels in the worst and average case settings. We only consider algorithms that use finitely many evaluations of arbitrary continuous linear functionals. We study EC-
(s,t)-weak tractability under the absolute or normalized error criterion, and obtain necessary and sufficient conditions for
0<min(s,t)<1 and
max(s,t)≤1 in the worst case setting and for
s,t>0 in the average case setting.