不定積分的隨機(jī)復(fù)雜性

不定積分的隨機(jī)復(fù)雜性斯特凡?海因里希，伯恩哈德?米拉凱澤斯勞滕大學(xué)計(jì)算機(jī)科學(xué)系,D-67653凱澤斯勞滕，德國(guó)摘要：我們表明，函數(shù)/eLp([O,lp)，其中i<p<?,積分族j0f(t)dt(x=(、,...,七)e[0,1]d)可以用一個(gè)隨機(jī)算法近似一致xe[0,1]d以相同的速率nT+1/min(P2)作為最優(yōu)率一個(gè)積分，其中n是樣本的數(shù)量.提出了兩算法，一個(gè)是最佳的順序，另一個(gè)對(duì)數(shù)因素.我們也證明下限和討論的依賴(lài)在尺寸誤差估計(jì)中的常數(shù).1、介紹眾所周知，最優(yōu)隨機(jī)算法為一體的Lp([°，1》)功能與樣品有錯(cuò)誤率nT+1/min(p，2)[14,4].在本文中，我們表明，同樣的速度得到所有積分的同時(shí)計(jì)算jf(t)dt均勻xe[0,1]d，因此，我們要近似的不定積分，反導(dǎo)數(shù)。雖然許多論文研究的復(fù)雜性，定積分，不確定積分的情況下至今未被考慮.我們提出并分析了兩種算法，并證明下限。第一個(gè)算法是簡(jiǎn)單的采樣算法-標(biāo)準(zhǔn)蒙特卡洛方法的函數(shù)值版本。第二個(gè)是一個(gè)組合的同時(shí)蒙特卡洛抽樣Smolyak算法。這兩種算法需要O(n)的函數(shù)值，并產(chǎn)生一個(gè)近似，這是一個(gè)線性組合的O(n)功能.一是優(yōu)化為1WPW8，此外，在常數(shù)誤差估計(jì)的尺寸取決于多項(xiàng)式。因此，它證明了多項(xiàng)式溫順的隨機(jī)設(shè)置中的問(wèn)題。這是值得注意的由于到目前為止，只有極少數(shù)的加權(quán)問(wèn)題(即，所有尺寸扮演同樣的角色)是巳知的共享多項(xiàng)式可追蹤性(見(jiàn)，例如，評(píng)論在第39頁(yè)的頂部[17]).第二算法2VPW8是最佳的順序，而1WPW2額外的對(duì)數(shù)因素的發(fā)生。第二種算法，但是，具有的優(yōu)點(diǎn)，一旦近似建立了任何價(jià)值，它可以在O(n)操作計(jì)算2VPW8和O((logn)D-1)1WPW2,而在第一種算法需要。案例(n).簡(jiǎn)單隨機(jī)抽算法，另一方面，可以更有效的D固定(和小)，見(jiàn)第6.2節(jié)。不過(guò)，2<PW8的Smolyak-蒙特卡洛算法具有更好的效率估計(jì)，看第6.2節(jié)結(jié)束時(shí)的討論.我們還提出了一個(gè)尖銳的N和尺寸獨(dú)立下限。此外，對(duì)于P>1,我們證明下限，表明固定的固定〉0的最小數(shù)量的依賴(lài)一個(gè)對(duì)尺寸誤差We樣本是線性算法讓我們注意，確定性算法的速度0(1)所有的P1PWW8，因沒(méi)有收斂到零，見(jiàn)第6.1節(jié).為了比較，最佳的隨機(jī)率算法，是n-1+1/min(p，2)，所以它是N-1/2,2WPW8,但在間隔1VPV2的指數(shù)隨著P接近1.最后，對(duì)于P=1的隨機(jī)算法的收斂速度是(1).以及。本文的組織方式如下：第2節(jié)包含符號(hào)和預(yù)賽，簡(jiǎn)單的采樣算法的描述和3部分的分析，-Smolyak蒙特卡洛第4節(jié)算法.下限是在第5節(jié)，并在第6節(jié)我們?cè)u(píng)論確定性設(shè)置，提出了一種有效的方法計(jì)算點(diǎn)評(píng)估的簡(jiǎn)單采樣算法，并討論了可測(cè)性問(wèn)題.2、符號(hào)和預(yù)備知識(shí)我們寫(xiě)n=(1,2,...｝和N0=｛0，1,2，。..｝。對(duì)數(shù)log總是意味著為log2。所有在本文中考慮的功能和巴拿赫空間被假定為定義在同一領(lǐng)域標(biāo)量ke(，｝。一個(gè)巴拿赫空間X是指單位球通過(guò)Bx和X*對(duì)偶空間。鑒于巴拿赫空間x，y，從x到y(tǒng)的所有有界線性算子的空間用L(x，y)表示，如果x=y，由L(x).讓D^N，Q=〔0，1〕DC(Q)，表示Q函數(shù)空間連續(xù)和在線雜志，對(duì)于1WpW8，好讓空間Lp(Q)(等價(jià)類(lèi)可積)p與功率的影響勒貝格測(cè)度函數(shù)，都配備了他們通常的標(biāo)準(zhǔn).讓f(Q)的線性表示在函數(shù)空間的在線Q好讓B0(Q)的Lebesgue可測(cè)空間的有界函數(shù)(不等價(jià)類(lèi)和最大模Q)在線.當(dāng)1<pV8，我們研究S(d)M十(Q),C(Q))得到(S(d)f)(x)=』[0^f(t)dt,(x=(x1xd)eQ)，在[0，X]=[X]，[0,X1]X-?-X[0,Xd].注意□S(d)：L(Q)—C(Q)□=1(問(wèn)題是規(guī)范化的).在整個(gè)文件中的符號(hào)C，C0，C1,...表示正常數(shù)，它們是絕對(duì)值或者只能依賴(lài)P和P1.常量，也可能取決于d表示由C(d),C0(d)等相同的符號(hào)可以表示不同的常量(當(dāng)它們出現(xiàn)在一系列關(guān)系中).3、簡(jiǎn)單采樣算法我們有(S(d)f)(x)=j[oi]dx(t)f(t)dt.我們介紹了簡(jiǎn)單的采樣算法如下：設(shè)NeN讓《1)我=1是獨(dú)立的，均勻地分布在q=[0,1]隨機(jī)變量對(duì)一些概率空間(Q,￡,P)。我假設(shè)不失一般性，(Q,￡,P)是完整的，即DcD1eZ和P(D1=0意味著De￡(如果(Q,￡,P)是不完整的，我們將它由其完成)。然后我們近似對(duì)于FeLP(Q)S(d)fWA1fn由A1f給出的n(A1f)=-Yx(&)f(如(xeQ).nn[0,x]ii=1i我們有A1f=-Yf(&)xnni=1i[&，i]這里(S⑷f(wàn))(x)=j[01]f(t)x_(x)dt(xe[0,1]d),該算法可以被視為一個(gè)功能值版本的標(biāo)準(zhǔn)蒙特卡洛方法整合。讓我們提到，簡(jiǎn)單的采樣算法產(chǎn)生不連續(xù)的X函數(shù)，所以我們認(rèn)為它是映射到B0(Q)和一個(gè)近似的(D)：LP(Q)—B0(Q),其中我們確定了C(Q)與子空間B0的典型方式(Q).此外，值得注意的是，&缺乏一定的可測(cè)性屬性，詳情見(jiàn)5n和6.3節(jié)的開(kāi)始.然而，映射o』S(d)f-氣f&)是￡可測(cè)的，我們?cè)谀抢?^…、，一、Ai,f=才x(g(①))x(①e。)nO氣=1[0,x],?號(hào)o),-]強(qiáng)調(diào)3eQ的依賴(lài).事實(shí)上，這如IE「町一&JI屬⑵=馴P|(5吁)住)一風(fēng)J)W|皿日念)(q有理數(shù))，其中，反過(guò)來(lái)，是一個(gè)簡(jiǎn)單的結(jié)果(4).因此，它是有意義的考慮P1圣矩:珂5唧-曲喂如適合1WP1V8，如我們下面.我們還引入了輕微的修改，該算法，其中有C([0,1]d)和具有所需的測(cè)量性能.為此，我們引入IeN的功能的中⑴eC([0,1]d)1ift<Xk?r)=,l一敏一母ifx<t<x+y0ifx—-<f.、、矛M([0,1嚴(yán)八…工定義’?設(shè)置為x=(X1)，。..和T=(t1)，。..，td)的％r)=n時(shí)”(M)-j=iTOC\o"1-5"\h\z現(xiàn)在我們把..A混=S評(píng)*制慚.讓我們先考慮計(jì)算的成本A1f和A2f.他們每個(gè)人都需要DN獨(dú)立均勻分布在[0，1]隨機(jī)變量和nnn個(gè)函數(shù)值，以確定各自代表(3)及(7)。接下來(lái)我們來(lái)看看計(jì)算A1f(x)和A2f(x)對(duì)于任何給定nn

的x￡Q.由于所涉及的功能的支持可以以任意方式重疊，我們需要CDN計(jì)算(3)中的術(shù)語(yǔ)，以及類(lèi)似的((7)).更有效的固定方法(小)D在第6.2節(jié)中討論.現(xiàn)在我們傳給錯(cuò)誤分析。MU讓「MQ=[0,1]d等距網(wǎng)格網(wǎng)格尺寸1/我們需要以下(包圍)引理.引理3.1讓1VPW8,MEN,FELP(Q)與FN0。讓g0>0和承擔(dān)甲[0,1]2d-R是滿(mǎn)足以下功能:可為每個(gè)XE[0,1]D存在Y,ZE「具有||0,z||-110,711<￡0.xDojitO<竹3,0<m*)￡[0,1]d).那么下面是p-幾乎肯定:那么下面是p-幾乎肯定:其中P給出1/p+1/p*=1.證明.我們假設(shè)f(S我)，1W我Wn,定義，這是個(gè)案，p-幾乎肯定。XEQ選擇Y,ZE「M滿(mǎn)足(8)-(10).然后f/(Odt湖朝<[f(Odf+I'/(c)dr--加.同⑸?J舊聞n]=iJ[^]\[Q,y]J[O.y]"i=i同樣「/(r)dr+-^""(掃</f(c)dr-f+10x1ni=iAo^lMO.yiJ[仇e|ni=i因此f1n!fM)df一一1貴"*&)/(&)[0=<|祖臺(tái)1口</十max加)山一二、部凹蒞沛?zhèn)?…</十max"I=14、thesmolyak-monte蒙特卡羅算法首先介紹Smolyak算法在形式為我們以后的需要的Smolyak算法現(xiàn)在是處理高維問(wèn)題的標(biāo)準(zhǔn)技術(shù)，特別是那些張量積形式.該算法的基本思想是在一定條件下的精細(xì)逼近平衡粗糙近似的維數(shù).進(jìn)一步的背景我們指[17,18]，參考文獻(xiàn)。每米EN與MN2讓(%ulSoU玄11))是一個(gè)形式的算子序列

nmPm,[f=（跖拓i=1XM，我，我u[0,1]和甲M,L,我uc([0,1]),VML，I#0(I=1,。..，NmL，LEN0)O，，我們認(rèn)為點(diǎn)｛XM,l,i=1,...,Nm,l｝兩兩不同，有序地增長(zhǎng)此外，我們定義了XM,1,0=0和XM,L,nm,L+1=1.我們假設(shè)如下：有常數(shù)C1-4>0，所有我UN與M2和N我UN0nm,j<max(xm^i-<C2m-r1導(dǎo)士血」+1||品』2皿舊.i]注<烏sup町一P愈fll匚

心心oji)這里W1P([0,1])代表在LP([0,1])的第一個(gè)衍生物的所有功能的空間，在分配意義上，也屬于LP([0([0,1]),賦予規(guī)范()通常修改為P=8).具有這些屬性的運(yùn)算符很容易構(gòu)造。例如，給定m,我們讓PM,L是分段線性插值算法，應(yīng)用于[0]細(xì)分，1ML長(zhǎng)度相等的子區(qū)間.對(duì)于這一選擇，它是眾所周知的(18)-(21)舉行.我們解決任何我UN,MN2。在續(xù)集M將是一個(gè)算法參數(shù)，并為方便表示我們放棄下標(biāo)m寫(xiě)PL,NL,XL,我甲L,I.用于隨后的分析的情況下，D〉1和Smolyak算法的定義我們使用張量積的算法。這種方法通常適用于的情況下，兩者源和目標(biāo)空間是希爾伯特空間。這里我們研究了巴拿赫空間的情況，源程序空間Lp(Q)(1WPW8)，目標(biāo)空間C(Q)。為此，我們使用巴拿赫空間張量規(guī)范，如最近在[20].巴拿赫空間中S(d)的張量積結(jié)構(gòu)比希爾伯特更微妙案例.特別是，我們必須考慮適當(dāng)?shù)膹埩恳?guī)范與空間C([0,1])和LP([0,1]D)對(duì)相應(yīng)空間的張量積的d維的立方體單位間隔.而且，這些張量乘積應(yīng)具有張量范數(shù)的性質(zhì)產(chǎn)品