平均框架下Korobov空间的逼近基于标准信息的易处理性

路婉婷，许贵桥

(天津师范大学数学科学学院，天津 300387)

1 预备知识

多元连续问题是指定义在多元函数类上算子的逼近问题.这些问题通常用信息基算法求得近似解.本文所用的信息为标准信息，即函数值.信息复杂性n(ε，d)是指对d元函数求得误差小于ε的解而需要的信息算子的最小数.多元连续问题易处理性的概念[1]于1994年引入，其着重研究n(ε，d)当维数d无限变大而ε无限变小时的变化趋势.若n(ε，d)是ε-1或d的指数函数，那么问题被称为不易处理的，否则就称为易处理的.有关易处理性问题的基本知识和结果可参见文献[2-4].本文在平均框架和归一化误差标准下讨论问题，相关定义如下：

(1) 如果存在正数C使得n(ε，d)≤Cdqε-p，则称问题是多项式易处理的；

(2) 如果存在正数C使得n(ε，d)≤Cε-p，则称问题是强多项式易处理的；

(3) 如果存在正数C，t使得n(ε，d)≤Cexp(t(1+lnd)(1+lnε-1))，

(1)

则称问题是拟多项式易处理的；

(2)

则称问题是弱易处理的.

在以上概念中，d∈N，ε∈(0，1)，p，q为与d，ε无关的正数.若问题是强多项式易处理的，则满足n(ε，d)≤Cε-p的p的下确界，称为强多项式易处理性的指数，并记作pstr.

2 Korobov空间逼近问题的易处理性

(3)

对任意n，利用Λall的最优算法An，d为

(4)

且其平均误差为

(5)

在平均框架下对于归一化误差标准，由文献[2]知利用Λall逼近的复杂性nall(ε，d)(利用nall(ε，d)代替n(ε，d)以区别于标准信息类)为

(6)

基于(6)式，在平均框架下利用Λall逼近的易处理性问题已有大量的研究.[2，4-9]计算函数在一点的值远比计算函数的连续线性泛函容易，因此比较Λstd和Λall的逼近效果成为近期的研究热点.[4，8]但至今未出现Λstd和Λall完全一致……