不定积分的随机复杂性

不定积分的随机复杂性斯特凡•海因里希，伯恩哈德•米拉凯泽斯劳滕大学计算机科学系,D-67653凯泽斯劳滕，德国摘要：我们表明，函数/eLp([O,lp)，其中i<p<«,积分族j0f(t)dt(x=(、,...,七)e[0,1]d)可以用一个随机算法近似一致xe[0,1]d以相同的速率nT+1/min(P2)作为最优率一个积分，其中n是样本的数量.提出了两算法，一个是最佳的顺序，另一个对数因素.我们也证明下限和讨论的依赖在尺寸误差估计中的常数.1、介绍众所周知，最优随机算法为一体的Lp([°，1》)功能与样品有错误率nT+1/min(p，2)[14,4].在本文中，我们表明，同样的速度得到所有积分的同时计算jf(t)dt均匀xe[0,1]d，因此，我们要近似的不定积分，反导数。虽然许多论文研究的复杂性，定积分，不确定积分的情况下至今未被考虑.我们提出并分析了两种算法，并证明下限。第一个算法是简单的采样算法-标准蒙特卡洛方法的函数值版本。第二个是一个组合的同时蒙特卡洛抽样Smolyak算法。这两种算法需要O(n)的函数值，并产生一个近似，这是一个线性组合的O(n)功能.一是优化为1WPW8，此外，在常数误差估计的尺寸取决于多项式。因此，它证明了多项式温顺的随机设置中的问题。这是值得注意的由于到目前为止，只有极少数的加权问题(即，所有尺寸扮演同样的角色)是巳知的共享多项式可追踪性(见，例如，评论在第39页的顶部[17]).第二算法2VPW8是最佳的顺序，而1WPW2额外的对数因素的发生。第二种算法，但是，具有的优点，一旦近似建立了任何价值，它可以在O(n)操作计算2VPW8和O((logn)D-1)1WPW2,而在第一种算法需要。案例(n).简单随机抽算法，另一方面，可以更有效的D固定(和小)，见第6.2节。不过，2<PW8的Smolyak-蒙特卡洛算法具有更好的效率估计，看第6.2节结束时的讨论.我们还提出了一个尖锐的N和尺寸独立下限。此外，对于P>1,我们证明下限，表明固定的固定〉0的最小数量的依赖一个对尺寸误差We样本是线性算法让我们注意，确定性算法的速度0(1)所有的P1PWW8，因没有收敛到零，见第6.1节.为了比较，最佳的随机率算法，是n-1+1/min(p，2)，所以它是N-1/2,2WPW8,但在间隔1VPV2的指数随着P接近1.最后，对于P=1的随机算法的收敛速度是(1).以及。本文的组织方式如下：第2节包含符号和预赛，简单的采样算法的描述和3部分的分析，-Smolyak蒙特卡洛第4节算法.下限是在第5节，并在第6节我们评论确定性设置，提出了一种有效的方法计算点评估的简单采样算法，并讨论了可测性问题.2、符号和预备知识我们写n=(1,2,...｝和N0=｛0，1,2，。..｝。对数log总是意味着为log2。所有在本文中考虑的功能和巴拿赫空间被假定为定义在同一领域标量ke(，｝。一个巴拿赫空间X是指单位球通过Bx和X*对偶空间。鉴于巴拿赫空间x，y，从x到y的所有有界线性算子的空间用L(x，y)表示，如果x=y，由L(x).让D^N，Q=〔0，1〕DC(Q)，表示Q函数空间连续和在线杂志，对于1WpW8，好让空间Lp(Q)(等价类可积)p与功率的影响勒贝格测度函数，都配备了他们通常的标准.让f(Q)的线性表示在函数空间的在线Q好让B0(Q)的Lebesgue可测空间的有界函数(不等价类和最大模Q)在线.当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(问题是规范化的).在整个文件中的符号C，C0，C1,...表示正常数，它们是绝对值或者只能依赖P和P1.常量，也可能取决于d表示由C(d),C0(d)等相同的符号可以表示不同的常量(当它们出现在一系列关系中).3、简单采样算法我们有(S(d)f)(x)=j[oi]dx(t)f(t)dt.我们介绍了简单的采样算法如下：设NeN让《1)我=1是独立的，均匀地分布在q=[0,1]随机变量对一些概率空间(Q,£,P)。我假设不失一般性，(Q,£,P)是完整的，即DcD1eZ和P(D1=0意味着De£(如果(Q,£,P)是不完整的，我们将它由其完成)。然后我们近似对于FeLP(Q)S(d)fWA1fn由A1f给出的n(A1f)=-Yx(&)f(如(xeQ).nn[0,x]ii=1i我们有A1f=-Yf(&)xnni=1i[&，i]这里(S⑷f)(x)=j[01]f(t)x_(x)dt(xe[0,1]d),该算法可以被视为一个功能值版本的标准蒙特卡洛方法整合。让我们提到，简单的采样算法产生不连续的X函数，所以我们认为它是映射到B0(Q)和一个近似的(D)：LP(Q)—B0(Q),其中我们确定了C(Q)与子空间B0的典型方式(Q).此外，值得注意的是，&缺乏一定的可测性属性，详情见5n和6.3节的开始.然而，映射o』S(d)f-气f&)是£可测的，我们在那里1^…、，一、Ai,f=才x(g(①))x(①e。)nO气=1[0,x],•号o),-]强调3eQ的依赖.事实上，这如IE「町一&JI属⑵=驯P|(5吁)住)一风J)W|皿日念)(q有理数)，其中，反过来，是一个简单的结果(4).因此，它是有意义的考虑P1圣矩:珂5唧-曲喂如适合1WP1V8，如我们下面.我们还引入了轻微的修改，该算法，其中有C([0,1]d)和具有所需的测量性能.为此，我们引入IeN的功能的中⑴eC([0,1]d)1ift<Xk«r)=,l一敏一母ifx<t<x+y0ifx—-<f.、、矛M([0,1严八…工定义’•设置为x=(X1)，。..和T=(t1)，。..，td)的％r)=n时”(M)-j=iTOC\o"1-5"\h\z现在我们把..A混=S评*制惭.让我们先考虑计算的成本A1f和A2f.他们每个人都需要DN独立均匀分布在[0，1]随机变量和nnn个函数值，以确定各自代表(3)及(7)。接下来我们来看看计算A1f(x)和A2f(x)对于任何给定nn

的x£Q.由于所涉及的功能的支持可以以任意方式重叠，我们需要CDN计算(3)中的术语，以及类似的((7)).更有效的固定方法(小)D在第6.2节中讨论.现在我们传给错误分析。MU让「MQ=[0,1]d等距网格网格尺寸1/我们需要以下(包围)引理.引理3.1让1VPW8,MEN,FELP(Q)与FN0。让g0>0和承担甲[0,1]2d-R是满足以下功能:可为每个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.证明.我们假设f(S我)，1W我Wn,定义，这是个案，p-几乎肯定。XEQ选择Y,ZE「M满足(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=<|祖台1口</十max加)山一二、部凹莅沛传)…</十max"I=14、thesmolyak-monte蒙特卡罗算法首先介绍Smolyak算法在形式为我们以后的需要的Smolyak算法现在是处理高维问题的标准技术，特别是那些张量积形式.该算法的基本思想是在一定条件下的精细逼近平衡粗糙近似的维数.进一步的背景我们指[17,18]，参考文献。每米EN与MN2让(%ulSoU玄11))是一个形式的算子序列

nmPm,[f=（跖拓i=1XM，我，我u[0,1]和甲M,L,我uc([0,1]),VML，I#0(I=1,。..，NmL，LEN0)O，，我们认为点｛XM,l,i=1,...,Nm,l｝两两不同，有序地增长此外，我们定义了XM,1,0=0和XM,L,nm,L+1=1.我们假设如下：有常数C1-4>0，所有我UN与M2和N我UN0nm,j<max(xm^i-<C2m-r1导士血」+1||品』2皿旧.i]注<乌sup町一P愈fll匚

心心oji)这里W1P([0,1])代表在LP([0,1])的第一个衍生物的所有功能的空间，在分配意义上，也属于LP([0([0,1]),赋予规范()通常修改为P=8).具有这些属性的运算符很容易构造。例如，给定m,我们让PM,L是分段线性插值算法，应用于[0]细分，1ML长度相等的子区间.对于这一选择，它是众所周知的(18)-(21)举行.我们解决任何我UN,MN2。在续集M将是一个算法参数，并为方便表示我们放弃下标m写PL,NL,XL,我甲L,I.用于随后的分析的情况下，D〉1和Smolyak算法的定义我们使用张量积的算法。这种方法通常适用于的情况下，两者源和目标空间是希尔伯特空间。这里我们研究了巴拿赫空间的情况，源程序空间Lp(Q)(1WPW8)，目标空间C(Q)。为此，我们使用巴拿赫空间张量规范，如最近在[20].巴拿赫空间中S(d)的张量积结构比希尔伯特更微妙案例.特别是，我们必须考虑适当的张量规范与空间C([0,1])和LP([0,1]D)对相应空间的张量积的d维的立方体单位间隔.而且，这些张量乘积应具有张量范数的性质产品