在做数值积分的时候，拟蒙特卡罗方法 的收敛速度是不是一定比 蒙特卡罗方法 快？

orionsnow

在做数值积分的时候，拟蒙特卡罗方法 的收敛速度是不是一定比 蒙特卡罗方法 快？

今天我们在讨论这问题，老板认为虽然收敛速度上拟蒙特卡罗方法快，但是在高维的时候，可能不稳定。
即随着重复点数的增多，拟蒙特卡罗方法的结果是跳跃着下降的

详细可以看这里的图

http://en.wikipedia.org/wiki/Low-discrepancy_sequence

当点数为 100，1000，10000 的时候拟蒙特卡罗方法所用的点分布为最优，

当点数为 101，1001，10001 的时候分布为最差，在这里，误差不向下，反而向上跳。 甚至有可能超过 101，1001，10001 点的蒙特卡罗方法

但是我认为， 只要避开这些点跳跃着增加点数，完全可以避开这些问题。

nancy_w

拟蒙特卡罗方法的结果是跳跃着下降的

拿QMC和MC对比，N为点数。
MC的结果更是“跳跃着下降的”，对吧？不可能一路单调下降的。如果论单次运行不稳定的程度，MC更甚于QMC。但讨论数值积分的收敛性能的时候，都是拿asymptotic behaviour 来说话的，比较在特定N的表现没有意义。

数值积分的误差的上限跟点分布的均匀度成反比 （Koksma–Hlawka inequality）。确实有些low discrepancy sequence 在高维的情况下均匀度变差。但也有些另一些，比如 niedereiter sequence 或者sobol sequence 的表现就很好。至少在我应用过的20维的情况下依然远好过MC。

orionsnow

nancy_w 发表于 2013-4-13 19:26
拿QMC和MC对比，N为点数。
MC的结果更是“跳跃着下降的”，对吧？不可能一路单调下降的。如果论单次运 ...

hi, 我现在在家，

我老板周五给了我一个他看的参考文献，是一个计算 圆周率的例子。

等周一我把文章看完，就贴上来。

另外我觉得他应该不是在说单次运行的不稳定性。

N 为点数，我认为也可以理解为运行次数吧。

orionsnow

地址在这里，是德语的，不过公式很多，看懂应该没有问题

他说的那个问题在66和67页
http://pauli.uni-muenster.de/~le ... mann_vortragqmc.pdf