Publication Date:
2014-01-25
Description:
We compare the cost complexities of two approximation schemes for functions f H p ( 1 x 2 ) which live on the product domain 1 x 2 of sufficiently smooth domains 1 R n 1 and 2 R n 2 , 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{ n 1 , n 2 }/ r , unknowns to reach a prescribed accuracy , provided that the smoothness of f satisfies p ≥ r (( n 1 + n 2 )/max{ n 1 , n 2 }), 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 〈 r (( n 1 + n 2 )/max{ n 1 , n 2 }), then the sparse grid approach gives essentially the rate O ( – q ) with q =( n 1 + n 2 )/ p , while, for the singular value decomposition, we can only prove the rate O( – q ) with q =(2 min{ r , p }min{ n 1 , n 2 } +2 p max{ n 1 , n 2 }){(2 p –min{ n 1 , n 2 }) 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.
Print ISSN:
0272-4979
Electronic ISSN:
1464-3642
Topics:
Mathematics
Permalink