Algorithm 版 (精华区)

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

递归方程组解的渐进阶的求法——差分方程法
这里只考虑形如：
T(n)=c1T(n-1)+c2T(n-2)+…+ ckT(n-k)+f(n)，n≥k (6.18)
的递归方程。其中ci (i=l，2，…，k)为实常数，且ck≠0。它可改写为一个线性常系数
k阶非齐次的差分方程：
T(n)-c1T(n-1)- c2T(n-2)-…-ckT(n-k)=f(n)，n≥k (6.19)
(6.19)与线性常系数k阶非齐次常微分方程的结构十分相似，因而解法类同。限于篇幅，
这里直接给出(6.19)的解法，略去其正确性的证明。
第一步，求(6.19)所对应的齐次方程：
T(n)-c1T(n-1)- c2T(n-2)-…-ckT(n-k)=0 (6.20)
的基本解系：写出(6.20)的特征方程：
C(t)=tk-c1tk-1-c2tk-2 -…-ck=0 (6.21)
若t=r是(6.21)的m重实根，则得(6.20)的m个基础解rn，nrn，n2rn，…，nm-1rn；若ρ
eiθ和ρe-iθ是(6.21)的一对l重的共扼复根，则得(6.20)的2l个基础解ρncosnθ，ρ
nsinnθ，nρncosnθ，nρnsinnθ，…，nl-1ρncosnθ，nl-1ρncosnθ。如此，求出
(6.21)的所有的根，就可以得到(6.20)的k个的基础解。而且，这k个基础解构成了(6.2
0)的基础解系。即(6.20)的任意一个解都可以表示成这k个基础解的线性组合。
第二步，求(6.19)的一个特解。理论上，(6.19)的特解可以用Lagrange常数变易法得到
。但其中要用到(6.20)的通解的显式表达，即(6.20)的基础解系的线性组合，十分麻烦
。因此在实际中，常常采用试探法，也就是根据f(n)的特点推测特解的形式，留下若干
可调的常数，将推测解代人(6.19)后确定。由于(6.19)的特殊性，可以利用迭加原理，
将f(n)线性分解为若干个单项之和并求出各单项相应的特解，然后迭加便得到f(n)相应
的特解。这使得试探法更为有效。为了方便，这里对三种特殊形式的f(n)，给出(6.19)
的相应特解并列在表6-1中，可供直接套用。其中pi，i=1,2,…,s是待定常数。
表6-1 方程(6.19)的常用特解形式
f(n)的形式  条    件  方程(6.19)的特解的形式
an  C(a)≠0
a是C(t)的m重根
ns  C(1)≠0
1是C(t)的m重根
nsan  C(a)≠0
a是C(t)的m重根
第三步，写出(6.19)即(6.18)的通解
 (6.22)
其中{Ti(n)，i=0,1,2,…,n}是(6.20)的基础解系，g(n)是(6.19)的一个特解。然后由(
6.18)的初始条件
T(i)=Ti ，i=1,2,…,k-1
来确定(6.22)中的待定的组合常数{ai}，即依靠线性方程组
或
解出{ai}，并代回(6.22)。其中βj=Tj-g(j)，j=0,1,2,…,k-1。
第四步，估计(6.22)的渐近阶，即为所要求。
下面用两个例子加以说明。
例l 考虑递归方程
它的相应特征方程为：
C(t)=t2-t-1=0
解之得两个单根和。相应的(6.20)的基础解系为{r0n，r1n}。相应的(6.19)的一个特解
为F*(n)=-8，因而相应的(6.19)的通解为：
F(n)=a0r0n +a1r1n- 8
令其满足初始条件，得二阶线性方程组：
或
或
解之得，，从而
于是
。
例2 考虑递归方程
T(n)=4T(n-1)-4T(n-2)+2nn (6.23)
和初始条件T(0)=0，T(1)=4/3。
它对应的特征方程(6.21)为
C(t)=t2-4t+4=0
有一个两重根r =2。故相应的(6.20)的基础解系为{2n，2nn}。由于f(n)=2nn，利用表6
-1，相应的(6.19)的一个特解为
T*(n)=n2(p0+p1n)2n，
代人(6.23)，定出p0=1/2，p1=1/6。因此相应的(6.19)的通解为：
T(n)=a02n+a1n2n+n2(1/2+n/6)2n，
令其满足初始条件得a0=a1=0，从而
T(n)=n2(1/2+n/6)2n
于是T(n)=θ(n32n)。

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

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