当前位置:首页 >> 学科竞赛 >>

12 Chap-9-Asymptotics


北京航空航天大学计算机学院

具体数学
Concrete Mathematics
赵启阳
2015年12月9日星期三

9.4 两个渐进技巧 Two asymptotic tricks

2015/12/9

2

技巧一:自助法
? 自

助法( bootstrapping )的主要思想: (1)构造关于目标量的递归式; (2)使用递归式,估计一个比较粗略的结果; (3)将粗略估计代入,得到更精确的结果 ? “自助法”名称的由来——同时也是一个重要 的统计学方法的命名

Pull ourselves up by our bootstraps
2015/12/9 3

自助法的例子
? 问题:当n趋向于无穷时,函数 ? zk ? G ( z ) ? exp ? ?? k2 ? ? ? k ?1 ? 在展开成幂级数之后,其中zn的系数gn的渐进值 是什么? ? 对函数G求关于z的导数,得到
k ?1 k ?1 ? ? ? ? ? z z ? n ?1 n? G?( z ) ? ? ng n z ? ? ? ? G( z ) ? ? ? ? ? ? gn z ? n ?0 ? ? k ?1 k ? ? k ?1 k ? ? n?0 ?

2015/12/9

4

自助法的例子
? 令两边的zn-1的系数相等,得到
gk ngn ? ? 0? k ? n n ? k

? 这个式子是递归式。初始条件为g0=1:
n
gn

0
1

1
1

2
3/4

3
19/36

4
107/288

5
641/2400

6
51103/259200

? 从上面看不出什么规律,到今天为止gn的封闭 形式解似乎还没有找到,那就渐进吧…..
2015/12/9 5

自助法的例子
? 首先很容易用归纳法得到所有的gn都有 0 ? gn ? 1 ? 这是第一个粗略估计:gn=O(1),代入到递归式
O(1) ngn ? ? ? H nO(1) ? O?log n ? 0? k ? n n ? k

? 因此有

? log n ? g n ? O? ?, 这里n ? 1 ? n ?

2015/12/9

6

自助法的例子
? 在此基础上,得到对于n>=1都有
?1? ? log n ? ? 1 ? log n ? g n ? O? ? ? O? ? ? O? ?, 这里n ? 1 ?n? ? n ? ? n ?

? 代入到递归式,得到
? 1 ? log k ? O? ? 1 O?log n ? k ??1? ngn ? ? ? ? ? n 0? k ? n n?k n 0? k ? n k ( n ? k )

1 1 ? O?log n ? 1 2 1 ?1 ? ? ?? ? ? ? H n ?1O(logn) ? O(logn) 2 ? n 0? k ? n ? k n ? k ? n n n n
2

log n ? ? 因此有 g n ? O? ? ? ? n ?
2015/12/9

7

自助法的例子
?
? log n ? ? log n ? g n ? O? g n ? O? ? ? 在前面成功地由 得到了 n n ? ? ? ?
2

,因 此这里有一个很自然的问题,能否这样一直下 m 去得到 ? log n ?
g n ? O? ? , m为任意正整数 ? n ?

? 答案是不能。在下一次“自助”的时候会有
? 1 ? 1 1 1 1 ? ? ? ? 2 ? ?? 2? 2 ? 2 ? 2 ? ? ? k ( n ? k ) k ( n ? k ) nk n k n n ? k 0? k ? n 0? k ? n 0? k ? n ? ? 1 ( 2) 2 ?1? ? H n ?1 ? 2 H n ?1 ? ?? ? n n ?n?

1? ? 因此无法对gn再得到比 ?? ? 2 ? 等级更低的估计。 ?n ?
2015/12/9 8

自助法的例子
? 在得到上述结论之后,可以再使用截取最大部 分的技巧得到最终结果
ngn ? gk 1? ? 1 ? g ? ? ? ? k? n n ? k n ? ? 0? k ? n 0? k ? n kgk 1 ?1 ? 1 ? ? ? gk ? ? gk ? ? ? n n ? k ? n 0? k ? n n ? k ? n 0? k

1

2

3

? 这里第一个求和式为

?1 1 1 ? g ? G ( 1 ) ? exp ? ? ? ... ? ??e 6 ? k ?1 4 9 ? 0? k

?2

? 第二个求和式为第一个求和式的尾部
2 m ?1 2 ? ? ?log n ?2 ? ?log k ?2 ? ? ?log n ?2 ? log k ? ? log n ? ? ? O? ? ? O? g k ? O? ?? ?? ? ? ? 2 2 2 2 ? ? ? ? ? m m ? 1 k k (k ? 1) ? n?k n? k 1? m n ? k ? n ? n?k k ? ? n ? ? n ? 2 2 2 ? ?log n ?2 ? ?log n ?2 ?log n ?2 ? ?log n ?2 ? ? ? m ? 1? ?log n ? ? m ? 1? ? ? ? O? ? ? O? ? ? O? ? ? ? m 2 m ?1 ? n2 ? 1 ? ? ? ? ? n n n n n ?m 1? m ? ? ? ? ? ?

?

?

2015/12/9

9

自助法的例子
? 第三个求和式有
2 ? ? ?log n ?3 ? ? kgk log n ? ? ? ? O? ? ? O? ? ? ? ? ? ? 0? k ? n n ? k ? 0? k ? n k ?n ? k ? ? ? n ?

? 因此得到

?2

e ? log n ? gn ? ? O? ? n ? n ?
6

3

? 再将代入到递归式中,并使用自助法得到
?2

e6 ? log n ? gn ? ? O? 3 ? n ? n ?
2015/12/9 10

技巧二:尾部替换
? 尾部替换的主要思想:
(1)首先将求和式拆分成两个不重叠的范围Dn和Tn,其中 Dn为主要部分,Tn对总和的贡献很小 (2)找到对Dn中的k都成立的式子(不必要求对Tn也成立) ak(n)=bk(n)+O(ck(n)) (3)再去证明下面的三个式子都很小: ? ( n) ? ? a k ( n)
a k?Tn

? ( n) ? ? b
b k?Tn

k

( n)

(4)最后得到估计结果
k?Dn ?Tn
2015/12/9

? ( n) ? ? c ( n)
c k?Dn k

? a (n) ? ?b (n) ? O?? (n)?? O?? (n)?? O?? (n)?
k k?Dn ?Tn k a b c
11

尾部替换的例子
? 例如对于
kgk 1 ?1 ? 1 ngn ? ? ? g k ? ? g k ? ? ? n n ? k ? n 0? k ? n n ? k ? n 0? k

? 可以设置
ak (n) ? ?0 ? k ? n? gk g kgk , bk (n) ? k , ck (n) ? n?k n n?n ? k ?

? 其求和范围是Dn={0, 1, …, n - 1},Tn={n, n + 1, …} ? 并且有 ? ?log n ? ? ? ?log n ? ? ? ? ? ? ( n ) ? 0 , ( n ) ? O , ( n ) ? O ? ? ? n ?? ? n ?
2 3 a b

? 很容易导出gn的最终估计结果。
2015/12/9 12

?

2

?

c

?

2

?

另外一个尾部替换的例子
? 问题:估计
ln n ? 2k Ln ? ? k! k ?0

?

?

? 很显然,最小的那些k对求和的贡献是主要的。 因为阶乘在分母上!!! ? 在k很小的时候(0 ? k ? ?lg n? ),有
k 2k 3k ? ? 2 2 2 k ? ln n ? 2 ? ln n ? ? 2 ? O? 3 ? ? n 2n ?n ?

?

?

2015/12/9

13

另外一个尾部替换的例子
? 接下来使用尾部替换法,首先构造
ln n ? 2 k ak ( n) ? k! 2k 4k ln n ? ? 2 n 2n bk (n) ? k! 8k ck ( n ) ? 3 n k!

?

?

? 这里

? Dn ? ?0,1,...,?lg n? ?1?, Tn ? ??lg n?, ?lg n? ? 1,...
14

2015/12/9

另外一个尾部替换的例子
? 首先分析最简单的
8k 8k e8 ?? 3 ? 3 ?c (n) ?k? 3 n ?Dn n k! k ?0 n k!

? 因此可用O(n-3)代替。 ? 然后再有
ln n ? 2k ? 4 k bk (n) ? ? ?b (n) ? k ?? k! k ? ?lg n ? ?lg n ? ? n2 ? ln n ? 2 ?lg n ? ? 4 ?lg n ? 4k ? ? ? ?? ? ? ? k ? 0 k! ?lg n?! ? ?lg n?! ?

? 由于 ?lg n?! 比n的任何幂的增长速度都快,因此 这个很小的误差不超过 ? (n) ?O?n ?
?3 c

2015/12/9

15

另外一个尾部替换的例子
? 而原来的尾部误差

?a (n) ?

k ? ?lg n ?

? ak (n) ?

k ? ln n ? k! k ? ?lg n ?

甚至比 ?b (n) 还要小,因此也是O(n-3)的量级。 ? 最后再计算下面求和式的封闭形式
2k 4k ln n ? ? 2 n 2n bk (n) ? ? ? k! k ?0 k ?0 1 1 2k 1 ? ln n? ? ? ? 2 n k ? 0 k! 2 n k ? 0 k! e2 e4 ? e ln n ? ? 2 n 2n
2015/12/9 16

4k ? k ? 0 k!

另外一个尾部替换的例子
? 组合在一起得到所要求的渐进估计
ln n ? 2k e2 e4 ?1? ? e ln n ? ? 2 ? O? 3 ? ? k! n 2n ?n ? k ?0

?

?

? 事实上,对任意的正整数m,都可以使用上述 方法得到
ln n ? 2 ? 1 ? k ?1 e ? e ln n ? ? ?? 1? ? O? m ? ? k k! kn ?n ? k ?0 k ?1
k m ?1

?

?

2k

? 这相当于级数截断的方法。

2015/12/9

17

6th Homework
? 练习题(不必上交) 9.2,9.7,9.20,9.32,9.54

2015/12/9

18


相关文章:
更多相关标签: