On the optimal convergence rate of universal and nonuniversal algorithms for multivariate integration and approximation
HTML articles powered by AMS MathViewer
- by Michael Griebel and Henryk Woźniakowski PDF
- Math. Comp. 75 (2006), 1259-1286 Request permission
Abstract:
We study the maximal rate of convergence (mrc) of algorithms for (multivariate) integration and approximation of $d$-variate functions from reproducing kernel Hilbert spaces $H(K_{d})$. Here $K_{d}$ is an arbitrary kernel all of whose partial derivatives up to order $r$ satisfy a Hölder-type condition with exponent $2\beta$. Algorithms use $n$ function values and we analyze their rate of convergence as $n$ tends to infinity. We focus on universal algorithms which depend on $d$, $r$, and $\beta$ but not on the specific kernel $K_d$, and nonuniversal algorithms which may depend additionally on $K_d$. For universal algorithms the mrc is $(r+\beta )/d$ for both integration and approximation, and for nonuniversal algorithms it is $1/2+ (r+\beta )/d$ for integration and $a+(r+\beta )/d$ with $a\in [1/(4+4(r+\beta )/d),1/2]$ for approximation. Hence, the mrc for universal algorithms suffers from the curse of dimensionality if $d$ is large relative to $r+\beta$, whereas the mrc for nonuniversal algorithms does not since it is always at least $1/2$ for integration, and $1/4$ for approximation. This is the price we have to pay for using universal algorithms. On the other hand, if $r+\beta$ is large relative to $d$, 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 $K_d$ has product structure, $K_{d,r,\beta }=\bigotimes _{j=1}^dK_{r_j,\beta _j}$. Here $K_{r_j,\beta _j}$ are some univariate kernels whose all derivatives up to order $r_j$ satisfy a Hölder-type condition with exponent $2\beta _j$. Then the mrc for universal algorithms is $q:=\min _{j=1,2,\dots ,d }(r_j+\beta _j)$ for both integration and approximation, and for nonuniversal algorithms it is $1/2 +q$ for integration and $a+q$ with $a\in [1/(4+4q),1/2]$ for approximation. If $r_j\ge 1$ or $\beta _j\ge \beta >0$ for all $j$, then the mrc is at least $\min (1,\beta )$, and the curse of dimensionality is not present. Hence, the product form of reproducing kernels breaks the curse of dimensionality even for universal algorithms.References
- N. Aronszajn, Theory of reproducing kernels, Trans. Amer. Math. Soc. 68 (1950), 337–404. MR 51437, DOI 10.1090/S0002-9947-1950-0051437-7
- K. I. Babenko, The saturation phenomenon in numerical analysis, Dokl. Akad. Nauk SSSR 241 (1978), no. 3, 505–508 (Russian). MR 504216
- Ivo Babuška, Über universal optimale Quadraturformeln, Apl. Mat. 13 (1968), 304–338; ibid. 13 (1968), 388–404 (German, with Czech and Russian summaries). MR 0244680
- V. I. Krylov, Priblizhennoe vychislenie integralob, Gosudarstv. Izdat. Fiz.-Mat. Lit., Moscow, 1959 (Russian). MR 0111138
- H. Brass, Universal quadrature rules in the space of periodic functions, Numerical integration, III (Oberwolfach, 1987) Internat. Schriftenreihe Numer. Math., vol. 85, Birkhäuser, Basel, 1988, pp. 16–24. MR 1021519, DOI 10.1007/978-3-0348-6398-8_{2}
- H.-J. Bungartz and M. Griebel, Sparse grids, Acta Numerica, 13, 147–269, 2004.
- Thomas Gerstner and Michael Griebel, Numerical integration using sparse grids, Numer. Algorithms 18 (1998), no. 3-4, 209–232. MR 1669959, DOI 10.1023/A:1019129717644
- F. J. Hickernell and H. Woźniakowski, Integration and approximation in arbitrary dimensions, Adv. Comput. Math. 12 (2000), no. 1, 25–58. High dimensional integration. MR 1758946, DOI 10.1023/A:1018948631251
- V. Motornyj, On the best quadrature formula of the form $\sum _{k=1}^np_kf(x_k)$ for some classes of periodic differentiable functions, Ivz. Akad. Nauk USSR Ser. Mat., 38, 538–614, 1974.
- Erich Novak, Deterministic and stochastic error bounds in numerical analysis, Lecture Notes in Mathematics, vol. 1349, Springer-Verlag, Berlin, 1988. MR 971255, DOI 10.1007/BFb0079792
- Erich Novak and Klaus Ritter, High-dimensional integration of smooth functions over cubes, Numer. Math. 75 (1996), no. 1, 79–97. MR 1417864, DOI 10.1007/s002110050231
- Erich Novak and Klaus Ritter, The curse of dimension and a universal method for numerical integration, Multivariate approximation and splines (Mannheim, 1996) Internat. Ser. Numer. Math., vol. 125, Birkhäuser, Basel, 1997, pp. 177–187. MR 1485004
- Erich Novak and Henryk Woźniakowski, When are integration and discrepancy tractable?, Foundations of computational mathematics (Oxford, 1999) London Math. Soc. Lecture Note Ser., vol. 284, Cambridge Univ. Press, Cambridge, 2001, pp. 211–266. MR 1836619
- Knut Petras, On the universality of the Gaussian quadrature formula, East J. Approx. 2 (1996), no. 4, 427–438. MR 1426714
- Klaus Ritter, Average-case analysis of numerical problems, Lecture Notes in Mathematics, vol. 1733, Springer-Verlag, Berlin, 2000. MR 1763973, DOI 10.1007/BFb0103934
- Klaus Ritter and Grzegorz W. Wasilkowski, Integration and $L_2$-approximation: average case setting with isotropic Wiener measure for smooth functions, Rocky Mountain J. Math. 26 (1996), no. 4, 1541–1557. MR 1447602, DOI 10.1216/rmjm/1181072003
- Klaus Ritter, Grzegorz W. Wasilkowski, and Henryk Woźniakowski, On multivariate integration for stochastic processes, Numerical integration, IV (Oberwolfach, 1992) Internat. Ser. Numer. Math., vol. 112, Birkhäuser, Basel, 1993, pp. 331–347. MR 1248414
- 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.
- Ian H. Sloan and Henryk Woźniakowski, When are quasi-Monte Carlo algorithms efficient for high-dimensional integrals?, J. Complexity 14 (1998), no. 1, 1–33. MR 1617765, DOI 10.1006/jcom.1997.0463
- V. N. Temlyakov, Universal cubature formulas, Dokl. Akad. Nauk SSSR 316 (1991), no. 1, 44–47 (Russian); English transl., Soviet Math. Dokl. 43 (1991), no. 1, 39–42. MR 1102770
- V. N. Temlyakov, Approximation of periodic functions, Computational Mathematics and Analysis Series, Nova Science Publishers, Inc., Commack, NY, 1993. MR 1373654
- 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
- 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. Woźniakowski, Academic Press, 1988.
- Grace Wahba, Spline models for observational data, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 59, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1990. MR 1045442, DOI 10.1137/1.9781611970128
- G. W. Wasilkowski, Integration and approximation of multivariate functions: average case complexity with isotropic Wiener measure, Bull. Amer. Math. Soc. (N.S.) 28 (1993), no. 2, 308–314. MR 1184000, DOI 10.1090/S0273-0979-1993-00379-3
- G. W. Wasilkowski and H. Woźniakowski, On the power of standard information for weighted approximation, Found. Comput. Math. 1 (2001), no. 4, 417–434. MR 1857723, DOI 10.1007/s102080010016
- Grzegorz W. Wasilkowski and Henryk Woźniakowski, Explicit cost bounds of algorithms for multivariate tensor product problems, J. Complexity 11 (1995), no. 1, 1–56. MR 1319049, DOI 10.1006/jcom.1995.1001
- H. Woźniakowski, Average case complexity of linear multivariate problems, Bull. Amer. Math. Soc. (N.S.) 29 (1993), no. 1, 70–76. MR 1193541, DOI 10.1090/S0273-0979-1993-00400-2
Additional Information
- Michael Griebel
- Affiliation: Institut für Numerische Simulation, Universität Bonn, Wegelerstrasse 6, D-53113 Bonn, Germany
- MR Author ID: 270664
- Email: griebel@ins.uni-bonn.de
- Henryk Woźniakowski
- 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
- 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. - © Copyright 2006
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Math. Comp. 75 (2006), 1259-1286
- MSC (2000): Primary 65D30, 65D15, 41A45
- DOI: https://doi.org/10.1090/S0025-5718-06-01865-5
- MathSciNet review: 2219028