随机数产生与模拟课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《随机数产生与模拟课件.ppt》由用户(晟晟文业)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 随机数 产生 模拟 课件
- 资源描述:
-
1、第三章第三章 随机数的产生与模拟目录随机数的产生与模拟目录 n随机数的产生与模拟随机数的产生与模拟n3.13.1均匀随机数的产生均匀随机数的产生n 3.1.13.1.1线性同余法(线性同余法(LCGLCG)的递推公式)的递推公式n 3.1.23.1.2反馈位移寄存器法(反馈位移寄存器法(FSRFSR)n 3.1.33.1.3组合发生器组合发生器n3.23.2非均匀随机数的产生非均匀随机数的产生n3.3 Monte Carlo3.3 Monte Carlo方法在解确定性问题中的应用方法在解确定性问题中的应用n 3.3.13.3.1计算定积分计算定积分 n 3.3.1.13.3.1.1随机投点法随
2、机投点法n 3.3.1.23.3.1.2平均值估计法平均值估计法n 3.3.1.33.3.1.3重要抽样法重要抽样法n 3.3.1.43.3.1.4分层抽样法分层抽样法n 3.3.2 3.3.2 计算多重积分计算多重积分n 3.3.2.1 3.3.2.1 随机投点法随机投点法n 3.3.2.2 3.3.2.2 平均值估计法平均值估计法n 3.3.33.3.3应用实例应用实例n3.4 3.4 随机模拟方法在随机服务系统中的应用随机模拟方法在随机服务系统中的应用n3.5 3.5 随机模拟方法在理论研究中的应用随机模拟方法在理论研究中的应用返回返回作业思考题随机数的产生与模拟随机数的产生与模拟 n用
3、随机模拟方法解决实际问题时,首先要解决的是随机数的产生方法,或称随机变量的抽样方法。本章目录本章目录随机数的产生与模拟随机数的产生与模拟 n伪随机数:在计算机上用数学方法产生均匀随机数是指按照一定的计算方法而产生的数列,它们具有类似于均匀随机变量的独立抽样序列的性质,这些数既然是依照确定算法产生的,便不可能是真正的随机数,因此常把用数学方法产生的随机数称为伪随机数。本章目录本章目录随机数的产生与模拟随机数的产生与模拟 n均匀分布随机数均匀分布随机数:定理:设)(xF是连续且严格单调上升的分布函数,它的反函数存在,且记为)(1xF,1、若随机变量的分布函数为)(xF,则)1,0()(UF;2、若
4、随机变量)1,0(UR,则)(1RF的分布函数为)(xF 本章目录本章目录随机数的产生与模拟随机数的产生与模拟 n均匀分布随机数均匀分布随机数:该定理说明了任意分布的随机数均可由均匀分布 的随机数变换得到。常简称 的随机数为均匀分布随机数。)1,0(U)1,0(U本章目录本章目录随机数的产生与模拟随机数的产生与模拟1 1 均匀随机数的产生均匀随机数的产生n均匀随机数的产生:均匀随机数的产生:主要有线性同余法(主要有线性同余法(LCG),组合同余),组合同余法,反馈位移寄存器方法等法,反馈位移寄存器方法等 本章目录本章目录n均匀随机数的产生:均匀随机数的产生:01)(mod(值xMxrMcaxx
5、nnnn初,.2,1n随机数的产生与模拟随机数的产生与模拟1 1 均匀随机数的产生均匀随机数的产生本章目录本章目录线性同余法(LCG)的递推公式为:n均匀随机数的产生:均匀随机数的产生:随机数的产生与模拟随机数的产生与模拟1 1 均匀随机数的产生均匀随机数的产生本章目录本章目录0c0c当 ,上式称为混合同余发生器,当时,称为乘同余发生器,此时当模为素数时,称它为素数模乘同余发生器。n两个常用的混合式发生器:两个常用的混合式发生器:350353511522)2)(mod15(xxrxxnnnn3103131122)2)(mod453806245314159269(xxrxxnnnn,.2,1n随
6、机数的产生与模拟随机数的产生与模拟1 1 均匀随机数的产生均匀随机数的产生本章目录本章目录n常用的素数模乘同余发生器常用的素数模乘同余发生器:312)312()312(mod312535035351xxrxxnnnn,.2,1n随机数的产生与模拟随机数的产生与模拟1 1 均匀随机数的产生均匀随机数的产生本章目录本章目录n常用的素数模乘同余发生器常用的素数模乘同余发生器:,.2,1n12)12()12(mod31031311xxrxaxnnnin)4,3,2,1(i168071a3972040942a7642611233a6303600164a随机数的产生与模拟随机数的产生与模拟1 1 均匀随机
7、数的产生均匀随机数的产生本章目录本章目录n反馈位移寄存器法(反馈位移寄存器法(FSRFSR):对寄存器中的二进制数码 作递推运算,其中 是给定的正整数,为给定的常数。取数列 中连续的 位构成一个 位二进制整数,一直下去,一般地有 令 则 即为FSR方法产生的均匀随机数列。)2)(mod(1111kpkppkpkccckp)1,.,2,1(10,1piorccipnL22)1(1)1(),(nLLnLnnx,.2,1nLnnxr2,.2,1n nrL随机数的产生与模拟随机数的产生与模拟1 1 均匀随机数的产生均匀随机数的产生本章目录本章目录n组合发生器组合发生器 :先用一个随机数发生器产生的随机
8、数列为基础,再用另一个发生器对随机数列进行重新排列得到的新数列作为实际使用的随机数。这种把多个独立的发生器以某种方式组合在一起作为实际使用的随机数,希望能够比任何一个单独的随机数发生器得到周期长、统计性质更优的随机数,即组合发生器。随机数的产生与模拟随机数的产生与模拟1 1 均匀随机数的产生均匀随机数的产生本章目录本章目录n组合发生器组合发生器 :随机数的产生与模拟随机数的产生与模拟1 1 均匀随机数的产生均匀随机数的产生本章目录本章目录Maclaren 和 Marsaglia在1965年提出的著名的组合发生器是组合同余发生器,该算法的具体步骤如下:n组合发生器组合发生器 :1用第一个LCG产
9、生 个随机数,一般取 。这 个随机数被顺序地存放在矢量 中。置 ;128kk),(21ktttT1nk2 用第二个LCG产生一个随机整数 ,要求 ;jkj 13 令 ,然后再用第一个LCG产生一个随机数 ,令 ;置 ;jntx yytj1 nn4 重复23,得随机数列 ,即为组合同余发生器产生的数列。若第一个LCG的模为 ,令 ,则 为均匀随机数 nxMMxrnn nr随机数的产生与模拟随机数的产生与模拟1 1 均匀随机数的产生均匀随机数的产生本章目录本章目录n由均匀分布随机数产生非均匀分布随机由均匀分布随机数产生非均匀分布随机数的主要方法有:逆变换法,合成法和数的主要方法有:逆变换法,合成法
10、和筛选法。筛选法。随机数的产生与模拟随机数的产生与模拟2 2非均匀随机数的产生非均匀随机数的产生 本章目录本章目录n1 1 逆变换法逆变换法:随机数的产生与模拟随机数的产生与模拟2 2非均匀随机数的产生非均匀随机数的产生 对任意分布函数对任意分布函数 ,要产生服从该分布要产生服从该分布的随机数,由定理知其抽样步骤为:的随机数,由定理知其抽样步骤为:(1)由)由 抽取抽取 ;(2)计算计算)(xF)1,0(UR)(1RF本章目录本章目录n1 1 逆变换法逆变换法:随机数的产生与模拟随机数的产生与模拟2 2非均匀随机数的产生非均匀随机数的产生 本章目录本章目录)1(1)(2xxpn例例1 1 已知
11、已知 (柯西分布柯西分布),试给出其抽样方法。试给出其抽样方法。n1 1 逆变换法逆变换法:随机数的产生与模拟随机数的产生与模拟2 2非均匀随机数的产生非均匀随机数的产生 解:设解:设 ,则则 ,因此因此其抽样步骤如下:其抽样步骤如下:(1 1)由)由 抽取抽取 ;(2 2)计算)计算)1,0(UR)()(tan21xpR)1,0(UR)(tan21R本章目录本章目录n1 1 逆变换法逆变换法:其其SASSAS程序为(产生程序为(产生100100个服从柯西分布的随机数):个服从柯西分布的随机数):data ex1;data ex1;seed=678;seed=678;do I=1 to 100
12、;do I=1 to 100;r=ranuni(seed);r=ranuni(seed);x=tan(3.14159x=tan(3.14159*(r-0.5);(r-0.5);output;output;end;end;run;run;随机数的产生与模拟随机数的产生与模拟2 2非均匀随机数的产生非均匀随机数的产生 本章目录本章目录n2 2 合成法合成法 :随机数的产生与模拟随机数的产生与模拟2 2非均匀随机数的产生非均匀随机数的产生 其想法是:如果X的密度 难于抽样,而X关于Y的条件密度 以及Y的密度函数 均易于抽样,则X的随机数可如下产生:由Y的密度 抽取y 由条件密度 抽取x 则X服从)(
13、yg)|(yxp)(xp)(yg)|(yxp)(xp本章目录本章目录n2 2 合成法合成法 :随机数的产生与模拟随机数的产生与模拟2 2非均匀随机数的产生非均匀随机数的产生 当 为离散形式时,即 ,其中 是密度函数,其抽样过程如下:1 产生一个正的随机整数 ,使得 ,2 产生分布为 的随机数。)(ygniiixpxp1)()(1,01niii)(xpiJjpjJP nj,.,2,1)(xpj本章目录本章目录n2 2 合成法合成法 :随机数的产生与模拟随机数的产生与模拟2 2非均匀随机数的产生非均匀随机数的产生 本章目录本章目录 设 时梯形分布的密度函数为,试用合成法产生其随机数。10 a其他
14、,0 1,0,)1(2)(xxaaxp例例2 2n2 2 合成法合成法 :随机数的产生与模拟随机数的产生与模拟2 2非均匀随机数的产生非均匀随机数的产生 解:首先将 进行分解,即 ,其中 其抽样框图为)(xp)()1()()(21xpaxapxp其他 0 1,0,1)(1xxp其他 ,0 1,0,2)(2xxxp本章目录本章目录n2 2 合成法合成法 :随机数的产生与模拟随机数的产生与模拟2 2非均匀随机数的产生非均匀随机数的产生 产生产生令产生令输出YN)1,0(URaR)1,0(UUU)1,0(,UVU),max(VU本章目录本章目录n2 2 合成法合成法 :其其SASSAS抽样程序如下(
15、假若产生抽样程序如下(假若产生100100个随机数个随机数,):):data ex2;data ex2;seed=789;a=0.3;seed=789;a=0.3;do I=1 to 100;do I=1 to 100;r=ranuni(seed);r3=ranuni(seed);r=ranuni(seed);r3=ranuni(seed);if r1=a then do;u=ranuni(seed);x=u;end;if r1=a then do;u=ranuni(seed);x=u;end;else do;u=ranuni(seed);v=ranuni(seed);x=max(u,v);e
16、nd;else do;u=ranuni(seed);v=ranuni(seed);x=max(u,v);end;output;output;end;end;run;run;随机数的产生与模拟随机数的产生与模拟2 2非均匀随机数的产生非均匀随机数的产生 本章目录本章目录n3 3 筛选抽样法筛选抽样法 :随机数的产生与模拟随机数的产生与模拟2 2非均匀随机数的产生非均匀随机数的产生 假设我们要从 抽样,如果可将 表示成 ,其中 是一个密度函数且易于抽样,而 ,是常数,)(xp)()()(xgxhcxp)(h1)(0 xg1c)(xp本章目录本章目录n3 3 筛选抽样法筛选抽样法 :随机数的产生与模
17、拟随机数的产生与模拟2 2非均匀随机数的产生非均匀随机数的产生 X的抽样可如下进行:1由 抽取 ,由 抽取2如果 ,则 ;否则,转1则X的密度函数为)1,0(UR)(yhy)(ygRyx)(xp本章目录本章目录n3 3 筛选抽样法筛选抽样法 :随机数的产生与模拟随机数的产生与模拟2 2非均匀随机数的产生非均匀随机数的产生 本章目录本章目录设 ,试用筛选法抽取其随机数。34)(xxp10 x例3n3 3 筛选抽样法筛选抽样法 :随机数的产生与模拟随机数的产生与模拟2 2非均匀随机数的产生非均匀随机数的产生 解:因为:,即:则抽样框图如下:314)(xxp3)(,1)(,4xxgxhc本章目录本章
18、目录n3 3 筛选抽样法筛选抽样法 :随机数的产生与模拟随机数的产生与模拟2 2非均匀随机数的产生非均匀随机数的产生 独立产生令NY)1,0(,21Urr321rr 2rx 本章目录本章目录n3 3 筛选抽样法筛选抽样法 :其其SASSAS程序如下:程序如下:data ex3;data ex3;seed=789;seed=789;do I=1 to 100;do I=1 to 100;r1=ranuni(seed);r2=ranuni(seed);r1=ranuni(seed);r2=ranuni(seed);if r1=r2 if r1=r2*3 then do;x=r2;output;en
19、d;3 then do;x=r2;output;end;end;end;run;run;随机数的产生与模拟随机数的产生与模拟2 2非均匀随机数的产生非均匀随机数的产生 本章目录本章目录 蒙特卡罗(蒙特卡罗(Monte CarloMonte Carlo)方法(即随机模拟方法)方法(即随机模拟方法)求解实际问题的基本步骤包括:求解实际问题的基本步骤包括:1 1 建模:对所求的问题构造一个简单而又便于实现的概建模:对所求的问题构造一个简单而又便于实现的概率统计模型,使所求的解恰好是所建模型的参数或有率统计模型,使所求的解恰好是所建模型的参数或有关的特征量。关的特征量。2 2 改进模型:根据概率统计模
20、型的特点和计算实践的需改进模型:根据概率统计模型的特点和计算实践的需要,尽量改进模型,以便减少误差和降低成本,提高要,尽量改进模型,以便减少误差和降低成本,提高计算效率。计算效率。3 3 模拟试验模拟试验4 4 求解:对模拟结果进行统计处理,给出所求问题的近求解:对模拟结果进行统计处理,给出所求问题的近似解。似解。随机数的产生与模拟随机数的产生与模拟3 Monte Carlo3 Monte Carlo方法在解确定性问题中的应用方法在解确定性问题中的应用 本章目录本章目录随机数的产生与模拟随机数的产生与模拟3 Monte Carlo3 Monte Carlo方法在解确定性问题中的应用方法在解确定
21、性问题中的应用 10)(dxxfI计算定积分计算定积分(1 1)随机投点法)随机投点法 赋初值:试验次数n=0,成功次数m=0;规定投点试验的总次数N;产生两个相互独立的均匀随机数 置n=n+1;判断nN是否成立,若成立转,否则停止试验,转;判断条件 是否成立,若成立置m=m+1,然后转,否则转;计算m/N,则)1,0(,U)(fNm/1本章目录本章目录随机数的产生与模拟随机数的产生与模拟3 Monte Carlo3 Monte Carlo方法在解确定性问题中的应用方法在解确定性问题中的应用 10)(dxxfI计算定积分计算定积分(1 1)随机投点法)随机投点法 本章目录本章目录随机数的产生与
22、模拟随机数的产生与模拟3 Monte Carlo3 Monte Carlo方法在解确定性问题中的应用方法在解确定性问题中的应用 10)(dxxfI计算定积分计算定积分(2)(2)平均值估计法平均值估计法 平均值估计法的计算步骤:产生0,1区间的均匀随机数 计算 令 =,则 为积分值 的近似解.Nrrr,21)(irf),.2,1(Ni 2NiirfN1)(12I本章目录本章目录随机数的产生与模拟随机数的产生与模拟3 Monte Carlo3 Monte Carlo方法在解确定性问题中的应用方法在解确定性问题中的应用 10)(dxxfI计算定积分计算定积分(3)(3)重要抽样法重要抽样法 重要抽
23、样法的计算步骤为:产生均匀随机数 用直接抽样法产生 随机数,即由 计算则 计算 =,则 是 的估计量.ir),.2,1(Ni)(xgix)(xgxiNiiiNiixgxfNzN11)()(113Iir3本章目录本章目录随机数的产生与模拟随机数的产生与模拟3 Monte Carlo3 Monte Carlo方法在解确定性问题中的应用方法在解确定性问题中的应用 10)(dxxfI计算定积分计算定积分(4)(4)分层抽样法分层抽样法 分层抽样法的计算步骤如下:本章目录本章目录随机数的产生与模拟随机数的产生与模拟3 Monte Carlo3 Monte Carlo方法在解确定性问题中的应用方法在解确定
24、性问题中的应用 (1)(1)随机投点法随机投点法 多重积分随机投点法计算步骤为:计算多重定积分计算多重定积分 1010102121),(kkkdxdxdxxxxfI本章目录本章目录随机数的产生与模拟随机数的产生与模拟3 Monte Carlo3 Monte Carlo方法在解确定性问题中的应用方法在解确定性问题中的应用 (1)(1)随机投点法随机投点法 计算多重定积分计算多重定积分 1010102121),(kkkdxdxdxxxxfI 赋初值:试验次数 n=0,成功次数 m=0;规定随机投点试验的总次数为 N;向1k维立方体10ix,ki,.,2,1,10 y内随机投点,即产生k+1个互独立
25、的均匀随机数(1,2,k,)=,置 n=n+1;判断 nN 是否成立,若成立则转;否则停止模拟试验,然后转;检验 k+1 维空间的点是否落入 V 中,即检验条件),.,(21kf是否成立,若成立即试验成功,置 m=m+1;然后转;否则转;计算Nm/5;其中 m 是 N 次试验中成功的总次数,则5kI 本章目录本章目录随机数的产生与模拟随机数的产生与模拟3 Monte Carlo3 Monte Carlo方法在解确定性问题中的应用方法在解确定性问题中的应用 (2)(2)平均值估计法平均值估计法 计算多重定积分计算多重定积分 1010102121),(kkkdxdxdxxxxfI多重积分的平均值法
展开阅读全文