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

1、不定積分的隨機(jī)復(fù)雜性斯特凡·海因里希，伯恩哈德·米拉凱澤斯勞滕大學(xué)計(jì)算機(jī)科學(xué)系,D-67653凱澤斯勞滕,德國(guó)摘要：我們表明,函數(shù),其中1p, 積分族 可以用一個(gè)隨機(jī)算法近似一致 x以相同的速率 作為最優(yōu)率一個(gè)積分,其中n是樣本的數(shù)量. 提出了兩算法，一個(gè)是最佳的順序，另一個(gè)對(duì)數(shù)因素.我們也證明下限和討論的依賴在尺寸誤差估計(jì)中的常數(shù). 1、 介紹眾所周知,最優(yōu)隨機(jī)算法為一體的功能與樣品有錯(cuò)誤率14,4. 在本文中,我們表明,同樣的速度得到所有積分的同時(shí)計(jì)算均勻x,因此，我們要近似的不定積分，反導(dǎo)數(shù)。雖然許多論文研究的復(fù)雜性，定積分，不確定積分的情況下至今未被考慮. 我們提出

2、并分析了兩種算法，并證明下限。第一個(gè)算法是簡(jiǎn)單的采樣算法-標(biāo)準(zhǔn)蒙特卡洛方法的函數(shù)值版本。第二個(gè)是一個(gè)組合的同時(shí)蒙特卡洛抽樣Smolyak算法。這兩種算法需要O(n)的函數(shù)值，并產(chǎn)生一個(gè)近似，這是一個(gè)線性組合的O(n)功能. 一是優(yōu)化為1P，此外，在常數(shù)誤差估計(jì)的尺寸取決于多項(xiàng)式。因此，它證明了多項(xiàng)式溫順的隨機(jī)設(shè)置中的問題。這是值得注意的由于到目前為止，只有極少數(shù)的加權(quán)問題（即，所有尺寸扮演同樣的角色）是已知的共享多項(xiàng)式可追蹤性（見，例如，評(píng)論在第39頁(yè)的頂部17）. 第二算法2P是最佳的順序，而1P2額外的對(duì)數(shù)因素的發(fā)生。第二種算法，但是，具有的優(yōu)點(diǎn)，一旦近似建立了任何價(jià)值，它可以在O(n)操

3、作計(jì)算2P和O（log n）D1）1P2，而在第一種算法需要案例（n）. 簡(jiǎn)單隨機(jī)抽算法，另一方面，可以更有效的D固定（和?。?，見第6.2節(jié)。不過，2P的Smolyak蒙特卡洛算法具有更好的效率估計(jì)，看第6.2節(jié)結(jié)束時(shí)的討論. 我們還提出了一個(gè)尖銳的N和尺寸獨(dú)立下限。此外，對(duì)于P > 1，我們證明下限，表明固定的固定> 0的最小數(shù)量的依賴一個(gè)對(duì)尺寸誤差樣本是線性算法讓我們注意，確定性算法的速度（1）所有的P 1 P，因沒有收斂到零，見第6.1節(jié). 為了比較，最佳的隨機(jī)率算法，是，所以它是N1 / 2，2P，但在間隔1P2的指數(shù)隨著P接近1. 最后，對(duì)于P = 1的隨機(jī)算法的收斂速度

4、是（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è)性問題. 2、 符號(hào)和預(yù)備知識(shí)我們寫n = 1，2, 和= 0，1，2，。. 。對(duì)數(shù)log總是意味著為log2。所有在本文中考慮的功能和巴拿赫空間被假定為定義在同一領(lǐng)域標(biāo)量k，。一個(gè)巴拿赫空間X是指單位球通過 和X對(duì)偶空間。鑒于巴拿赫空間x，y，從x到y(tǒng)的所有有界線性算子的空間用L（x，y）表示，如果x = y，由L（x）. 讓DN，Q0，1D C（Q），表示 Q

5、函數(shù)空間連續(xù)和在線雜志，對(duì)于1p，好讓空間Lp（Q）（等價(jià)類可積）p與功率的影響勒貝格測(cè)度函數(shù)，都配備了他們通常的標(biāo)準(zhǔn). 讓f（Q）的線性表示在函數(shù)空間的在線Q好讓（Q） 的Lebesgue可測(cè)空間的有界函數(shù)（不等價(jià)類和最大模Q）在線. 當(dāng)，我們研究 得到 （x=(x1，xd)Q），在0,X = X ，0,X1×···×0,Xd. 注意（問題是規(guī)范化的）. 在整個(gè)文件中的符號(hào)C，C0，C1，表示正常數(shù)，它們是絕對(duì)值或者只能依賴P和P1. 常量，也可能取決于d表示由C（d），C0（d）等相同的符號(hào)可以表示不同的常量（當(dāng)它們出現(xiàn)在一系列關(guān)系中）.

6、3、 簡(jiǎn)單采樣算法我們有.我們介紹了簡(jiǎn)單的采樣算法如下：設(shè)NN讓（I）我= 1是獨(dú)立的，均勻地分布在q = 0，1 隨機(jī)變量對(duì)一些概率空間（，P）。我假設(shè)不失一般性，（，P）是完整的，即DD1和P（D1= 0意味著D（如果（，P）是不完整的，我們將它由其完成）。然后我們近似對(duì)于FLP（Q），由給出的 （xQ）. 我們有,這里=. 有 ，該算法可以被視為一個(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è)

7、性屬性，詳情見5和6.3節(jié)的開始. 然而，映射是可測(cè)的，我們?cè)谀抢?強(qiáng)調(diào)的依賴. 事實(shí)上，這如（q有理數(shù)），其中，反過來，是一個(gè)簡(jiǎn)單的結(jié)果（4）. 因此，它是有意義的考慮P1圣矩適合1P1，如我們下面. 我們還引入了輕微的修改，該算法，其中有C()和具有所需的測(cè)量性能. 為此，我們引入IN 的功能的 C()定義設(shè)置為x =（X1），。.和T =（t1），。.，td）現(xiàn)在我們把讓我們先考慮計(jì)算的成本和.他們每個(gè)人都需要DN獨(dú)立均勻分布在 0，1 隨機(jī)變量和n個(gè)函數(shù)值，以確定各自代表（3）及（7）。接下來我們來看看計(jì)算（x）和（x）對(duì)于任何給定的xQ. 由于所涉及的功能的支持可以以任意方式重疊，我

8、們需要CDN計(jì)算（3）中的術(shù)語，以及類似的（7）. 更有效的固定方法（?。〥在第6.2節(jié)中討論. 現(xiàn)在我們傳給錯(cuò)誤分析。M讓M Q = 0，1 d等距網(wǎng)格網(wǎng)格尺寸1 /我們需要以下（包圍）引理. 引理3.1 讓1P，MN，F(xiàn)LP（Q）與F0。讓00和承擔(dān) 0，1 2dR是滿足以下功能：可為每個(gè)X 0，1 D存在Y，Z具有那么下面是p-幾乎肯定：其中P給出1/p+1/p*=1. 證明. 我們假設(shè)f（我），1我n，定義，這是個(gè)案，p-幾乎肯定。XQ選擇Y，ZM滿足（8）-（10）. 然后同樣因此4、 the smolyakmonte蒙特卡羅算法首先介紹Smolyak算法在形式為我們以后的需要的Sm

9、olyak算法現(xiàn)在是處理高維問題的標(biāo)準(zhǔn)技術(shù)，特別是那些張量積形式. 該算法的基本思想是在一定條件下的精細(xì)逼近平衡粗糙近似的維數(shù). 進(jìn)一步的背景我們指17,18，參考文獻(xiàn)。每米N與M2讓是一個(gè)形式的算子序列XM，我，我 0，1 和M，L，我C（ 0，1 ），M，L，I 0（I = 1，。.，Nm，L，LN0）。我們認(rèn)為點(diǎn) XM，l，i = 1，.，NM，L兩兩不同，有序地增長(zhǎng)此外，我們定義了XM，l，0 = 0和XM，L，nm，L + 1 = 1. 我們假設(shè)如下：有常數(shù)C14 > 0，所有我N與M 2和我N0這里W1P（ 0，1 ）代表在LP（ 0，1 ）的第一個(gè)衍生物的所有功能的空間，在

10、分配意義上，也屬于LP（ 0，1 ），賦予規(guī)范（）通常修改為P=）. 具有這些屬性的運(yùn)算符很容易構(gòu)造。例如，給定m，我們讓PM，L是分段線性插值算法，應(yīng)用于 0 細(xì)分，1 ML長(zhǎng)度相等的子區(qū)間. 對(duì)于這一選擇，它是眾所周知的（18）-（21）舉行. 我們解決任何我N，M2。在續(xù)集M將是一個(gè)算法參數(shù)，并為方便表示我們放棄下標(biāo)m寫PL，NL，XL，我L，I. 用于隨后的分析的情況下，D1和Smolyak算法的定義我們使用張量積的算法。這種方法通常適用于的情況下，兩者源和目標(biāo)空間是希爾伯特空間。這里我們研究了巴拿赫空間的情況，源程序空間Lp（Q）（1P），目標(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維的立