确定性与随机化框架下的Sobolev类上的嵌入与积分的复杂性  

Complexity of Sobolev imbeddings and integration in the deterministic and randomized settings

作　　者：叶培新[1] 

机构地区：[1]南开大学数学学院,天津300071

出　　处：《中国科学：数学》2011年第2期165-180,共16页Scientia Sinica：Mathematica

基　　金：国家自然科学基金(批准号:10971251)资助项目

摘　　要：本文研究各向异性Sobolev类上的嵌入以及积分问题的复杂性.我们得到这些问题在确定性、随机化框架以及平均框架下n-重最小误差的精确阶.所得结果表明在非嵌入连续函数空间情形,随机误差与平均误差实质性地小于确定性误差.从数量级看,对于嵌入问题,收敛阶最大改进可达到n-1+ε,这里ε是任意正数.对于积分问题最大改进可达到n-1.这是数值分析中迄今发现的随机化算法较之确定性算法在收敛阶方面的最大改进.This paper reformulates the problems of approximation of imbedding and integration from anisotropic Sobolev classes B（Wpr （[0,1]d）） in the deterministic,randomized and average case settings,and obtains the exact orders of the n-th minimal error of these problems in all three settings.The results show that in the case of B（Wpr （[0,1]d）） being not imbedded into the space of continuous functions C（[0,1]d）,the randomized and average case error are essential smaller than the deterministic ones.Quantitatively,this maximal gain for imbedding problem amounts to the factor n-1＋ε for any ε 0,and for integration problem the gain is up to factor n-1 which is also the maximal speedup over the deterministic algorithms observed so far in natural numerical problems.

关 键 词：Sobolev嵌入 MONTE Carlo积分 随机化方法 平均框架 n-重最小误差 

分 类 号：O241.5[理学—计算数学]