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

Authors:
Peter Kritzer, Friedrich Pillichshammer and Henryk Woźniakowski

Journal:
Math. Comp. **83** (2014), 1189-1206

MSC (2010):
Primary 11K45, 65C05, 65D30

DOI:
https://doi.org/10.1090/S0025-5718-2013-02739-1

Published electronically:
November 20, 2013

MathSciNet review:
3167455

Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 and of numbers no less than one and a parameter . Let be the minimal worst-case error of all algorithms that use function values in the -variate case. We would like to check conditions on , and such that decays exponentially fast, i.e., for some and we have as goes to infinity. The factor in the notation may depend on in an arbitrary way. We prove that exponential convergence holds iff independently of and . Furthermore, the largest of exponential convergence is . We also study exponential convergence with weak, polynomial and strong polynomial tractability. This means that for all and and with for weak tractability, with a polynomial bound on for polynomial tractability, and with uniformly bounded for strong polynomial tractability. We prove that the notions of weak, polynomial and strong polynomial tractability are equivalent, and hold iff and are exponentially growing with . We also prove that the largest (or the supremum of) for exponential convergence with strong polynomial tractability belongs to .

**[1]**N. Aronszajn,*Theory of reproducing kernels*, Trans. Amer. Math. Soc.**68**(1950), 337-404. MR**0051437 (14,479c)****[2]**Helmut Brass and Knut Petras,*Quadrature theory*, Mathematical Surveys and Monographs, vol. 178, American Mathematical Society, Providence, RI, 2011. The theory of numerical integration on a compact interval. MR**2840013 (2012h:65047)****[3]**Josef Dick, Gerhard Larcher, Friedrich Pillichshammer, and Henryk Woźniakowski,*Exponential convergence and tractability of multivariate integration for Korobov spaces*, Math. Comp.**80**(2011), no. 274, 905-930. MR**2772101 (2012g:65035)**, https://doi.org/10.1090/S0025-5718-2010-02433-0**[4]**Josef Dick and Friedrich Pillichshammer,*Digital nets and sequences*, Cambridge University Press, Cambridge, 2010. Discrepancy theory and quasi-Monte Carlo integration. MR**2683394 (2012b:65005)****[5]**Erich Novak and Henryk Woźniakowski,*Tractability of multivariate problems. Volume I: Linear information*, EMS Tracts in Mathematics, vol. 6, European Mathematical Society (EMS), Zürich, 2008. MR**2455266 (2009m:46037)****[6]**Erich Novak and Henryk Woźniakowski,*Tractability of multivariate problems. Volume II: Standard information for functionals*, EMS Tracts in Mathematics, vol. 12, European Mathematical Society (EMS), Zürich, 2010. MR**2676032 (2011h:46093)****[7]**I. H. Sloan and H. Woźniakowski,*An intractability result for multiple integration*, Math. Comp.**66**(1997), no. 219, 1119-1124. MR**1401946 (97i:41040)**, https://doi.org/10.1090/S0025-5718-97-00834-X**[8]**J. F. Traub, G. W. Wasilkowski, and H. Woźniakowski,*Information-based complexity*, Computer Science and Scientific Computing, Academic Press Inc., Boston, MA, 1988. With contributions by A. G. Werschulz and T. Boult. MR**958691 (90f:68085)****[9]**Jörg Waldvogel,*Towards a general error theory of the trapezoidal rule*, Approximation and computation, Springer Optim. Appl., vol. 42, Springer, New York, 2011, pp. 267-282. MR**2759090 (2012i:65047)**, https://doi.org/10.1007/978-1-4419-6594-3_17

Retrieve articles in *Mathematics of Computation*
with MSC (2010):
11K45,
65C05,
65D30

Retrieve articles in all journals with MSC (2010): 11K45, 65C05, 65D30

Additional Information

**Peter Kritzer**

Affiliation:
Institut für Finanzmathematik, Johannes Kepler University Linz, Altenbergstraße 69, A-4040 Linz, Austria

Email:
peter.kritzer@jku.at

**Friedrich Pillichshammer**

Affiliation:
Institut für Finanzmathematik, Johannes Kepler University Linz, Altenbergstraße 69, A-4040 Linz, Austria

Email:
friedrich.pillichshammer@jku.at

**Henryk Woźniakowski**

Affiliation:
Department of Computer Science, Columbia University, New York, New York 10027 – and – Institute of Applied Mathematics, University of Warsaw, ul. Banacha 2, 02-097 Warszawa, Poland

Email:
henryk@cs.columbia.edu

DOI:
https://doi.org/10.1090/S0025-5718-2013-02739-1

Received by editor(s):
March 9, 2012

Received by editor(s) in revised form:
May 23, 2012

Published electronically:
November 20, 2013

Additional Notes:
The first author was supported by the Austrian Science Fund (FWF), Project P23389-N18.

The second author was partially supported by the Austrian Science Fund (FWF), Project S 9609, that is part of the Austrian Research Network “Analytic Combinatorics and Probabilistic Number Theory”.

The third author was partially supported by the National Science Foundation.

Article copyright:
© Copyright 2013
American Mathematical Society