We analyse convergence rates of Smolyak integration for parametric maps u: U → X taking values in a Banach space X, defined on the parameter domain U = [−1,1]N. For parametric maps which are sparse, as quantified by summability of their Taylor polynomial chaos coefficients, dimension-independent convergence rates superior to N-term approximation rates under the same sparsity are achievable. We propose a concrete Smolyak algorithm to a priori identify integrand-adapted sets of active multiindices (and thereby unisolvent sparse grids of quadrature points) via upper bounds for the integrands’ Taylor gpc coefficients. For so-called “($$,ε)-holomorphic” integrands u with $$∈$$(∕) for some p ∈ (0, 1), we prove the dimension-independent convergence rate 2/p − 1 in terms of the number of quadrature points. The proposed Smolyak algorithm is proved to yield (essentially) the same rate in terms of the total computational cost for both nested and non-nested univariate quadrature points. Numerical experiments and a mathematical sparsity analysis accounting for cancellations in quadratures and in the combination formula demonstrate that the asymptotic rate 2/p − 1 is realized computationally for a moderate number of quadrature points under certain circumstances. By a refined analysis of model integrand classes we show that a generally large preasymptotic range otherwise precludes reaching the asymptotic rate 2/p − 1 for practically relevant numbers of quadrature points.
Mots-clés : Generalized polynomial chaos, Smolyak quadrature, sparsity, holomorphy, Convergence rates of high dimensional Smolyak quadrature
@article{M2AN_2020__54_4_1259_0,
author = {Zech, Jakob and Schwab, Christoph},
title = {Convergence rates of high dimensional {Smolyak} quadrature},
journal = {ESAIM: Mathematical Modelling and Numerical Analysis },
pages = {1259--1307},
publisher = {EDP-Sciences},
volume = {54},
number = {4},
year = {2020},
doi = {10.1051/m2an/2020003},
mrnumber = {4113052},
zbl = {07240638},
language = {en},
url = {http://www.numdam.org/articles/10.1051/m2an/2020003/}
}
TY - JOUR AU - Zech, Jakob AU - Schwab, Christoph TI - Convergence rates of high dimensional Smolyak quadrature JO - ESAIM: Mathematical Modelling and Numerical Analysis PY - 2020 SP - 1259 EP - 1307 VL - 54 IS - 4 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/m2an/2020003/ DO - 10.1051/m2an/2020003 LA - en ID - M2AN_2020__54_4_1259_0 ER -
%0 Journal Article %A Zech, Jakob %A Schwab, Christoph %T Convergence rates of high dimensional Smolyak quadrature %J ESAIM: Mathematical Modelling and Numerical Analysis %D 2020 %P 1259-1307 %V 54 %N 4 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/m2an/2020003/ %R 10.1051/m2an/2020003 %G en %F M2AN_2020__54_4_1259_0
Zech, Jakob; Schwab, Christoph. Convergence rates of high dimensional Smolyak quadrature. ESAIM: Mathematical Modelling and Numerical Analysis , Tome 54 (2020) no. 4, pp. 1259-1307. doi : 10.1051/m2an/2020003. http://www.numdam.org/articles/10.1051/m2an/2020003/
, and , Sparse polynomial approximation of parametric elliptic PDEs. Part I: affine coefficients. ESAIM: M2AN 51 (2017) 321–339. | DOI | Numdam | MR | Zbl
, and , High dimensional polynomial interpolation on sparse grids. Multivariate polynomial interpolation. Adv. Comput. Math. 12 (2000) 273–288. | DOI | MR | Zbl
, , and , On the optimal polynomial approximation of stochastic PDEs by Galerkin and collocation methods. Math. Models Methods Appl. Sci. 22 (2012) 1250023, 33. | DOI | MR | Zbl
and , Sparse grids. Acta Numer. 13 (2004) 147–269. | DOI | MR | Zbl
and , Lagrange interpolation at real projections of Leja sequences for the unit disk. Proc. Amer. Math. Soc. 140 (2012) 4271–4284. | DOI | MR | Zbl
and , On the Lebesgue constant of Leja sequences for the unit disk and its applications to multivariate interpolation. J. Approx. Theory 163 (2011) 608–622. | DOI | MR | Zbl
, Holomorphy and Calculus in Normed Spaces. With an appendix by Angus E. Taylor. In: Vol. 92 of Monographs and Textbooks in Pure and Applied Mathematics. Marcel Dekker, Inc., New York (1985). | MR | Zbl
, On the Lebesgue constant of Leja sequences for the complex unit disk and of their real projection. J. Approx. Theory 166 (2013) 176–200. | DOI | MR | Zbl
, , , , Adaptive algorithms for sparse polynomial approximation of parametric and stochastic elliptic pdes. ESAIM: M2AN 47 (2013) 253–280. | DOI | Numdam | MR | Zbl
, and , Convergence rates of best -term Galerkin approximations for a class of elliptic sPDEs. Found. Comput. Math. 10 (2010) 615–646. | DOI | MR | Zbl
, and , Analytic regularity and polynomial approximation of parametric and stochastic elliptic PDE’s. Anal. Appl. (Singap.) 9 (2011) 11–47. | DOI | MR | Zbl
, and , Breaking the curse of dimensionality in sparse polynomial approximation of parametric pdes. J. Math. Pures Appl. 103 (2015) 400–428. | DOI | MR
, and , Shape holomorphy of the stationary Navier-Stokes equations. SIAM J. Math. Anal. 50 (2018) 1720–1752. | DOI | MR
, , , and , Higher order QMC Petrov-Galerkin discretization for affine parametric operator equations with random field inputs. SIAM J. Numer. Anal. 52 (2014) 2676–2702. | DOI | MR
, and , High-dimensional integration: the quasi-Monte Carlo way. Acta Numer. 22 (2013) 133–288. | DOI | MR | Zbl
and , Computational higher order quasi-Monte Carlo integration, In: Vol. 163 Monte Carlo and Quasi-Monte Carlo Methods: MCQMC, Leuven, Belgium, April 2014 (2016) 271–288. | DOI | MR
and , Numerical integration using sparse grids. Numer. Algorithms 18 (1998) 209–232. | DOI | MR | Zbl
and , Dimension-adaptive tensor-product quadrature. Computing 71 (2003) 65–87. | DOI | MR | Zbl
, , , , and , Quasi-Monte Carlo finite element methods for elliptic PDEs with lognormal random coefficients. Numer. Math. 131 (2015) 329–368. | DOI | MR
and , On tensor product approximation of analytic functions. J. Approx. Theory 207 (2016) 348–379. | DOI | MR
, , and , Multi-index stochastic collocation for random PDEs. Comput. Methods Appl. Mech. Eng. 306 (2016) 95–122. | DOI | MR
, , and , Novel results for the anisotropic sparse grid quadrature. J. Complexity 47 (2018) 62–85. | DOI | MR
, and , Analysis of the domain mapping method for elliptic diffusion problems on random domains. Numer. Math. 134 (2016) 823–856. | DOI | MR
, Analyticity in Infinite-dimensional Spaces. In: Vol. 10 of De Gruyter Studies in Mathematics. Walter de Gruyter & Co., Berlin (1989). | MR | Zbl
, , and , Large deformation shape uncertainty quantification in acoustic scattering. Adv. Comput. Math. 44 (2018) 1475–1518. | DOI | MR
and , -term Wiener chaos approximation rate for elliptic PDEs with lognormal Gaussian random inputs. Math. Models Methods Appl. Sci. 24 (2014) 797–826. | DOI | MR | Zbl
, and , Electromagnetic wave scattering by random surfaces: shape holomorphy. Math. Mod. Meth. Appl. Sci. 27 (2017) 2229–2259. | DOI | MR
and , Application of quasi-Monte Carlo methods to elliptic PDEs with random diffusion coefficients: a survey of analysis and implementation. Found. Comput. Math. 16 (2016) 1631–1696. | DOI | MR
, , , and , Multilevel Quasi-Monte Carlo Methods for Lognormal Diffusion Problems. Technical Report 2015–22, Seminar for Applied Mathematics, ETH Zürich (2016). | MR
, and , An anisotropic sparse grid stochastic collocation method for partial differential equations with random input data. SIAM J. Numer. Anal. 46 (2008) 2411–2442. | DOI | MR | Zbl
, A remark on Stirling’s formula. Amer. Math. Monthly 62 (1955) 26–29. | DOI | MR | Zbl
and , Sparse, adaptive Smolyak quadratures for Bayesian inverse problems. Inverse Prob. 29 (2013) 065011. | DOI | MR | Zbl
and , Sparse tensor discretizations of high-dimensional parametric and stochastic pdes. Acta Numer. 20 (2011) 291–467. | DOI | MR | Zbl
and , Sparse deterministic approximation of Bayesian inverse problems. Inverse Prob. 28 (2012) 045003. | DOI | MR | Zbl
, Quadrature and interpolation formulas for tensor products of certain classes of functions. Sov. Math. Dokl. 4 (1963) 240–243. | MR | Zbl
and , Convergence rates of sparse chaos approximations of elliptic problems with stochastic coefficients. IMA J. Numer. Anal. 44 (2007) 232–261. | DOI | MR | Zbl
, Sparse-grid approximation of high-dimensional parametric PDEs. Ph.D. thesis. Dissertation 25683, ETH Zürich (2018). doi: . | DOI
, and , Multilevel approximation of parametric and stochastic PDEs. Math. Models Methods Appl. Sci. 29 (2019) 1753–1817. | DOI | MR
Cité par Sources :
