Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

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 $ \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]$.


References [Enhancements On Off] (What's this?)

  • [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

Similar Articles

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

American Mathematical Society