×

Sampling and cubature on sparse grids based on a B-spline quasi-interpolation. (English) Zbl 1359.41001

Summary: Let \(X_n = \{x^j\}_{j=1}^n\) be a set of \(n\) points in the \(d\)-cube \({\mathbb {I}}^d:=[0,1]^d\), and \(\Phi _n = \{\varphi _j\}_{j =1}^n\) a family of \(n\) functions on \({\mathbb {I}}^d\). We consider the approximate recovery of functions \(f\) on \({{\mathbb {I}}}^d\) from the sampled values \(f(x^1),\dotsc, f(x^n)\), by the linear sampling algorithm \( L_n(X_n,\Phi _n,f) := \sum _{j=1}^n f(x^j)\varphi _j. \) The error of sampling recovery is measured in the norm of the space \(L_q({\mathbb {I}}^d)\)-norm or the energy quasi-norm of the isotropic Sobolev space \(W^\gamma _q({\mathbb {I}}^d)\) for \(1 < q < \infty \) and \(\gamma > 0\). Functions \(f\) to be recovered are from the unit ball in Besov-type spaces of an anisotropic smoothness, in particular, spaces \(B^{\alpha ,\beta }_{p,\theta }\) of a “hybrid” of mixed smoothness \(\alpha > 0\) and isotropic smoothness \(\beta \in {\mathbb {R}}\), and spaces \(B^a_{p,\theta }\) of a nonuniform mixed smoothness \(a \in {\mathbb {R}}^d_+\). We constructed asymptotically optimal linear sampling algorithms \(L_n(X_n^\ast,\Phi _n^\ast,\cdot )\) on special sparse grids \(X_n^\ast\) and a family \(\Phi _n^\ast\) of linear combinations of integer or half integer translated dilations of tensor products of B-splines. We computed the asymptotic order of the error of the optimal recovery. This construction is based on B-spline quasi-interpolation representations of functions in \(B^{\alpha ,\beta }_{p,\theta }\) and \(B^a_{p,\theta }\). As consequences, we obtained the asymptotic order of optimal cubature formulas for numerical integration of functions from the unit ball of these Besov-type spaces.

MSC:

41A15 Spline approximation
41A05 Interpolation in approximation theory
41A25 Rate of convergence, degree of approximation
41A58 Series expansions (e.g., Taylor, Lidstone series, but not Fourier series)
41A63 Multidimensional problems

References:

[1] K. Babenko, On the approximation of periodic functions of several variables by trigonometric polynomials, Dokl. Akad. Nauk USSR 132, 247-250 (1960); English transl. in Soviet Math. Dokl. 1(1960). · Zbl 0099.28302
[2] R. Bellmann, Dynamic Programming, (Princeton University Press, Princeton, 1957). · Zbl 0081.36901
[3] J. Bergh and J. Löfström, Interpolation Spaces, An Introduction, (Grundlehren der Mathematischen Wissenschaften 223, Springer-Verlag, 1976). · Zbl 0344.46071
[4] O. Bokanowski, J. Garcke, M. Griebel, I. Klompmaker, An adaptive sparse grid semi-Lagrangian scheme for first order Hamilton-Jacobi Bellman equations, J. of Scientific Computing 55, 575-605 (2013). · Zbl 1269.65076
[5] H.-J. Bungartz, M. Griebel, A note on the complexity of solving Poisson’s equation for spaces of bounded mixed derivatives, J. Complexity 15, 167-199 (1999). · Zbl 0954.65078
[6] H.-J. Bungartz, M. Griebel, Sparse grids, Acta Numer. 13, 147-269 (2004). · Zbl 1118.65388
[7] G. Byrenheid, D. Dũng, W. Sickel, T. Ullrich, Sampling on energy-norm based sparse grids for the optimal recovery of Sobolev type functions in \[H^{\gamma }\] Hγ, arXiv:1408.3498 [math.NA] (2014). · Zbl 1347.42003
[8] C. Chui, An Introduction to Wavelets, (Academic Press, New York, 1992). · Zbl 0925.42016
[9] C. de Bore, K. Höllig, S. Riemenschneider, Box Spline, (Springer-Verlag, Berlin, 1993). · Zbl 0814.41012 · doi:10.1007/978-1-4757-2244-4
[10] R. DeVore, G. Lorentz, Constructive approximation, (Springer-Verlag, New York, 1993). · Zbl 0797.41016 · doi:10.1007/978-3-662-02888-9
[11] D. Dũng (Din’ Zung), The number of integral points in some sets and approximation of functions of several variables, Mat. Zametki 36, 479-491 (1984). · Zbl 0589.42013
[12] D. Dũng (Din’ Zung), Approximation of functions of several variables on a torus by trigonometric polynomials, Mat. Sb. (N.S.) 131(173)(2), 251-271 (1986). · Zbl 0634.42005
[13] D. Dũng (Din’ Zung), On recovery and one-sided approximation of periodic functions of several variables, Dokl. Akad. SSSR 313, 787-790 (1990).
[14] D. Dũng, On optimal recovery of multivariate periodic functions, In Harmonic Analysis, ed. by S. Igary, (Springer, Berlin, 1991), pp. 96-105. · Zbl 0792.42008
[15] D. Dũng, Optimal recovery of functions of a certain mixed smoothness, Vietnam J. Math. 20(2), 18-32 (1992). · Zbl 0940.41502
[16] D. Dũng, Non-linear sampling recovery based on quasi-interpolant wavelet representations, Adv. Comput. Math. 30, 375-401 (2009). · Zbl 1175.41025
[17] D. Dũng, Optimal adaptive sampling recovery, Adv. Comput. Math. 34, 1-41 (2011). · Zbl 1211.41007
[18] D. Dũng, B-spline quasi-interpolant representations and sampling recovery of functions with mixed smoothness, J. Complexity 27, 541-567 (2011). · Zbl 1230.65017
[19] D. Dũng, High-dimensional periodic sampling on Smolyak grids based on B-spline quasi-interpolation, arXiv:1502.01447v2 [math.NA] (2015)
[20] D. Dũng, T. Ullrich, \[NN\]-dimensions for high-dimensional approximations, Foundations of Comp. Math. 13, 965-1003 (2013). · Zbl 1284.42001
[21] D. Dũng, T. Ullrich, Lower bounds for the integration error for multivariate functions with mixed smoothness and optimal Fibonacci cubature for functions on the square, Math. Nachr. doi: 10.1002/mana.201400048 (2014). · Zbl 1317.65067
[22] J. Garcke, M. Hegland, Fitting multidimensional data using gradient penalties and the sparse grid combination technique, Computing 84(1-2), 1-25 (2009). · Zbl 1166.65004
[23] T. Gerstner, M. Griebel, Numerical Integration using Sparse Grids, Numer. Algorithms 18, 209-232 (1998). · Zbl 0921.65022
[24] T. Gerstner, M. Griebel, Sparse grids, In Encyclopedia of Quantitative Finance, ed. by R. Cont, (John Wiley and Sons, 2010). · Zbl 1185.91001
[25] M. Griebel, J. Hamaekers, Tensor product multiscale many-particle spaces with finite-order weights for the electronic Schrödinger equation, Zeitschrift für Physikalische Chemie 224, 527-543 (2010).
[26] M. Griebel, J. Hamaekers, Fast discrete Fourier transform on generalized sparse grids, in Sparse grids and Applications, volume 97 of Lecture Notes in Computational Science and Engineering, (Springer, Berlin, 2014), pp. 75-108. · Zbl 1316.65119
[27] M. Griebel, H. Harbrecht, A note on the construction of \[L\] L-fold sparse tensor product spaces, Constr. Approximation 38(2), 235-251 (2013). · Zbl 1283.41015
[28] M. Griebel, H. Harbrecht, On the construction of sparse tensor product spaces, Mathematics of Computations 82(282), 975-994 (2013). · Zbl 1267.41012
[29] M. Griebel, M. Holtz, Dimension-wise integration of high-dimensional functions with applications to finance, J. Complexity 26, 455-489 (2010). · Zbl 1203.65056
[30] M. Griebel, S. Knapek, Optimized general sparse grid approximation spaces for operator equations, Math. Comp. 78(268), 2223-2257 (2009). · Zbl 1198.65053
[31] H.-C. Kreusler, H. Yserentant, The mixed regularity of electronic wave functions in fractional order and weighted Sobolev spaces, Numer. Math. 121, 781-802 (2012). · Zbl 1258.35152
[32] S. Nikol’skii, Approximation of functions of several variables and embedding theorems, (Springer, Berlin, 1975). · Zbl 0307.46024 · doi:10.1007/978-3-642-65711-5
[33] E. Novak, H. Triebel, Function spaces in Lipschitz domains and optimal rates of convergence for sampling, Constr. Approx. 23, 325-350 (2006). · Zbl 1106.41014
[34] E. Novak, H. Woźniakowski, Tractability of Multivariate Problems, Volume I: Linear Information, EMS Tracts in Mathematics, Vol. 6, (Eur. Math. Soc. Publ. House, Zürich, 2008). · Zbl 1156.65001
[35] E. Novak and H. Woźniakowski, Tractability of Multivariate Problems, Volume II: Standard Information for Functionals, EMS Tracts in Mathematics, Vol. 12, (Eur. Math. Soc. Publ. House, Zürich, 2010). · Zbl 1241.65025
[36] W. Sickel, T. Ullrich, The Smolyak algorithm, sampling on sparse grids and function spaces of dominating mixed smoothness, East J. Approx. 13, 387-425 (2007). · Zbl 1487.41025
[37] W. Sickel, T. Ullrich, Spline Interpolation on sparse grids, Applicable Analysis 90, 337-383 (2011). · Zbl 1219.41012
[38] S. Smolyak, Quadrature and interpolation formulas for tensor products of certain classes of functions, Dokl. Akad. Nauk 148, 1042-1045 (1963). · Zbl 0202.39901
[39] S. Telyakovskii, Some estimates for trigonometric series with quasi-convex coefficients, Mat. Sb. 63(105), 426-444 (1964); English transl. in Amer. Math. Soc. Transl. 86 (1970). · Zbl 0198.09403
[40] V. Temlyakov, Approximation recovery of periodic functions of several variables, Mat. Sb. 128(1985), 256-268.
[41] V. Temlyakov, Approximation of functions with bounded mixed derivative, Trudy MIAN, 178(1986); English transl. in Proc. Steklov Inst. Math. (1989), Issue 1. · Zbl 0625.41028
[42] V. Temlyakov, On approximate recovery of functions with bounded mixed derivative, J. Complexity 9, 41-59 (1993). · Zbl 0784.41027
[43] V. Temlyakov, Approximation of periodic functions, (Nova Science Publishers, Inc., New York, 1993). · Zbl 0899.41001
[44] H. Triebel, Interpolation Theory, Function Spaces, Differential Operators, (VEB Deutscher Verlag der Wissenschaften, Berlin, 1978), (Johann Ambrosius Barth, Heidelberg, 1995). · Zbl 0830.46028
[45] H. Triebel, Bases in function spaces, sampling, discrepancy, numerical integration, (European Math. Soc. Publishing House, Zürich, 2010). · Zbl 1202.46002 · doi:10.4171/085
[46] T. Ullrich, Smolyak’s algorithm, sampling on sparse grids and Sobolev spaces of dominating mixed smoothness. East J. Approx. 14, 1-38 (2008). · Zbl 1217.41021
[47] T. Ullrich and B. Vedel, Hyperbolic wavelet analysis of classical isotropic and anisotropic Besov-Sobolev spaces, Manuscript (2015). · Zbl 1467.42058
[48] H. Yserentant, The hyperbolic cross space approximation of electronic wavefunctions, Numer. Math. 105, 659-690 (2007). · Zbl 1116.78007
[49] H. Yserentant, Regularity and approximability of electronic wave functions, Lecture Notes in Mathematics, 2000, (Springer-Verlag, Berlin, 2010). · Zbl 1204.35003
[50] H. Yserentant, The mixed regularity of electronic wave functions multiplied by explicit correlation factors, ESAIM Math. Model. Numer. Anal. 45, 803-824 (2011). · Zbl 1311.35243
[51] C. Zenger, Sparse grids, in Parallel Algorithms for Partial Differential Equations ed. by W. Hackbusch, Vol. 31 of Notes on Numerical Fluid Mechanics, (Vieweg, Braunschweig/Wiesbaden, 1991). · Zbl 0763.65091
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.