COMPUTATIONAL COMPLEXITY IN WORST, STOCHASTIC AND AVERAGE CASE SETTING ON FUNCTIONAL APPROXIMATION PROBLEM OF MULTIVARIATE  

作　　者：房艮孙 叶培新 

机构地区：[1]School of Mathematical Sciences Beijing Normal University [2]School of Mathematical Sciences and LPMC Nankai university

出　　处：《Acta Mathematica Scientia》2005年第3期439-448,共10页数学物理学报（B辑英文版）

基　　金：Project supported by the Natural Science Foundation of China(10371009) and Research Fund for the Doctoral Program Higher Education.

摘　　要：The order of computational complexity of all bounded linear functional ap proximation problem is determined for the generalized Sobolev class Wp?（Id）, Nikolskii class H|∞k（Id） in the worst （deterministic）, stochastic and average case setting, from which it is concluded that the bounded linear functional approximation problem for the classes Wp?（Id） and H∞k（Id） is intractable in worst case setting, but is tractable with respect to stochastic and average case setting.<正>The order of computational complexity of all bounded linear functional ap proximation problem is determined for the generalized Sobolev class Wp?（Id）, Nikolskii class H|∞k（Id） in the worst （deterministic）, stochastic and average case setting, from which it is concluded that the bounded linear functional approximation problem for the classes Wp?（Id） and H∞k（Id） is intractable in worst case setting, but is tractable with respect to stochastic and average case setting.

关 键 词：worst (deterministic) case stochastic case average case setting bounded linear functional error estimate 

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