求解递归方程方法.ppt

递推方程求解 递推方程定义 给定数列f(0),f(1),…,f(n), 一个把f(n)和某些f(i)， 0?in，联系起来的等式称为递推方程 给定关于f(n)的递推方程和初值，求f(n)称为解递推方程 求解方法 公式法 换元法 迭代归纳法 差消法 Master定理 ;1. 常系数线性齐次递推方程的求解（公式法） 标准形式：k阶;例6 Fibonacci数列 ;例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)为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 ;例12 归并排序 T(n) = 2 T( n/2 ) + n-1 , n = 2k T(2) =1 H(k)= 2H(k-1) +2k - 1 H(1) = 1 令 H*(k) = P1k2k +P2 , 解得 P1=P2=1, H*(k) = k2k +1 通解 H(k)=C 2k + k2k +1, 代入初值，得 C= -1 H(k) = - 2k + k2k +1 T(n) = n log n – n +1 ;3．叠代归纳法 例13 H(n) = (4n-6) H(n-1) H(1) =1 ;4．差消法----化简递推方程 例14 求解递推方程 ;由叠代得 ;5.Master定理 ;例20