Acta mathematica scientia,Series B ›› 2005, Vol. 25 ›› Issue (3): 439-448.

• Articles • Previous Articles     Next Articles

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

 FANG Gen-Sun, XIE Pei-Xin   

  • Online:2005-07-20 Published:2005-07-20
  • Supported by:

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

Abstract:

The order of computational complexity of all bounded linear functional approximation
problem is determined for the generalized Sobolev class W
p (Id), Nikolskii
class Hk
1(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
W
p (Id) and Hk
1(Id) is intractable in worst case setting, but is tractable with respect to
stochastic and average case setting.

Key words: Worst (deterministic) case, stochastic case, average case setting, bounded
linear functional,
error estimate

CLC Number: 

  • 41A55
Trendmd