×
Hinrichs, Aicke; Novak, Erich; Ullrich, Mario

On weak tractability of the Clenshaw-Curtis Smolyak algorithm. (English) Zbl 1295.41028

J. Approx. Theory 183, 31-44 (2014).
The authors consider the integration of \(d\)-variable (real) analytic functions \(f:[0,1]^d\to \mathbb{R}\) whose directional derivatives of all orders are bounded by one. They show that the Clenshaw-Curtis Smolyak algorithm is weakly traceable for this class of functions. The proof uses the polynomial exactness of the algorithm and an explicit bound on its operator norm.
Reviewer: Peter Massopust (München)

Cited in 13 Documents

MSC:

41A55 Approximate quadratures
65D30 Numerical integration
26E05 Real-analytic functions

Keywords:

numerical integration; quadrature rules; Clenshaw-Curtis Smolyak algorithm
Cite Review PDF
Full Text: DOI arXiv

References:

[1] Babuška, I.; Nobile, F.; Tempone, R., A stochastic collocation method for elliptic partial differential equations with random input data, SIAM Rev., 52, 317-355 (2010) · Zbl 1226.65004
[2] Bakhvalov, N. S., On approximate computation of integrals, Vestn. MGU, Ser. Math. Mech. Astron. Phys. Chem., 4, 3-18 (1959), (in Russian)
[3] Barthelmann, V.; Novak, E.; Ritter, K., High dimensional polynomial interpolation on sparse grids, Adv. Comput. Math., 12, 273-288 (1999) · Zbl 0944.41001
[4] Brass, H.; Petras, K., Quadrature Theory (2011), American Math. Soc.: American Math. Soc. Providence · Zbl 1231.65059
[5] Bungartz, H.-J.; Griebel, M., Sparse grids, Acta Numer., 13, 147-269 (2004) · Zbl 1118.65388
[6] Davis, P. J., A construction of nonnegative approximate quadratures, Math. Comp., 21, 578-582 (1967) · Zbl 0189.16401
[7] Dick, J.; Kuo, F. Y.; Sloan, I. H., High-dimensional integration: the quasi-Monte Carlo way, Acta Numer., 22, 133-288 (2013) · Zbl 1296.65004
[8] Dick, J.; Pillichshammer, F., Discrepancy theory and quasi-Monte Carlo integration, (Chen, W. W.L.; Srivastav, A.; Travaglini, G., A Panorama in Discrepancy Theory. A Panorama in Discrepancy Theory, Lecture Notes in Mathematics, vol. 2107 (2014), Springer Verlag) · Zbl 1358.11086
[9] Gerstner, Th.; Griebel, M., Numerical integration using sparse grids, Numer. Algorithms, 18, 209-232 (1998) · Zbl 0921.65022
[10] Griebel, M., Sparse grids and related approximation schemes for higher dimensional problems, (Pardo, L. M.; etal., Foundations of Computational Mathematics, Santander 2005. Foundations of Computational Mathematics, Santander 2005, London Math. Soc., Lecture Note Series, vol. 331 (2006), Cambridge University Press), 106-161 · Zbl 1106.65332
[11] Hinrichs, A.; Novak, E.; Ullrich, M.; Woźniakowski, H., The curse of dimensionality for numerical integration of smooth functions, Math. Comp. (2014), in press · Zbl 1345.65014
[12] Hinrichs, A.; Novak, E.; Ullrich, M.; Woźniakowski, H., The curse of dimensionality for numerical integration of smooth functions II, J. Complexity, 30, 117-143 (2014) · Zbl 1286.65040
[13] Huang, F. L.; Zhang, S., Approximation of infinitely differentiable multivariate functions is not strongly tractable, J. Complexity, 23, 73-81 (2007) · Zbl 1108.41024
[14] Müller-Gronbach, Th., Hyperbolic cross designs for approximation of random fields, J. Statist. Plann. Inference, 66, 321-344 (1998) · Zbl 0952.62087
[15] Novak, E., (Deterministic and Stochastic Error Bounds in Numerical Analysis. Deterministic and Stochastic Error Bounds in Numerical Analysis, LNiM, vol. 1349 (1988), Springer-Verlag: Springer-Verlag Berlin) · Zbl 0656.65047
[16] Novak, E.; Ritter, K., High dimensional integration of smooth functions over cubes, Numer. Math., 75, 79-97 (1996) · Zbl 0883.65016
[17] Novak, E.; Ritter, K., The curse of dimension and a universal method for numerical integration, (Nürnberger, G.; Schmidt, J. W.; Walz, G., Multivariate Approximation and Splines. Multivariate Approximation and Splines, ISNM, vol. 125 (1997), Birkhäuser: Birkhäuser Basel), 177-188 · Zbl 0889.65016
[18] Novak, E.; Ritter, K., Simple cubature formulas with high polynomial exactness, Constr. Approx., 15, 499-522 (1999) · Zbl 0942.41018
[19] Novak, E.; Woźniakowski, H., (Tractability of Multivariate Problems. Tractability of Multivariate Problems, Linear Information, vol. 1 (2008), European Math. Soc.: European Math. Soc. Zürich) · Zbl 1156.65001
[20] Novak, E.; Woźniakowski, H., Approximation of infinitely differentiable multivariate functions is intractable, J. Complexity, 25, 398-404 (2009) · Zbl 1180.41031
[21] Novak, E.; Woźniakowski, H., (Tractability of Multivariate Problems. Tractability of Multivariate Problems, Standard Information for Functionals, vol. II (2010), European Math. Soc. Publ. House: European Math. Soc. Publ. House Zürich) · Zbl 1241.65025
[22] Petras, K., On the Smolyak cubature error for analytic functions, Adv. Comput. Math., 12, 71-93 (2000) · Zbl 0947.65024
[23] Sickel, W.; Ullrich, T., Smolyak’s algorithm, sampling on sparse grids and function spaces of dominating mixed smoothness, East J. Approx., 13, 387-425 (2007) · Zbl 1487.41025
[24] Sickel, W.; Ullrich, T., Spline interpolation on sparse grids, Appl. Anal., 90, 337-383 (2011) · Zbl 1219.41012
[25] Siedlecki, P., Uniform weak tractability, J. Complexity, 29, 438-453 (2013) · Zbl 1336.68146
[26] Smolyak, S. A., Quadrature and interpolation formulas for tensor products of certain classes of functions, Dokl. Akad. Nauk SSSR, 4, 240-243 (1963) · Zbl 0202.39901
[27] Vybíral, J., Weak and quasi-polynomial tractability of approximation of infinitely differentiable functions, J. Complexity, 30, 48-55 (2014) · Zbl 1308.46034
[28] Wasilkowski, G. W.; Woźniakowski, H., Explicit cost bounds of algorithms for multivariate tensor product problems, J. Complexity, 11, 1-56 (1995) · Zbl 0819.65082
[29] Wasilkowski, G. W.; Woźniakowski, H., Weighted tensor-product algorithms for linear multivariate problems, J. Complexity, 15, 402-447 (1999) · Zbl 0939.65079
[30] Wasilkowski, G. W.; Woźniakowski, H., Polynomial-time algorithms for multivariate linear problems with finite-order weights; worst case setting, Found. Comput. Math., 5, 451-491 (2005) · Zbl 1103.41025
[31] Weimar, M., Tractability results for weighted Banach spaces of smooth functions, J. Complexity, 28, 59-75 (2012) · Zbl 1234.41027
[32] Wojtaszczyk, J. O., Multivariate integration in \(C^\infty([0, 1]^d)\) is not strongly tractable, J. Complexity, 19, 638-643 (2003) · Zbl 1057.68043
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.