Summary
We study approximation of functions belonging to Sobolev spaces W r p (Q) by randomized algorithms based on function values. Here 1 ≤ p ≤ ∞, Q = [0, 1] d , and r, d ∈ N. The error is measured in L q (Q), with 1 ≤ q < ∞, and we assume r/d > 1/p − 1/q, guaranteeing that W r p (Q) is embedded into L q (Q). The optimal order of convergence for the case that W r p (Q) is embedded even into C(Q) is wellknown. It is n−r/d+max(1/p−1/q,0) (n the number of function evaluations). This rate is already reached by deterministic algorithms, and randomization gives no speedup.
In this paper we are concerned with the case that W r p (Q) is not embedded into C(Q) (but, of course, still into L q (Q)). For this situation approximation based on function values was not studied before. We prove that for randomized algorithms the above rate also holds, while for deterministic algorithms no rate whatsoever is possible. Thus, in the case of low smoothness, Monte Carlo approximation algorithms reach a considerable speedup over deterministic ones (up to n −1+ε for any ε > 0).
We also give some applications to integration of functions and to approximation of solutions of elliptic PDE.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
R.A. Adams. Sobolev Spaces. Academic Press, New York (1975).
P.G. Ciarlet. The Finite Element Method for Elliptic Problems. North-Holland, Amsterdam (1978).
S. Dahlke, E. Novak, and W. Sickel. Optimal approximation of elliptic problems by linear and nonlinear mappings I, J. Complexity 22, 29–49 (2006).
S. Dahlke, E. Novak, and W. Sickel. Optimal approximation of elliptic problems by linear and nonlinear mappings II, J. Complexity 22, 549–603 (2006).
S.M. Ermakov and V.G. Zolotukhin. Polynomial approximation and the Monte Carlo method, Theor. Prob. Appl. 5, 428–431 (1960).
S. Heinrich. Random approximation in numerical analysis. In: K.D. Bierstedt, A. Pietsch, W.M. Ruess, and D. Vogt (eds) Functional Analysis. Marcel Dekker, New York, 123–171 (1993).
S. Heinrich. Monte Carlo approximation of weakly singular integral operators. J. Complexity 22, 192–219 (2006).
S. Heinrich. The randomized information complexity of elliptic PDE. J. Complexity 22, 220–249 (2006).
P. Mathé. Random approximation of Sobolev embeddings. J. Complexity 7, 261–281 (1991).
E. Novak. Deterministic and Stochastic Error Bounds in Numerical Analysis. Lecture Notes in Mathematics 1349, Springer-Verlag, Berlin (1988).
E. Novak and H. Triebel. Function spaces in Lipschitz domains and optimal rates of convergence for sampling. Constr. Approx. 23, 325–350 (2006).
J.F. Traub, G.W. Wasilkowski, and H. Woźniakowski. Information- Based Complexity. Academic Press, New York (1988).
H. Triebel. Interpolation Theory, Function Spaces, Differential Operators. North-Holland, Amsterdam, New York, Oxford (1978).
G.W. Wasilkowski. Randomization for continuous problems. J. Complexity 5, 195–218 (1989).
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Heinrich, S. (2008). Randomized Approximation of Sobolev Embeddings. In: Keller, A., Heinrich, S., Niederreiter, H. (eds) Monte Carlo and Quasi-Monte Carlo Methods 2006. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-74496-2_26
Download citation
DOI: https://doi.org/10.1007/978-3-540-74496-2_26
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-74495-5
Online ISBN: 978-3-540-74496-2
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)