平均框架下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完全一致的易處理性結果.本文利用文獻[10]構造隨機逼近算子的思路來證明對文獻[5]提出的基于一元Korobov核的多元逼近問題，在易處理問題上Λstd和Λall有相同逼近效果.

以β∈[0，1]，r>1/2為參數的一元Korobov核Rγ，β定義為

假設{gk}滿足

1≥g1≥g2≥…>0.

(7)

記Dd=[0，1]d.對d∈N，定義d元Korobov核

(8)

考慮連續實函數空間C(Dd)上具有零均值高斯測度，且其協方差核為

的Korobov空間在L2(Dd)上的逼近問題：APP={APPd}d∈N.其中對任一固定d逼近問題為APPd：C(Dd)→L2(Dd)，這里APPdf=f，?f∈C(Dd).

的特征值集合可表示為

Ad={λd，z|Z=[z1，z2，…zd]∈Nd}，

(9)

這里λ(k，1)=1，且

λ(k，2j)=λ(k，2j+1)=gk/j2r，?j∈N.

(10)

為使用方便，把Ad中的元素重新排列為{λd，i}i∈N，使其滿足λd，1≥λd，2≥…≥0.由文獻[5]知相應的特征向量為三角多項式，記為ηd，i.由(4)式知其對應的最優算法為

(11)

對于歸一化誤差標準，文獻[5，7-8]得到了問題APP關于Λall具有易處理性的一些結果：

引理1設逼近問題APP={APPd}的gk滿足(7)式.對于Λall，有：

(1)APP是多項式易處理的，當且僅當

(12)

(2)APP是多項式易處理的，等價于APP是強多項式易處理的，且

pstr=max(2/(2r-1)，2/(ρg-1))；

(3)APP是擬多項式易處理的，當且僅當

(13)

其中ln+x∶=max(1，lnx)；

(4)APP是一致弱易處理的，當且僅當

(14)

(15)

定理1設逼近問題APP={APPd}的gk滿足(7)式.對于Λstd，有：

(1)APP是多項式易處理的，當且僅當

(16)

(2)APP是多項式易處理的，等價于APP是強多項式易處理的，且

pstr=max(2/(2r-1)，2/(ρg-1))；

(3)APP是擬多項式易處理的，當且僅當

(17)

(4)APP是一致弱易處理的，當且僅當

(18)

(19)

證明必要性可由Λstd?Λall及引理1給出，下證充分性.對任意固定的整數m

(20)

(21)

(22)

其中

(23)

(24)

(25)

(26)

(27)

(28)

由(24)及(28)式可得

(29)

由(29)式及Fubini定理，

(30)

(31)

由(21)，(30)—(31)式可得

(32)

(33)

下面作迭代.令Ad，0=0，

Ad，kg=Ad，k-1g+Ad，τ(g-Ad，k-1g).

(34)

令Δd，kg=g-Ad，kg，則上式化為

Δd，kg=Δd，k-1g-Ad，τ(Δd，k-1g).

(35)

(36)

由(33)及(36)式可推出

(37)

對任意給定的0<ε<1，在(37)式中令m=nall(ε/2，d)，n=2nall(ε/2，d)且令k=[2log2ε-1]+1，則由(6)式可得到

(38)

由于算法Ad，k僅用到了2([2log2ε-1]+1)nall(ε/2，d)個標準信息且有(38)式成立，因此

n(ε，d)≤2([2log2ε-1]+1)nall(ε/2，d).

(39)

由(39)式和引理1容易檢驗定理的充分性，由于檢驗過程所用方法極其常規，這里略去.

注1本文算法是非構造性的，尋找構造性的算法是更有意義的問題.