Griebel, Michael and Harbrecht, Helmut. (2014) Approximation of bi-variate functions : singular value decomposition versus sparse grids. Ima Journal of Numerical Analysis, Vol. 34, H. 1. pp. 8-54.
PDF
- Published Version
897Kb |
Official URL: http://edoc.unibas.ch/dok/A6223408
Downloads: Statistics Overview
Abstract
We compare the cost complexities of two approximation schemes for functions finHp(Omega1timesOmega2) which live on the product domain Omega1timesOmega2 of sufficiently smooth domains Omega1subsetmathbbRn1 and Omega2subsetmathbbRn2, namely the singular value / Karhunen-L`oeve decomposition and the sparse grid representation. Here we assume that suitable finite element methods with associated {em fixed} order r of accuracy are given on the domains Omega1 and Omega2. Then, the sparse grid approximation essentially needs only mathcalO(varepsilon−q) with q=fracmaxn1,n2r unknowns to reach a prescribed accuracy varepsilon provided that the smoothness of f satisfies pgerfracn1+n2maxn1,n2, which is an almost optimal rate. The singular value decomposition produces this rate only if f is analytical since otherwise the decay of the singular values is not fast enough. If p>rfracn1+n2maxn1,n2, then the sparse grid approach gives essentially the rate mathcalO(varepsilon−q) with q=fracn1+n2p while, for the singular value decomposition, we can only prove the rate mathcalO(varepsilon−q) with q=frac2minr,pminn1,n2+2pmaxn1,n2(2p−minn1,n2)minr,p. We derive the resulting complexities, compare the two approaches and present numerical results which demonstrate that these rates are also achieved in numerical practice. pfracn1+n2maxn1,n2, then the sparse grid approach gives essentially the rate mathcalO(varepsilon−q) with q=fracn1+n2p while, for the singular value decomposition, we can only prove the rate mathcalO(varepsilon−q) with q=frac2minr,pminn1,n2+2pmaxn1,n2(2p−minn1,n2)minr,p. We derive the resulting complexities, compare the two approaches and present numerical results which demonstrate that these rates are also achieved in numerical practi
Faculties and Departments: | 05 Faculty of Science > Departement Mathematik und Informatik > Mathematik > Computational Mathematics (Harbrecht) |
---|---|
UniBasel Contributors: | Harbrecht, Helmut |
Item Type: | Article, refereed |
Article Subtype: | Research Article |
Publisher: | Oxford University Press |
ISSN: | 0272-4979 |
Note: | Publication type according to Uni Basel Research Database: Journal article |
Language: | English |
Identification Number: | |
edoc DOI: | |
Last Modified: | 13 Mar 2018 17:15 |
Deposited On: | 27 Mar 2014 13:13 |
Repository Staff Only: item control page