TY - JOUR
T1 - Tractability of multivariate integration for periodic functions
AU - Hickernell, Fred J.
AU - Woźniakowski, Henryk
N1 - Funding Information:
Fred J. Hickernell: This research was supported in part by Hong Kong Research Grants Council Grant RCG/HKBU/2030/99P and Hong Kong Baptist University Grant FRG/97-98/II-99.
Henryk Wozniakowski was supported in part by the National Science Foundation.
PY - 2001/12
Y1 - 2001/12
N2 - We study multivariate integration in the worst case setting for weighted Korobov spaces of smooth periodic functions of d variables. We wish to reduce the initial error by a factor e for functions from the unit ball of the weighted Korobov space. Tractability means that the minimal number of function samples needed to solve the problem is polynomial in e-1 and d. Strong tractability means that we have only a polynomial dependence in e-1. This problem has been recently studied for quasi-Monte Carlo quadrature rules and for quadrature rules with non-negative coefficients. In this paper we study arbitrary quadrature rules. We show that tractability and strong tractability in the worst case setting hold under the same assumptions on the weights of the Korobov space as for the restricted classes of quadrature rules. More precisely, let γj moderate the behavior of functions with respect to the jth variable in the weighted Korobov space. Then strong tractability holds iff ∑j=1 ∞ γj < ∞, whereas tractability holds iff lim supd→∞ ∑j=1 d γj/ln d < ∞. We obtain necessary conditions on tractability and strong tractability by showing that multivariate integration for the weighted Korobov space is no easier than multivariate integration for the corresponding weighted Sobolev space of smooth functions with boundary conditions. For the weighted Sobolev space we apply general results from E. Novak and H. Woźniakowski (J. Complexity 17 (2001), 388-441) concerning decomposable kernels.
AB - We study multivariate integration in the worst case setting for weighted Korobov spaces of smooth periodic functions of d variables. We wish to reduce the initial error by a factor e for functions from the unit ball of the weighted Korobov space. Tractability means that the minimal number of function samples needed to solve the problem is polynomial in e-1 and d. Strong tractability means that we have only a polynomial dependence in e-1. This problem has been recently studied for quasi-Monte Carlo quadrature rules and for quadrature rules with non-negative coefficients. In this paper we study arbitrary quadrature rules. We show that tractability and strong tractability in the worst case setting hold under the same assumptions on the weights of the Korobov space as for the restricted classes of quadrature rules. More precisely, let γj moderate the behavior of functions with respect to the jth variable in the weighted Korobov space. Then strong tractability holds iff ∑j=1 ∞ γj < ∞, whereas tractability holds iff lim supd→∞ ∑j=1 d γj/ln d < ∞. We obtain necessary conditions on tractability and strong tractability by showing that multivariate integration for the weighted Korobov space is no easier than multivariate integration for the corresponding weighted Sobolev space of smooth functions with boundary conditions. For the weighted Sobolev space we apply general results from E. Novak and H. Woźniakowski (J. Complexity 17 (2001), 388-441) concerning decomposable kernels.
UR - http://www.scopus.com/inward/record.url?scp=0035702360&partnerID=8YFLogxK
U2 - 10.1006/jcom.2001.0592
DO - 10.1006/jcom.2001.0592
M3 - Journal article
AN - SCOPUS:0035702360
SN - 0885-064X
VL - 17
SP - 660
EP - 682
JO - Journal of Complexity
JF - Journal of Complexity
IS - 4
ER -