查看“︁拟蒙特卡罗方法”︁的源代码

{{multiple image
   | direction = horizontal
   | width     = 230
   | footer    = 由伪随机数法和低差异列法生成的256点序列（红点为第1至10点，蓝点为第11至100点，绿点为第101至256点）
直观上，低差异列的分布更为均匀
   | image1    = Pseudorandom sequence 2D.svg
   | alt1      = 
   | caption1  = 伪随机序列
   | image2    = Sobol_sequence_2D.svg
   | alt2      = 
   | caption2  = 低差异序列（索博尔列）
  }}

[[数值分析]]中，'''拟蒙特卡罗方法'''(Quasi-Monte Carlo method)是使用[[低差异列]]（一种确定生成的[[超均匀分布]]列，也称为拟随机列、次随机列）来进行[[数值积分]]和研究其它一些数值问题的方法。而普通的[[蒙特卡罗方法]]或蒙地卡罗积分方法使用的是伪随机数。[[MATLAB]]中提供了生成如[[哈尔顿列]]、[[索博尔列]]等超均匀分布列的[[函数]]<ref>[http://www.mathworks.com/help/toolbox/stats/br5k9hi-8.htmlMATLAB: Generating Quasi-Random Numbers]</ref>。   

拟蒙特卡罗方法和蒙特卡罗方法的具体内容相似，要解决的问题都是通过测量某个[[测度|可测函数]] ''f'' 在某些点上的取值，而在数值上求它的积分的近似值。例如要求在单位体积<math>[0,1]^s</math>上的积分近似，可以设取的点为''x''<sub>1</sub>, ..., ''x''<sub>''N''</sub>，那么： 

:<math> \int_{[0,1]^s} f(u)\,{\rm d}u \approx \frac{1}{N}\,\sum_{i=1}^N f(x_i). </math>

其中的''x''<sub>''i''</sub>都是s维[[向量]]。拟蒙特卡罗方法和普通蒙特卡罗方法的区别在于''x''<sub>''i''</sub>的具体选取方式。蒙特卡罗方法用的是伪随机列，而拟蒙特卡罗方法用到的是[[哈尔顿列]]、[[索博尔列]]等低差异列。使用低差异列的优点是收敛速率较快。拟蒙特卡罗方法可以达到O(1/N)的收敛速率，而普通蒙特卡罗方法的收敛速率则是 O(N<sup>-0.5</sup>)<ref name="asmunssen_glynn_book"> Søren Asmussen and Peter W. Glynn, ''Stochastic Simulation: Algorithms and Analysis'', Springer, 2007, 476 pages </ref>。

近年来，拟蒙特卡罗方法在[[金融数学]]和[[计算机数学]]领域里得到了越来越多的应用<ref name="asmunssen_glynn_book" />，因为其中常常会需要计算高维积分的数值近似。蒙特卡罗方法和拟蒙特卡罗方法可以快捷简单地得到较好的结果。

== 误差估计 ==
拟蒙特卡罗方法的近似误差可以用取点''x''<sub>1</sub>, ..., ''x''<sub>''N''</sub>的差异度作为上限。具体来说，Koksma-Hlawka不等式表明，误差项 
:<math> \epsilon = | \int_{[0,1]^s} f(u)\,{\rm d}u - \frac{1}{N}\,\sum_{i=1}^N f(x_i) | </math> 
被 
:<math> |\epsilon| \leq V(f) D_N </math>
限制，其中V(f)为函数''f''的Hardy-Krause变差<ref name="morokoffNcaflisch" />，D<sub>N</sub>是(x<sub>1</sub>,...,x<sub>N</sub>)的差异度，定义为
:<math> D_N = \sup_{Q \subset [0,1]^s} \left| \frac{  Q  \mbox{中的点的数量}}{N} - Q\mbox{的体积}\right| </math>,
其中'''Q'''是任何[0,1]<sup>s</sup>中边界与坐标轴平行的方形“块”<ref name="morokoffNcaflisch">William J. Morokoff and Russel E. Caflisch, ''Quasi-Monte Carlo integration'', J. Comput. Phys. '''122''' (1995), no. 2, 218--230. ''(At [[CiteSeer]]: [http://citeseer.ist.psu.edu/morokoff95quasimonte.html] {{Wayback|url=http://citeseer.ist.psu.edu/morokoff95quasimonte.html |date=20080107021756 }})''</ref>。<math> |\epsilon| \leq V(f) D_N </math>表明拟蒙特卡罗方法的近似误差大约是<math> O(\frac{1}{N}) </math>的量级，于此相对的是普通蒙特卡罗方法的近似误差为<math> O(\frac{1}{\sqrt{N}}) </math>量级。注意这里的不等式给出的是误差上限，事实上拟蒙特卡罗方法的收敛速率要比其上限所示的速率快得多<ref name="asmunssen_glynn_book" />。因此，一般来说拟蒙特卡罗方法比起普通的蒙特卡罗方法来说大大加快了收敛的速率。

==参考来源==
{{reflist}}

* R. E. Caflisch, ''Monte Carlo and quasi-Monte Carlo methods'', Acta Numerica vol. 7, Cambridge University Press, 1998, pp. 1-49.

* Josef Dick and Friedrich Pillichshammer, ''Digital Nets and Sequences. Discrepancy Theory and Quasi-Monte Carlo Integration'', Cambridge University Press, Cambridge, 2010, ISBN 978-0-521-19159-3 

* Michael Drmota and Robert F. Tichy, ''Sequences, discrepancies and applications'', Lecture Notes in Math.,'''1651''', Springer, Berlin, 1997, ISBN 3-540-62606-9

* William J. Morokoff and Russel E. Caflisch, ''Quasi-random sequences and their discrepancies'', SIAM J. Sci. Comput. '''15''' (1994), no. 6, 1251--1279 ''(At[[CiteSeer]]:[http://citeseer.ist.psu.edu/morokoff94quasirandom.html] {{Wayback|url=http://citeseer.ist.psu.edu/morokoff94quasirandom.html |date=20060315070536 }})''

* Harald Niederreiter. ''Random Number Generation and Quasi-Monte Carlo Methods.'' Society for Industrial and Applied Mathematics, 1992. ISBN 0-89871-295-5

* Harald G. Niederreiter, ''Quasi-Monte Carlo methods and pseudo-random numbers'', Bull. Amer. Math. Soc. '''84'''(1978), no. 6, 957--1041

* Oto Strauch and Štefan Porubský, ''Distribution of Sequences: A Sampler'', Peter Lang Publishing House, Frankfurt am Main 2005, ISBN 3-631-54013-2

== 外部链接==
*{{en}}[https://web.archive.org/web/20120621193817/http://www.puc-rio.br/marco.ind/quasi_mc.html 一个直观的拟蒙特卡罗方法简介]


[[Category:蒙地卡罗方法]]
[[Category:拟随机数]]