平均框架下Korobov空間的逼近基于標(biāo)準(zhǔn)信息的易處理性

路婉婷，許貴橋

(天津師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院，天津 300387)

1 預(yù)備知識(shí)

多元連續(xù)問(wèn)題是指定義在多元函數(shù)類上算子的逼近問(wèn)題.這些問(wèn)題通常用信息基算法求得近似解.本文所用的信息為標(biāo)準(zhǔn)信息，即函數(shù)值.信息復(fù)雜性n(ε，d)是指對(duì)d元函數(shù)求得誤差小于ε的解而需要的信息算子的最小數(shù).多元連續(xù)問(wèn)題易處理性的概念[1]于1994年引入，其著重研究n(ε，d)當(dāng)維數(shù)d無(wú)限變大而ε無(wú)限變小時(shí)的變化趨勢(shì).若n(ε，d)是ε-1或d的指數(shù)函數(shù)，那么問(wèn)題被稱為不易處理的，否則就稱為易處理的.有關(guān)易處理性問(wèn)題的基本知識(shí)和結(jié)果可參見(jiàn)文獻(xiàn)[2-4].本文在平均框架和歸一化誤差標(biāo)準(zhǔn)下討論問(wèn)題，相關(guān)定義如下：

(1) 如果存在正數(shù)C使得n(ε，d)≤Cdqε-p，則稱問(wèn)題是多項(xiàng)式易處理的；

(2) 如果存在正數(shù)C使得n(ε，d)≤Cε-p，則稱問(wèn)題是強(qiáng)多項(xiàng)式易處理的；

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

(1)

則稱問(wèn)題是擬多項(xiàng)式易處理的；

(2)

則稱問(wèn)題是弱易處理的.

在以上概念中，d∈N，ε∈(0，1)，p，q為與d，ε無(wú)關(guān)的正數(shù).若問(wèn)題是強(qiáng)多項(xiàng)式易處理的，則滿足n(ε，d)≤Cε-p的p的下確界，稱為強(qiáng)多項(xiàng)式易處理性的指數(shù)，并記作pstr.

2 Korobov空間逼近問(wèn)題的易處理性

(3)

對(duì)任意n，利用Λall的最優(yōu)算法An，d為

(4)

且其平均誤差為

(5)

在平均框架下對(duì)于歸一化誤差標(biāo)準(zhǔn)，由文獻(xiàn)[2]知利用Λall逼近的復(fù)雜性nall(ε，d)(利用nall(ε，d)代替n(ε，d)以區(qū)別于標(biāo)準(zhǔn)信息類)為

(6)

基于(6)式，在平均框架下利用Λall逼近的易處理性問(wèn)題已有大量的研究.[2，4-9]計(jì)算函數(shù)在一點(diǎn)的值遠(yuǎn)比計(jì)算函數(shù)的連續(xù)線性泛函容易，因此比較Λstd和Λall的逼近效果成為近期的研究熱點(diǎn).[4，8]但至今未出現(xiàn)Λstd和Λall完全一致的易處理性結(jié)果.本文利用文獻(xiàn)[10]構(gòu)造隨機(jī)逼近算子的思路來(lái)證明對(duì)文獻(xiàn)[5]提出的基于一元Korobov核的多元逼近問(wèn)題，在易處理問(wèn)題上Λstd和Λall有相同逼近效果.

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

假設(shè){gk}滿足

1≥g1≥g2≥…>0.

(7)

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

(8)

考慮連續(xù)實(shí)函數(shù)空間C(Dd)上具有零均值高斯測(cè)度，且其協(xié)方差核為

的Korobov空間在L2(Dd)上的逼近問(wèn)題：APP={APPd}d∈N.其中對(duì)任一固定d逼近問(wèn)題為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.由文獻(xiàn)[5]知相應(yīng)的特征向量為三角多項(xiàng)式，記為ηd，i.由(4)式知其對(duì)應(yīng)的最優(yōu)算法為

(11)

對(duì)于歸一化誤差標(biāo)準(zhǔn)，文獻(xiàn)[5，7-8]得到了問(wèn)題APP關(guān)于Λall具有易處理性的一些結(jié)果：

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

(1)APP是多項(xiàng)式易處理的，當(dāng)且僅當(dāng)

(12)

(2)APP是多項(xiàng)式易處理的，等價(jià)于APP是強(qiáng)多項(xiàng)式易處理的，且

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

(3)APP是擬多項(xiàng)式易處理的，當(dāng)且僅當(dāng)

(13)

其中l(wèi)n+x∶=max(1，lnx)；

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

(14)

(15)

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

(1)APP是多項(xiàng)式易處理的，當(dāng)且僅當(dāng)

(16)

(2)APP是多項(xiàng)式易處理的，等價(jià)于APP是強(qiáng)多項(xiàng)式易處理的，且

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

(3)APP是擬多項(xiàng)式易處理的，當(dāng)且僅當(dāng)

(17)

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

(18)

(19)

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

(20)

(21)

(22)

其中

(23)

(24)

(25)

(26)

(27)

(28)

由(24)及(28)式可得

(29)

由(29)式及Fubini定理，

(30)

(31)

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

(32)

(33)

下面作迭代.令A(yù)d，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)

對(duì)任意給定的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)個(gè)標(biāo)準(zhǔn)信息且有(38)式成立，因此

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

(39)

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

注1本文算法是非構(gòu)造性的，尋找構(gòu)造性的算法是更有意義的問(wèn)題.