线性常系数递推关系.ppt

《线性常系数递推关系.ppt》由会员分享，可在线阅读，更多相关《线性常系数递推关系.ppt（41页珍藏版）》请在三一办公上搜索。

1、2.3 线性常系数递推关系,线性常系数齐次递推关系 线性常系数非齐次递推关系,1.线性常系数齐次递推关系,确定一个数列an的最常用的方法是：,(1)给出一般项an的表达式;,(2)得到该数列的母函数;,(3)建立数列所满足的递推关系。,一个r-阶递推关系定义为：有正整数r 以及一个r+1元函数F，使得对所有nr,有关系式,这样若已知这个数列的前r项a0,a1,ar-1(称为初始条件)，则可以通过递推关系逐项确定整个数列。,定义：如果序列an满足,如果b(n)=0，则称为齐次的，,否则称为非齐次的。,其中 都是常数，,则(1)称为一个k阶线性常系数递推关系，,(2)称为初始条件。,先考虑二阶线性

2、常系数齐次递推关系，即,令母函数为G(x)=a0+a1x+a2x2+，则,因此有,与分母相对应的方程 x2+bx+c=0 称为特征方程，它的根,称为特征根。,这样G(x)可以表示为：,(1)如果r1r2，则,下面要根据特征根来进行分类讨论。,因此通项表达式为：,其中常数A,B可以利用待定系数法确定，或者利用初始条件(A+B=a0,Ar1+Br2=a1)来确定。,(1)如果r1r2，且是一对共轭复根，则可以假设,这样就有：,定义两个新的待定常数：,则通项表达式为：,其中k1,k2由初始条件决定。,(2)如果r1=r2，则可以令r=r1=r2=-b/2，,因此通项表达式为：,其中常数C,D可以利用

3、初始条件来确定。,例如，若已知a0,a1，则,例1 求解递推关系：,特征方程为,因此通项表达式可以设为：,解得特征根为,代入初始条件有,因此通项表达式为：,例2 求解递推关系：,特征方程为,因此通项表达式可以设为：,解得特征根为,代入初始条件有,因此通项表达式为：,例3 Fibonacci数列：,特征方程为,因此通项表达式可以设为：,解得特征根为,代入初始条件有,因此通项表达式为：,例4 求解递推关系：,特征方程为,因此通项表达式可以设为：,解得特征根为,代入初始条件有,因此通项表达式为：,接下来讨论一般的k阶线性常系数齐次递推关系：,类似的，令母函数为G(x)=a0+a1x+a2x2+，则,

4、+),整理得,其中右端是次数不超过k-1次的多项式，设为P(x)。,定义,为特征方程，它在复数域内刚好有k个根，即,其中k1+ki=k。这些根称为特征根。,这样，等式左边的函数可以表示为：,即,(1)如果所有特征根都互不相同，则,下面同样要根据特征根来进行分类讨论。,因此通项表达式为：,其中常数A1,A2,Ak可以利用初始条件来确定。,(1)如果有一对共轭复根(重数都为1)，重复以前的讨论，不妨假设这一对共轭复根是,则an的通项表达式中对应于,的项为：,其中常数A1,A2和通项表达式中的其他常数一起由初始条件来决定。,(2)如果有重根，不妨假设a1是m重根，则母函数中对应于a1的项可以表示为,

5、因此通项表达式中对应于a1的部分为：,注意到C(j+n-1,n)=C(j+n-1,j-1)是n的j-1次多项式，因此这部分也可以表示为,例5 求下列n阶行列式的值dn：,特征方程为,根据行列式的性质有：,这是一个二重根，因此通项表达式可以设为：,解得特征根为,代入初始条件有,因此n阶行列式的值为：,例6 计算Sn=1+2+n。,显然有 Sn-Sn-1=n，但这不是一个齐次递推关系。,注意到 Sn-1-Sn-2=n-1，两式相减有,再次利用 两式相减得,这是一个三阶线性常系数齐次递推关系。,特征方程为,解得特征根为,这是一个三重根，因此可以设,代入初始条件有,因此有：,例7 计算Sn=12+22

6、+n2。,显然有 Sn-Sn-1=n2，Sn-1-Sn-2=(n-1)2，两式相减有,再次利用 两式相减得,特征方程为,解得特征根为,这是一个四重根，因此可以设,再次利用 两式相减得,代入初始条件有,因此有：,代入初始条件有,因此有：,另外一种更快的方法：由于已经知道Sn是三次多项式，因此可以假设,例8 计算Sn=13+23+n3。,显然有 Sn-Sn-1=n3，类似前面的讨论容易得到,特征方程为,解得特征根为,这是一个五重根，因此Sn是一个四次多项式，所以可以设,代入初始条件有,因此有：,可以令n=5做验证：S5=S4+53=225，,例9 求解递推关系：,特征方程为,因此通项表达式可以设为

7、：,解得特征根为,代入初始条件有,因此通项表达式为：,2.线性常系数非齐次递推关系,对于一个k阶线性常系数非齐次递推关系：,与一般的线性问题类似，它的通解可以表示为特解与对应的齐次问题通解的和，即,其中an*是非齐次递推关系的一个特解，而an是对应的齐次递推关系,的通解。,关于齐次递推关系的通解，我们已经讨论完全了。,因此关键在于如何得到非齐次递推关系的一个特解。,下面我们针对一些特殊的右端项来讨论如何得到特解。,例10 求递推关系：,的一个特解。,假设有如下形式的特解,代入原递推关系，并整理后可得,因此有,因此可以得到一个特解,解得,(1)一般来说，当右端项b(n)是n的k次多项式时，特解形

8、式也可以设为k次多项式，即,其中系数Ai由代入非齐次递推关系后确定。,例11 求递推关系 的一个特解。,假设有如下形式的特解,代入原递推关系，并整理后易有,但这是不可能的！,问题出在当1是原递推关系的特征根时，若把特解设为多项式，代入递推关系后，最高次会被消去。,回到上例，因此1是一重特征根，因此特解设为,代入原递推关系，并整理后可得,(2)当右端项b(n)是n的k次多项式时，若1是递推关系的t重特征根，则特解的次数要提高t次，即,易有A=B=7/2，即一个特解为：,例12 求递推关系：,的一个特解。,假设有如下形式的特解,代入原递推关系有,化简得42A=4216，即A=16。,因此可以得到一

9、个特解,例13 求递推关系：,的一个特解。,注意到2是递推关系的一个特征根，因此2n是对应齐次递推关系的解，即若把特解设为A2n，则代入递推关系后，左端为0，无法解出A。,代入原递推关系有,化简求得A=-2。,因此可以得到一个特解,因此可以设特解形式为：,(3)当右端项b(n)是常数乘以sn的形式时，若s是递推关系的t重特征根，则特解形式可以设为,其中系数A由代入非齐次递推关系后确定。,注意这包含了s不是特征根的情形，即t=0.,把上面三种情况综合在一起，我们有下面的结论：,若右端项b(n)=f(n)sn，其中f(n)是n的k次多项式，s是递推关系的t(t=0,1,2,)重特征根，则特解形式可

10、以设为,例14 求递推关系：,的通解。,显然特征根为-5,2，-7不是特征根，因此特解可设为,代入原递推关系解得,注意到对应齐次递推关系的通解为A(-5)n+B2n，因此原递推关系的通解为,其中A,B由初始条件确定。,例15 求递推关系：,的通解。,显然特征根为-5，2，2是1重根，因此特解可以设为,代入原递推关系解得,注意到对应齐次递推关系的通解为A(-5)n+B2n，因此原递推关系的通解为,其中A,B由初始条件确定。,例16 求Sn=12+22+n2。,显然Sn满足Sn-Sn-1=n2，这是一个非齐次递推关系。,由于1是递归关系的1重特征根，因此在设特解时需要把右端非齐次项中的多项式次数提高一次，即设,另一方面，对应齐次递推关系的通解为常数，因此Sn应该是一个三次多项式，即可设为,常数A,B,C,D代入初始条件即可确定。,同样的技巧可以用来计算Sn=13+23+n3等。,叠加原理：设右端项b(n)有如下形式：,则非齐次递推关系的一个特解为,其中ai是右端项为bi(n)时对应的特解。,例17 求递推关系：,的一个特解。,根据叠加原理，问题变为求当右端项分别为424n和2n时的特解，而这前面已经计算过了。因此特解为,