不定积分的随机复杂性

1、不定积分的随机复杂性斯特凡·海因里希，伯恩哈德·米拉凯泽斯劳滕大学计算机科学系,D-67653凯泽斯劳滕,德国摘要：我们表明,函数,其中1p, 积分族 可以用一个随机算法近似一致 x以相同的速率 作为最优率一个积分,其中n是样本的数量. 提出了两算法，一个是最佳的顺序，另一个对数因素.我们也证明下限和讨论的依赖在尺寸误差估计中的常数. 1、 介绍众所周知,最优随机算法为一体的功能与样品有错误率14,4. 在本文中,我们表明,同样的速度得到所有积分的同时计算均匀x,因此，我们要近似的不定积分，反导数。虽然许多论文研究的复杂性，定积分，不确定积分的情况下至今未被考虑. 我们提出

2、并分析了两种算法，并证明下限。第一个算法是简单的采样算法-标准蒙特卡洛方法的函数值版本。第二个是一个组合的同时蒙特卡洛抽样Smolyak算法。这两种算法需要O(n)的函数值，并产生一个近似，这是一个线性组合的O(n)功能. 一是优化为1P，此外，在常数误差估计的尺寸取决于多项式。因此，它证明了多项式温顺的随机设置中的问题。这是值得注意的由于到目前为止，只有极少数的加权问题（即，所有尺寸扮演同样的角色）是已知的共享多项式可追踪性（见，例如，评论在第39页的顶部17）. 第二算法2P是最佳的顺序，而1P2额外的对数因素的发生。第二种算法，但是，具有的优点，一旦近似建立了任何价值，它可以在O(n)操

3、作计算2P和O（log n）D1）1P2，而在第一种算法需要案例（n）. 简单随机抽算法，另一方面，可以更有效的D固定（和小），见第6.2节。不过，2P的Smolyak蒙特卡洛算法具有更好的效率估计，看第6.2节结束时的讨论. 我们还提出了一个尖锐的N和尺寸独立下限。此外，对于P > 1，我们证明下限，表明固定的固定> 0的最小数量的依赖一个对尺寸误差样本是线性算法让我们注意，确定性算法的速度（1）所有的P 1 P，因没有收敛到零，见第6.1节. 为了比较，最佳的随机率算法，是，所以它是N1 / 2，2P，但在间隔1P2的指数随着P接近1. 最后，对于P = 1的随机算法的收敛速度

4、是（1）. 以及本文的组织方式如下：第2节包含符号和预赛，简单的采样算法的描述和3部分的分析，Smolyak蒙特卡洛第4节算法. 下限是在第5节，并在第6节我们评论确定性设置，提出了一种有效的方法计算点评估的简单采样算法，并讨论了可测性问题. 2、 符号和预备知识我们写n = 1，2, 和= 0，1，2，。. 。对数log总是意味着为log2。所有在本文中考虑的功能和巴拿赫空间被假定为定义在同一领域标量k，。一个巴拿赫空间X是指单位球通过 和X对偶空间。鉴于巴拿赫空间x，y，从x到y的所有有界线性算子的空间用L（x，y）表示，如果x = y，由L（x）. 让DN，Q0，1D C（Q），表示 Q

5、函数空间连续和在线杂志，对于1p，好让空间Lp（Q）（等价类可积）p与功率的影响勒贝格测度函数，都配备了他们通常的标准. 让f（Q）的线性表示在函数空间的在线Q好让（Q） 的Lebesgue可测空间的有界函数（不等价类和最大模Q）在线. 当，我们研究 得到 （x=(x1，xd)Q），在0,X = X ，0,X1×···×0,Xd. 注意（问题是规范化的）. 在整个文件中的符号C，C0，C1，表示正常数，它们是绝对值或者只能依赖P和P1. 常量，也可能取决于d表示由C（d），C0（d）等相同的符号可以表示不同的常量（当它们出现在一系列关系中）.

6、3、 简单采样算法我们有.我们介绍了简单的采样算法如下：设NN让（I）我= 1是独立的，均匀地分布在q = 0，1 随机变量对一些概率空间（，P）。我假设不失一般性，（，P）是完整的，即DD1和P（D1= 0意味着D（如果（，P）是不完整的，我们将它由其完成）。然后我们近似对于FLP（Q），由给出的 （xQ）. 我们有,这里=. 有 ，该算法可以被视为一个功能值版本的标准蒙特卡洛方法整合。让我们提到，简单的采样算法产生不连续的X函数，所以我们认为它是映射到B0（Q）和一个近似的（D）：LP（Q）B0（Q），其中我们确定了C（Q）与子空间B0的典型方式（Q）. 此外，值得注意的是，缺乏一定的可测

7、性属性，详情见5和6.3节的开始. 然而，映射是可测的，我们在那里=强调的依赖. 事实上，这如（q有理数），其中，反过来，是一个简单的结果（4）. 因此，它是有意义的考虑P1圣矩适合1P1，如我们下面. 我们还引入了轻微的修改，该算法，其中有C()和具有所需的测量性能. 为此，我们引入IN 的功能的 C()定义设置为x =（X1），。.和T =（t1），。.，td）现在我们把让我们先考虑计算的成本和.他们每个人都需要DN独立均匀分布在 0，1 随机变量和n个函数值，以确定各自代表（3）及（7）。接下来我们来看看计算（x）和（x）对于任何给定的xQ. 由于所涉及的功能的支持可以以任意方式重叠，我

8、们需要CDN计算（3）中的术语，以及类似的（7）. 更有效的固定方法（小）D在第6.2节中讨论. 现在我们传给错误分析。M让M Q = 0，1 d等距网格网格尺寸1 /我们需要以下（包围）引理. 引理3.1 让1P，MN，FLP（Q）与F0。让00和承担 0，1 2dR是满足以下功能：可为每个X 0，1 D存在Y，Z具有那么下面是p-几乎肯定：其中P给出1/p+1/p*=1. 证明. 我们假设f（我），1我n，定义，这是个案，p-几乎肯定。XQ选择Y，ZM满足（8）-（10）. 然后同样因此4、 the smolyakmonte蒙特卡罗算法首先介绍Smolyak算法在形式为我们以后的需要的Sm

9、olyak算法现在是处理高维问题的标准技术，特别是那些张量积形式. 该算法的基本思想是在一定条件下的精细逼近平衡粗糙近似的维数. 进一步的背景我们指17,18，参考文献。每米N与M2让是一个形式的算子序列XM，我，我 0，1 和M，L，我C（ 0，1 ），M，L，I 0（I = 1，。.，Nm，L，LN0）。我们认为点 XM，l，i = 1，.，NM，L两两不同，有序地增长此外，我们定义了XM，l，0 = 0和XM，L，nm，L + 1 = 1. 我们假设如下：有常数C14 > 0，所有我N与M 2和我N0这里W1P（ 0，1 ）代表在LP（ 0，1 ）的第一个衍生物的所有功能的空间，在

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