線性常系數(shù)非齊次遞推關(guān)系

1、2.4 線性常系數(shù)非齊次遞推關(guān)系線性常系數(shù)非齊次遞推關(guān)系主講教師主講教師 數(shù)學學院魏毅強教授數(shù)學學院魏毅強教授聯(lián)系電話聯(lián)系電話Email : Yiqiang Wei 22.4 線性常系數(shù)非齊次遞推關(guān)系線性常系數(shù)非齊次遞推關(guān)系2.4.1 定義定義定義定義2.4.1 形如形如 an+c1an-1+c2an-2+ckan-k=bn, (nk-1)( (其中其中c1,c2,ck是常數(shù)，是常數(shù)，ck0， bn0， k是正整數(shù)是正整數(shù)) )的遞推關(guān)的遞推關(guān)系稱系稱為為k k階線性常系數(shù)非齊次遞推關(guān)系階線性常系數(shù)非齊次遞推關(guān)系。稱稱a0=d0，a1=d1，ak-1=dk-1 為為初

2、值條件初值條件。例如例如 Hanoi問題問題滿足滿足hn-2hn-1=1，(n1)為為1 1階線性常系數(shù)非齊階線性常系數(shù)非齊次遞推關(guān)系次遞推關(guān)系an-3an-1-2an-2+4an-3=n3n 是三階線性常系數(shù)非齊次遞推關(guān)系是三階線性常系數(shù)非齊次遞推關(guān)系例如，例如，an+3an-1+2an-2=2n 是二階線性常系數(shù)非齊次遞推關(guān)系是二階線性常系數(shù)非齊次遞推關(guān)系Yiqiang Wei 32.4 線性常系數(shù)非齊次遞推關(guān)系線性常系數(shù)非齊次遞推關(guān)系定義定義2.3.2 給定給定k k階線性常系數(shù)齊次遞推關(guān)系階線性常系數(shù)齊次遞推關(guān)系an+c1an-1+c2an-2+ckan-k=0, (ck0，nk-1)

3、記記 C(x)=xk+c1xk-1+c2xk-2+ck 稱稱為線性常系數(shù)齊次遞推關(guān)為線性常系數(shù)齊次遞推關(guān)系的系的特征多項式特征多項式，而稱，而稱 C(x)=0 為為特征方程特征方程。例如例如 Fibonacci數(shù)列數(shù)列所滿足的所滿足的2 2階線性常系數(shù)齊次遞推關(guān)系階線性常系數(shù)齊次遞推關(guān)系 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根據(jù)遞

4、推關(guān)系，有根據(jù)遞推關(guān)系，有nnknknnnnkkkkkkkkkkkkkkxbacacacaxxbacacacaxxbacacacax)()()(221111112111022112.4.2 線性常系數(shù)非齊次遞推關(guān)系的母函數(shù)方法線性常系數(shù)非齊次遞推關(guān)系的母函數(shù)方法設(shè)設(shè) an的母函數(shù)為的母函數(shù)為G(x)nnxaxaaxG10)(nknknnnbacacaca2211設(shè)設(shè)an滿足滿足k階線性常系數(shù)非齊次遞推關(guān)系階線性常系數(shù)非齊次遞推關(guān)系2.4 線性常系數(shù)非齊次遞推關(guān)系線性常系數(shù)非齊次遞推關(guān)系Yiqiang Wei 5將這些式子兩邊分別相加，得到將這些式子兩邊分別相加，得到 knnnkkkikiiii

5、ixbxGxCxaxGxCxaxG10201即即 knnnkjjkiiijjkkxbxaxCxGxCxCxC10102211其中其中 C0=1令令 10100kjjkiiijjxaxCxP為次數(shù)不超過為次數(shù)不超過k-1的多項式的多項式2.4 線性常系數(shù)非齊次遞推關(guān)系線性常系數(shù)非齊次遞推關(guān)系為為k次多項式次多項式 knnnxbxP1kkkxCxCxCx 111C(x)也稱為特征多項式也稱為特征多項式Y(jié)iqiang Wei 6如果如果C(x)=0 在復數(shù)域中有在復數(shù)域中有k個根。設(shè)個根。設(shè) kkkkxxxxCskskks212121則則 skskkkkkxxxxCxCxCx1111121211于是

6、于是)()()(1101xPxPxGxCxCkk2.4 線性常系數(shù)非齊次遞推關(guān)系線性常系數(shù)非齊次遞推關(guān)系 xxxxP xxxxPxGsskskkkskk 111)(111)()(2121211210Yiqiang Wei 7 xxxxP xxxxPxGsskskkkskk 111)(111)()(2121211210它的第一項是有理式，對應(yīng)齊次遞推關(guān)系，可進行分解它的第一項是有理式，對應(yīng)齊次遞推關(guān)系，可進行分解并展開冪級數(shù)。并展開冪級數(shù)。 xxxxPxGskskk 111)()(212100 xAsikjjiiji 11)1( 01111)(ksikjkkijjkijixCA 其中其中Aij為

7、待定系數(shù)為待定系數(shù)2.4 線性常系數(shù)非齊次遞推關(guān)系線性常系數(shù)非齊次遞推關(guān)系Yiqiang Wei 8它的第二項對應(yīng)非齊次遞推關(guān)系的非齊次項，首先求出分子它的第二項對應(yīng)非齊次遞推關(guān)系的非齊次項，首先求出分子非齊次項的級數(shù)和，可進行展開冪級數(shù)。非齊次項的級數(shù)和，可進行展開冪級數(shù)。 111)()(212111skskkxxxxPxG 0kkkx 從而從而 01111)(G(x)ksikjkkkijjkijixCA比較比較xk的系數(shù)，得的系數(shù)，得0,1111 nCAannijjnsikjijni2.4 線性常系數(shù)非齊次遞推關(guān)系線性常系數(shù)非齊次遞推關(guān)系Yiqiang Wei 92.4 線性常系數(shù)非齊次遞

8、推關(guān)系線性常系數(shù)非齊次遞推關(guān)系例例2.4.1 求求an-an-1-6an-2=54n , a0=5, a1=3 的解的解 設(shè)母函數(shù)為設(shè)母函數(shù)為 解解0)(nnnxaxG代入遞推關(guān)系有代入遞推關(guān)系有 22110)456()(nnnnnxaaxaaxG202145635nnnnnnnnnxxaxxaxxxxxGxxGxx4145)(6)5)(35222xxxxGxx418025)()61 (22Yiqiang Wei 102.4 線性常系數(shù)非齊次遞推關(guān)系線性常系數(shù)非齊次遞推關(guān)系)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 線性常系數(shù)非齊次遞推關(guān)系線性常系數(shù)非齊次遞推關(guān)系例例2.4.2 求求an-an-1-6an-2=3n , a0=5, a1=2 的解的解 設(shè)母函數(shù)為設(shè)母函數(shù)為 解解0)(nnnxaxG代入遞推關(guān)系有代入遞推關(guān)系有 22110)36()(nnnnnxaaxaaxG20213625nnnnnnnnnxxaxxaxxxxxGxxGxx313)(6)5)(25222xxxxGxx31935)(

10、)61 (22Yiqiang Wei 122.4 線性常系數(shù)非齊次遞推關(guān)系線性常系數(shù)非齊次遞推關(guān)系)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 線性常系數(shù)非齊次遞推關(guān)系線性常系數(shù)非齊次遞推關(guān)系2.4.3 線性常系數(shù)非齊次遞推關(guān)系的待定

11、系數(shù)法線性常系數(shù)非齊次遞推關(guān)系的待定系數(shù)法nknknnnbacacaca2211由母函數(shù)方法可知由母函數(shù)方法可知k階線性常系數(shù)非齊次遞推關(guān)系階線性常系數(shù)非齊次遞推關(guān)系nnsisktntnstnsCAa 111的解的解而齊次遞推關(guān)系的解可由特征根方法解得，所以我們只而齊次遞推關(guān)系的解可由特征根方法解得，所以我們只要求解非齊次遞推關(guān)系的一個特解即可。要求解非齊次遞推關(guān)系的一個特解即可。解可表示為齊次關(guān)系的解與非齊次關(guān)系的解之和解可表示為齊次關(guān)系的解與非齊次關(guān)系的解之和Yiqiang Wei 14 待定系數(shù)法待定系數(shù)法1 1)(nqnrmknn 01111BnBnBnBnqmmmmm其中其中qm(n

12、)為系數(shù)待定的為系數(shù)待定的重特征根是不是特征根krkrk02.4 線性常系數(shù)非齊次遞推關(guān)系線性常系數(shù)非齊次遞推關(guān)系如果自由項如果自由項 bn=rnpm(n), 其中其中pm(n)為為n的的m次多項式次多項式, 則可設(shè)則可設(shè)非齊次遞推關(guān)系的解為非齊次遞推關(guān)系的解為其中其中k為為r作為特征根的個數(shù)，即作為特征根的個數(shù)，即Yiqiang Wei 15例例2.4.3 求求an-an-1-12an-2=3n , a0=3, a1=26 的解的解 特征方程特征方程 x2-x-12=0根為根為: : x=4 x=-3故齊次關(guān)系的通解為故齊次關(guān)系的通解為0,) 3(421nAAannn解解2.4 線性常系數(shù)非

13、齊次遞推關(guān)系線性常系數(shù)非齊次遞推關(guān)系由于自由項由于自由項: : bn=3n , 所以可設(shè)特解為所以可設(shè)特解為 a*n=B3n 代入關(guān)系式代入關(guān)系式 B3n-B3n-1-12B3n-2=3n 解得解得 B=-3/2Yiqiang Wei 162.4 線性常系數(shù)非齊次遞推關(guān)系線性常系數(shù)非齊次遞推關(guān)系由初值條件由初值條件23321AA323) 3(42621AA解得解得142574421AA，所求解為所求解為0,323) 3(14254744nannnn故非齊次關(guān)系的通解為故非齊次關(guān)系的通解為0,323) 3(421nAAannnnYiqiang Wei 17例例2.4.4 求求an+3an-1-1

14、0an-2=2n (n+5)的通解的通解 2.4 線性常系數(shù)非齊次遞推關(guān)系線性常系數(shù)非齊次遞推關(guān)系特征方程特征方程 x2+3x-10=0根為根為: : x=-5 x=2故齊次關(guān)系的通解為故齊次關(guān)系的通解為0,)5(221nAAannn解解由于自由項由于自由項: : bn=2n (n+5) , 所以可設(shè)特解為所以可設(shè)特解為a*n=n1(B0+B1n)2n 代入關(guān)系式代入關(guān)系式 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 線性常系數(shù)非齊次遞推關(guān)系線性常系數(shù)非齊次遞推關(guān)系Yiqiang Wei 19 待定系數(shù)法待定系數(shù)法2 22.4 線性常系數(shù)非齊次遞推關(guān)系線性常系數(shù)非齊次遞推關(guān)系sin)(sin)(nnhnnqnrmmknn 01111BnBnBnBnqmmmmm重特征根是不是特征根kirkirk)sin(cos)sin(cos0其中其中qm(n)與與h(n)為系數(shù)待定的為系數(shù)待定的如果自由項如果自由項 bn=rnpm(n)sin或或bn=rnpm(n)cos, 其中其中pm(n)為為n的的m次多項式次多項式, 則可設(shè)非齊次遞推關(guān)系的解為則可設(shè)非齊次遞推關(guān)系的解為其

16、中其中k為為r作為特征根的個數(shù)，即作為特征根的個數(shù)，即 01111CnCnCnCnhmmmmmYiqiang Wei 202.4 線性常系數(shù)非齊次遞推關(guān)系線性常系數(shù)非齊次遞推關(guān)系例例2.4.5 求求an-3an-1+2an-2=3sin(n/2) , a0=0, a1=1 的解的解 特征方程特征方程 x2-3x+2=0根為根為: : x=1 x=2故齊次關(guān)系的通解為故齊次關(guān)系的通解為0,2121nAAannn解解由于自由項由于自由項: : bn=3sin(n/2) , 所以可設(shè)特解為所以可設(shè)特解為 a*n=Bcos(n/2) +Csin(n/2)Yiqiang Wei 21故通解為故通解為2,

17、2sin1032cos109221nnnAAann由初值條件由初值條件21109AA 210321AA 解得解得10151A1032A所求解為所求解為0,2sin1032cos1092106101nnnann2.4 線性常系數(shù)非齊次遞推關(guān)系線性常系數(shù)非齊次遞推關(guān)系代入關(guān)系式解得代入關(guān)系式解得 B=-9/10， C=-3/10 Yiqiang Wei 22總之：總之：nkknnBnBBa)(1110若若是是特征方程特征方程C(x)=0的單根，則遞推關(guān)系的解中含有項的單根，則遞推關(guān)系的解中含有項nnaaA若若是特征方程是特征方程C(x)=0的的k重根，則遞推關(guān)系的解中含有項重根，則遞推關(guān)系的解中含

18、有項若若1 1, ,2 2是一對是一對k k重共軛復根，且重共軛復根，且)sin(cos12iaa則遞推關(guān)系的解中含有項則遞推關(guān)系的解中含有項nnCnCCnnBnBBankknkknsin)(cos)(111011102.3 線性常系數(shù)齊次遞推關(guān)系線性常系數(shù)齊次遞推關(guān)系Yiqiang Wei 232.4 線性常系數(shù)非齊次遞推關(guān)系線性常系數(shù)非齊次遞推關(guān)系2.4.3 線性常系數(shù)非齊次遞推關(guān)系的齊次化方法線性常系數(shù)非齊次遞推關(guān)系的齊次化方法例例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