常係數線性遞迴關係式 (上)

本文的閱讀等級:初級

k 階常係數線性遞迴關係式 (linear recurrence relation) 可表示如下:

a_n=d_1a_{n-1}+d_2a_{n-2}+\cdots+d_ka_{n-k}+F(n),~~~n\ge k

其中 d_1,d_2,\ldots,d_k 是常數,d_k\neq 0F(n) 稱為控制項。滿足上式的序列 \{a_n\} 稱為線性遞迴數列,由設定的初始值 a_0,a_1,\ldots,a_{k-1} 唯一決定。考慮較簡單的情況,F(n)=0,我們稱之為齊次 (homogeneous) 遞迴關係式。例如,費布納西 (Fibonacci) 數列

0,1,1,2,3,5,8,13,21,34,55,89,\ldots

的二階遞歸生成規則如下 (見“費布納西數列的表達式”):

a_n=a_{n-1}+a_{n-2},~~n\ge 2

初始條件為 a_0=0a_1=1。通項 a_n 的代數表達式有兩種常見解法:母函數法 (見“遞迴關係式的母函數解法”) 與線性代數法。下面以費布納西數列為例說明兩個線性代數解法。

 
第一個解法將無窮數列 \mathbf{x}=(x_0,x_1,\ldots) 形成的集合 \mathcal{S} 視為一個向量空間。在無窮數列空間 \mathcal{S},零向量為 \mathbf{0}=(0,0,\ldots)。對於 \mathcal{S} 的兩個數列 (向量) \mathbf{x}\mathbf{y},以及純量 c,我們有向量加法 \mathbf{x}+\mathbf{y}=(x_0+y_0,x_1+y_1,\ldots),和純量乘法 c\mathbf{x}=(cx_0,cx_1,\ldots)。為了表示遞迴關係式,定義兩個線性算子 I:\mathcal{S}\to\mathcal{S}D:\mathcal{S}\to\mathcal{S},其中 I 是單位算子,I\mathbf{x}=\mathbf{x},而 D 是平移算子,D\mathbf{x}=(x_1,x_2,\ldots)。因此,齊次遞迴關係式 a_n-a_{n-1}-a_{n-2}=0n\ge 2,可表示為

D^2\mathbf{a}-D\mathbf{a}-I\mathbf{a}=(D^2-D-I)\mathbf{a}=\mathbf{0}

其中 \mathbf{a}=(a_0,a_1,\ldots)\in\mathcal{S}。解齊次遞迴關係式等價於求算子多項式 D^2-D-I 的零空間 (nullspace),或稱核 (kernel),記為 N(D^2-D-I)。二次多項式 t^2-t-1 有兩個相異根,\lambda_1=\frac{1+\sqrt{5}}{2}\lambda_2=\frac{1-\sqrt{5}}{2},故 D^2-D-I=(D-\lambda_1I)(D-\lambda_2I),其中 D-\lambda_1ID-\lambda_2I 可交換。若非零向量 \mathbf{a}\in N(D^2-D-I),則

(D^2-D-I)\mathbf{a}=(D-\lambda_1I)(D-\lambda_2I)\mathbf{a}=\mathbf{0}

第一個等號右邊至少存在一 \mathbf{x}\neq\mathbf{0} 使得 (D-\lambda_1I)\mathbf{x}=\mathbf{0}(D-\lambda_2I)\mathbf{x}=\mathbf{0}。考慮特徵方程 (D-\lambda I)\mathbf{x}=\mathbf{0},即 D\mathbf{x}=\lambda\mathbf{x},展開可得

D(x_0,x_1,x_2,\ldots)=(x_1,x_2,x_3,\ldots)=(\lambda x_0,\lambda x_1,\lambda x_2,\ldots)

比較等號兩邊,x_{n+1}=\lambda x_nn\ge 0,可知任一純量 \lambda 是線性算子 D 的一個特徵值,對應的特徵向量為 \boldsymbol{\lambda}=(1,\lambda,\lambda^2,\ldots)。因此,N(D^2-D-I) 包含線性算子 D 對應特徵值 \lambda_1\lambda_2 的特徵向量 \boldsymbol{\lambda}_1=(1,\lambda_1,\lambda_1^2,\ldots)\boldsymbol{\lambda}_2=(1,\lambda_2,\lambda^2_2,\ldots)。因為 \lambda_1\neq\lambda_2,立知 \{\boldsymbol{\lambda}_1,\boldsymbol{\lambda}_2\} 是一個線性獨立集。我們可以證明 \dim N(D^2-D-I)=2 (另一個證明見[1])。使用反證法,假設非零向量 \mathbf{x}\notin\text{span}\{\boldsymbol{\lambda}_1,\boldsymbol{\lambda}_2\} 使得 (D^2-D-I)\mathbf{x}=(D-\lambda_1I)(D-\lambda_2I)\mathbf{x}=\mathbf{0}。令 \mathbf{y}=(D-\lambda_2I)\mathbf{x}。明顯地,\mathbf{y}\neq\mathbf{0}(D-\lambda_1I)\mathbf{y}=\mathbf{0},可知 \mathbf{y}=\alpha\boldsymbol{\lambda}_1\alpha\neq 0。因此,(D-\lambda_2I)\mathbf{x}=\alpha\boldsymbol{\lambda}_1,或表示為 D\mathbf{x}=\lambda_2\mathbf{x}+\alpha\boldsymbol{\lambda}_1。另一方面,令 \mathbf{z}=(D-\lambda_1I)\mathbf{x}。因為 D-\lambda_1ID-\lambda_2I 可交換,沿用上述推論步驟,可得 D\mathbf{x}=\lambda_1\mathbf{x}+\beta \boldsymbol{\lambda}_2\beta\neq 0。合併上面兩式,(\lambda_1-\lambda_2)\mathbf{x}-\alpha\boldsymbol{\lambda}_1+\beta\boldsymbol{\lambda}_2=\mathbf{0},但 \{\mathbf{x},\boldsymbol{\lambda}_1,\boldsymbol{\lambda}_2\} 是一個線性獨立集,即有 \lambda_1=\lambda_2\alpha=\beta=0,得到一個矛盾。因此,\{\boldsymbol{\lambda}_1,\boldsymbol{\lambda}_2\}N(D^2-D-I) 的一組基底,稱為解基 (solution basis)。每一 \mathbf{a}\in N(D^2-D-I) 可表示成解基 \boldsymbol{\lambda}_1\boldsymbol{\lambda}_2 的唯一線性組合:

\mathbf{a}=c_1\boldsymbol{\lambda}_1+c_2\boldsymbol{\lambda}_2

其中第 n 項為 a_n=c_1\lambda_1^n+c_2\lambda_2^nn\ge 0

 
上述解法涉及無限維向量空間,不適宜矩陣分析,故不常見於線性代數教本。第二個解法是將齊次遞迴關係式寫成線性聯立方程組:

\displaystyle\begin{aligned}  a_n&=a_{n-1}+a_{n-2}\\  a_{n-1}&=a_{n-1},  \end{aligned}

或表示為矩陣形式:

\displaystyle  \begin{bmatrix}  a_n\\  a_{n-1}  \end{bmatrix}=\begin{bmatrix}  1&1\\  1&0  \end{bmatrix}\begin{bmatrix}  a_{n-1}\\  a_{n-2}  \end{bmatrix},~~n\ge 2

\mathbf{u}_n=\begin{bmatrix}    a_{n+1}\\      a_n      \end{bmatrix}A=\begin{bmatrix}      1&1\\      1&0      \end{bmatrix}。上式可簡明地寫為差分方程:

\mathbf{u}_{n+1}=A\mathbf{u}_n,~~n=0,1,2,\ldots

其中初始條件為 \mathbf{u}_0=\begin{bmatrix}  a_1\\  a_0  \end{bmatrix}=\begin{bmatrix}      1\\      0      \end{bmatrix}。解差分方程等同於計算冪矩陣 A^n,因為

\mathbf{u}_n=A\mathbf{u}_{n-1}=A(A\mathbf{u}_{n-2})=A^2\mathbf{u}_{n-2}=\cdots=A^n\mathbf{u}_0

下面說明如何計算 A^n。寫出 A 的特徵多項式

\displaystyle  p(t)=\det(A-tI)=\begin{vmatrix}  1-t&1\\  1&-t  \end{vmatrix}=t^2-t-1

二根 \lambda_1\lambda_2A 的特徵值,分別對應特徵向量 \begin{bmatrix}  \lambda_1\\  1  \end{bmatrix}\begin{bmatrix}  \lambda_2\\  1  \end{bmatrix}。任一方陣的相異特徵值對應線性獨立的特徵向量 (見“相異特徵值對應線性獨立的特徵向量之簡易證明”),故 A 可對角化為 A=S\Lambda S^{-1},其中 \Lambda=\hbox{diag}(\lambda_1,\lambda_2)S=\begin{bmatrix}  \lambda_1&\lambda_2\\  1&1  \end{bmatrix},即有 A^n=(S\Lambda S^{-1})^n=S\Lambda^nS^{-1}。令 \begin{bmatrix}  c_1\\  c_2  \end{bmatrix}=S^{-1}\mathbf{u}_0。使用前述結果,

\displaystyle\begin{aligned}   \begin{bmatrix}  a_{n+1}\\  a_n  \end{bmatrix}&=\mathbf{u}_n=A^n\mathbf{u}_0=S\Lambda^nS^{-1}\mathbf{u}_0\\  &=\begin{bmatrix}  \lambda_1&\lambda_2\\  1&1  \end{bmatrix}\begin{bmatrix}  \lambda_1^n&0\\  0&\lambda_2^n  \end{bmatrix}\begin{bmatrix}  c_1\\  c_2  \end{bmatrix}\\  &=\begin{bmatrix}  c_1\lambda_1^{n+1}+c_2\lambda_2^{n+1}\\  c_1\lambda_1^{n}+c_2\lambda_2^{n}  \end{bmatrix},  \end{aligned}

其中第二元給出 a_n=c_1\lambda_1^{n}+c_2\lambda_2^{n}n\ge 0

 
根據以上討論,一 k 階常係數線性齊次遞迴關係式 a_n=d_1a_{n-1}+d_2a_{n-2}+\cdots+d_ka_{n-k} 的求解程序包含兩個步驟:

  1. 寫出特徵方程

    \displaystyle  t^k=d_1t^{k-1}+d_2t^{k-2}+\cdots+d_k

    並解出特徵多項式的 k 個根 \lambda_1,\ldots,\lambda_k

  2. \lambda_1,\ldots,\lambda_k 彼此相異,通項為

    \displaystyle   a_n=c_1\lambda_1^n+c_2\lambda_2^n+\cdots+c_k\lambda_k^n,~~n\ge 0

  3. 組合係數 c_1,\ldots,c_k 可由給定的 k 個初始條件解得:a_j=c_1\lambda_1^j+c_2\lambda_2^j+\cdots+c_k\lambda_k^jj=0,1,\ldots,k-1。因為 \lambda_1,\ldots,\lambda_k 相異,係數 c_1,\ldots,c_k 有唯一解 (見“線性世界的根基──疊加原理”)。

 
回到前面的例子,費布納西數列的遞歸規則 a_n=a_{n-1}+a_{n-2} 的特徵方程為 t^2=t+1,解出二根 \lambda_1=\frac{1+\sqrt{5}}{2}\lambda_2=\frac{1-\sqrt{5}}{2},故通項可表示為 a_n=c_1\lambda_1^n+c_2\lambda_2^n,其中組合係數 c_1c_2 由初始值決定,0=a_0=c_1+c_21=a_1=c_1\lambda_1+c_2\lambda_2,解得 c_1=\frac{1}{\sqrt{5}}c_2=-\frac{1}{\sqrt{5}}。合併以上結果,費布納西數列的第 n 項為

\displaystyle    a_n=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right],~~n=0,1,2,\ldots

 
如果特徵多項式包含重根,譬如,假設常係數遞迴關係式 a_n=d_1a_{n-1}+d_2a_{n-2}+d_3a_{n-3} 的特徵多項式有重根 \lambda,重數為 3,通項 a_n 的表達式為何?要完整地回答這個問題涉及 Jordan 形式。此外,若控制項 F(n)\neq 0,如何求得非齊次遞迴關係式的一個特解?我們將在續篇討論這兩個主題。

 
附註:
[1] 網友Meiyue Shao提供一個 \dim N((D-\lambda_1I)(D-\lambda_2I))=2 的證明:假設 \mathcal{X}=N((D-\lambda_1I)(D-\lambda_2I)) 是有限維的子空間,n=\dim\mathcal{X}>2。對於任一 \mathbf{x}\in\mathcal{X},設 \mathbf{y}=(D-\lambda_1I)\mathbf{x},則

\begin{aligned}  (D-\lambda_1I)(D-\lambda_2I)\mathbf{y}&=(D-\lambda_1I)(D-\lambda_2I)(D-\lambda_1I)\mathbf{x}\\  &=(D-\lambda_1I)(D-\lambda_1I)(D-\lambda_2I)\mathbf{x}\\  &=(D-\lambda_1I)\mathbf{0}=\mathbf{0},\end{aligned}

說明 (D-\lambda_1I)\mathbf{x}\in\mathcal{X}。同樣道理,(D-\lambda_2I)\mathbf{x}\in\mathcal{X}。我們將線性算子 D-\lambda_iI 限定於子空間 \mathcal{X},稱為限定算子 (restriction),記作 (D-\lambda_iI)_{/\mathcal{X}}i=1,2。對於每一 \mathbf{x}\in\mathcal{X}(D-\lambda_1I)_{/\mathcal{X}}(D-\lambda_2I)_{/\mathcal{X}}\mathbf{x}=\mathbf{0},即知 \hbox{rank}((D-\lambda_1I)_{/\mathcal{X}}(D-\lambda_2I)_{/\mathcal{X}})=0。另一方面,根據秩─零度定理,\hbox{rank}((D-\lambda_iI)_{/\mathcal{X}})=n-\dim N((D-\lambda_iI)_{/\mathcal{X}})=n-1i=1,2。利用 Sylvester 不等式 (見“破解矩陣秩的等式與不等式證明”,不等式二),

\begin{aligned}  \hbox{rank}((D-\lambda_1I)_{/\mathcal{X}}(D-\lambda_2I)_{/\mathcal{X}})&\ge\hbox{rank}(D-\lambda_1I)_{/\mathcal{X}}+\hbox{rank}(D-\lambda_2I)_{/\mathcal{X}}-n\\  &=(n-1)+(n-1)-n=n-2>0,\end{aligned}

得到矛盾結果,證畢。

繼續閱讀:
Advertisements
本篇發表於 特徵分析, 線性代數專欄 並標籤為 , , , 。將永久鏈結加入書籤。

7 則回應給 常係數線性遞迴關係式 (上)

  1. Meiyue Shao 說道:

    我觉得第一种方法里从 N(D^2-D-I) 包含两个线性无关的特征向量得到 N(D^2-D-I) 的维数就是 2 这步有逻辑跳跃,还需要再解释一两句。

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s