文档介绍：17. 蒙特卡罗(Monte Carlo)模拟
蒙特卡罗方法,或称计算机随机模拟方法,是一种基于“随机数”的计算方法。该方法源于美国在WWI后研制原子弹的“曼哈顿计划”。 S. M. Ulam (1908-1984)和该计划的主持人之一、数学家冯·诺伊曼( Neumann )用驰名世界的赌城—摩纳哥的Monte Carlo—来命名这种方法。
蒙特卡罗模拟
其基本思想很早以前就被人们所发现和利用:
17世纪,用事件发生的“频率”来决定事件的“概率”;
19世纪人们用投针试验的方法来决定π。
高速计算机:用数学方法在计算机上大量模拟这样的试验
必要性
科技计算及社会中的问题比计算π要复杂得多。比如金融衍生产品(期权、期货、掉期等)的定价及交易风险估算,问题的维数(即变量的个数)可能高达数百甚至数千。对这类问题,难度随维数的增加呈指数增长,这就是所谓的“维数的灾难”(Curse of Dimensionality),传统的数值方法难以对付(即使使用速度最快的计算机)。Monte Carlo方法能很好地用来对付维数的灾难,因为该方法的计算复杂性不再依赖于维数。以前那些本来是无法计算的问题现在也能够计算量。为提高方法的效率,科学家们提出了许多所谓的“方差缩减”技巧。
另一类形式与Monte Carlo方法相似,但理论基础不同的方法—“拟蒙特卡罗方法”(Quasi-Monte Carlo方法)—近年来也获得迅速发展。我国数学家华罗庚、王元提出的“华—王”方法即是其中的一例。这种方法的基本思想是“用确定性的超均匀分布序列(数学上称为Low Discrepancy Sequences)代替Monte Carlo方法中的随机数序列。对某些问题该方法的实际速度一般可比Monte Carlo方法提出高数百倍,并可计算精确度。
/gkjqy/rkx/
拟蒙特卡罗模拟
许多计算机系统都有随机数生成函数
F90: call random_seed
call random_number(a)
计算程序产生的随机数不是真正的随机数,它们是确定的,但看上去是随机的,且能通过一些随机性的检验,故常称为伪随机数
若采用当前时刻作随机数种子,则也是不可重复的
随机数
如
对32位字长的计算机
real procedure random((xi))
integer array (li)n
real array (xi)n
l0 any integer that 1< l0 <231-1
for i=1 to n do
li =(231-1)除以16807 li-1的余数
xi =li/ (231-1)
endfor
其它算法
1. 取初值x0 (0,1),let xi be the fractional part of (π+ xi-1)5
2. Let u0 =1. For i=1,2,3,…, let ui be the remainder of (8t-3) ui-1 divided by 28, and xi = ui/2i. Here t can be any large integer
注意:上述随机数序列均具周期性,如上页random子程序的周期约230。
Maple has a collection of random number generators.
如:
With(stats)
x :=uniform(0..1):
seq(x(),i=1..10);
Matlab: x=rand(10,1)产生10个随机数
x=rand(N) 产生元素在(0, 1)间随机分布的N*N矩阵
s= rand(‘state’,0) 重设该生成函数到初始状态
如(b-a)r+a x (a,b)
integer((n+1)r) x {0,1,2,……n}
试产生1000个在椭圆x2+4y2=4内均匀分布的随机点:
方法:在中均匀产生足够
多随机点,当位于椭圆内的点数为1000时停止。
可由随机数序列 r (0,1)构造一系列随机数序列
有时随机数产生函数通不过严格的随机性测试。而在一些计算(如MC积分)中随机性非常重要。故使用更长字节的计算机更好。
应用之一
估计面积和体积
Numerical integration
选取(0, 1)中随机数序列x1, x2, x3, …… xn。则
误差约,它并不能和一些高级的数值积分算法比拟,
但对多维情况,MC方法却很有吸引力。