线性常系数非齐次递推关系

1、2.4 线性常系数非齐次递推关系线性常系数非齐次递推关系主讲教师主讲教师 数学学院魏毅强教授数学学院魏毅强教授联系电话联系电话Email : Yiqiang Wei 22.4 线性常系数非齐次递推关系线性常系数非齐次递推关系2.4.1 定义定义定义定义2.4.1 形如形如 an+c1an-1+c2an-2+ckan-k=bn, (nk-1)( (其中其中c1,c2,ck是常数，是常数，ck0， bn0， k是正整数是正整数) )的递推关的递推关系称系称为为k k阶线性常系数非齐次递推关系阶线性常系数非齐次递推关系。称称a0=d0，a1=d1，ak-1=dk-1 为为初

2、值条件初值条件。例如例如 Hanoi问题问题满足满足hn-2hn-1=1，(n1)为为1 1阶线性常系数非齐阶线性常系数非齐次递推关系次递推关系an-3an-1-2an-2+4an-3=n3n 是三阶线性常系数非齐次递推关系是三阶线性常系数非齐次递推关系例如，例如，an+3an-1+2an-2=2n 是二阶线性常系数非齐次递推关系是二阶线性常系数非齐次递推关系Yiqiang Wei 32.4 线性常系数非齐次递推关系线性常系数非齐次递推关系定义定义2.3.2 给定给定k k阶线性常系数齐次递推关系阶线性常系数齐次递推关系an+c1an-1+c2an-2+ckan-k=0, (ck0，nk-1)

3、记记 C(x)=xk+c1xk-1+c2xk-2+ck 称称为线性常系数齐次递推关为线性常系数齐次递推关系的系的特征多项式特征多项式，而称，而称 C(x)=0 为为特征方程特征方程。例如例如 Fibonacci数列数列所满足的所满足的2 2阶线性常系数齐次递推关系阶线性常系数齐次递推关系 Fn-Fn-1-Fn-2=0，(n2)的特征方程的特征方程为为x2-x-1=0。例如，例如，an+3an-1+2an-2=0 的特征多项式为的特征多项式为 x2+3x+2=0 an-3an-1-2an-2+4an-3=0 的特征多项式为的特征多项式为 x3-3x2-2x+4=0Yiqiang Wei 4根据递

4、推关系，有根据递推关系，有nnknknnnnkkkkkkkkkkkkkkxbacacacaxxbacacacaxxbacacacax)()()(221111112111022112.4.2 线性常系数非齐次递推关系的母函数方法线性常系数非齐次递推关系的母函数方法设设 an的母函数为的母函数为G(x)nnxaxaaxG10)(nknknnnbacacaca2211设设an满足满足k阶线性常系数非齐次递推关系阶线性常系数非齐次递推关系2.4 线性常系数非齐次递推关系线性常系数非齐次递推关系Yiqiang Wei 5将这些式子两边分别相加，得到将这些式子两边分别相加，得到 knnnkkkikiiii

5、ixbxGxCxaxGxCxaxG10201即即 knnnkjjkiiijjkkxbxaxCxGxCxCxC10102211其中其中 C0=1令令 10100kjjkiiijjxaxCxP为次数不超过为次数不超过k-1的多项式的多项式2.4 线性常系数非齐次递推关系线性常系数非齐次递推关系为为k次多项式次多项式 knnnxbxP1kkkxCxCxCx 111C(x)也称为特征多项式也称为特征多项式Yiqiang Wei 6如果如果C(x)=0 在复数域中有在复数域中有k个根。设个根。设 kkkkxxxxCskskks212121则则 skskkkkkxxxxCxCxCx1111121211于是

6、于是)()()(1101xPxPxGxCxCkk2.4 线性常系数非齐次递推关系线性常系数非齐次递推关系 xxxxP xxxxPxGsskskkkskk 111)(111)()(2121211210Yiqiang Wei 7 xxxxP xxxxPxGsskskkkskk 111)(111)()(2121211210它的第一项是有理式，对应齐次递推关系，可进行分解它的第一项是有理式，对应齐次递推关系，可进行分解并展开幂级数。并展开幂级数。 xxxxPxGskskk 111)()(212100 xAsikjjiiji 11)1( 01111)(ksikjkkijjkijixCA 其中其中Aij为

7、待定系数为待定系数2.4 线性常系数非齐次递推关系线性常系数非齐次递推关系Yiqiang Wei 8它的第二项对应非齐次递推关系的非齐次项，首先求出分子它的第二项对应非齐次递推关系的非齐次项，首先求出分子非齐次项的级数和，可进行展开幂级数。非齐次项的级数和，可进行展开幂级数。 111)()(212111skskkxxxxPxG 0kkkx 从而从而 01111)(G(x)ksikjkkkijjkijixCA比较比较xk的系数，得的系数，得0,1111 nCAannijjnsikjijni2.4 线性常系数非齐次递推关系线性常系数非齐次递推关系Yiqiang Wei 92.4 线性常系数非齐次递

8、推关系线性常系数非齐次递推关系例例2.4.1 求求an-an-1-6an-2=54n , a0=5, a1=3 的解的解 设母函数为设母函数为 解解0)(nnnxaxG代入递推关系有代入递推关系有 22110)456()(nnnnnxaaxaaxG202145635nnnnnnnnnxxaxxaxxxxxGxxGxx4145)(6)5)(35222xxxxGxx418025)()61 (22Yiqiang Wei 102.4 线性常系数非齐次递推关系线性常系数非齐次递推关系)41)(21)(31(80)21)(31(25)(2xxxxxxxxG xxx4134021567311576 000)

9、4(340)2(1576)3(567kkkkkkxxx nnnnnx )4340)2(57631567(0 所求解为所求解为 0,4340)2(57631567 na nnnnYiqiang Wei 112.4 线性常系数非齐次递推关系线性常系数非齐次递推关系例例2.4.2 求求an-an-1-6an-2=3n , a0=5, a1=2 的解的解 设母函数为设母函数为 解解0)(nnnxaxG代入递推关系有代入递推关系有 22110)36()(nnnnnxaaxaaxG20213625nnnnnnnnnxxaxxaxxxxxGxxGxx313)(6)5)(25222xxxxGxx31935)(

10、)61 (22Yiqiang Wei 122.4 线性常系数非齐次递推关系线性常系数非齐次递推关系)21 ()31 (9)21)(31 (35)(22xxxxxxxG2)31 (2515312536212574xxx 1100)3(2515)3(2536)2(2574 nnnnnnxnxxnnnnnxn)3)1(251532536)2(2574( 0所求解为所求解为 0,3)1(251532536)2(2574a nnnnnn0,35332551)2(2574nnnnnYiqiang Wei 132.4 线性常系数非齐次递推关系线性常系数非齐次递推关系2.4.3 线性常系数非齐次递推关系的待定

11、系数法线性常系数非齐次递推关系的待定系数法nknknnnbacacaca2211由母函数方法可知由母函数方法可知k阶线性常系数非齐次递推关系阶线性常系数非齐次递推关系nnsisktntnstnsCAa 111的解的解而齐次递推关系的解可由特征根方法解得，所以我们只而齐次递推关系的解可由特征根方法解得，所以我们只要求解非齐次递推关系的一个特解即可。要求解非齐次递推关系的一个特解即可。解可表示为齐次关系的解与非齐次关系的解之和解可表示为齐次关系的解与非齐次关系的解之和Yiqiang Wei 14 待定系数法待定系数法1 1)(nqnrmknn 01111BnBnBnBnqmmmmm其中其中qm(n

12、)为系数待定的为系数待定的重特征根是不是特征根krkrk02.4 线性常系数非齐次递推关系线性常系数非齐次递推关系如果自由项如果自由项 bn=rnpm(n), 其中其中pm(n)为为n的的m次多项式次多项式, 则可设则可设非齐次递推关系的解为非齐次递推关系的解为其中其中k为为r作为特征根的个数，即作为特征根的个数，即Yiqiang Wei 15例例2.4.3 求求an-an-1-12an-2=3n , a0=3, a1=26 的解的解 特征方程特征方程 x2-x-12=0根为根为: : x=4 x=-3故齐次关系的通解为故齐次关系的通解为0,) 3(421nAAannn解解2.4 线性常系数非

13、齐次递推关系线性常系数非齐次递推关系由于自由项由于自由项: : bn=3n , 所以可设特解为所以可设特解为 a*n=B3n 代入关系式代入关系式 B3n-B3n-1-12B3n-2=3n 解得解得 B=-3/2Yiqiang Wei 162.4 线性常系数非齐次递推关系线性常系数非齐次递推关系由初值条件由初值条件23321AA323) 3(42621AA解得解得142574421AA，所求解为所求解为0,323) 3(14254744nannnn故非齐次关系的通解为故非齐次关系的通解为0,323) 3(421nAAannnnYiqiang Wei 17例例2.4.4 求求an+3an-1-1

14、0an-2=2n (n+5)的通解的通解 2.4 线性常系数非齐次递推关系线性常系数非齐次递推关系特征方程特征方程 x2+3x-10=0根为根为: : x=-5 x=2故齐次关系的通解为故齐次关系的通解为0,)5(221nAAannn解解由于自由项由于自由项: : bn=2n (n+5) , 所以可设特解为所以可设特解为a*n=n1(B0+B1n)2n 代入关系式代入关系式 n(B0+B1n)2n+3(n-1)(B0+B1(n-1)2n-1 -10 (n-2)(B0+B1(n-2)2n-2=2n(n+5) Yiqiang Wei 18解得解得,71,498710BB所求解为所求解为nnnnnn

15、AAa2)714987()5(22212.4 线性常系数非齐次递推关系线性常系数非齐次递推关系Yiqiang Wei 19 待定系数法待定系数法2 22.4 线性常系数非齐次递推关系线性常系数非齐次递推关系sin)(sin)(nnhnnqnrmmknn 01111BnBnBnBnqmmmmm重特征根是不是特征根kirkirk)sin(cos)sin(cos0其中其中qm(n)与与h(n)为系数待定的为系数待定的如果自由项如果自由项 bn=rnpm(n)sin或或bn=rnpm(n)cos, 其中其中pm(n)为为n的的m次多项式次多项式, 则可设非齐次递推关系的解为则可设非齐次递推关系的解为其

16、中其中k为为r作为特征根的个数，即作为特征根的个数，即 01111CnCnCnCnhmmmmmYiqiang Wei 202.4 线性常系数非齐次递推关系线性常系数非齐次递推关系例例2.4.5 求求an-3an-1+2an-2=3sin(n/2) , a0=0, a1=1 的解的解 特征方程特征方程 x2-3x+2=0根为根为: : x=1 x=2故齐次关系的通解为故齐次关系的通解为0,2121nAAannn解解由于自由项由于自由项: : bn=3sin(n/2) , 所以可设特解为所以可设特解为 a*n=Bcos(n/2) +Csin(n/2)Yiqiang Wei 21故通解为故通解为2,

17、2sin1032cos109221nnnAAann由初值条件由初值条件21109AA 210321AA 解得解得10151A1032A所求解为所求解为0,2sin1032cos1092106101nnnann2.4 线性常系数非齐次递推关系线性常系数非齐次递推关系代入关系式解得代入关系式解得 B=-9/10， C=-3/10 Yiqiang Wei 22总之：总之：nkknnBnBBa)(1110若若是是特征方程特征方程C(x)=0的单根，则递推关系的解中含有项的单根，则递推关系的解中含有项nnaaA若若是特征方程是特征方程C(x)=0的的k重根，则递推关系的解中含有项重根，则递推关系的解中含

18、有项若若1 1, ,2 2是一对是一对k k重共轭复根，且重共轭复根，且)sin(cos12iaa则递推关系的解中含有项则递推关系的解中含有项nnCnCCnnBnBBankknkknsin)(cos)(111011102.3 线性常系数齐次递推关系线性常系数齐次递推关系Yiqiang Wei 232.4 线性常系数非齐次递推关系线性常系数非齐次递推关系2.4.3 线性常系数非齐次递推关系的齐次化方法线性常系数非齐次递推关系的齐次化方法例例2.4.6 求求an-an-1-6an-2=3n , a0=5, a1=2 的解的解 解解由由 an-an-1-6an-2=3n , an-1-an-2-6an-3=3n-1 ,相减得相减得由由 an-4an-1