摘要訊息 : 使用特徵根法解一個遞迴方程式.
0. 前言
在《【遞迴方程式】替代法與歸納法》中, 我們講解了使用替換法, 歸納法和列表法三種方法去解一個遞迴方程式. 但是對於比較複雜的遞迴方程式, 這三種方法可能都難以得到最終的解.
更新紀錄 :
- 2022 年 6 月 5 日進行第一次更新和修正.
1. 線性遞迴方程式
定義 1. 若遞迴方程式 f(n) 滿足 f(n)=i=1∑kgi(n)f(n−i)+g(n), (I) 其中 gi(n)(i=1,2,...,k) 與 g(n) 都是關於 n 的函數, 而不是關於 f 的函數; k 為任意正整數; gk(n)=0, 那麼我們稱 f(n) 為線性遞迴方程式 (linear recurrence).
根據定義 1, 若 gk(n)=0, 則 f(n)=i=1∑k−1gi(n)f(n−i)+g(n), 其遞迴深度未達到 k, 不能稱為線性遞迴方程式.
定義 2. 若存在 k 個整數 a1,a2,...,ak 使得 g1(n)=a1,g2(n)=a2,...,gk(n)=ak, 那麼 f(n)=i=1∑kgi(n)f(n−i)+g(n) 可以展開為 f(n)=a1f(n−1)+a2f(n−2)+...+akf(n−k)+g(n). (II) 其中, ak=0 且 n≥k. 當 g(n)=0 時, 稱 f(n) 為齊次線性遞迴方程式 (homogeneous recurrence); 當 g(n)=0 時, 稱 f(n) 為非齊次線性遞迴方程式 (non-homogeneous recurrence).
實際上, (II) 式就是分而治之演算法 (《分而治之演算法》) 時間複雜度的一種表達. 這裡, 我們採用的方式是一分為 k.
對於 f(n)={c1n=12f(2n)+c2nn≥2,其中 log2n 為整數. 由於線性遞迴方程式要求右側的 f 為 f(n−i) 的形式, i=1,2,...,k. 而上述遞迴方程式中, f(2n) 不滿足這樣的形式, 因此上述遞迴方程式不是線性遞迴方程式. 但因為 log2n 為整數, 因此 f(n) 可以寫為 f(2k)={c12f(2k−1)+c22kk=0k≥1. 記 h(k)=f(2k), 則有 h(k)={c12h(k−1)+c22kk=0k≥1. 顯然, h(k) 和 f(k) 等價, 解 h(k) 實質上就是要解 f(n). 而 h(k) 是一個線性遞迴方程式. 根據 k 的值, 我們稱 (I) 式為 k 階線性遞迴方程式 (linear recurrence of order k). 因此 h(k) 是一個一階線性遞迴方程式. 其中, g1(k)=2 且 g(k)=c22k. h(k) 是一個一階非齊次線性遞迴方程式.
再考慮 T(n)=⎩⎪⎨⎪⎧c1n2i=1∑n−1T(i)+c2nn≤1n>1. 其中, c1 和 c2 為任意常數. T(n) 同樣不是線性遞迴方程式, 但是可以通過轉化, 讓其成為線性遞迴方程式. 當 n>1 時, T(n)=n2i=1∑n−1T(i)+c2n. (III) 等式兩側同時乘以 n, 可得 nT(n)=2i=1∑n−1T(i)+c2n2. 使用 n−1 替換 n, 有 (n−1)T(n−1)=2i=1∑n−2T(i)+c2(n−1)2. (IV) 使用 (III) 式減去 (IV) 式, 得 nT(n)−(n−1)T(n−1)=2i=1∑n−1T(i)−2i=1∑n−2T(i)+c2n2−c2(n−1)2. 展開之後有 nT(n)−nT(n−1)+T(n−1)=2T(n−1)+c2(2n−1). 移項得 nT(n)=(n+1)T(n−1)+c2(2n−1). 等式兩側同時乘以 n1, 最終可得 T(n)=nn+1T(n−1)+c2(2−n1). 不難看出, T(n) 是一個一階非齊次線性遞迴方程式. 其中, g1(n)=nn+1,g(n)=c2(2−n1).
2. 特徵根法
對於函數 f(n)=i=1∑kgi(n)f(n−i)+g(n) 時需要 k 個初始值的 : f(0),f(1),...,f(k−1), 從而使得 f(k),f(k+1),... 有惟一值. 此時, f(n) 可以表示為 f(n)=⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧c1c2⋮ck−1i=1∑kgi(n)f(n−i)+g(n)n=0n=1⋮n=k−1n≥k. 對於函數 f(n)=a1f(n−1)+a2f(n−2)+...+akf(n−k)+g(n), 若已知 f(0),f(1),...,f(k−1), 則我們可以通過建立方程式組來得到 a1,a2,...,ak 的值.
在代數學中我們知道, 對於非齊次線性遞迴方程式 f(n)=a1f(n−1)+a2f(n−2)+...+akf(n−k)+g(n) 的解是其對應的齊次線性遞迴方程式的通解 fh(n)=a1f(n−1)+a2f(n−2)+...+akf(n−k) (V) 再加上一個非齊次線性遞迴方程式的一個特解 fp(n)=a1f(n−1)+a2f(n−2)+...+akf(n−k)+g(n). (VI) 即 f(n) 的通解可以表示為 fh(n)+fp(n).
為了確定 fh(n), 我們首先對 (V) 式進行移項, 得 fh(n)−a1f(n−1)−a2f(n−2)−...−akf(n−k)=0. 不妨假設上述方程式可以得到一個解 fh(n)=Axn, 其中 A=0. 將解代入上述方程式, 可以得到 Axn−a1Axn−1−a2Axn−2−...−akAxn−k=0 等式兩側同時乘以 A1 並提取 xn−k 可得到 xn−k(xk−a1xk−1−a2xk−2−...−ak−1x−ak)=0. 上式可以簡寫為 xn−k(xk−i=1∑kaixk−1)=0. 顯然這個方程式有 n 個根, 其中有 n−k 個根是 0, 剩下 k 個根取決於 xk−a1xk−1−a2xk−2−...−ak−1x−ak=0. 這個方程式就是 fh(n) 的特徵方程式, 有 k 個根 : r1,r2,...,rk. 當然, 可能存在某個根 ri (i=1,2,...,k) 重複 j 次 (j≤k).
定理 1. 若 fh(n) 的特徵方程式 xk−a1xk−1−a2xk−2−...−ak−1x−ak=0 有 s 個互異解 t1,t2,...,ts (s≤k). 則通解為 fh(n) 可以表示為 fh(n)=u1(n)+u2(n)+...+us(n). 其中, ui(n)=(ci0+ci1n+ci2n2+...+ciw−1nw−1)tin, w 是根 ti 的重複次數, i=1,2,...,s.
這個定理我們暫時不進行證明.
例題 1. 解二階齊次線性遞迴方程式 F(n)=⎩⎪⎪⎨⎪⎪⎧01F(n−1)+F(n−2)n=0n=1n>1. 這個遞迴方程式是非常有名的費氏數列 (Fibonacci number sequence).
解 :設其通解為 Fh(n)=Axn, 其中 A=0, 將 Fh(n) 代入上式得到其特徵方程式 x2−x−1=0. 解得 x1=−25+21,x2=25+21. 每個根僅重複一次, 則 w=1. 故 u1(n)=c1(−25+21)n,u2(n)=c2(25+21)n. 因此, F(n)=F(n−1)+F(n−2) 的通解為 Fh(n)=u1(n)+u2(n)=c1(−25+21)n+c2(25+21)n. 考慮 F(0)=0,F(1)=1, 得到一個方程式組並解這個方程式組可以得到 {F(0)=c1+c2=0F(1)=c1(−25+21)+c2(25+21)=1, ⇒ {c1=−51c2=51.
故費氏數列的通項公式可以表示為 F(n)=51(21+5)n−51(21−5)n
■
目前, 我們僅得到了齊次線性遞迴方程式的求解方法, 對於 g(n)=0 的情況, 我們還需要得到一個特解 fp(n). 對於任意 g(n)=0, 目前還沒有一個適用於任意 g(n) 的特解 fp(n). fp(n) 的形式取決於 g(n). 然而 g(n) 的樣式可以是多種多樣的, 此處我們僅考慮兩種形式 : g(n) 是關於 n 的多項式及 g(n) 是關於 n 的指數函數.
首先, 當 g(n)=0 時, f(n) 的特解 fp(n)=0; 當 g(n)=i=0∑deini, 其中 ed=0, 那麼特解 fp(n) 有如下形式 fp(n)=p0+p1n+p2n2+...+pd+mnd+m. 其中, m 的值取決於 f(n) 對應的齊次線性遞迴方程式的特徵方程式的解. 如果 r=1 時特徵方程式的解, 那麼 m 的值時根 r=1 的重複次數; 如果 r=1 不是特徵方程式的解, 則 m=0.
由於 fp(n) 是 f(n) 的一個特解, 為了確定 p0,p1,...,pd+m 的值, 我們將 fp(n) 代入 f(n) 中, 得到 fp(n)=p0+p1n+p2n2+...+pd+mnd+m=a1(p0+p1(n−1)+p2(n−1)2+...+pd+m(n−1)d+m) + a2(p0+p1(n−2)+p2(n−2)2+...+pd+m(n−2)d+m) + ... + ak(p0+p1(n−k)+p2(n−k)2+...+pd+m(n−k)d+m)+g(n). 觀察等式兩側, 可以得到共計 d+m 個關於 pi (i=1,2,...,d+m) 的方程式. 將這些方程式組成一個方程式組, 解得 p1,p2,...,pd+m 的值即可.
當 g(n)=can, 其中 a 與 c 為任意常數, a>0, 那麼特解 fp(n) 有如下形式 fp(n)=(p0+p1n+p2n2+...+pwnw)an. 其中, w 的值取決於 f(n) 對應的齊次線性遞迴方程式的特徵方程式的解. 如果 r=a 是特徵方程式的解, 那麼 w 的值是根 r=a 的重複次數, 如果 r=a 不是特徵方程式的解, 則 w=0.
同樣地, 由於 fp(n) 時 f(n) 的一個特解, 為了確定 p1,p2,...,pd+m 的值, 我們將 fp(n) 代入 f(n) 中, 得到共計 w 個關於 pi (i=1,2,...,d+m) 的方程式. 將這些方程式組成一個方程式組, 解得 p1,p2,...,pd+m 的值即可.
自此, 我們得到了使用特徵根法來求解遞迴方程式的過程. 對於線性遞迴方程式 f(n)=⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧c1c2⋮ck−1i=1∑kgi(n)f(n−i)+g(n)n=0n=1⋮n=k−1n≥k, 其中 c1,c2,...,ck−1,a1,a2,...,ak 是常數, g(n) 是關於 n 的函數而不是關於 f 的函數. f(n) 的求解過程如下 :
- 對於 n≥k 時的 f(n), 寫下其特徵方程式 xk−i=1∑kaixk−i=0;
- 求解特徵方程式的互異根 t1,t2,...,ts (s≤k), 並確定任意根 r=ti 的重複次數 ji (i=1,2,...,s,ji≤k);
- 根據每個根 ri, 寫下 ui(n), 並令 fh(n)=u1(n)+u2(n)+...+us(n). 其中, ui(n)=(ci0+ci1n+ci2n2+...+ciw−1nw−1)tin,i=1,2,...,s,w=ji;
- 根據給定的 f(0),f(1),...,f(k−1) 的值, 計算每一個 ui(n) 中的 ci0,ci1,...,ciw−1. 其中, i=1,2,...,s,w=ji;
- 考慮 g(n) :
- 若 g(n)=0, 則 fp(n)=0;
- 若 g(n)=i=1∑deini, 其中 ed=0, ei (i=1,2,...,d) 為任意常數. 則 fp(n)=p0+p1n+p2n2+...+pd+mnd+m;
- 若 g(n)=can, 其中 a 與 c 為任意常數, a>0, 則 fp(n)=(p0+p1n+p2n2+...+pwnw)an. 其中, w 的值取決於 r=a 是否為特徵方程式的根;
- 若 g(n)=0, 則將 fp(n) 代入 f(n) 中, 求得 p0,p1,...,pd+m 或 p0,p1,...,pw 的值;
- 最終, 線性遞迴方程式 f(n) 的解為 f(n)=fh(n)+fp(n).
這七個步驟稱為求解線性遞迴方程式 f(n) 的特徵根法 (characteristic root method).
斷言 1. 通過特徵根法的七個步驟找到的 f(n)=fh(n)+fp(n) 是線性遞迴方程式 f(n) 的惟一解.
這個斷言我們暫時不進行證明.
3. 一些非線性情形
某些非線性遞迴方程式也可以通過適當的變換, 將其轉化為線性遞迴方程式, 再利用特徵根法進行求解. 考慮 fc(n)=i=1∑kaifc(n−i)+g(n), 其中 n≥k, c 為任意常數. 我們記 q(n)=fc(n), 則有 q(n)=i=1∑kaiq(n−i)+g(n). 此時, 非線性的 fc(n) 就轉化為了線性的 q(n).
另外, 某些線性遞迴方程式可能具有非恆定的係數 : nf(n)=i=1∑kaif(n−i)+g(n), 其中 n≥k. 我們無法直接使用特徵根法進行求解, 但也可以作適當的變換, 使其具有恆定係數. 記 q(n)=nf(n), 則有 q(n)=i=1∑kaiq(n−i)+g(n). 在這樣的情況下, 我們得到的是關於 q(n) 的通解, 此時只需將 q(n) 使用 f(n) 進行替換, 即可得到原遞迴方程式的通解.