生成函數與差分方程 2
http://episte.math.ntu.edu.tw/articles/mm/mm_02_4_10/img3.gif可看成是定義在非負整數集上的函數，其於整數 http://episte.math.ntu.edu.tw/articles/mm/mm_02_4_10/img30.gif之值就是 an。差分算子 Δ(difference operator)是一在這些函數組成的集合上之變換，其定義為http://episte.math.ntu.edu.tw/articles/mm/mm_02_4_10/img31.gif
高階差分算子 http://episte.math.ntu.edu.tw/articles/mm/mm_02_4_10/img32.gif (k=2,3,…)是定義為
http://episte.math.ntu.edu.tw/articles/mm/mm_02_4_10/img33.gif
我們並定義 http://episte.math.ntu.edu.tw/articles/mm/mm_02_4_10/img34.gif，其中 I 是恆等算子，即 Ian=an (n=0,1,2,…)。與差分算子有密切關係的是位移算子 E (Translation operator)，其定義為
Ean=an+1
高階位移算子 Ek (k=2,3,…) 是定義為
Ekan=E(Ek-1an)=an+k
我們並定義 E0=I，顯見有 http://episte.math.ntu.edu.tw/articles/mm/mm_02_4_10/img35.gif。任何方程含有差分算子或與其等價之位移算子的稱為差分方程 (difference equation)。一個 k階常係數線性差分方程 (或回歸方程)有一般形式
http://episte.math.ntu.edu.tw/articles/mm/mm_02_4_10/img36.gif
其中 http://episte.math.ntu.edu.tw/articles/mm/mm_02_4_10/img7.gif 是一給定數列，C0, C1, …, Ck 是給定之常數。如果有 k 個相連的值為給出，稱為邊界條件，則方程(6)有唯一的解。與 (6)對應之齊次差分方程是
http://episte.math.ntu.edu.tw/articles/mm/mm_02_4_10/img37.gif
前述之方程 (1)與 (4)均是一階非齊次差分方程;方程 (5)是二階齊次差分方程。利用位移算子，方程 (6)與 (7)又可記為
http://episte.math.ntu.edu.tw/articles/mm/mm_02_4_10/img38.gif
及
http://episte.math.ntu.edu.tw/articles/mm/mm_02_4_10/img39.gif
方程 (9)之解稱為齊次解；任意滿足方程 (8) 之解稱特別解。讀者已可觀察到 k階常係數線性差分方程與微積分中的 k 階常係數線性微分方程之間相似性；實際上它們之間有許多相平行的性質。例如所有齊次解形成的集合是一向量空間；方程(8)之解必為一個齊次解及某個特別解之和。這些性質的證明與微分方程中相應性質的證明相似，我們不在此詳細說明。有關差分方程一般性質請參閱參考資料。 下面我們討論 k階齊次常係數線性差分方程 (9)之求解步驟。在 (9)中令 an=rn，我們有
http://episte.math.ntu.edu.tw/articles/mm/mm_02_4_10/img40.gif
我們不考慮 r=0的情況，故又有
http://episte.math.ntu.edu.tw/articles/mm/mm_02_4_10/img41.gif
方程 (10)是一次代數方程式，稱為與 (9)對應之特徵方程式;它有 k個根，稱為方程 (9)之特徵根。如果 (10)有 k個不同的根 r1， r2， …， rk，則任一方程 (9)之解有形式
http://episte.math.ntu.edu.tw/articles/mm/mm_02_4_10/img42.gif
其中 A1, A2, …, Ak 是未定係數，由所給出的邊界條件所決定。如果一特徵根 r是 (10)之 m 重根，則與之對應的齊次解是
http://episte.math.ntu.edu.tw/articles/mm/mm_02_4_10/img43.gif
如果方程 (10)有一對共軛複根 p+qi 及 p-qi，則與之對應之齊次解又可寫成
http://episte.math.ntu.edu.tw/articles/mm/mm_02_4_10/img44.gif
其中 http://episte.math.ntu.edu.tw/articles/mm/mm_02_4_10/img45.gif， http://episte.math.ntu.edu.tw/articles/mm/mm_02_4_10/img46.gif，B1=A1+A2 及 B2=i(A1-A2)。下面我們在用例題來說明齊次差分方程之求解步驟。 [例4]
解例3中的齊次差分方程 (5):
http://episte.math.ntu.edu.tw/articles/mm/mm_02_4_10/img47.gif
方程 (11)之特徵方程是
r2-r-1=0
它有兩個不同的特徵根 http://episte.math.ntu.edu.tw/articles/mm/mm_02_4_10/img48.gif與 http://episte.math.ntu.edu.tw/articles/mm/mm_02_4_10/img49.gif，故其齊次解有形式
http://episte.math.ntu.edu.tw/articles/mm/mm_02_4_10/img50.gif
為了決定未定係數 A1 與 A2，我們將(11)中之邊界條件代入(12)得
http://episte.math.ntu.edu.tw/articles/mm/mm_02_4_10/img51.gif
解聯立方程 (13)得
http://episte.math.ntu.edu.tw/articles/mm/mm_02_4_10/img52.gif
因此方程 (11)之解是
http://episte.math.ntu.edu.tw/articles/mm/mm_02_4_10/img28.gif
[例5] 計算 n 階行列式
http://episte.math.ntu.edu.tw/articles/mm/mm_02_4_10/img53.gif
設 (14)中之 n階行列式之值為 an，由第一列將 (14)展開得差分方程
http://episte.math.ntu.edu.tw/articles/mm/mm_02_4_10/img54.gif
它的特徵方程是 r2-r+1=0，故有兩個共軛複根
http://episte.math.ntu.edu.tw/articles/mm/mm_02_4_10/img55.gif
http://episte.math.ntu.edu.tw/articles/mm/mm_02_4_10/img56.gif
得方程 (15)之齊次解有形式
http://episte.math.ntu.edu.tw/articles/mm/mm_02_4_10/img57.gif
將 (15)中之邊界條件代入 (16)有
http://episte.math.ntu.edu.tw/articles/mm/mm_02_4_10/img58.gif
從而得未定係數 B1=1， http://episte.math.ntu.edu.tw/articles/mm/mm_02_4_10/img59.gif。方程(15)之解是
http://episte.math.ntu.edu.tw/articles/mm/mm_02_4_10/img60.gif
由方程 (15)可見由 n=1起 an之值的首幾項是
http://episte.math.ntu.edu.tw/articles/mm/mm_02_4_10/img61.gif
最後我們介紹一種非齊次差分方程 (8)的求解步驟。由上面討論知只需求出方程 (8)的某個特別解。我們所用的是一種經驗法，是由方程 (8)之右邊 bn之形式來判斷特別解可能有的形式，然後再決定其中未定係數。下表列出幾種常遇到的 bn形式
http://episte.math.ntu.edu.tw/articles/mm/mm_02_4_10/img62.gif
其中表之右列中 B,B1,B2,…,Bp 為未定係數。這種解法也是求常微分方程之非齊次解時常用方法之一，讀者應對這兩種情況之異同作一比較。 [例6] 問在由 0,1,2,3 所組成的 n 位數中有多少含有偶數個零？ 設 an 是由 0,1,2,3 所組成的 n 位數中含偶數個 0 的個數，則在這些數中，最後一位數或者不為零，這樣的數有 3an-1 個；或者最後一位數為零，則它前面 n-1位中必有奇數個零，這樣的數一共有 4n-1-an-1 個，故得 an=3an-1+4n-1-an-1。顯然有 a1=3，故所求的差分方程可寫成
http://episte.math.ntu.edu.tw/articles/mm/mm_02_4_10/img63.gif
方程 (18)之特徵方程式 r-2=0，它有唯一的特徵根 r=2，故得方程(18)之齊次解有形式
an=A2n
其中 A 是未定係數。為了求方程的特別解，由表(17)得它有形式 an=B4n，其中 B為未定係數。代入方程(18)得
B4n+1-2B4n=4n
從而 http://episte.math.ntu.edu.tw/articles/mm/mm_02_4_10/img64.gif。因此方程(18)之任一解均有形式
http://episte.math.ntu.edu.tw/articles/mm/mm_02_4_10/img65.gif
將(18)中邊界條件代入(19)得 http://episte.math.ntu.edu.tw/articles/mm/mm_02_4_10/img66.gif，因此方程(18)之解為
http://episte.math.ntu.edu.tw/articles/mm/mm_02_4_10/img67.gif
用試驗解法求特別解也有失效的情況，那時我們必需作必要的修正。最後我們舉下例來說明此點。 [例7] 解差分方程
http://episte.math.ntu.edu.tw/articles/mm/mm_02_4_10/img68.gif
方程 (20)的特徵方程是 r-1=0，故它有唯一的特徵根 r=1。因此方程(20)的齊次解是 an=A(1)n=A，其中 A 是未定係數。根據表(17)方程(20)的特別解有形式
http://episte.math.ntu.edu.tw/articles/mm/mm_02_4_10/img69.gif
但齊次解與特別解中均有一項是常數，將 (21)代入 (20)將無法決定未定係數 B1。這時我們可以將特別解乘一最低次數之 n 的整數冪，使得齊次解與特別解中的這種相似項消失。因此我們可令方程(20)之特別解有形式 an=B1n+B2n2 並代入(20)得
B1(n+1)+B2(n+1)2-B1n-B2n2 = 2n
比較兩邊係數得 B1=-1, B2=1。方程(20)之任一解均有形式
http://episte.math.ntu.edu.tw/articles/mm/mm_02_4_10/img70.gif
將(20)中之邊界條件代入(21)得 A=2，因此方程(20)之解為
an=n2-n+2
頁:
[1]