Algorithm 版 (精华区)

发信人: Lerry (想不开·撞树), 信区: Algorithm
标  题: 递归方程组解的渐进阶的求法——母函数法
发信站: 哈工大紫丁香 (2002年03月22日14:42:07 星期五), 站内信件

递归方程组解的渐进阶的求法——母函数法
关于T(n)的递归方程的解的母函数通常设为：
 (6.24)
当(6.24)右端由于T(n)增长太快而仅在x=0处收敛时可另设
 (6.25)
如果我们可以利用递归方程建立A(x)的一个定解方程并将其解出，那么，把A(x)展开成
幂级数，则xn或xn/n!项的系数便是所求的递归方程的解。其渐近阶可接着进行估计。
下面举两个例子加以说明。
例1 考虑线性变系数二阶齐次递归方程
(n-1)T(n)=(n-2)T(n-1)+2T(n-2) ，n≥2 (6.26)
和初始条件T(0)=0，T(1)=1。根据初始条件及(6.26)，可计算T(2)=0，T(3)=T(1)=1。
设{T(n)}的母函数为：
由于T (0)=T (2)=0，T(1)= 1，有 ：
令 B(x)= A (x)/x，即：
那么：
利用(6.26)并代入T (3)= 1，得
即
两边同时沿[0,x]积分，并注意到B(0)=1，有：
把B(x)展开成幂级数，得
从而
最后得
例2 考虑线性变系数一阶非齐次递归方程
D(n)=nD(n-1)+(-1)n  n≥1 (6.27)
及初始条件D (0)= 1
很明显D(n)随n的增大而急剧增长。如果仍采用(6.24)形式的函数，则(6.24)的右端可能
仅在x=0处收敛，所以这里的母函数设为：
用xn/n!乘以(6.27)的两端，然后从1到∞求和得：
化简并用母函数表达，有：
A(x) -1= xA(x)+e-x-1
或
(1-x)A(x)=e-x
从而
A(x)=e-x/(1-x)
展成幂级数，则：
故

--
　　不在乎天长地久，就怕你从来没有！

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 天外飞仙]