Approximation of Mixed Order Sobolev Functions on the d-Torus: Asymptotics, Preasymptotics, and d-Dependence

详细信息    查看全文

• 作者：Thomas Kühn ; Winfried Sickel ; Tino Ullrich
• 关键词：Approximation numbers ; Sobolev spaces of mixed smoothness ; Rate of convergence ; Preasymptotics ; d ; Dependence ; Quasi ; polynomial tractability ; 42A10 ; 41A25 ; 41A63 ; 46E35 ; 65D15
• 刊名：Constructive Approximation
• 出版年：2015
• 出版时间：December 2015
• 年：2015
• 卷：42
• 期：3
• 页码：353-398
• 全文大小：1,009 KB
• 参考文献：1.Babenko, K.I.: About the approximation of periodic functions of many variable trigonometric polynomials. Dokl. Akad. Nauk SSR 32, 247-50 (1960)MathSciNet
  2.Bugrov, Y.S.: Approximation of a class of functions with a dominant mixed derivative. Mat. Sbornik 64(106), 410-18 (1964)MathSciNet
  3.Bungartz, H.-J., Griebel, M.: A note on the complexity of solving Poisson’s equation for spaces of bounded mixed derivatives. J. Complex. 15, 167-99 (1999)MathSciNet CrossRef MATH
  4.Bungartz, H.-J., Griebel, M.: Sparse grids. Acta Numer. 13, 147-69 (2004)MathSciNet CrossRef
  5.Byrenheid, G., Dinh D?ng, Sickel, W., Ullrich, T.: Sampling on energy-norm based sparse grids for the optimal recovery of Sobolev type functions in \({H}^{\gamma }\) . ArXiv e-prints (2014). arXiv:-408.-498 [math.NA]
  6.Chernov, A., D?ng, D.: New explicit-in-dimension estimates for the cardinality of high-dimensional hyperbolic crosses and approximation of functions having mixed smoothness. ArXiv e-prints (2014). arXiv:-309.-170 [math.NA]
  7.Cobos, F., Kühn, T., Sickel, W.: Optimal approximation of Sobolev functions in the sup-norm. ArXiv e-prints (2015). arXiv:-505.-2636 [math. FA]
  8.Dinh D?ng: Approximation of classes of functions according to the theory given by mixed modulus of continuity. In: Constructive Theory of Functions, pp. 43-8. Publishing House of the Bulgarian Academy of Sciences, Sofia (1984)
  9.D?ng, Dinh: B-spline quasi-interpolant representations and sampling recovery of functions with mixed smoothness. J. Complex. 27, 541-67 (2011)CrossRef MATH
  10.D?ng, Dinh: Ullrich, T.: \(N\) -widths and \(\varepsilon \) -dimensions for high-dimensional approximations. Found. Comput. Math. 13, 965-003 (2013)MathSciNet CrossRef MATH
  11.Galeev, E.M.: Approximation by Fourier sums of classes of functions with several bounded derivatives. Mat. Zametki 23, 197-12 (1978)MathSciNet MATH
  12.Gnewuch, M., Wo?niakowski, H.: Quasi-polynomial tractability. J. Complex. 27(3-), 312-30 (2011)CrossRef MATH
  13.Griebel, M.: Sparse grids and related approximation schemes for higher dimensional problems. In: Proceedings of Foundations of Computational Mathematics, Santander 2005, pp. 106-61. London Mathematical Society Lecture Notes Series, 331, Cambridge University Press, Cambridge (2006)
  14.Griebel, M., Knapek, S.: Optimized tensor-product approximation spaces. Constr. Approx. 16(4), 525-40 (2000)MathSciNet CrossRef MATH
  15.Griebel, M., Knapek, S.: Optimized general sparse grid approximation spaces for operator equations. Math. Comput. 78(268), 2223-257 (2009)MathSciNet CrossRef MATH
  16.Kolmogorov, A.N.: über die beste Ann?herung von Funktionen einer gegebenen Funktionenklasse. Ann. Math. 37, 107-10 (1936)MathSciNet CrossRef MATH
  17.K?nig, H.: Eigenvalue Distribution of Compact Operators. Birkh?user, Basel (1986)CrossRef MATH
  18.Kühn, T., Mayer, S., Ullrich, T.: Counting via entropy—new preasymptotics for the approximation numbers of Sobolev embeddings. ArXiv e-prints (2015). arXiv:-505.-0631 [math. NA]
  19.Kühn, T., Sickel, W., Ullrich, T.: Approximation numbers of Sobolev embeddings—sharp constants and tractability. J. Complex. 30, 95-16 (2014)CrossRef MATH
  20.Mityagin, B.S.: Approximation of functions in \(L^p\) and \(C\) on the torus. Math. Notes 58, 397-14 (1962)
  21.Nikol’skaya, N.S.: Approximation of differentiable functions of several variables by Fourier sums in the \(L_p\) metric. Sibirsk. Mat. Zh. 15, 395-12 (1974)MATH
  22.Novak, E., Wo?niakowski, H.: Tractability of Multivariate Problems. Volume I: Linear Information. EMS, Zürich (2008)
  23.Novak, E., Wo?niakowski, H.: Optimal order of convergence and (in)tractability of multivariate approximation of smooth functions. Constr. Approx. 30, 457-73 (2009)MathSciNet CrossRef MATH
  24.Novak, E., Wo?niakowski, H.: Tractability of multivariate problems. Volume II: Standard information for functionals. EMS, Zürich (2010)
  25.Novak, E., Wo?niakowski, H.: Tractability of multivariate problems. Volume III: Standard information for operators. EMS, Zürich (2012)
  26.Pietsch, A.: Operator ideals. VEB Deutscher Verlag der Wissenschaften, Berlin (1978) and North-Holland, Amsterdam (1980)
  27.Pietsch, A.: History of Banach Spaces and Linear Operators. Birkh?user, Basel (2007)MATH
  28.Pinkus, A.: \(n\) -Widths in Approximation Theory. Springer, Berlin (1985)
  29.Schwab, C., Süli, E., Todor, R.A.: Sparse finite element approximation of high-dimensional transport-dominated diffusion problems. ESAIM Math. Model. Numer. Anal. 42(05), 777-19 (2008)CrossRef MATH
  30.Sickel, W., Ullrich, T.: Smolyak’s algorithm, sampling on sparse grids and function spaces of dominating mixed smoothness. Jenaer Schriften zur Math. und Inf. 14/06 (2006)
  31.Sickel, W., Ullrich, T.: Smolyak’s algorithm, sampling on sparse grids and function spaces of dominating mixed smoothness. East J. Approx. 13, 387-25 (2007)MathSciNet
  32
• 作者单位：Thomas Kühn (1)
  Winfried Sickel (2)
  Tino Ullrich (3)
  
  1. Universit?t Leipzig, Augustusplatz 10, 04109, Leipzig, Germany
  2. Friedrich-Schiller-Universit?t Jena, Ernst-Abbe-Platz 2, 07737, Jena, Germany
  3. Hausdorff-Center for Mathematics, Endenicher Allee 62, 53115, Bonn, Germany
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Numerical Analysis
  Analysis
  
• 出版者：Springer New York
• ISSN：1432-0940

文摘

We investigate the approximation of d-variate periodic functions in Sobolev spaces of dominating mixed (fractional) smoothness \(s>0\) on the d-dimensional torus, where the approximation error is measured in the \(L_2\)-norm. In other words, we study the approximation numbers \(a_n\) of the Sobolev embeddings \(H^s_\mathrm{mix}(\mathbb {T}^d)\hookrightarrow L_2(\mathbb {T}^d)\), with particular emphasis on the dependence on the dimension d. For any fixed smoothness \(s>0\), we find two-sided estimates for the approximation numbers as a function in n and d. We observe super-exponential decay of the constants in d, if n, the number of linear samples of f, is large. In addition, motivated by numerical implementation issues, we also focus on the error decay that can be achieved by approximations using only a few linear samples (small n). We present some surprising results for the so-called “preasymptotic-decay and point out connections to the recently introduced notion of quasi-polynomial tractability of approximation problems. Keywords Approximation numbers Sobolev spaces of mixed smoothness Rate of convergence Preasymptotics d-Dependence Quasi-polynomial tractability