算法设计与分析-求解递归方程.ppt

递推方程求解
递推方程定义
给定数列f(0),f(1),…,f(n), 一个把f(n)和某些f(i),
0i<n,联系起来的等式称为递推方程
给定关于f(n)的递推方程和初值,求f(n)称为解递推方程
求解方法
公式法换元法
迭代归纳法差消法
Master定理
1. 常系数线性齐次递推方程的求解(公式法)
标准形式:k阶
求解步骤:
(1)求出特征方程的k个根
(2)如果没有重根,则该递推方程的通解为
如果有重根,如果q是e重特征根,通解对应于根q的部分为
整个通解为各个不等的特征根的对应部分之和
(3)代入初值确定待定常数。
例6 i数列
解:x2-x-1 =0 的根为
,
递推方程的通解为
带入初值得
解得
例7 H(n)+H(n-1)-3H(n-2)-5H(n-3)-2H(n-4) = 0
H(0) = 1, H(1) = 0, H(2) = 1, H(3) = 2
特征方程 x4+x3-3x2-5x-2 = 0 , 特征根-1,-1,-1,2,
通解为
解得
解为
常系数线性非齐次递推方程求解(公式法)
标准形
通解为对应的齐次通解加上特解

特解的函数形式依赖于f(n)
求解的关键是用待定系数法确定一个特解H*(n)
f(n)为n的t次多项式,一般H*(n)也为n的t次多项式
例8 求an +5an-1 +6an-2 = 3n2 的通解
设 an* = P1n2 + P2n + P3 ,
代入得
P1n2+P2n+P3+5[P1(n-1)2+P2(n-1)+P3]+6[P1(n-2)2+P2(n-2)+P3]=3n2
从而得到方程组
12P1 = 3
-34P1+ 12P2 = 0
29P1 – 17P2 + 12P3 = 0
通解为
例10 Hanoi塔
H(n) = 2 H(n-1)+1
设 H*(n) = P
P = 2 P + 1 , P = -1
H(n) = A 2n –1
代入初值
H(1) = 1
得 A = 1
解为 H(n) = 2n –1
f(n)为指数函数n,特解也为指数形式
若不是特征根,则特解为H*(n) = Pn
若是e重特征根,则特解为Pnen
例13 H(n) +5H(n-1) +6H(n-2) = 424n
令 H*(n) = P 4n ,
代入得
P 4n + 5P 4n-1 + 6P 4 n-2 = 424n
42P = 4216, P =16
通解为 H(n) = C1(-2)n + C2(-3)n + 4n+2
H(n) – 5H(n-1) + 6H(n-2) = 2n
求特解
2为1重根
令 H*(n) = Pn 2n ,
代入得
Pn2n – 5 P(n-1) 2n-1 + 6 P(n-2) 2n-2 = 2n
解得 P= -2
H*(n) = -n 2n+1
2. 转化成常系数线性递推方程求解---换元法
例11
令
代入得
bn =2 bn-1 +1,
b0 = 4
解得