（计算机软件与理论专业论文）并行monte+carlo方法研究及其在期权定价中的应用.pdf

郑州大学硕士学位论文并行m o n t cc a r l o 方法研究及其在期权定价中的应用 摘要 金融分析是计算科学的重要应用领域，目前受到越来越广泛的关注。但 是随着科技发展，金融分析提出来的越来越复杂的随机性问题，用确定性方 法给出其近似解是很困难的，甚至是不可能的。m o n t ec a r l o 方法是金融分析 最为常用的方法，是对欧式期权定价的一种十分有效的特殊数值分析方法， 有时甚至是唯一的方法。然而由于蒙特卡罗方法一次有效的定价过程所需的 模拟次数巨大，有时甚至需要上百万次的模拟，计算量相当大。巨大的计算 代价严重地阻碍了蒙特卡罗方法的应用，所以迫切需要解决计算量大的问题。 并行计算机的出现，提供了并行计算的方法，为解决计算量大、计算时 间长的问题提供了有效的方法。 本文通过对蒙特卡罗方法的基本原理和欧式期权定价特点的研究分析， 用蒙特卡罗方法对欧式期权定价问题进行模拟，针对金融分析的复杂性和蒙 特卡罗方法计算量巨大的问题，采用符合对数正态分布的伪随机数代替随机 数，把巨大数目的伪随机实验交由计算机完成。在对模拟过程深入分析的基 础上，结合并行计算的特点，提出采用并行蒙特卡罗方法的解决方案。在分 布式存储结构的机群系统上，采用可移植消息传递接口m p i 与c 语言绑定， 设计并实现了并行蒙特卡罗算法。通过对机群节点间通信时问开销的研究分 析，对并行算法进行多次改进，采用主从式编程模型，实现了负载平衡，提 高了机群处理器的利用率，有效地解决了计算量大、串行算法执行时间长的 问题。通过对并行算法进行验证，证明并行算法得了到较高的加速比和并行 效率，大大提高了计算效率，缩短了执行时问，以较低的成本完成了复杂的、 大量的计算任务。 关键词：蒙特卡罗，欧式期权，消息传递，并行计算，并行效率 郑州大学硕士学位论文并行m o n t ec a r l o 方法研究及其在期权定价中的应用 a b s t r a c t f i n a n c i a la n a l y s i si st h ei m p o r t a n ta p p l i c a t i o no fc a l c u l a t i o ns c i e n c ea t p r e s e n t i tr e c e i v e st h em o r ea n dm o r ew i d e s p r e a da t t e n t i o n b u ta l o n gw i t ht h e t e c h n i c a ld e v e l o p m e n t , t h ef i n a n c i a la n a l y s i sp r o p o s e dt h em o r ea n dm o r e c o m p l e xr a n d o mq u e s t i o n , 8 0i ti sv e r yd i f f i c u l to fe v e ni m p o s s i b l et og i v ea a p p r o x i m a t er e s d tw i t ht h ed e f t r i t em e t h o d t h em o n t ec a r l om e t h o di st h em o s t c o m m o n l yu s e dm e t h o dt ot h ef i n a n c i a la n a l y s i s , s o m e t i m e se v e ni st h eo n l y m e t h o d a tt h e $ a n l ot i m ei ti sav e r ye f f e c t i v es p e c i a ln u m e r i c a la n a l y s i sm e t h o d f o re u r o p e a no p t i o np r i c i n g h o w e v e r , d u et ot h eh u g en u m b e ro fe x p e r i m e n t s ， s o m e t i m e so nm i l l i o n so fs i m u l a t i o n , t h e r ei sac o n s i d e r a b l ea m o u n to f c o m p u t a t i o no nt h em o n t ec a r l om e t h o df o ra l le f f e c t i v ep r i c i n gp r o c e s s e n 锄o l 玛c o m p u t a t i o n s lc o s th a ss e r i o u sh i n d e r e dt h ea p p l i c a t i o no ft h em o n t e c a r l om e t h o d , t h e r e f o r ei ti su r g e n tn e e d st os o l v et h ep r o b l e mo fm a j o r c o m p u t a t i o nq u a n t i t y t h ep a r a l l e lm a c h i n ep r o v i d e dt h ep a r a l l e lc o m p u t i n gm e t h o dw h i c hs o l v e s l a r g ea m o u n to f c o m p u t a t i o na n dl o n gt i m ef o rc a l c u l a t i n gp r o b l e m t h r o u g ht h es t u d yo ft h eb a s i cp r i n c i p l eo ft h em o n t ec a r l om e t h o da n dt h e s p e c i a l t yo f t h ee u r o p e a no p t i o np r i c i n g , t h i sa r t i c l ec a r r i e do nt h es i m u l a t i o nw i l h m o n t ec a r l om e t h o df o re u r o p e a no p t i o np r i c i n g i nv i e wo f t h ec o m p l e x i t yo f t h e f i n a n c i a la n a l y s i sa n dt h eh u g ec o m p u t a t i o nq t l a n t i t yq u e s t i o no fm o n t ec a r l o m e t h o d , t h i sa r t i c l eu s e dt h ep s e n d o - r a n d o mn u m b e r so fl o g n o r m a ld i s t r i b u t i o n i n s t e a do fr a n d o mn u m b e r s ，h a n d e do v e rt h et m g en u m b e ro fp s e u d o r a n d o mt o t h ec o m p u t e rc o m p l e t e d t h i sa r t i c l ep r o p o s e dt h ep a r a l l e lm o n t ec a r l om e t h o dt o s o v l et h ep r o b l e m ，b a s e do nt h ed e e pa n a l y s i so ft h es i m u l a t i o np r o c e s sa n dt h e c h a r a c t e r i s t i c so fp a r a l l e lc o m p u t a t i o n t h r o u g ht h er e s e a r c ha n da n a l y s i so f c o m m u n i c a t i o nt i m eb e t w e e nc l u s t e rn o d e si nc o w ，t h ep a r a l l e la l g o r i t h mh a s e b e e ni m p r o v e da g a i na n da g a i n t h eb e s tp a r a l l e la l g o r i t h mu s e dm a s t e r - s l a v e i i 宴堕垡兰翌型兰坠型笙l 一一 兰堑翌竺塑! 型! 查鲨墅塞墨苎童塑壑塞丝主堕壁旦 p r o g r a m m i n gm o d e l ，r e a l i z e dl o a d - b a l a n c i n g , i m p r o v e dt h eu t i l i z a t i o nr a t eo f p f d 。日s o $ i nc o w , e f f e c t i v e l ys o l v e dt h ep r o b l e mt h a tt h er u n n i n gt i m ew a s l o n g o ne n o 曲0 璐c o m p u t a t i o nf o rs e r i a la l g o r i t h m s t h r o u g ht h ec o n f i r m a t i o n , t h e p a r a l l e la l g o r i t h mo b t a i n e dah i g hs p e e d u pa n dp a r a l l e le f f i c i e n c y , l l a n c e dt l l e e f f i c i e n c yo ft h oc o m p u t a t i o ng r e a t l y , r e d u c e dt h et i m oo fe x e c u t i o mc o m p l e t c d n l ec o m p l e xa n dm a s s i v e t a s ko f c a l c u l a t i n ga tal o w e rc o s t 1 k 删d 躬m o n t ec a r l o , e u r o p e a no p t i o n , m e s s a g e p a s s i a g , p a r a l l e lc o m p u t i n g , p a r a l l e le f f i c i e n c y i 郑州大学硕士学位论文 并行m o n t ec 州。方法研究及其在期权定价中的戍用 第一章引言 1 1 问题的提出及研究意义 1 1 1 问题的提出 蒙特卡罗方法( m o n t ec a r l o ) 是用频率近似地估计概率的随机实验方法。 然而要使计算结果有足够高的准确度，就需要进行大量的模拟，而用人工对 随机模拟中数据进行计算，实际上是不可能的。因此，蒙特卡罗方法的基本 思想虽然早已被人们提出，却很少被使用。 近几十年来，随着电子计算机的出现和迅速发展，人们才有意识地、广 泛地、系统地应用随机抽样实验来解决数学、物理问题【”，把巨大数目的随机 实验交由电子计算机完成，通过电子计算机来模拟随机实验过程，使得蒙特 卡罗方法得以广泛地应用，在现代化的科学技术中发挥巨大的作用。 然而随着现代科技发展提出越来越复杂的问题，蒙特卡罗方法一次有效 的模拟过程通常需要百万次甚至更多次的随机模拟，要想达到较高的模拟精 度需要进行更多的模拟，否则可能产生较大的方差，因此计算量巨大通过 人工方法做大量模拟是不可能的，即使通过串行计算方法实现也是相当困难 的，不仅需要耗费大量的时间、人力、物力等，而且在实际应用中可能仍是 不可实现的。 1 1 2 研究的意义 现代科技发展中提出来的越来越复杂的随机性问题，除极少数外，要想 给出其严格解是根本不可能的，用确定性方法给出其近似解也很困难，甚至 不可能。然而蒙特卡罗方法以随机模拟和统计实验为手段，是一种从随机变 量的概率分布中，通过随机选择数字的方法产生一种符合该随机变量概率分 布特性的随机数值序列，作为输入序列进行特定的模拟、求解的方法。蒙特 卡罗方法以对随机性问题进行模拟为其基本特征，这就决定了蒙特卡罗方法 是解决这类问题能力很强的一种特殊的数值方法。 郑州大学硕士学位论文 并行m o n t ec 州。方法研究及其在期权定价中的应用 蒙特卡罗方法具有其它数值方法不具有的优点： ( 1 ) 适应性强，解题时受问题条件限制的影响较小； ( 2 ) 收敛速度与问题的维数无关，从而能够更好地应用于高维度问题； ( 3 ) 蒙特卡罗方法及其程序结构简单。 因此蒙特卡罗方法具有很大的研究意义。 但蒙特卡罗方法也有它相应的缺点：蒙特卡罗方法一次有效的模拟过程 通常需要百万次甚至更多次的随机抽样，要想达到较高的模拟精度需要进行 更多次的模拟，否则可能产生较大的方差，因此计算量巨。针对其缺点，可 以把蒙特卡罗方法交由并行计算机处理，对模拟并行化，缩短计算时间，提 高计算效率，使蒙特卡罗方法切实可用。 并行蒙特卡罗算法在对庞大数据进行分析计算时，具有明显的优点： ( 1 ) 它可以加快速度，即在更短的时间内解决相同的问题或在相同的时 间内解决更多更复杂的问题，特别是对新出现的具有巨大挑战性的问题，不 使用并行计算是根本无法解决的； ( 2 ) 节省投入，并行计算可以以较低的投入完成串行计算的任务。 因此，对蒙特卡罗方法并行算法及其应用的研究具有较高的学术理论价 值和研究意义。 1 2 国内外研究现状及分析 1 2 1 国内外研究现状 随着现代科技的发展，蒙特卡罗方法可以借助计算机实现它所要求的大 量的随机抽样实验，因而能够广泛地应用于数学、物理、工程技术、生产管 理等各个领域。 近年来，m o n t ec a r l o 模拟是金融分析最为常用的方法，有时甚至是唯一 的方法嘲。自从1 9 7 7 年b o y l e 首先利用蒙特卡罗方法对基于单标的资产的欧 式期权定价以来，蒙特卡罗方法现已成为对金融衍生工具定价的一种十分有 效的特殊数值分析方法嘲。对期权的定价问题，7 0 年代，b l a c k 和s c h o l e s 提 出计算欧式期权的布莱克一斯科尔斯模型“1 。布莱克一斯科尔斯模型是在假设波 2 郑州大学硕+ 学位论文并行m o n t ec a r l o 方法研究及其在期权定价中的戍用 动率不变的一系列前提下得出的，而实际上波动率本身是一个随机变量，因 此s c o t t 、w i g g i n s 、r e n a u l t 、t o u z i 、f o u q u e 、p a p a n i e o l a o u 和s i r e a r 等把布莱 克一斯科尔斯模型推广到随机波动率的情形。4 。”。蒙特卡罗方法是以概率为基 础的一种数值计算方法，有收敛速度比较慢的缺点，因此为了克服此缺点， p a s k o v 和t r a u b 提出用伪随机数序列代替随机数序列的蒙特卡罗方法对欧式 期权定价。1 。m a s e a g n i 和c h i 用伪随机数序列来计算特殊的金融衍生证券的 价格，提高了蒙特卡罗模拟的收敛速度“”，但期权定价的精度不够。为了达 到足够的计算精度，需要的计算时间可能会很长。解决这一问题可以采用数 学方法，如方差减小技术，也可以应用并行计算方法。p e r r y 、g r i m w o o d 和 k e r b y s o n 采用并行计算方法解决了计算量大。计算时间长的问题“。因此并 行蒙特卡罗方法广泛应用于欧式期权的定价“”以。 并行计算是高性能计算的一支，是一个国家经济和科技实力的综合体现， 也是促进经济、科技发展的重要因素，已成为世界各国竟相争夺的战略制高 点。一些发达国家纷纷制定战略计划，提出很高的目标，投入大量资金，加 速研制开发步伐。我国近十年来对高性能并行计算机的研究也给予很大重视， 但与发达国家相比，差距仍然很大。如何使用高性能并行机系统在科研和社 会应用中发挥作用，成为当务之急。 1 2 2 分析 在信息快速增长的今天，由于期权定价的复杂性和某些定价对实时性的 要求，传统的期权定价方法已经很难满足现实的需要，很难切实在金融定价 领域应用。 同时，蒙特卡罗方法本身有局限性。当样本容量太小时，蒙特卡罗方法 导出的分布与真实分布的近似性较差，所以是否能获得足够多的观察数据是 十分重要的。而且蒙特卡罗方法所需的计算量很大，常常需要在计算的精度 与计算量上作某种程度的折衷。因此，尽管蒙特卡罗方法是期权定价的好方 法，但由于其自身的局限性，阻碍了蒙特卡罗方法在期权定价中的实际应用。 随着并行计算机的发明和使用，才使这一问题得到解决。 在用蒙特卡罗方法对欧式期权定价的程序进行并行化时，需要解决以下 几个方面的问题： 郑州大学硕士学位论文并行m o n t ec a r l o 方法研究及其在期权定价中的应用 ( 1 ) 伪随机数的抽取：要保证伪随机数是独立同分布的，伪随机数的周 期大于所抽取的伪随机数数目。并且伪随机数序列是符合欧式期权定价的对 数正态分布的伪随机数序列； ( 2 ) 多c p u 计算结果的综合问题； ( 3 ) 当计算量巨大时，调整算法，尽可能减少程序的运行时间； ( 4 ) 并行程序的运行时间在很大程度上与所使用的节点个数有关，所以 应多次实验以找到合适的节点个数； ( 5 ) 并行程序的品质因素：品质因素是反映计算效率的重要参数，对并 行程序来说，主要包括并行程序的加速比、并行效率等。 1 3 蒙特卡罗方法在其它领域的应用概况 1 3 1 蒙特卡罗方法在积分计算中的应用 定积分的近似计算是实际工作中最常碰到的数学问题之一。在原子能科 学技术、武器装备论证等问题中会出现许多复杂的单重与多重定积分。通常， 人们都选用矩形公式、辛普森公式等来完成积分的近似计算。在许多情况下， 使用这些近似计算公式虽然能够得到相当满意的结果，但计算量随着积分重 数的增加而显著增加，以至于达到用电子计算机都无法完成的程度 定积分的计算是蒙特卡罗方法引入计算数学的开端。在实际应用中，许 多需要计算多重积分的复杂问题，用蒙特卡罗方法一般都能够很有效地予以 解决。尽管蒙特卡罗方法给出的计算结果精度不是很高，但它能很快地提供 一个低精度的模拟结果也是很有价值的。在多重积分计算中，由于蒙特卡罗 方法的误差与积分重数无关，所以它比常用的均匀网格求积公式要优越。 蒙特卡罗方法求积分的一般规则如下：任何一个积分，都可看作某个随 机变量的期望值。因此，可以用这个随机变量的平均值来近似替代它。 设欲求积分为 i = ig ( p ) d p ( 1 1 ) jrj 其中，尸= m l ，x 2 ，五) 表示s 维空间的点，k 表示积分区域。取圪上 任一联合概率密度函数，尸) ，令 4 郑州大学硕士学位论文并行m e n uc a r l o 方法研究及其在期权定价中的应用 卯，= 器 2 ， 则 i = r e ( 1 3 ) , g ( p ) f ( p ) d p = e l k ( p ) 即，是随机变量g ( d 的数学期望。因为p 的分布密度函数为厂( d ，现从，( d 中抽取随机向量p 的个样本p l ，f = 1 ，2 ，则 “2 专善粥) 1 舢 就是川向近似估计，也就是用平均值近似地计算出了积分值。 蒙特卡罗方法求积分通常有两种概率统计模型，即随机投点法和平均值 法，这里不再详述。 用蒙特卡罗方法计算定积分的误差阶为o ( n2 ) ，与积分重数无关。而用 矩形公式求s 重定积分误差的阶为o ( n ) ，这里表示求积结点数。因此， 当s 3 时，使用蒙特卡罗方法求积便显示出其优越性了“1 。 1 3 2 蒙特卡罗方法在屏蔽计算中的应用 辐射屏蔽问题是蒙特卡罗方法广泛应用的领域之一。对于诸如辐射传播、 多次散射和通量计算等一般粒子输运问题都是适用的。 在任何一种与放射性有关的工作中，为了使周围的工作人员不致受放射 性物质的伤害，必须对其中的光子、中子和其它有害的粒子进行屏蔽。采用 的办法通常是，用由吸收物质制成的屏蔽层对这些有害的粒子进行屏蔽，使 有害的粒子穿过屏蔽层后被减弱到对人体不致产生伤害的程度。因此，屏蔽 计算所关心的问题是粒子穿过屏蔽层的份额，或者说是粒子穿过屏蔽层的概 率，简称穿透概率。 当屏蔽物的形状复杂，散射各向异性，材料介质不均匀，核反应截面与 能量、位置有关时，难以用数值方法求解，但用蒙特卡罗方法能够得到满意 的结果。 粒子的输运问题带有明显的随机性质，是一个随机过程。粒子的运动规 律是根据大量粒子的运动状况总结出来的，是一种统计规律。蒙特卡罗模拟 郑州大学硕士学位论文并行m o n t ec a r l o 方法研究及其在期权定价中的麻用 实际上就是模拟相当数量的粒子在介质中运动的状况，使粒子运动的统计规 律得以重现。不过这种模拟不是用实验方法，而是利用数值方法和技巧，即 利用随机数来实现的。 在平板屏蔽计算问题中运用蒙特卡罗方法，是蒙特卡罗方法的应用问题 中最早的一个，而且蒙特卡罗方法中各种降低方差的技巧几乎都有所应用。 一般蒙特卡罗方法用于屏蔽计算的最大困难是当屏蔽层的厚度超过一定范围 之后，它的计算结果常比实际结果偏低很多，屏蔽层越厚，这种现象越明显。 这种现象，即所谓深穿透问题的蒙特卡罗计算结果偏低的现象，是k a h n 在 1 9 5 0 年首先指出的，而且他还给出了一些解决方法“”，这些方法是指数变换 ( e x p o n e n t i a lt r a n s f o r m a t i o n ) 方法、限额抽样( q u o t as a m p l i n g ) 方法、分裂 与轮盘赌( s p l i t t i n ga n dr o u l e t t e ) 方法和统计估( s t a t i s t i c a le s t i m a t i o n ) 方法。 随后，他同h a r r i s 合作又给出了重要抽样( i m p o r t a n c es a m p l i n g ) 方法“。后 来，有关蒙特卡罗方法在平板屏蔽计算中的应用，又有了新的进展，对于平 板屏蔽问题和几何深层穿透问题进一步受到重视。关于这方面的工作有偏倚 抽样( b i a ss a m p l i n g ) 方法嘛“蛳町、伴随( a d j o i n t ) 指数变换方法和历次 飞行估计方法m 1 等等。 1 3 3 蒙特卡罗方法在核临界安全计算中的应用 任何一个含有裂变的核系统，由于其中的中子在发生裂变反应时有增殖 现象存在，就整个核系统而言，中子的增殖有无限制地继续下去而发生事故 的可能，因此必须考虑它的安全问题，这就是所谓的核临界安全问题。中子 由于发生裂变反应而增殖和由于被吸收或跑出核系统而死亡，是中子在核增 殖系统中的最基本现象。很明显当核系统中的中子增殖数不大于死亡数时， 该核系统是安全的；相反的，当核系统中的中子增殖数大于死亡数时，该系 统是不安全的。当核系统中的中子增殖数等于死亡数时，核系统正好处于安 全与不安全的临界状态，常称处于这种状态的核系统为临界的，而称处于安 全状态而又不属于临界状态的核系统为次临界的，处于不安全状态的核系统 为超临界的。 用来解决核系统临界安全问题的主要的计算方法有：扩散近似( d i f f u s i o n a p p r o x i m a t i o n ) 方法，n 近似( p la p p r o x i m a t i o n ) ，曲方法和蒙特卡罗方法等 6 郑州大学硕士学位论文并行m o n t ec a r l o 方法研究及其在期权定价中的应用 等。前三种方法适合解一维或二维几何的核系统临界安全问题，对于解三维 几何问题则是非常困难的。蒙特卡罗方法不受核系统的几何形状和维数限制， 因此，它以成为解核系统临界安全问题的一种不可缺少的方法豳“。 用蒙特卡罗方法来解决核系统临界安全问题常用的方法有：裂变矩阵方 法( f i s s i o nm a t r i x ) ，计算矩阵元素碰撞点方法，计算矩阵元素的径迹长度 ( t r a c k - l e n g t h ) 方法，函数展开方法，分区迭代方法，源迭代的直接抽样方 法，系统抽样( s y s t e m a t i cs a m p l i n g ) 方法，非独立抽样( n o n - i n d e p e n d e n t s a m p l i n g ) 方法，多迭代矩估计( m u l t i g e n e r a t i o nm o m e n te s t i m a t i o n ) 方法。 其中，多迭代矩估计方法有很多优点，是目前计算有效增殖因子的蒙特卡罗 方法中应用最为广泛的一种，有很大生命力。 1 3 4 蒙特卡罗方法在稀薄气体绕流计算中的应用 稀薄气体动力学及其相应闯题的数值计算研究是空气动力学研究领域中 的一个重要分支。在现代科技中，尤其是在航空航天领域、高速化学反应中 占有特殊的地位。对于气象卫星、载人宇宙飞船、空间实验站及航天飞机等 长时间在外层空间飞行的物体，稀薄气动特性的研究就是绝对不可缺少的。 描述稀薄气体中发生的现象要采用熟知的b o l t z m a n n 方程。一般来说， 它是一个七维的非线性微积分方程，求解它的分析方法分为两类：一类是根 据问题的性质从直观概念出发，选取分布函数表达式，用矩法求解；另一类 是对b 氏方程本身进行某种简化，即用模化方程代替它。这两类方法仅对某 些简化的或特殊的情形适用，问题稍一复杂，求解就很困难。 人们把稀薄气体动力学中发生的现象视为某随机过程，用蒙特卡罗方 法求解获得了很好的效果。先是a l d e r 和w a i n w r i g h t 用此法考察了封闭系统 中气体达到平衡的过程。接着b i r d 等人对a l d e r 方法做了很大的改进和发展， 建立了流场直接模拟法，并用它成功地研究了简单物形绕流，松弛过程，激 波结构，激波反射，稀薄气体流场显示技术及复杂的旋成体绕流计算，受到 人们的关注。 郑州大学硕士学位论文并行m o n t ec a r l o 方法研究及其在期权定价中的应用 1 4 研究的目的和内容 1 4 1 研究的目的 并行计算是高性能计算的一支，如何使高性能并行机系统在科研和社会 发展中发挥作用，成为当务之急。 金融计算是计算科学的重要领域，目前受到越来越广泛的关注。但是随 着科技发展，金融分析提出来的越来越复杂的随机性问题，用通常的数值计 算方法求解是不可能的。蒙特卡罗方法是解决随机性问题能力很强的一种特 殊的数值方法，是金融分析最为常用的方法，有时甚至是唯一的方法嘲。而要 使计算结果的精度足够高，需要进行的模拟次数相当大，计算时问相当长 因此，本文的主要研究目的就是根据欧式期权定价的特点，用蒙特卡罗 方法对欧式期权定价问题进行模拟。为了解决蒙特卡罗方法模拟计算量巨大、 计算时间长的问题，把蒙特卡罗模拟交由并行计算机处理，使其并行化。并 进一步研究并行算法的特性，不断改进并行算法，缩短计算时间，提高计算 效率，使蒙特卡罗方法切实可用。 1 4 2 研究的内容 从上面的阐述可知，蒙特卡罗方法在期权定价方面的研究具有很高的学 术理论意义和非常广阔的应用前景。本文在已有的研究基础上，主要做了以 下几个方面的工作： 把蒙特卡罗方法与欧式认购期权定价问题相结合，深入分析了欧式 认购期权定价的随机性，根据其随机特点建立定价模型； 深入分析了蒙特卡罗方法的优缺点，针对蒙特卡罗方法的计算量巨 大、计算时问长的缺点，采用并行计算方法缩短计算时间； 为了提高定价精度，增加蒙特卡罗方法的样本数目。由于采用的是 并行计算，在不断改进并行算法的前提下，增加样本数目，计算时 间增加是微小的。这样就达到了提高计算精度但对计算时自j 影响不 大的目的； 在联想深腾1 8 0 0 + 机群系统上，采用消息传递接口m p i 与标准c 绑 郑州大学硕士学位论文 并行m o n t ec a r l o 方法研究及其存期权定价中的应用 定的一个并行的环境中，根据蒙特卡罗方法的特点，实现欧式认购 期权定价的并行算法； 对并行算法进行改进，进一步提高程序的执行效率； 验证改进后并行算法的效率，进行效率分析。 1 5 本文的章节安排 本文共由六章组成。 第一章为并行蒙特卡罗方法的综述。阐述了蒙特卡罗方法及其并行计算 在国内外的研究现状，并进行分析。针对存在的问题提出了本文的研究目的 和研究内容。 第二章介绍了蒙特卡罗方法的概念、原理、特性以及蒙特卡罗方法中的 关键技术和用蒙特卡罗方法进行模拟的基本步骤；第三章提出了蒙特卡罗方 法在欧式期权定价中的应用。对欧式期权定价进行研究，得到欧式期权定价 的一般模型。对这个模型进行进一步的分析，结合蒙特卡罗方法的特点，提 出了蒙特卡罗方法欧式期权定价的模型；第四章介绍了并行系统的相关概念， 对并行系统进行研究，把物理模拟转换成并行模型，并阐述了在并行计算机 上实现并行程序时用到的并行技术及应注意的问题。 第五章在第三章得出的并行蒙特卡罗欧式期权定价模型的基础上，给出 了并行的方案，然后根据并行程序的特点对方案进行改进。为了进一步提高 并行算法的性能，在对并行程序深入研究分析的基础上，对改进后的算法进 行二次改进，得n t 第三种并行方案。通过对第三种并行方案进行性能分析， 证明了第三种并行方案达到了较好的加速比和并行效率。最后总结了把物理 模型转换成并行模型以及编写并行程序时存在的一些问题及应注意的一些问 题。 第六章是对全文工作的总结。 9 郑州大学硕十学位论文并行m o n t ec a r l o 方法研究及其在期权定价中的应用 2 1 引言 第二章蒙特卡罗方法 蒙特卡罗方法是从轮盘赌以及硬币投掷等随机过程中总结出的数值求解 物理问题的一套方法。古代的蒙特卡罗方法是最早用频率近似地估计概率的 随机实验方法。后来从随机过程中蕴藏着的规律而总结出来的数值求解物理 问题的一套方法就是蒙特卡罗( m o n t ec a r l o ) 方法，也称为随机模拟( r a n d o m s i m u l a t i o n ) 方法，有时也称为随机抽样( r a n d o ms a m p l i n g ) 技术或统计实验 ( s t a t i s t i c a lt e s t i n g ) 方法。 蒙特卡罗方法作为一种可行的计算方法，是由u l a m 和v o nn e u m a n n 在 2 0 世纪4 0 年代二次世界大战期间为解决研制核武器中的计算问题而首先提 出并加以运用的。1 9 4 6 年，物理学家v o n n e u m a n n 等在电子计算机上用随机 抽样方法模拟了中子连锁反应，并把这种方法称为蒙特卡罗方法。1 9 4 7 年， m e t r o p o l l i s 提出“m o n t e c a r l o ”一名，并将其作为一篇描述l o s a l a m o s 实验 室早期工作的文章标题，该名的选定是因为在计算机中广泛地采用了随机数 的概念。在此之前，作为该方法的基本思想，实际上早已被统计学家所发现 和利用。随着电子计算机的出现和发展，使得数学方法在电子计算机上模拟 大量的实验成为可能，蒙特卡罗方法得到越来越广泛的应用。 另外，随着科学技术的不断发展，出现了越来越多复杂而困难的问题， 用通常的解析方法或数学方法很难解决问题。蒙特卡罗方法就是在这种情况 下，作为一种可行的而且是不可缺少的计算方法被提出和迅速发展起来。 2 2 蒙特卡罗方法的原理和思想 蒙特卡罗方法是一种计算方法，但与一般数值计算方法有很大区别，它 以概率统计理论为基础，能够比较逼真地描述事物的特点及物理实验过程， 解决一些数值方法难以解决的问题。 蒙特卡罗方法的原理：蒙特卡罗方法以随机模拟和统计实验为手段，从 0 郑州大学硕士学位论文并行m o n t ec a r l o 方法研究及其在期权定价中的应用 随机变量的概率分布中，通过随机选取数字的方法产生一种符合该随机变量 概率分布特性的随机数字序列，作为输入序列进行模拟、求解的方法“1 。 蒙特卡罗方法的思想是：首先建立一个概率模型或随机过程，使其参数 等于问题的解；然后通过对模型或过程的观察或抽样实验来计算所求参数的 统计特征值，最后给出所求解的近似值。而解的精确度可以用估计值的标准 差来表示。 假设所要求解的量x 是随机变量x 的数学期望风的，那么近似确定x 的 方法是对x 进行次重复抽样，产生相互独立的x 值的序列x l 、x 2 、h ， 并计算其算术平均值： 一x n - - - = 万1 善m ( 2 1 ) 根据柯尔莫罗夫加强大数定理有嘲 p ( 艘善2 力= l ( 2 2 ) 因此，当充分大时，下式 x , v 居( 朋= 工 ( 2 3 ) 成立的概率等于1 ，即可以用；，作为所求量j 的估计值。 用蒙特卡罗方法求解时，最简单的情况是模拟一个发生概率为p 的随机 事件爿。考虑一个随机变量x ，若在一次实验中事件彳出现，则工取值为1 ； 若事件爿不出现，则工取值为o 。令q = l p ，那么随机变i x 的数学期望为 e g ) = t p + o g = p ， ( 2 4 ) 此即一次实验中事件4 出现的概率。x 的方差为 e ( x e o 。) 2 = p p 2 = p q ( 2 5 ) 假设在次实验中事件爿出现1 ，次，那么观察频率v 也是一个随机变量， 其数学期望为 e ( v ) = n p ( 2 6 ) 方差为 郑州大学硕士学位论文并行m o n t ec a r l o 方法研究及其在期权定价中的应用 式 盯2 ( = n ? q ( 2 7 ) 令；= v 表示观察频率，那么按照加强大数定理，当n 充分大时，下 ；：导z e ( 曲= p p 2 面2 d 【砷2 p ( 2 8 ) 成立的概率为1 。 因此，由上述模型得到的频率；= | 近似等于所求量p ，说明了频率收 敛于概率，而且可用样本方差 以p ) = 訾 作为理论方差盯2 p ) 的估计值嘲。 ( 2 9 ) 蒙特卡罗方法可以解决多种类型的问题，但总的来说，视其是否涉及随 机过程的性态和结果可以分为两类： 第一类是确定的数学问题。用蒙特卡罗方法求解这类确定性问题的基本 思想是：首先对于给定的确定性问题，设计一个概率统计模型，使所求的解 是所建立模型的数学期望或符合所建立模型的概率分布；然后采用一定的抽 样方法对这个模型进行随机抽样，产生随机变量；最后把这个模型产生的一 个数字特征值作为该确定性问题解的近似估计值。计算多重积分、求逆矩阵、 解线性代数方程组、解积分方程、解某些偏微分方程边值问题和计算微分算 子的特征值等都属于这类问题。 第二类是随机性问题。例如中子在介质中的扩散等问题就属于随机性问 题。对于这类问题，虽然有时可表示为多重积分或某些函数方程，并进而可 考虑用随机抽样方法求解，然而一般情况下都不采用这种间接模拟方法，而 是采用直接模拟方法，即根据实际物理情况的概率法则，用电子计算机进行 抽样实验。原子核物理问题、运筹学中的库存问题、随机服务系统中的排队 问题、动物的生态竞争和传染病的蔓延等都属于这一类问题。 1 2 郑州大学硕士学位论文 并行m o n t ec a r l o 方法研究及其在期权定价中的应用 2 3 蒙特卡罗方法的特点、收敛性以及误差 蒙特卡罗方法无论从步骤方面，还是结果精度和收敛方面，都是一种具 有独特风格的数值计算方法，与一般数值方法的不同点或者说是它的优点， 可归纳为以下三个方面的： ( 1 ) 蒙特卡罗方法及其程序结构简单 在计算机上进行蒙特卡罗方法计算时，程序结构简单，分块性强，易于 实现。 例如用平均值方法计算定积分 l i = ig ( x ) d x ( 2 1 0 ) i 的数值，其计算步骤为： 产生均匀分布在 o ，1 i - i 勺随机数( 萨l ，2 ，) ； 计算g 以) ( 舻l ，2 ，) ； 用平均值 7 = 专薹酬 泣m 作为，的近似值。 这个例子体现了蒙特卡罗方法计算积分是通过大量的简单的重复抽样实 现的，方法和程序都很简单。 ( 2 ) 收敛的概率性和收敛速度与问题维数无关 蒙特卡罗方法的收敛是概率意义下的收敛。也就是说蒙特卡罗方法虽然 不能断言其误差不超过某个值，但能指出其误差以接近l 的概率不超过某个 界限。 蒙特卡罗方法的收敛速度与一般数值方法相比是很慢的，其主阶仅为 o ( n2 ) 。因此，蒙特卡罗方法不宜于求解精度要求很高的问题。 如果随机变量序列而、x 2 、x n 独立同分布，且盯0 ，那么蒙特卡 罗方法的误差s 为 郑州大学硕士学位论文并行m o n t ec a r l o 方法研究及其在期权定价中的戍用 占= 鸳 ( 2 1 2 ) - n 由此式可见蒙特卡罗方法的误差f 只与标准差仃和样本容量有关，而 与样本中元素所在空间无关，即蒙特卡罗方法的收敛速度与问题维数无关， 而其它数值方法则不然。 ( 3 ) 蒙特卡罗方法的适应性强，受几何条件限制小 例如s 维空间中任意一个区域历上的积分为 i = - ig ( x l ，恐，) 嘲呶地， ( 2 1 3 ) 五 无论协的形状如何特殊，只要能给出描述d j 的几何条件，就可以用平均值 方法给出川i 勺近似估计为 了= 鲁耋酬”爿”，一) ( 2 1 4 ) 其中点( 五，屯，o ) e n ，且均匀分布在4 上，但其它数值方法受问题 的条件限制影响比较大。在具有随机性质的问题中，如考虑的系统形状很复 杂，难以用一般数值方法求解，而使用蒙特卡罗方法不会有原则上的困难。 而一般数值方法计算高维积分时都有难以克服的问题。 此外，蒙特卡罗方法还具有一些其它特点： ( 1 ) 能够比较逼真地描述具有随机性质的事物的特点及物理实验过程。 从这个意义上讲，蒙特卡罗方法可以代替部分物理实验，甚至可以得到物理 实验难以得到的结果。用蒙特卡罗方法解决实际问题，可以直接从实际问题 本身出发，而不从方程或数学表达式出发。因此具有直观、形象的特点。 ( 2 ) 误差容易确定。对于一般计算方法，常存在着有效位数损失问题， 要给出计算结果与真值的误差并不是一件容易的事情，而蒙特卡罗方法则不 然。根据蒙特卡罗方法的误差公式，可以在计算所求量的同时计算出误差。 对于很复杂的蒙特卡罗方法计算问题，也是容易确定的。 蒙特卡罗方法的误差可用随机变量的标准差或方差来度量，因此可以在 解题过程的同时加以计算。 如果随机变量序列五、x 2 、h 独立同分布，且盯o ，那么蒙特卡 郑州大学硕+ 学位论文并行m o n t ec a r l o 方法研究及其在期权定价中的应用 罗方法的误差p 为 占：鸳( 2 1 5 ) 0 n 上式中的正态差丸与显著水平口是一一对应的，其对应关系可用( o ，1 ) 积 分表及 击r e 一 2 出小詈 眨 算出。 关于蒙特卡罗方法的误差需说明两点：第一，蒙特卡罗方法的误差为概 率误差，这与其他数值计算方法是有区别的。第二，误差中的均方差盯是未 知的，必须使用其估计值 盯= ( 2 1 7 ) 来代替，在计算所求量的同时，可计算出厅。 同时，蒙特卡罗方法也具有一些缺点： ( 1 ) 收敛速度慢 l 如前所述，蒙特卡罗方法的收敛速度为o ( n2 ) ，一般不容易得到精确度 较高的近似结果。对于维数少( 三维以下) 的问题，不如其它方法好。 ( 2 ) 误差具有概率性 由于蒙特卡罗方法的误差是在一定置信水平下估计的，所以它的误差具 有概率性，而不是一般意义下的误差。 ( 3 ) 在粒子输运问题中，计算结果与系统大小有关。 因此，在使用蒙特卡罗方法时，可以考虑把蒙特卡罗方法与解析方法相 结合，取长补短，既能解决解析方法难以解决的问题，也可以解决单纯使用 蒙特卡罗方法难以解决的问题。这样，可以发挥蒙特卡罗方法的特长，使其 应用范围更加广泛。 郑州大学硕士学位论文 并行m o n t ec a r l o 方法研究及其在期权定价中的戍用 2 4 随机数 2 4 1 随机数的定义 用蒙特卡罗方法模拟某过程时，需要产生某种概率分布的随机变量。最 简单、最基本、最重要的随机变量是在 0 ，1 上均匀分布的随机变量。通常把 0 , 1 3 上均匀分布随机变量的抽样值称为随机数。其它分布随机变量的抽样都 是借助于随机数来实现的。因此，随机数是随机抽样的基本工具。 随机数是实现由已知分布抽样的基本量，在已知分布的抽样过程中，将 随机数作为已知量，用适当的数学方法可以由它产生任意已知分布的简单子 样。 随机数在蒙特卡罗方法中占有极其重要的位置。我们用专门的符号f 表 示。由随机数序列的定义可知，f l ，f 2 ，是相互独立且具有相同单位均 匀分布的随机数序列。也就是说，独立性、均匀性是随机数必备的两个特点。 2 4 2 随机数表 1 9 2 5 年t i p p e t t 为了做大量抽样实验，搜集了一套随机数，借以发现某些 理论分布。于1 9 2 7 年编制了随机抽样数字表或简称随机数表。此表包含0 到 9 十个数字，它们的排序是杂乱无章的或者是随机的。表中任意一位上的数字 以1 1 0 的等概率出现，而且与其上下左右相邻的其它数字的出现都是相互独 立的。满足上面条件的数字就是从0 到9 十个离散的随机数字。这些随机数 字组成的序列就是随机数字序列口力。如果要得到雄位有效数字的随机数，只 需将表中每栉个相邻的随机数字合并在一起，且在最高位的前边加上小数点 即可。如果将表中的四个随机数字合并成