§22数字积分(计算定积分的值) 2.概率算法2 用 HitorMiss和 Crude运行三次的结果为: hit3.141855.3.141422.3.141434 crude3.141662.3.141486.3.141527 假定()和(存在,由算法求得的估算 值的方差反比于点数n。当n足够大时,估计的分 布近似为正态分布。 对于给定的迭代次数n, Crude算法的方差不会大 于 HitorMiss的方差。但不能说, Crude算法总是 优于 HitorMiss。因为后者在给定的时间内能迭代 的次数更多。例如,计算π值时, Crude需计算 平方根,而用投镖算法 darts时无需计算平方根。 26
26 2. 概率算法2 用HitorMiss和Crude运行三次的结果为： 假定 和 存在，由算法求得的估算 值的方差反比于点数n。当n足够大时，估计的分 布近似为正态分布。 对于给定的迭代次数n，Crude算法的方差不会大 于HitorMiss的方差。但不能说，Crude算法总是 优于HitorMiss。因为后者在给定的时间内能迭代 的次数更多。例如，计算π值时，Crude需计算 平方根，而用投镖算法darts时无需计算平方根。 §2.2 数字积分 (计算定积分的值) 3.141855, 3.141422, 3.141434 1 3.141662, 3.141486, 3.141527 hit n crude = 亿 ( ) b a f x dx 2 ( ) b a f x dx
§22数字积分(计算定积分的值) 3.确定的算法 梯形算法 将区间分为n-1个子区间,每个子区间内的长度为6 积分值=δ(f(aδ)+f(a+2δ)+..+ f(a)+f(b Trapezoid〔,n,a,b){ ∥假设n≥2 deta←(b-a)/(n-1) sum←(f(a)+f(b)/2; for x +a+delta step delta to b-delta do sum←sum+f(x) return sun× delta
27 3. 确定的算法 梯形算法 将区间分为n-1个子区间，每个子区间内的长度为δ， Trapezoid (f, n, a, b) { // 假设 n ≥ 2 delta ← (b-a)/(n-1); sum ← (f(a) + f(b))/2; for x ← a+delta step delta to b – delta do sum ← sum + f(x) return sum × delta; } §2.2 数字积分 (计算定积分的值) f (a) f (b) = f a f a 2 2 + 积分值 ( ( + )+ ( + )+...+ )
922数字积分(计算定积分的值 3.确定的算法 当n=100,T=3.140399 当n=1,000,T=3141555 当n=10,000,T=3141586 当n=100,000T=3141593 般地,在同样的精度下,梯形算法的迭代次数少于Mc 积分,但是 ①有时确定型积分算法求不出解:例如, f(x=sin ((100 )! Tix),I f(rkdr-I 但若用梯形算法,当2≤n≤101时,返回值是0。若用 MC积分则不会发生该类问题,或虽然发生,但概率小 得多
28 3. 确定的算法 当n=100, π=3.140399 当n=1,000, π=3.141555 当n=10,000, π=3.141586 当n=100,000, π=3.141593 一般地，在同样的精度下，梯形算法的迭代次数少于MC 积分，但是 ① 有时确定型积分算法求不出解：例如， f(x)=sin2 ((100)! πx)， 。 但若用梯形算法，当2 ≤n≤101时，返回值是0。若用 MC积分则不会发生该类问题，或虽然发生，但概率小 得多。 §2.2 数字积分 (计算定积分的值) 1 0 1 ( ) 2 f x dx =
922数字积分(计算定积分的值 ②多重积分 在确定算法中,为了达到一定的精度,采样点的 数目随着积分维数成指数增长,例如,一维积分若有 100个点可达到一定的精度,则二维积分可能要计算 1002个点才能达到同样的精度,三维积分则需计算 1003个点。(系统的方法) 但概率算法对维数的敏感度不大,仅是每次迭代 中计算的量稍增一点,实际上,MC积分特别适合用 于计算4或更高维数的定积分。 若要提高精度,则可用混合技术:部分采用系统 的方法,部分采用概率的方法
29 ② 多重积分 在确定算法中，为了达到一定的精度，采样点的 数目随着积分维数成指数增长，例如，一维积分若有 100个点可达到一定的精度，则二维积分可能要计算 1002个点才能达到同样的精度，三维积分则需计算 1003个点。(系统的方法) 但概率算法对维数的敏感度不大，仅是每次迭代 中计算的量稍增一点，实际上，MC积分特别适合用 于计算4或更高维数的定积分。 若要提高精度，则可用混合技术：部分采用系统 的方法，部分采用概率的方法 §2.2 数字积分 (计算定积分的值)
§23概率计数 上一节可以认为,数字概率算法被用来近似 个实数,本节可用它们来估计一个整数值。例 如,设X为有限集,若要求X的势,则当X较大 时,枚举显然不现实。 1.问题:随机选出25人,你是否愿意赌其中至少有 两个人生日相同吗?直觉告诉我们,一般人都不 愿意赌其成立,但实际上成立的概率大于50%
30 上一节可以认为，数字概率算法被用来近似 一个实数，本节可用它们来估计一个整数值。例 如，设X为有限集，若要求X的势|X|，则当X较大 时，枚举显然不现实。 1. 问题：随机选出25人，你是否愿意赌其中至少有 两个人生日相同吗？直觉告诉我们，一般人都不 愿意赌其成立，但实际上成立的概率大于50%。 §2.3 概率计数