Discrete least squares polynomial approximation with random evaluations − application to parametric and stochastic elliptic PDEs
ESAIM: Mathematical Modelling and Numerical Analysis , Tome 49 (2015) no. 3, pp. 815-837.

Motivated by the numerical treatment of parametric and stochastic PDEs, we analyze the least-squares method for polynomial approximation of multivariate functions based on random sampling according to a given probability measure. Recent work has shown that in the univariate case, the least-squares method is quasi-optimal in expectation in [A. Cohen, M A. Davenport and D. Leviatan. Found. Comput. Math. 13 (2013) 819–834] and in probability in [G. Migliorati, F. Nobile, E. von Schwerin, R. Tempone, Found. Comput. Math. 14 (2014) 419–456], under suitable conditions that relate the number of samples with respect to the dimension of the polynomial space. Here “quasi-optimal” means that the accuracy of the least-squares approximation is comparable with that of the best approximation in the given polynomial space. In this paper, we discuss the quasi-optimality of the polynomial least-squares method in arbitrary dimension. Our analysis applies to any arbitrary multivariate polynomial space (including tensor product, total degree or hyperbolic crosses), under the minimal requirement that its associated index set is downward closed. The optimality criterion only involves the relation between the number of samples and the dimension of the polynomial space, independently of the anisotropic shape and of the number of variables. We extend our results to the approximation of Hilbert space-valued functions in order to apply them to the approximation of parametric and stochastic elliptic PDEs. As a particular case, we discuss “inclusion type” elliptic PDE models, and derive an exponential convergence estimate for the least-squares method. Numerical results confirm our estimate, yet pointing out a gap between the condition necessary to achieve optimality in the theory, and the condition that in practice yields the optimal convergence rate.

Reçu le :
DOI : 10.1051/m2an/2014050
Classification : 41A10, 41A25, 65N35, 65N12, 65N15, 35J25
Mots clés : Approximation theory, polynomial approximation, least squares, parametric and stochastic PDEs, high-dimensional approximation
Chkifa, Abdellah 1 ; Cohen, Albert 1 ; Migliorati, Giovanni 2 ; Nobile, Fabio 2 ; Tempone, Raul 3

1 Institut Universitaire de France, UPMC Univ Paris 06, UMR 7598, Laboratoire Jacques-Louis Lions, 75005 Paris, France.
2 MATHICSE-CSQI, École Polytechnique Fédérale de Lausanne, 1015 Lausanne, Switzerland
3 Applied Mathematics and Computational Sciences, and SRI Center for Uncertainty Quantification in Computational Science and Engineering, KAUST, 23955-6900 Thuwal, Saudi Arabia.
@article{M2AN_2015__49_3_815_0,
     author = {Chkifa, Abdellah and Cohen, Albert and Migliorati, Giovanni and Nobile, Fabio and Tempone, Raul},
     title = {Discrete least squares polynomial approximation with random evaluations \ensuremath{-} application to parametric and stochastic elliptic {PDEs}},
     journal = {ESAIM: Mathematical Modelling and Numerical Analysis },
     pages = {815--837},
     publisher = {EDP-Sciences},
     volume = {49},
     number = {3},
     year = {2015},
     doi = {10.1051/m2an/2014050},
     zbl = {1318.41004},
     mrnumber = {3342229},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/m2an/2014050/}
}
TY  - JOUR
AU  - Chkifa, Abdellah
AU  - Cohen, Albert
AU  - Migliorati, Giovanni
AU  - Nobile, Fabio
AU  - Tempone, Raul
TI  - Discrete least squares polynomial approximation with random evaluations − application to parametric and stochastic elliptic PDEs
JO  - ESAIM: Mathematical Modelling and Numerical Analysis 
PY  - 2015
SP  - 815
EP  - 837
VL  - 49
IS  - 3
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/m2an/2014050/
DO  - 10.1051/m2an/2014050
LA  - en
ID  - M2AN_2015__49_3_815_0
ER  - 
%0 Journal Article
%A Chkifa, Abdellah
%A Cohen, Albert
%A Migliorati, Giovanni
%A Nobile, Fabio
%A Tempone, Raul
%T Discrete least squares polynomial approximation with random evaluations − application to parametric and stochastic elliptic PDEs
%J ESAIM: Mathematical Modelling and Numerical Analysis 
%D 2015
%P 815-837
%V 49
%N 3
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/m2an/2014050/
%R 10.1051/m2an/2014050
%G en
%F M2AN_2015__49_3_815_0
Chkifa, Abdellah; Cohen, Albert; Migliorati, Giovanni; Nobile, Fabio; Tempone, Raul. Discrete least squares polynomial approximation with random evaluations − application to parametric and stochastic elliptic PDEs. ESAIM: Mathematical Modelling and Numerical Analysis , Tome 49 (2015) no. 3, pp. 815-837. doi : 10.1051/m2an/2014050. http://archive.numdam.org/articles/10.1051/m2an/2014050/

I. Babuška, F. Nobile and R. Tempone, A stochastic collocation method for elliptic partial differential equations with random input data. SIAM J. Numer. Anal. 45 (2007) 1005–1034 . | DOI | MR | Zbl

I. Babuška, R. Tempone and G.E. Zouraris, Galerkin finite element approximations of stochastic elliptic partial differential equations. SIAM J. Numer. Anal. 42 (2004) 800–825. | DOI | MR | Zbl

J. Bäck, F. Nobile, L. Tamellini and R. Tempone, On the optimal polynomial approximation of stochastic PDEs by Galerkin and Collocation methods. Math. Model. Methods Appl. Sci. 22 (2012) 1250023. | DOI | MR | Zbl

J. Beck, F. Nobile, L. Tamellini, R. Tempone, Convergence of quasi-optimal Stochastic Galerkin Methods for a class of PDES with random coefficients. Comput. Math. Appl. 67 (2014) 732–751. | DOI | MR | Zbl

A. Chkifa, A. Cohen, R. Devore and Ch. Schwab, Sparse adaptive Taylor approximation algorithms for parametric and stochastic elliptic PDEs. Math. Model. Numer. Anal. 47 (2013) 253–280. | DOI | Numdam | MR | Zbl

A. Chkifa, A. Cohen and Ch. Schwab, High-dimensional adaptive sparse polynomial interpolation and applications to parametric PDEs. Found. Comput. Math. 14 (2014) 601–633. | DOI | MR | Zbl

A. Chkifa, A. Cohen and C. Schwab, Breaking the curse of dimensionality in sparse polynomial approximation of parametric PDEs. To appear in J. Math. Pures Appl. (2015). | MR | Zbl

A. Cohen, M A. Davenport and D. Leviatan, On the stability and accuracy of least squares approximations. Found. Comput. Math. 13 (2013) 819–834. | DOI | MR | Zbl

A. Cohen, R. Devore and C. Schwab, Convergence rates of best N-term Galerkin approximations for a class of elliptic sPDEs, Found. Comput. Math. 10 (2010) 615–646. | DOI | MR | Zbl

A. Cohen, R. Devore and C. Schwab, Analytic regularity and polynomial approximation of parametric and stochastic PDE’s. Anal. Appl. 9 (2011) 1–37. | DOI | MR | Zbl

D. Coppersmith and T.J. Rivlin, The growth of polynomials bounded at equally spaced points. SIAM J. Math. Anal. 23 (1992) 970–983. | DOI | MR | Zbl

Ph.J. Davis, Interpolation and Approximation. Blaisdell Publishing Company (1963). | MR | Zbl

C. De Boor and A. Ron, Computational aspects of polynomial interpolation in several variables. Math. Comput. 58 (1992) 705–727. | DOI | MR | Zbl

C.J. Gittelson, An adaptive stochastic Galerkin method for random elliptic operators. Math. Comput. 82 (2013) 1515–1541. | DOI | MR | Zbl

M. Kleiber and T. D. Hien, The stochastic finite element methods. John Wiley & Sons, Chichester (1992). | MR | Zbl

J. Kuntzman, Méthodes numériques - Interpolation, dérivées. Dunod, Paris (1959). | MR | Zbl

G. Lorentz and R. Lorentz, Solvability problems of bivariate interpolation I. Constructive Approximation 2 (1986) 153–169. | DOI | MR | Zbl

G.Migliorati, Polynomial approximation by means of the random discrete L 2 projection and application to inverse problems for PDEs with stochastic data. Ph.D. thesis, Dipartimento di Matematica “Francesco Brioschi” Politecnico di Milano, Milano, Italy, and Centre de Mathématiques Appliquées, École Polytechnique, Palaiseau, France (2013).

G. Migliorati, Multivariate Markov-type and Nikolskii-type inequalities for polynomials associated with downward closed multi-index sets. J. Approx. Theory 189 (2015) 137–159. | DOI | MR | Zbl

G. Migliorati, F. Nobile, E. Von Schwerin and R. Tempone, Analysis of discrete L 2 projection on polynomial spaces with random evaluations. Found. Comput. Math. 14 (2014) 419–456. | MR | Zbl

G. Migliorati, F. Nobile, E. Von Schwerin and R. Tempone, Approximation of Quantities of Interest in stochastic PDEs by the random discrete L 2 projection on polynomial spaces. SIAM J. Sci. Comput. 35 (2013) A1440–A1460. | DOI | MR | Zbl

V. Nistor and Ch. Schwab, High order Galerkin approximations for parametric, second order elliptic partial differential equations, Report 2012-22, Seminar for Applied Mathematics, ETH Zürich. Math. Models Methods Appl. Sci. 23 (2013). | MR | Zbl

F. Nobile, R. Tempone and C.G. Webster, A sparse grid stochastic collocation method for elliptic partial differential equations with random input data. SIAM J. Num. Anal. 46 (2008) 2309–2345. | DOI | MR | Zbl

F. Nobile, R. Tempone and C.G. Webster, An anisotropic sparse grid stochastic collocation method for elliptic partial differential equations with random input data. SIAM J. Num. Anal. 46 (2008) 2411–2442. | DOI | MR | Zbl

Cité par Sources :