On the optimal convergence rate of universal and nonuniversal algorithms for multivariate integration and approximation

Authors:
Michael Griebel and Henryk Wozniakowski

Journal:
Math. Comp. **75** (2006), 1259-1286

MSC (2000):
Primary 65D30, 65D15, 41A45

DOI:
https://doi.org/10.1090/S0025-5718-06-01865-5

Published electronically:
May 1, 2006

MathSciNet review:
2219028

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We study the maximal rate of convergence (mrc) of algorithms for (multivariate) integration and approximation of -variate functions from reproducing kernel Hilbert spaces . Here is an arbitrary kernel all of whose partial derivatives up to order satisfy a Hölder-type condition with exponent . Algorithms use function values and we analyze their rate of convergence as tends to infinity. We focus on *universal* algorithms which depend on , , and but not on the specific kernel , and *nonuniversal* algorithms which may depend additionally on .

For universal algorithms the mrc is for both integration and approximation, and for nonuniversal algorithms it is for integration and with for approximation. Hence, the mrc for universal algorithms suffers from the curse of dimensionality if is large relative to , whereas the mrc for nonuniversal algorithms does *not* since it is always at least for integration, and for approximation. This is the price we have to pay for using universal algorithms. On the other hand, if is large relative to , then the mrc for universal and nonuniversal algorithms is approximately the same.

We also consider the case when we have the additional knowledge that the kernel has product structure, . Here are some univariate kernels whose all derivatives up to order satisfy a Hölder-type condition with exponent . Then the mrc for universal algorithms is for both integration and approximation, and for nonuniversal algorithms it is for integration and with for approximation. If or for all , then the mrc is at least , and the curse of dimensionality is *not* present. Hence, the product form of reproducing kernels breaks the curse of dimensionality even for universal algorithms.

**1.**N. Aronszajn, Theory of reproducing kernels,*Trans. Amer. Math. Soc.*, 68, 337-404, 1950. MR**0051437 (14:479c)****2.**K. I. Babenko, On the phenomenon of saturation in numerical analysis,*Dokl. Akad. Nauk SSSR*, 241, 505-509, 1978. Translation in*Soviet Math. Dokl.*, 19, 859-863, 1978. MR**0504216 (80c:65116)****3.**I. Babuska, Über universal optimale Quadraturformeln,*Appl. Mat.*, 13, 304-338, 338-404, 1968. MR**0244680 (39:5994)****4.**N. S. Bakhvalov, On approximate calculation of integrals (in Russian),*Vestnik MGV, Ser. Mat. Mekh. Astron. Fiz.*, 4, 3-18, 1959. MR**0111138 (22:2002)****5.**H. Brass, Universal quadrature rules in the space of periodic functions, in Numerical Integration III, eds. H. Brass and G. Hämmerlin, ISNM, vol. 85, Birkhäuser, 16-24, 1988. MR**1021519 (91a:65057)****6.**H.-J. Bungartz and M. Griebel, Sparse grids,*Acta Numerica*, 13, 147-269, 2004.**7.**T. Gerstner and M. Griebel, Numerical integration using sparse grids,*Numer. Alg.*, 18, 209-232, 1998. MR**1669959 (99m:65042)****8.**F. J. Hickernell and H. Wozniakowski, Integration and approximation in arbitrary dimension,*Adv. in Comput. Math.*, 12, 25-58, 2000. MR**1758946 (2001d:65017)****9.**V. Motornyj, On the best quadrature formula of the form for some classes of periodic differentiable functions,*Ivz. Akad. Nauk USSR Ser. Mat.*, 38, 538-614, 1974.**10.**E. Novak,*Deterministic and Stochastic Error Bounds in Numerical Analysis*, Lectures Notes in Mathematics, No. 1349, Springer, New York, 1988. MR**0971255 (90a:65004)****11.**E. Novak and K. Ritter, High dimensional integration of smooth functions over cubes,*Numerische Mathematik*, 75, 79-97, 1996. MR**1417864 (97k:65057)****12.**E. Novak and K. Ritter, The curse of dimension and a universal method for numerical integration, in*Multivariate Approximation and Splines*, G. Nürnberger, J. Schmidt and G. Walz, eds., International Series in Numerical Mathematics, Birkhäuser, Basel, 177-188, 1998. MR**1485004 (98g:65022)****13.**E. Novak and H. Wozniakowski, When are integration and discrepancy tractable?, Foundation of Computational Mathematics, Oxford, 1999, R. A. DeVore, A. Iserles, and E. Süli, eds.,*Cambridge University Press*, Cambridge, 211-266, 2001. MR**1836619 (2002h:68083)****14.**K. Petras, On the universality of the Gaussian formula,*East J. Approx.*, 2, 427-438, 1996. MR**1426714 (97k:41050)****15.**K. Ritter,*Average-Case Analysis of Numerical Problems*, Lectures Notes in Mathematics, No. 1733, Springer, New York, 2000. MR**1763973 (2001i:65001)****16.**K. Ritter and G. W. Wasilkowski, Integration and -approximation: Average case setting with isotropic Wiener measure for smooth functions,*Rocky Mountain J. Math.*, 26, 1541-1557, 1996. MR**1447602 (98c:65212)****17.**K. Ritter, G. W. Wasilkowski and H. Wozniakowski, On multivariate integration for stochastic processes, in Numerical Integration IV, eds. H. Brass and G. Hämmerlin, ISNM, vol. 112, Birkhäuser, 331-347, 1993. MR**1248414 (94j:65031)****18.**S. Smolyak, Quadrature and interpolation formulas for tensor product of certain classes of functions,*Soviet Math. Dokl.*, 4, 240-243, Russian original in*Dokl. Akad. Nauk. SSSR*, 148, 1042-1045, 1963.**19.**I. H. Sloan and H. Wozniakowski, When are Quasi-Monte Carlo algorithms efficient for high dimensional integrals,*J. Complexity*, 14, 1-33, 1998. MR**1617765 (99d:65384)****20.**V. Temlyakov, On universal cubature formulae,*Soviet Math. Dokl.*, 43, 39-42, 1991. MR**1102770 (92e:65030)****21.**V. Temlyakov,*Approximation of Periodic Functions*, Nova Science, New York, 1994, MR**1373654 (96j:41001)****22.**J. F. Traub, G. W. Wasilkowski and H. Wozniakowski,*Information-based Complexity*, Academic Press, New York, 1988. MR**0958691 (90f:68085)****23.**J. Trojan, Asymptotic setting for linear problems, unpublished manuscript, available as Chapter 10 in*Information-based Complexity*by J. F. Traub, G. W. Wasilkowski and H. Wozniakowski, Academic Press, 1988.**24.**G. Wahba,*Spline models for observational data*, CBSM-NSF Regional Conf. Ser. Appl. Math., 59, SIAM, Philadelphia. MR**1045442 (91g:62028)****25.**G. W. Wasilkowski, Integration and approximation of multivariate functions: average case setting with isotropic Wiener measure,*Bull. Amer. Math. Soc*, 28, 308-314, 1993. Full version*J. Approx. Theory*, 77, 212-227, 1994. MR**1184000 (93i:65136)**; MR**1275937 (95c:65234)****26.**G. W. Wasilkowski and H. Wozniakowski, On the power of standard information for weighted approximation,*Journal of FoCM*, 4, 417-438, 2001. MR**1857723 (2002g:41052)****27.**G. W. Wasilkowski and H. Wozniakowski, Explicit cost bounds of algorithms for multivariate tensor product problems,*J. Complexity*, 11, 1-56, 1995. MR**1319049 (95k:65138)****28.**H. Wozniakowski, Average case complexity of linear multivariate problems, Part I: Theory, Part II: Applications,*J. Complexity*, 8, 337-372, 373-392, 1992. MR**1195257 (94a:65076b)**; MR**1195258 (94a:65076c)**

Retrieve articles in *Mathematics of Computation*
with MSC (2000):
65D30,
65D15,
41A45

Retrieve articles in all journals with MSC (2000): 65D30, 65D15, 41A45

Additional Information

**Michael Griebel**

Affiliation:
Institut für Numerische Simulation, Universität Bonn, Wegelerstrasse 6, D-53113 Bonn, Germany

Email:
griebel@ins.uni-bonn.de

**Henryk Wozniakowski**

Affiliation:
Department of Computer Science, Columbia University, New York, NY 10027, USA; 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-06-01865-5

Received by editor(s):
July 25, 2005

Received by editor(s) in revised form:
August 15, 2005

Published electronically:
May 1, 2006

Additional Notes:
The research of the first author was supported in part by the Sonderforschungsbereich 611 Singuläre Phänomene und Skalierung in Mathematischen Modellen sponsored by the Deutsche Forschungsgemeinschaft.

The research of the second author was supported in part by the National Science Foundation.

Article copyright:
© Copyright 2006
American Mathematical Society

The copyright for this article reverts to public domain 28 years after publication.