论文部分内容阅读
摘 要： 本文主要介绍蒙特卡罗方法的基本原理及思想特征，详细讨论了蒙特卡罗方法在计算曲线积分等实际问题中的应用，突出了蒙特卡罗方法的过程及优势。
关键词： 蒙特卡罗方法 曲线积分 教学应用
1.引言
近些年来，随着电子计算机的迅速发展与广泛使用，计算数学获得了新的发展，增添了许多新内容，蒙特卡罗方法就是其中一种。该方法的出现，极大地促进了科学文明的进步，开辟了人们研究问题的新途径。
在程序编制和计算机算法设计中常采用的算法一般是确定性算法，也就是算法的每一个计算步骤都是确定的。但是在很多情况下，当算法在执行过程中遇到一个选择时，随机性选择经常比最优选择更节省时间且效率极高。我们把这种允许算法在执行过程中随机选择下一个计算步骤的算法叫做概率算法。概率算法可以很大程度地降低算法的复杂程度。
蒙特卡罗算法、拉斯维加斯算法和舍伍德算法都是一些常用的概率算法。这些算法的基本特征是：对要求问题的同一个例子，用同一概率算法运算若干次，所得到的结果可能完全不同。但是通过多次执行反复求解，会使正确性和精确性达到令人满意的效果，而失败或误差的概率则可以接近无限小[1]。
本文的主要研究内容：
（1）蒙特卡罗方法的基本思想及其基本特点。
（2）蒙特卡罗方法求解问题的基本过程。
（3）蒙特卡罗方法的应用领域。
（4）蒙特卡罗方法在计算曲线积分中的应用。
2.蒙特卡罗方法的基本思想及其基本特点
2.1蒙特卡罗方法的提出
二十世纪四十年代的二战中美国有个研制原子弹的计划——“曼哈顿计划”，该计划的成员J.冯·诺伊曼和S.M.乌拉姆首先提出蒙特卡罗方法。著名数学家冯·诺伊曼采用世界有名的赌城——摩纳哥的Monte Carlo命名这一方法。而实际上，在这之前，蒙特卡罗方法就已经存在。早在1777年，法国著名数学家布丰（Georges Louis Leclere de Buffon，1707-1788）就提出用投针实验的方法计算圆周率π。这被认为是蒙特卡罗方法的起源。
2.2蒙特卡罗方法概述
蒙特卡罗方法又称为随机抽样技术、统计模拟法，是一种随机模拟方法，它是以概率和统计理论方法为基础的一种计算方法，是使用随机数（或更常见的伪随机数）解决很多计算问题的方法。将所求解的问题同一定的概率模型联系起来，用电子计算机实现统计模拟或抽样，从而获得问题的近似解。为了象征性地表明这一方法的概率统计特征，所以借用赌城蒙特卡罗命名。
2.3蒙特卡罗方法基本思想
当所要求解的问题是某种随机事件出现的概率，或者是某个随机变量的期望值时，通过某个“实验”的方法，以这种事件出现的频率估计这个随机事件的概率，或者得到的这个随机变量的某些数字特征，并将它们作为问题的解。
3.蒙特卡罗方法求解问题的基本过程
蒙特卡罗方法求解问题的过程大致分为三个主要的步骤。
3.1描述或构造概率过程
对于那些本身就有随机性质的问题，比如粒子的输运问题，主要是要对这个概率的过程进行正确的描述和模拟；对于确定性的问题，比如说计算数学上的定积分，就一定要事先人为地构造一个概率过程，而且这个概率过程的一些参量刚好是所要求的问题的解。也就是要把不具有随机性质的问题转化为有随机性质的问题。
3.2实现从已知概率分布抽样
构造了概率模型以后，因为各种概率模型都可以看做是由各种各样的概率分布而组成的，因此产生已知概率分布的随机变量（或随机向量），就成为实现蒙特卡罗方法模拟实验基本的手段，这是蒙特卡罗方法被称为随机抽样的原因。最基本、最简单、最重要的一个概率分布是（0，1）上的均匀分布（或称矩形分布）。随机数就是具有这种均匀分布的随机变量。随机数序列就是具有这种分布的总体的一个简单子样，也就是一个具有此种分布的相互独立的随机变数序列。产生随机数的问题，就是从这个分布的抽样问题。在计算机中可以用物理方法产生随机数，但是价格比较昂贵，且不能重复，使用不方便。另一种方法是用数学的递推公式产生。这样产生的序列，与真正的随机数序列不同，所以称为伪随机数，或伪随机数序列。不过，经过多种统计检验表明，它与真正的随机数序列或随机数具有很相似的性质，所以可将其作为真正的随机数应用。由已知分布随机抽样有很多的方法，不同于从（0，1）上的均匀分布抽样的是，此类方法都是凭借于随机序列从而得到实现，也就是说，其前提都是产生随机数。因此，实现蒙特卡罗方法的基本工具是随机数。
3.3建立各种估计量
一般来说，概率模型被构造出来并可以从中抽样以后，一定要确定一个随机变量，作为所求的问题的解，我们把它叫做无偏估计。建立各种估计量，也就是对模拟实验的结果进行观察和记录，从而把问题的解求出来。
4.蒙特卡罗方法的应用领域
通常蒙特卡罗方法通过构造符合一定规则的随机数来解决数学上的问题。对于那些因为计算太过复杂而很难得到解析解或根本没有解析解的问题，蒙特卡罗方法是一种有效的求解出数值解的方法。
除了在数学方面得到很好的应用外，蒙特卡罗方法在其他很多领域也得到很好的应用，比如说蒙特卡罗方法在金融学、工程学、宏观经济学、地质学、生物医学、计算物理学（如粒子输运计算、空气动力学计算、量子热力学计算）及计算机科学等广泛的领域都得到非常成功的应用。
下面探讨蒙特卡罗方法在数学领域中的应用。
5.蒙特卡罗方法在计算曲线积分中的应用
在物理的很多研究时，要求平面或空间中的一条可求长度的曲线形物体的质量，或者一个质点在平面或者空间中沿曲线L从A点运动到B点时力F所做的功，这时就要用到曲线积分。 平面或空间曲中的曲线积分有两种类型：第一型曲线积分和第二型曲线积分。下面着重探讨如何用蒙特卡罗法计算第一型曲线积分。
5.1第一型曲线积分的定义
设L为平面上可求长度的曲线段，f（x，y）为定义在L上的函数。对曲线L做分割T，它把L分成n个可求长度的小曲线段L■（i=1，2，…n），L■的弧长记为Δs■，分割T的细度为‖T‖=■Δs■，在L■上任取一点（ξ■，η■）（i=1，2，…，n），若有极限
■■f（ξ■，η■）Δs■=J，
且J的值与分割T与点（ξ■，η■）的取法无关，则称此极限为f（x，y）在L上的第一型曲线积分，记作：
？蘩■f（x，y）ds。
5.2第一型曲线积分的一般计算方法
设有光滑曲线
L：x=φ（t），y=ψ（t），t∈[α，β]，
函数f（x，y）为定义在L上的连续函数，则
？蘩■f（x，y）ds=？蘩■■f（φ（t），ψ（t））■dt。
5.3第一型曲线积分的蒙特卡罗计算法
对于L上的曲线积分I=？蘩■f（x，y）ds=？蘩■■f（φ（t），ψ（t））■dt，其中L：x=φ（t），y=ψ（t），t∈[α，β]。令f（t）=f（φ（t），ψ（t））■，则
I=？蘩■■f（t）dt。（1）
在[α，β]上构造一个均匀分布的随机变量t，则密度函数为
p（t）=■，α 又令
F（t）=f（t）/p（t），p（t）≠00， p（t）=0，
则
I=？蘩■■F（t）p（t）dt=E（F（t））。（2）
（2）式给我们传达了：F（t）在t∈[α，β]上的数学期望就是（1）式的曲线积分[2]-[4]。
现在只要抽取概率密度为p（t）的随机变量t的容量为N的随机样本t■（i=1，2，…，n），由大数定理就可以得到：
I≈■■f（t■）=■■f（φ（t■），ψ（t■））■。（3）
5.4实例
设L是半椭圆
L：x=2cost，y=3sint， t∈[0，π]，
求第一型曲线积分？蘩■（x■ y■）ds。
首先，由曲线积分方法得：
？蘩■（x■ y■）ds=？蘩■■（4cos■t 9sin■t）■dt。
这样的积分很难直接求得结果，这里考虑用蒙特卡罗法计算：
？蘩■（x■ y■）ds≈■■（4cos■t■ 9sin■t■）■。
用计算机程序模拟10次得到随机表如下表所示：
模拟1000次得到随机表如下表所示：
模拟10000次得到随机表如下表所示：
模拟20000次得到随机表如下表所示：
模拟30000次得到随机表如下表所示：
由以上的模拟数据可以看出，模拟次数越多，得出的积分均值越趋于稳定。
5.5三维空间的第一型曲线积分
上面讨论的是平面上曲线段的曲线积分，下面开始探讨蒙特卡罗法如何应用于三维空间中的曲线积分。对于三维空间中的光滑曲线段：
L：x=φ（t），y=ψ（t），t∈[α，β]，z=ζ（t），
函数f（x，y，z）为定义在L上的连续函数，则
？蘩■f（x，y，z）ds=？蘩■■f（φ（t），ψ（t），ζ（t））■dt，（4）
类比平面上的曲线积分，很容易等到三维空间中，曲线积分的蒙特卡罗算法：
I≈■■f（t■）=■■f（φ（t■），ψ（t■），ζ（t■））■。（5）
6.结论和展望
与其他的计算方法相比较，蒙特卡罗方法有下面几个优点：
（1）问题的维数不影响该方法的收敛速度。但是很多的数值计算方法，比如计算N重积分时，达到相同的误差，点数和维数的幂次成正比。
（2）受问题的条件限制的影响不大。
（3）程序的结构简单，在计算机上实现蒙特卡罗计算时，程序的结构简单清晰，占用内存单位较少。
当然，蒙特卡罗方法并不是完美的，它也有其缺陷的地方：
（1）伪随机数的均匀性影响随机变量取值从而影响结果。
（2）收敛速度慢。蒙特卡罗模拟的收敛速度为O（n■），一般不容易得到精确度较高的近似结果。对于维数比较少（三维以下）的问题，不如其他方法好。
（3）如误差是概率误差，误差与点数（抽样数）的平方根成反比，而其他数值方法的误差是确切的，一般情况下，误差与点数成反比，因此，对于维数不高的问题，数值方法可以给出误差很小的结果，而且计算量小。
蒙特卡罗方法与其他数值方法都有其本身的一定适用范围，把二者结合起来，取长补短，发挥它们各自的长处，目前在国外已受到普遍重视，是蒙特卡罗方法发展的一个重要方向。
参考文献：
[1]王晓东.算法设计与分析[M].北京：清华人学出版社，2008.
[2]黎锁平.运用蒙特卡罗方法求解随机性问题[J].甘肃工业大学学报，2001，27（2）：95-97.
[3]姚贵平，等.重积分近似计算方法的讨论[J].内蒙古农业大学学报，2000，21（4）：98-101.
[4]宫野.计算多重积分的蒙特卡罗方法与数论网格法[J].大连理工大学学报，2001，41（1）：20-23.
[5]尹增谦，等.蒙特卡罗方法及其应用[J].物理与工程，2002，12（3）：45-49.
[6]易大义，陈道琦.数值分析引论[M].杭州：浙江大学出版社，1998，165-170.
[7]Sobol I M. Asymmetric convergence of approximations of the Monte Carlo method [J]. Computational Mathematics and Mathematical Physics，1993，33：1391-1396.
关键词： 蒙特卡罗方法 曲线积分 教学应用
1.引言
近些年来，随着电子计算机的迅速发展与广泛使用，计算数学获得了新的发展，增添了许多新内容，蒙特卡罗方法就是其中一种。该方法的出现，极大地促进了科学文明的进步，开辟了人们研究问题的新途径。
在程序编制和计算机算法设计中常采用的算法一般是确定性算法，也就是算法的每一个计算步骤都是确定的。但是在很多情况下，当算法在执行过程中遇到一个选择时，随机性选择经常比最优选择更节省时间且效率极高。我们把这种允许算法在执行过程中随机选择下一个计算步骤的算法叫做概率算法。概率算法可以很大程度地降低算法的复杂程度。
蒙特卡罗算法、拉斯维加斯算法和舍伍德算法都是一些常用的概率算法。这些算法的基本特征是：对要求问题的同一个例子，用同一概率算法运算若干次，所得到的结果可能完全不同。但是通过多次执行反复求解，会使正确性和精确性达到令人满意的效果，而失败或误差的概率则可以接近无限小[1]。
本文的主要研究内容：
（1）蒙特卡罗方法的基本思想及其基本特点。
（2）蒙特卡罗方法求解问题的基本过程。
（3）蒙特卡罗方法的应用领域。
（4）蒙特卡罗方法在计算曲线积分中的应用。
2.蒙特卡罗方法的基本思想及其基本特点
2.1蒙特卡罗方法的提出
二十世纪四十年代的二战中美国有个研制原子弹的计划——“曼哈顿计划”，该计划的成员J.冯·诺伊曼和S.M.乌拉姆首先提出蒙特卡罗方法。著名数学家冯·诺伊曼采用世界有名的赌城——摩纳哥的Monte Carlo命名这一方法。而实际上，在这之前，蒙特卡罗方法就已经存在。早在1777年，法国著名数学家布丰（Georges Louis Leclere de Buffon，1707-1788）就提出用投针实验的方法计算圆周率π。这被认为是蒙特卡罗方法的起源。
2.2蒙特卡罗方法概述
蒙特卡罗方法又称为随机抽样技术、统计模拟法，是一种随机模拟方法，它是以概率和统计理论方法为基础的一种计算方法，是使用随机数（或更常见的伪随机数）解决很多计算问题的方法。将所求解的问题同一定的概率模型联系起来，用电子计算机实现统计模拟或抽样，从而获得问题的近似解。为了象征性地表明这一方法的概率统计特征，所以借用赌城蒙特卡罗命名。
2.3蒙特卡罗方法基本思想
当所要求解的问题是某种随机事件出现的概率，或者是某个随机变量的期望值时，通过某个“实验”的方法，以这种事件出现的频率估计这个随机事件的概率，或者得到的这个随机变量的某些数字特征，并将它们作为问题的解。
3.蒙特卡罗方法求解问题的基本过程
蒙特卡罗方法求解问题的过程大致分为三个主要的步骤。
3.1描述或构造概率过程
对于那些本身就有随机性质的问题，比如粒子的输运问题，主要是要对这个概率的过程进行正确的描述和模拟；对于确定性的问题，比如说计算数学上的定积分，就一定要事先人为地构造一个概率过程，而且这个概率过程的一些参量刚好是所要求的问题的解。也就是要把不具有随机性质的问题转化为有随机性质的问题。
3.2实现从已知概率分布抽样
构造了概率模型以后，因为各种概率模型都可以看做是由各种各样的概率分布而组成的，因此产生已知概率分布的随机变量（或随机向量），就成为实现蒙特卡罗方法模拟实验基本的手段，这是蒙特卡罗方法被称为随机抽样的原因。最基本、最简单、最重要的一个概率分布是（0，1）上的均匀分布（或称矩形分布）。随机数就是具有这种均匀分布的随机变量。随机数序列就是具有这种分布的总体的一个简单子样，也就是一个具有此种分布的相互独立的随机变数序列。产生随机数的问题，就是从这个分布的抽样问题。在计算机中可以用物理方法产生随机数，但是价格比较昂贵，且不能重复，使用不方便。另一种方法是用数学的递推公式产生。这样产生的序列，与真正的随机数序列不同，所以称为伪随机数，或伪随机数序列。不过，经过多种统计检验表明，它与真正的随机数序列或随机数具有很相似的性质，所以可将其作为真正的随机数应用。由已知分布随机抽样有很多的方法，不同于从（0，1）上的均匀分布抽样的是，此类方法都是凭借于随机序列从而得到实现，也就是说，其前提都是产生随机数。因此，实现蒙特卡罗方法的基本工具是随机数。
3.3建立各种估计量
一般来说，概率模型被构造出来并可以从中抽样以后，一定要确定一个随机变量，作为所求的问题的解，我们把它叫做无偏估计。建立各种估计量，也就是对模拟实验的结果进行观察和记录，从而把问题的解求出来。
4.蒙特卡罗方法的应用领域
通常蒙特卡罗方法通过构造符合一定规则的随机数来解决数学上的问题。对于那些因为计算太过复杂而很难得到解析解或根本没有解析解的问题，蒙特卡罗方法是一种有效的求解出数值解的方法。
除了在数学方面得到很好的应用外，蒙特卡罗方法在其他很多领域也得到很好的应用，比如说蒙特卡罗方法在金融学、工程学、宏观经济学、地质学、生物医学、计算物理学（如粒子输运计算、空气动力学计算、量子热力学计算）及计算机科学等广泛的领域都得到非常成功的应用。
下面探讨蒙特卡罗方法在数学领域中的应用。
5.蒙特卡罗方法在计算曲线积分中的应用
在物理的很多研究时，要求平面或空间中的一条可求长度的曲线形物体的质量，或者一个质点在平面或者空间中沿曲线L从A点运动到B点时力F所做的功，这时就要用到曲线积分。 平面或空间曲中的曲线积分有两种类型：第一型曲线积分和第二型曲线积分。下面着重探讨如何用蒙特卡罗法计算第一型曲线积分。
5.1第一型曲线积分的定义
设L为平面上可求长度的曲线段，f（x，y）为定义在L上的函数。对曲线L做分割T，它把L分成n个可求长度的小曲线段L■（i=1，2，…n），L■的弧长记为Δs■，分割T的细度为‖T‖=■Δs■，在L■上任取一点（ξ■，η■）（i=1，2，…，n），若有极限
■■f（ξ■，η■）Δs■=J，
且J的值与分割T与点（ξ■，η■）的取法无关，则称此极限为f（x，y）在L上的第一型曲线积分，记作：
？蘩■f（x，y）ds。
5.2第一型曲线积分的一般计算方法
设有光滑曲线
L：x=φ（t），y=ψ（t），t∈[α，β]，
函数f（x，y）为定义在L上的连续函数，则
？蘩■f（x，y）ds=？蘩■■f（φ（t），ψ（t））■dt。
5.3第一型曲线积分的蒙特卡罗计算法
对于L上的曲线积分I=？蘩■f（x，y）ds=？蘩■■f（φ（t），ψ（t））■dt，其中L：x=φ（t），y=ψ（t），t∈[α，β]。令f（t）=f（φ（t），ψ（t））■，则
I=？蘩■■f（t）dt。（1）
在[α，β]上构造一个均匀分布的随机变量t，则密度函数为
p（t）=■，α
F（t）=f（t）/p（t），p（t）≠00， p（t）=0，
则
I=？蘩■■F（t）p（t）dt=E（F（t））。（2）
（2）式给我们传达了：F（t）在t∈[α，β]上的数学期望就是（1）式的曲线积分[2]-[4]。
现在只要抽取概率密度为p（t）的随机变量t的容量为N的随机样本t■（i=1，2，…，n），由大数定理就可以得到：
I≈■■f（t■）=■■f（φ（t■），ψ（t■））■。（3）
5.4实例
设L是半椭圆
L：x=2cost，y=3sint， t∈[0，π]，
求第一型曲线积分？蘩■（x■ y■）ds。
首先，由曲线积分方法得：
？蘩■（x■ y■）ds=？蘩■■（4cos■t 9sin■t）■dt。
这样的积分很难直接求得结果，这里考虑用蒙特卡罗法计算：
？蘩■（x■ y■）ds≈■■（4cos■t■ 9sin■t■）■。
用计算机程序模拟10次得到随机表如下表所示：
模拟1000次得到随机表如下表所示：
模拟10000次得到随机表如下表所示：
模拟20000次得到随机表如下表所示：
模拟30000次得到随机表如下表所示：
由以上的模拟数据可以看出，模拟次数越多，得出的积分均值越趋于稳定。
5.5三维空间的第一型曲线积分
上面讨论的是平面上曲线段的曲线积分，下面开始探讨蒙特卡罗法如何应用于三维空间中的曲线积分。对于三维空间中的光滑曲线段：
L：x=φ（t），y=ψ（t），t∈[α，β]，z=ζ（t），
函数f（x，y，z）为定义在L上的连续函数，则
？蘩■f（x，y，z）ds=？蘩■■f（φ（t），ψ（t），ζ（t））■dt，（4）
类比平面上的曲线积分，很容易等到三维空间中，曲线积分的蒙特卡罗算法：
I≈■■f（t■）=■■f（φ（t■），ψ（t■），ζ（t■））■。（5）
6.结论和展望
与其他的计算方法相比较，蒙特卡罗方法有下面几个优点：
（1）问题的维数不影响该方法的收敛速度。但是很多的数值计算方法，比如计算N重积分时，达到相同的误差，点数和维数的幂次成正比。
（2）受问题的条件限制的影响不大。
（3）程序的结构简单，在计算机上实现蒙特卡罗计算时，程序的结构简单清晰，占用内存单位较少。
当然，蒙特卡罗方法并不是完美的，它也有其缺陷的地方：
（1）伪随机数的均匀性影响随机变量取值从而影响结果。
（2）收敛速度慢。蒙特卡罗模拟的收敛速度为O（n■），一般不容易得到精确度较高的近似结果。对于维数比较少（三维以下）的问题，不如其他方法好。
（3）如误差是概率误差，误差与点数（抽样数）的平方根成反比，而其他数值方法的误差是确切的，一般情况下，误差与点数成反比，因此，对于维数不高的问题，数值方法可以给出误差很小的结果，而且计算量小。
蒙特卡罗方法与其他数值方法都有其本身的一定适用范围，把二者结合起来，取长补短，发挥它们各自的长处，目前在国外已受到普遍重视，是蒙特卡罗方法发展的一个重要方向。
参考文献：
[1]王晓东.算法设计与分析[M].北京：清华人学出版社，2008.
[2]黎锁平.运用蒙特卡罗方法求解随机性问题[J].甘肃工业大学学报，2001，27（2）：95-97.
[3]姚贵平，等.重积分近似计算方法的讨论[J].内蒙古农业大学学报，2000，21（4）：98-101.
[4]宫野.计算多重积分的蒙特卡罗方法与数论网格法[J].大连理工大学学报，2001，41（1）：20-23.
[5]尹增谦，等.蒙特卡罗方法及其应用[J].物理与工程，2002，12（3）：45-49.
[6]易大义，陈道琦.数值分析引论[M].杭州：浙江大学出版社，1998，165-170.
[7]Sobol I M. Asymmetric convergence of approximations of the Monte Carlo method [J]. Computational Mathematics and Mathematical Physics，1993，33：1391-1396.