§22数字积分(计算定积分的值) Monte carlo积分(但不是指我们定义的MC算法) 、概率算法1 设f:[0,1→[0,们是一个连续函数,则由曲线y=f(x),x 轴,y轴和直线x=围成的面积由下述积分给出 s=lf(x)dx 向单位面积的正方形内投镖n次,落入阴影部分的镖的 数目为k,则 k =>s=k/n 显然,只要n足够大S->k/n
21 Monte Carlo积分(但不是指我们定义的MC算法) 1、概率算法1 设f: [0, 1] → [0, 1]是一个连续函数，则由曲线y=f(x), x 轴, y轴和直线x=1围成的面积由下述积分给出： 向单位面积的正方形内投镖n次，落入阴影部分的镖的 数目为k，则 显然，只要n足够大 §2.2 数字积分 (计算定积分的值) 1 0 S f x dx = ( ) / 1 k S S k n n = = =S k n − / 1 x y 1
§22数字积分(计算定积分的值) 1.概率算法1 HitorMiss(t, n)t k←0 fori←1 to n do{ X← uniform(0,1) y← uniforn(0,1); ify≤f(x) then k+; return k/n Note:-x是S4的面积,=S,;,丌=4小-h 22
22 1. 概率算法1 HitorMiss (f, n) { k ← 0; for i ← 1 to n do { x ← uniform(0, 1); y ← uniform(0, 1); if y ≤ f(x) then k++; } return k/n; } Note: 是S/4的面积，∵ π =S, ∴ §2.2 数字积分 (计算定积分的值) 1 2 0 1− x dx 1 2 0 = − 4 1 x dx
§22数字积分(计算定积分的值) 1.概率算法1 Ex2在机器上用4-xh估计m值,给出不 同的n值及精度。 Ex3设a,b,c和d是实数,且a≤b,c≤d,f[a, b]→[c,d]是一个连续函数,写一概率算法计 算积分: f(da 注意,函数的参数是a,b,c,d,n和f,其中用函 数指针实现,请选一连续函数做实验,并给出 实验结果
23 1. 概率算法1 Ex2. 在机器上用 估计π值，给出不 同的n值及精度。 Ex3. 设a, b, c和d是实数，且a ≤ b, c ≤ d, f:[a, b] → [c, d]是一个连续函数，写一概率算法计 算积分： 注意，函数的参数是a, b, c, d, n和f, 其中f用函 数指针实现，请选一连续函数做实验，并给出 实验结果。 §2.2 数字积分 (计算定积分的值) 1 2 0 4 1− x dx ( ) b a f x dx
§22数字积分(计算定积分的值) 1.概率算法1 Ex4设E,6是(0,1)之间的常数,证明: 若是「∫(x的正确值,h是由 Hitormiss算法返回的 值,则当n≥I(1-D/26时有 Prob[h-<8]≥1-8 上述的意义告诉我们: Prob[h-≥8≤6,即:当n≥I(1 /g2δ6时,算法的计算结果的绝对误差超过ε的概率不超 过6,因此我们根据给定E和6可以确定算法迭代的次数 (∵:/(1-D) 4 解此问题时可用切比雪夫不等式,将看作是数学期望
24 1. 概率算法1 *Ex4. 设ε,δ是(0,1)之间的常数，证明： 若I是 的正确值，h是由HitorMiss算法返回的 值，则当n ≥ I(1-I)/ε 2δ时有： Prob[|h-I| < ε] ≥ 1 – δ 上述的意义告诉我们：Prob[|h-I| ≥ ε] ≤δ, 即：当n ≥ I(1- I)/ ε 2δ时，算法的计算结果的绝对误差超过ε的概率不超 过δ，因此我们根据给定ε和δ可以确定算法迭代的次数 解此问题时可用切比雪夫不等式，将I看作是数学期望。 §2.2 数字积分 (计算定积分的值) 1 0 f x dx ( ) 2 2 (1 ) 1 1 ( (1 ) ) 4 4 I I n I I − = −
922数字积分(计算定积分的值 2.概率算法2 更有效的概率算法是:在积分区间上随机均匀地产生点,求 出这些点上的函数值的算术平均值,再乘以区间的宽度: f(xx=(b-a)∑f(x),a≤x≤b Crude(f, n, a, bt sum←0 fori←1 to n do{ x← uniform(a,b) sum←sum+f(x); return (b-asum/n;
25 2. 概率算法2 更有效的概率算法是： 在积分区间上随机均匀地产生点，求 出这些点上的函数值的算术平均值，再乘以区间的宽度： Crude (f, n, a, b) { sum ← 0; for i ← 1 to n do { x ← uniform(a, b); sum ← sum + f(x); } return (b-a)sum/n; } §2.2 数字积分 (计算定积分的值) 1 1 ( ) ( ) ( ), n b i i a i f x dx b a f x a x b n − = −