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

本文的閱讀等級:中級

前文介紹了常係數線性齊次遞迴關係式在特徵多項式有相異根的情況下的兩個線性代數解法 (見“常係數線性遞迴關係式 (上)”)。第一個方法建立於數列形成的無限維向量空間,通過與齊次遞迴關係式的特徵多項式同形式之算子多項式的零空間找出解。然而,當特徵多項式存在重根時,零空間基底的推導過程相當繁複。本文使用第二個方法,以簡潔的矩陣分析解出當特徵多項式存在重根時齊次遞迴關係式的通項表達式。

 
我們以五階線性齊次遞迴關係式為例說明解法。假設數列 \{a_n\} 滿足

a_n=d_1a_{n-1}+d_2a_{n-2}+d_3a_{n-3}+d_4a_{n-4}+d_5a_{n-5},~~n\ge 5

其中 d_1,\ldots,d_5 是常數,d_5\neq 0。上式再加入四個等式 a_{n-i}=a_{n-i}1\le i\le 4,構成一線性聯立方程組,以矩陣表示如下:

\begin{bmatrix}  a_n\\  a_{n-1}\\  a_{n-2}\\  a_{n-3}\\  a_{n-4}\end{bmatrix}=\begin{bmatrix}  d_1&d_2&d_3&d_4&d_5\\  1&0&0&0&0\\  0&1&0&0&0\\  0&0&1&0&0\\  0&0&0&1&0  \end{bmatrix}\begin{bmatrix}  a_{n-1}\\  a_{n-2}\\  a_{n-3}\\  a_{n-4}\\  a_{n-5}  \end{bmatrix}

或簡記為 \mathbf{u}_{n-4}=A\mathbf{u}_{n-5},其中 A 是係數矩陣,\mathbf{u}_{n-i}=(a_{n-i+4},\ldots,a_{n-i})^T。因為 d_5\neq 0,觀察可知係數矩陣 A 有線性獨立的行向量 (column vector),故 A 是可逆矩陣。換句話說,利用 \mathbf{u}_{n-5}=A^{-1}\mathbf{u}_{n-4},數列 \{a_n\} 可以反向回溯。對於 n\ge 0,不難驗證

\mathbf{u}_n=\begin{bmatrix}  a_{n+4}\\  a_{n+3}\\  a_{n+2}\\  a_{n+1}\\  a_n  \end{bmatrix}=A^n\begin{bmatrix}  a_4\\  a_3\\  a_2\\  a_1\\  a_0  \end{bmatrix}=A^n\mathbf{u}_0

其中 a_0,a_1,\ldots,a_4 是初始條件。

 
接下來的問題要計算 A^n。標準的作法是寫出 Jordan 形式 A=MJM^{-1},其中 J 為 Jordan 矩陣,即得 A^n=MJ^nM^{-1}。Jordan 矩陣 J 的推導過程說明於下。考慮係數矩陣 A 的特徵多項式,以第一列 (row) 展開,可得

\displaystyle\begin{aligned}  p(t)&=\det(A-tI)=\begin{vmatrix}  d_1-t&d_2&d_3&d_4&d_5\\  1&-t&0&0&0\\  0&1&-t&0&0\\  0&0&1&-t&0\\  0&0&0&1&-t  \end{vmatrix}\\  &=(d_1-t)(-t)^4-d_2(-t)^3+d_3(-t)^2-d_4(-t)+d_5\\  &=(-1)^5\left(t^5-d_1t^4-d_2t^3-d_3t^2-d_4t-d_5\right).  \end{aligned}

忽略常數 (-1)^5,遞迴關係式的特徵多項式即為係數矩陣 A 的特徵多項式,說明 A 的特徵值決定通項的形式。上面這種特殊形態的係數矩陣 A 稱為多項式 p(t) 的相伴 (companion) 矩陣。為便利說明,考慮下例,

a_n=15a_{n-2}+10a_{n-3}-60a_{n-4}-72a_{n-5}

對應的特徵方程

t^5=15t^3+10t^2-60t-72

等價於 (t-3)^2(t+2)^3=0,特徵多項式 p(t) 有兩個相異根,\lambda_1=3 (重數為 2) 和 \lambda_2=-2 (重數為 3)。相伴矩陣具有一個特別的性質 (見“多項式的相伴矩陣”):相伴矩陣 A 的特徵多項式即為最小多項式 (minimal polynomial)。具體的表現是,從特徵多項式 (也是最小多項式) p(t)=(-1)^5(t-\lambda_1)^2(t-\lambda_2)^3 可斷言 A 的 Jordan 矩陣為

\displaystyle  J=J(\lambda_1)\oplus J(\lambda_2)=\begin{bmatrix}  \lambda_1&1&\vline&0&0&0\\  0&\lambda_1&\vline&0&0&0\\\hline  0&0&\vline&\lambda_2&1&0\\  0&0&\vline&0&\lambda_2&1\\  0&0&\vline&0&0&\lambda_2  \end{bmatrix}

也就是說,J(\lambda_i) 分塊的指標 (index,最大 Jordan 分塊階數) 等於 \lambda_i 的重數。據此,J 的冪為 (見“Jordan 分塊”)

\displaystyle  J^n=\begin{bmatrix}  \lambda_1^n&n\lambda_1^{n-1}&\vline&0&0&0\\  0&\lambda_1^n&\vline&0&0&0\\\hline  0&0&\vline&\lambda_2^n&n\lambda_2^{n-1}&\frac{n(n-1)}{2}\lambda_2^{n-2}\\  0&0&\vline&0&\lambda_2^n&n\lambda_2^{n-1}\\  0&0&\vline&0&0&\lambda_2^n  \end{bmatrix}

因為 A 是可逆矩陣,特徵值 \lambda_1\lambda_2 不為零。再者,矩陣乘法是線性運算,通項 a_n,即 A^n\mathbf{u}_0=MJ^nM^{-1}\mathbf{u}_0 的第 5 個元,必為 \lambda_1^n,\left(\frac{n}{\lambda_1}\right)\lambda_1^n, \lambda_2^n,\left(\frac{n}{\lambda_2}\right)\lambda_2^n,\left(\frac{n}{\lambda_2}\right)^2\lambda_2^n 的線性組合。將分母併入組合係數,a_n 可表示為

\displaystyle\begin{aligned}  a_n&=(\alpha_0+\alpha_1n)\lambda_1^n+(\beta_0+\beta_1n+\beta_2n^2)\lambda_2^n\\  &=(\alpha_0+\alpha_1n)3^n+(\beta_0+\beta_1n+\beta_2n^2)(-2)^n,~~n\ge 0,\end{aligned}

其中係數 \alpha_0,\alpha_1,\beta_0,\beta_1,\beta_2 由初始條件 a_0,a_1,\ldots,a_4 決定。當 n=0,1,\ldots,4,可得

\displaystyle  \begin{bmatrix}  1&1&0&0&0\\  \lambda_1&\lambda_2&\lambda_1&\lambda_2&\lambda_2\\  \lambda_1^2&\lambda_2^2&2\lambda_1^2&2\lambda_2^2&2^2\lambda_2^2\\  \lambda_1^3&\lambda_2^3&3\lambda_1^3&3\lambda_2^3&3^2\lambda_2^3\\  \lambda_1^4&\lambda_2^4&4\lambda_1^4&4\lambda_2^4&4^2\lambda_2^4  \end{bmatrix}\begin{bmatrix}  \alpha_0\\  \beta_0\\  \alpha_1\\  \beta_1\\  \beta_2  \end{bmatrix}=\begin{bmatrix}  a_0\\  a_1\\  a_2\\  a_3\\  a_4  \end{bmatrix}

上面的係數矩陣是可逆的,故組合係數有唯一解,理由如下:(1) 因為 \lambda_1\lambda_2 相異且不為零,第 1 行和第 2 行是獨立的;(2) 如不考慮零元,第 3-5 行可分解為

\begin{bmatrix}  \lambda_1&\lambda_2&\lambda_2\\  2\lambda_1^2&2\lambda_2^2&2^2\lambda_2^2\\  3\lambda_1^3&3\lambda_2^3&3^2\lambda_2^3\\  4\lambda_1^4&4\lambda_2^4&4^2\lambda_2^4  \end{bmatrix}=\begin{bmatrix}  1&0&0&0\\  0&2&0&0\\  0&0&3&0\\  0&0&0&4  \end{bmatrix}\begin{bmatrix}  \lambda_1&\lambda_2&0\\  \lambda_1^2&\lambda_2^2&\lambda_2^2\\  \lambda_1^3&\lambda_2^3&2\lambda_2^3\\  \lambda_1^4&\lambda_2^4&3\lambda_2^4  \end{bmatrix}\begin{bmatrix}  1&0&0\\  0&1&1\\  0&0&1  \end{bmatrix}

推知第 3-5 行是獨立的;(3) 第 1-2 行和第 3-5 行的領先列位置相異,因此彼此獨立。

 
給定一 k 階常係數線性齊次遞迴關係式 a_n=d_1a_{n-1}+d_2a_{n-2}+\cdots+d_ka_{n-k}d_k\neq 0,以上求解程序可簡化為兩個步驟:

  1. 寫出特徵方程

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

    並解出特徵多項式的根,假設有 m 個相異根 \lambda_1,\ldots,\lambda_m,重數分別為 \beta_1,\ldots,\beta_m

  2. 通項 a_n 的表達式為

    \displaystyle     a_n=p_1(n)\lambda_1^n+p_2(n)\lambda_2^n+\cdots+p_m(n)\lambda_m^n,~~n\ge 0

    其中 p_i(n)=c_{i0}+c_{i1}n+\cdots+c_{i,\beta_{i-1}}n^{\beta_i-1}i=1,\ldots,m,組合係數 \{c_{ij}\} 由給定的初始條件 a_0,a_1,\ldots,a_{k-1} 唯一決定。

繼續閱讀:
廣告
本篇發表於 線性代數專欄, 典型形式 並標籤為 , , 。將永久鏈結加入書籤。

發表迴響

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

WordPress.com Logo

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

Twitter picture

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

Facebook照片

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

Google+ photo

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

連結到 %s