【正文】 c1和 c2為待定常數(shù) 37 遞推方程求解：二階常系數(shù)線性遞推式例 1 第二種情況 ：有兩個相等實根 , 齊次遞推方程通解為 ： 第三種情況：特征方程在實數(shù)域無解。略。 定理 2： 把非齊次方程的特解和相應(yīng)的齊次方程通解相加，得到該 非齊次 方程的通解 。 例 1：求齊次遞推方程通解和特解 解：該遞推方程的特征方程為： 特征方程有兩個相等的實根，根據(jù)定理 1，該遞推方程 通解 為： 根據(jù)初始條件解出待定常數(shù)，得到一個 特解 ： 12q q q??1 2 1 2( ) ( )n n nx n c q c n q c c n q? ? ? ?c1和 c2為待定常數(shù) ( ) 6 ( 1 ) 9 ( 2 ) 0( 0 ) 0 , ( 1 ) 3x n x n x nxx? ? ? ? ???22 126 9 0, ( 3 ) 0, 3q q q q q q? ? ? ? ? ? ? ?1 2 1 2( ) 3 3 ( ) 3n n nx n c c n c c n? ? ? ?c1和 c2為待定常數(shù) 01 2 111 2 20( 0) ( ( ) 330)3( 1 ) ( 1 )3 1nxc xnc nccx c c?? ? ? ? ??????? ? ?38 遞推方程求解：二階常系數(shù)線性遞推式例 2 例 2：求非齊次遞推方程滿足初始條件的特解 解： 根據(jù)例 1，該非齊次方程對應(yīng)的 齊次方程的通解 為： 注意 ：此時不能代入初始條件解出 非齊次方程 的一個特解（為什么？） 現(xiàn)在，求 非齊次方程的一個特解 ： 設(shè)特解為 ，由遞推式解得 根據(jù)定理 2，得到 非齊次遞推方程的通解 ： (疊加 ) 據(jù)初始條件解出特解中待定常數(shù)，得特解： ( ) 6 ( 1 ) 9 ( 2 40)( 0 ) 0 , ( 1 ) 3x n x n x nxx? ? ? ? ????1 2 1 2( ) 3 3 ( ) 3n n nx n c c n c c n? ? ? ?c1和 c2為待定常數(shù) ()x n c? 6 9 4 1c c c c? ? ? ? ?12( ) 3 3 1nnx n ncc? ? ?c1和 c2為待定常數(shù) 001 2 1111 2 1 212( 0 ) 3 0 3 1 1 0( 1 ) 3 1 3 1 3 3 113 5 / 3x c c cc c cccxc? ? ? ? ? ? ? ?? ? ? ? ? ? ? ?????5( ) 3 3 13nnx n n? ? ? ?39 遞推方程求解： k階常系數(shù)線性遞推式 公式法求解： k 階 常系數(shù)線性遞推式 （二階的推廣） 它的齊次遞推方程：方程右端項為 0，即 齊次方程的特征方程：（相同系數(shù)的一個 k 次方程，超越方程 ） 12( ) ( 1 ) ( (2) ( ))kx n x n xa a a f nn x n k? ? ?? ? ? ? ?( ) 0fn ?1 2 1 01 2 1 0k k k kkq a q a q a q a q?? ?? ? ? ? ? ?1212321 2 31121 2 3( ) ( 1 ) 0( ) ( 1 ) ( 2 ) 0( ) ( 1 ) (1:2:3:0020) ( 3 ) 0qaq a qx n a x nx n a x n a x nx n a x n a x naq a q aakkqxnak? ? ? ?? ? ? ? ? ?? ? ? ? ? ?????? ? ?? ? ?????數(shù)值解法 40 遞推方程求解： k階常系數(shù)線性遞推式（ 2） 求 k 階齊次遞推方程通解：定理 1推廣 （ 1）特征方程有 k 個不相等實根 qk ，齊次遞推方程通解為 ： （ 2） 特征方程有 r 個相等實根（重根），齊次遞推方程通解為 ： 說明： k 次特征方程有 k個實根 q1 , q2 ,... ,qk , 其中有 r 個實根相同。 這相同的 r 個實根為： 1 1 2 2() n n nkkx n c q c q c q? ? ?ck 為待定常數(shù) ? ?0 1 11 1 1( i 1 ) r( k ( i 1 ) r ) = ( k ) (1i+1r ) + 11()niin r ni i ri r i rinnkkx n c q c q c n c n c n qc q c q? ? ??? ???? ? ? ? ? ? ?? ? ?前 面 個 非 重 根 中 間 個 重 根后 面 個 非 重 根12: ( 1 ) ( ) 11i i riiirr irq q q q q??? ? ?????? ? ? ? ?個41 遞推方程求解： k階常系數(shù)線性遞推式（ 3） 求 k 階非齊次遞推方程特解： 前面已求得其相應(yīng)的齊次遞推方程通解；據(jù)定理 2，再求得非齊次方程的 任意一個特解，則兩者相加可得非齊次遞推方程通解。最后，根據(jù)給定 初始條件可得滿足初始條件的非齊次遞推方程特解。 對一般的非齊次遞推方程，不存在尋找特解的通用方法，只能用觀察法 去假定特解的形式，然后用待定系數(shù)法確定系數(shù)。 1. 當(dāng) f(n) 是 n 的 t 次多項式時，可設(shè)特解也是 n的多項式即特解形式 : 2. 當(dāng) f(n)是 n的指數(shù)函數(shù) , a,b為待定常數(shù)時，設(shè)特解形式： （ 1） b 不是相應(yīng)齊次方程的 特征根 時 （ 2） b 是相應(yīng)齊次方程的 e 重 特征根 時 1 1 01 2 1() tt ttx n p n p n p n p n? ?? ? ? ? ?0111221 2 30 : ( )1 : ( )2 : ( )t x n p n pt x n p n pt x n p n p n p? ? ?? ? ?? ? ? ?() nf n a b?() ,nx n c b c? 待 定p 為待定系數(shù) () ,en cx n c n b? 待 定42 遞推方程求解： k階常系數(shù)線性遞推式例 例：解遞歸方程 解： 1）求齊次遞推方程的特征根：（特征方程的根） 2）根據(jù)定理 1，兩個特征根不相等，齊次方程通解為： 3）求非齊次方程的一個任意特解： 因方程右端為 n的指數(shù)形式，且 b=4不是特征根，可設(shè)定特解形式： 將特解代入非齊次遞推方程： 4( ) 5 ( 1 ) 6 ( 2 )( 0 ) 04, ( 1 )20nx n x n x nxx? ? ? ? ? ??????2125 6 0 ( 2) ( 3) 02 , 3q q q qqq? ? ? ? ? ? ?? ? ? ? ?1 1 2 2 1 2( ) ( 2 ) ( 3 )n n n nx n c q c q c c? ? ? ? ? ?( ) 4 ,nnx n c b c c? ? ? ? 待 定12564 4 4 4 2 4n n n nc c c??? ? ? ? ? ? ?43 遞推方程求解： k階常系數(shù)線性遞推式例（續(xù)） 124 4 4 4 2 4564 4 4 424 1 61 0 3 2 14 2 4 2 1 6854868nnn n n nnnc c cc c cc c c c c??? ? ? ? ? ? ?? ? ? ? ? ? ?? ? ? ? ? ? ? 非齊次遞推方程的一個特解為： 4）非齊次遞推方程的通解：（定理 2） 2( ) 4 1 6 4 4n n nx n c ?? ? ? ? ?212( ) ( 2 ) ( 3 ) 4n n nx n c c ?? ? ? ? ?非 齊 次 特 解齊 次 通 解5）求滿足初始條件的非齊次遞推方程的解（特解）： 非齊次遞推方程的通解中代入初始條件 x(0)=0, x(1)=0 0 0 0 21 2 1 21 1 1 21 2 1 212( 0 ) ( 2 ) ( 3 ) 4 1 6 0( 1 ) ( 2 ) ( 3 ) 4 2 3 6 4 01 1 2 , 9 6x c c c cx c c c ccc???? ? ? ? ? ? ? ? ??? ? ? ? ? ? ? ? ??? ? ? ?2( ) 1 1 2 ( 2) 9 6 ( 3) 4n n nxn ?? ? ? ? ? ?47 遞推算法效率分析通用方案 ? 遞推算法效率分析通用方案（類似于非遞歸算法） 1 確定 輸入規(guī)模 ； 2 確定 基本操作 ；（規(guī)律：它總是位于算法的最內(nèi)層循環(huán)里） 3 考慮基本操作的執(zhí)行次數(shù)是否僅僅與輸入規(guī)模有關(guān)。若還與其他因數(shù) 有關(guān)（比如順序查找算法中基本操作執(zhí)行次數(shù)還與查找鍵在列表中的 位置有關(guān)），則按需要對 最差 、最佳、平均效率作出分析。 4 建立基本操作數(shù)與規(guī)模的函數(shù)關(guān)系，即遞推關(guān)系和初始條件。 5 解遞推方程，確定增長函數(shù)的增長率。