Approximation of two-variate functions: singular value decomposition versus sparse grids
Approximation of two-variate functions: singular value decomposition versus sparse grids
Dokument öffnen (547.2KB)Datum der Veröffentlichung
2011Verlag / herausgebende Einrichtung
Institut für Numerische Simulation (INS)Verlagsort
BonnMetadaten
Zur Langanzeige
Zitierbarer Link (Handle URI) 
https://hdl.handle.net/20.500.11811/11958
Inhalt
We compare the cost complexities of two approximation schemes for functions f ∈ Hp(Ω1 × Ω2) which live on the product domain Ω1 × Ω2 of sufficiently smooth domains Ω1 ⊂ ℝn1 and Ω2 ⊂ ℝn2 , namely the singular value / Karhunen-Lòeve decomposition and the sparse grid representation. Here we assume that suitable finite element methods with associated fixed order r of accuracy are given on the domains Ω1 and Ω2. Then, the sparse grid approximation essentially needs only O(ε−q) with q = max{n1,n2}/r unknowns to reach a prescribed accuracy ε provided that the smoothness of f satisfies p ≥ rn1+n2/max{n1,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 < rn1+n2/max{n1,n2} , then the sparse grid approach gives essentially the rate O(ε−q) with q = n1,n2/p while, for the singular value decomposition, we can only prove the rate O(ε−q) with q = 2min{r,p}min{n1,n2}+2pmax{n1,n2}/ (2p−min{n1,n2})min{r,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.
Schlagwörter
singular value decomposition, sparse grids, complexity
Klassifikation (DDC)
510 Mathematik 518 Numerische AnalysisErstpublikation
https://ins.uni-bonn.de/publication/preprintsZugehörige Publikation(en)
https://doi.org/10.1093/imanum/drs047Reihe, Nummer
INS Preprints ; 1109Griebel, Michael; Harbrecht, Helmut: Approximation of two-variate functions: singular value decomposition versus sparse grids. In: INS Preprints, 1109.
Online-Ausgabe in bonndoc: https://hdl.handle.net/20.500.11811/11958
Online-Ausgabe in bonndoc: https://hdl.handle.net/20.500.11811/11958
@unpublished{handle:20.500.11811/11958,
author = {{Michael Griebel} and {Helmut Harbrecht}},
title = {Approximation of two-variate functions: singular value decomposition versus sparse grids},
publisher = {Institut für Numerische Simulation (INS)},
year = 2011,
INS Preprints},
volume = 1109,
note = {We compare the cost complexities of two approximation schemes for functions f ∈ Hp(Ω1 × Ω2) which live on the product domain Ω1 × Ω2 of sufficiently smooth domains Ω1 ⊂ ℝn1 and Ω2 ⊂ ℝn2 , namely the singular value / Karhunen-Lòeve decomposition and the sparse grid representation. Here we assume that suitable finite element methods with associated fixed order r of accuracy are given on the domains Ω1 and Ω2. Then, the sparse grid approximation essentially needs only O(ε−q) with q = max{n1,n2}/r unknowns to reach a prescribed accuracy ε provided that the smoothness of f satisfies p ≥ rn1+n2/max{n1,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 < rn1+n2/max{n1,n2} , then the sparse grid approach gives essentially the rate O(ε−q) with q = n1,n2/p while, for the singular value decomposition, we can only prove the rate O(ε−q) with q = 2min{r,p}min{n1,n2}+2pmax{n1,n2}/ (2p−min{n1,n2})min{r,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.},
url = {https://hdl.handle.net/20.500.11811/11958}
}
author = {{Michael Griebel} and {Helmut Harbrecht}},
title = {Approximation of two-variate functions: singular value decomposition versus sparse grids},
publisher = {Institut für Numerische Simulation (INS)},
year = 2011,
INS Preprints},
volume = 1109,
note = {We compare the cost complexities of two approximation schemes for functions f ∈ Hp(Ω1 × Ω2) which live on the product domain Ω1 × Ω2 of sufficiently smooth domains Ω1 ⊂ ℝn1 and Ω2 ⊂ ℝn2 , namely the singular value / Karhunen-Lòeve decomposition and the sparse grid representation. Here we assume that suitable finite element methods with associated fixed order r of accuracy are given on the domains Ω1 and Ω2. Then, the sparse grid approximation essentially needs only O(ε−q) with q = max{n1,n2}/r unknowns to reach a prescribed accuracy ε provided that the smoothness of f satisfies p ≥ rn1+n2/max{n1,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 < rn1+n2/max{n1,n2} , then the sparse grid approach gives essentially the rate O(ε−q) with q = n1,n2/p while, for the singular value decomposition, we can only prove the rate O(ε−q) with q = 2min{r,p}min{n1,n2}+2pmax{n1,n2}/ (2p−min{n1,n2})min{r,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.},
url = {https://hdl.handle.net/20.500.11811/11958}
}
Die folgenden Nutzungsbestimmungen sind mit dieser Ressource verbunden:
