高中數學擴充套件/矩陣/線性遞推關係再探

高中數學擴充套件

---

補充章節 — 素數和模算術 — 邏輯

數學證明 — 集合論和無限過程 — 計數和生成函式 — 離散機率

矩陣 — 進一步的模算術 — 數學規劃 — 馬爾可夫鏈

HSME
內容
矩陣
遞推關係
問題和專案
問題集
專案
解決方案
練習解答
問題集解答
雜項
定義表
完整版

*線性遞推關係再探*

我們在計數與生成函式章節中已經討論過線性遞推關係。我們將在矩陣的幫助下再次研究它。考慮斐波那契數列

1, 1, 2, 3, 5, 8, 13, 21...

其中每個數字都是前兩個數字的總和。令x_n為第 (n + 1) 個斐波那契數，我們可以寫成

${\begin{matrix}{\begin{pmatrix}x_{n}\\x_{n-1}\end{pmatrix}}&=&{\begin{pmatrix}x_{n-1}+x_{n-2}\\x_{n-1}\end{pmatrix}}\\\\&=&{\begin{pmatrix}1&1\\1&0\end{pmatrix}}{\begin{pmatrix}x_{n-1}\\x_{n-2}\end{pmatrix}}\\\\&=&{\begin{pmatrix}1&1\\1&0\end{pmatrix}}^{2}{\begin{pmatrix}x_{n-2}\\x_{n-3}\end{pmatrix}}\\\\&...\\\\&=&{\begin{pmatrix}1&1\\1&0\end{pmatrix}}^{n-1}{\begin{pmatrix}x_{1}\\x_{0}\end{pmatrix}}\\\\&=&{\begin{pmatrix}1&1\\1&0\end{pmatrix}}^{n-1}{\begin{pmatrix}1\\1\end{pmatrix}}\end{matrix}}$

事實上，許多線性遞推關係可以用矩陣形式表示，例如

$x_{n}=2x_{n-1}+x_{n-2};\ {\mbox{if n}}\geq 2$

$x_{1}=1$

$x_{0}=1$

可以表示為

${\begin{pmatrix}x_{n}\\x_{n-1}\end{pmatrix}}={\begin{pmatrix}2&1\\1&0\end{pmatrix}}{\begin{pmatrix}x_{n-1}\\x_{n-2}\end{pmatrix}}$

因此

${\begin{pmatrix}x_{n}\\x_{n-1}\end{pmatrix}}={\begin{pmatrix}2&1\\1&0\end{pmatrix}}^{n-1}{\begin{pmatrix}1\\1\end{pmatrix}}$

所以，如果我們知道如何快速計算矩陣的冪，那麼我們可以相當快地計算出第 (n + 1) 個斐波那契數！

快速計算冪

請注意，從現在開始，我們將強調矩陣是否是向量，並在其頂部新增箭頭以區分。

考慮

$A={\begin{pmatrix}1&-2\\1&4\end{pmatrix}}$

${\overrightarrow {x}}={\begin{pmatrix}2\\-1\end{pmatrix}}$

${\overrightarrow {y}}={\begin{pmatrix}-1\\1\end{pmatrix}}$

當您將 *A* 乘以 ${\overrightarrow {x}}$ 或 ${\overrightarrow {y}}$ 時（*試試看*），會發生一些有趣的事情。實際上

$A{\overrightarrow {x}}=2{\overrightarrow {x}}$

以及

$A{\overrightarrow {y}}=3{\overrightarrow {y}}$.

通常對於矩陣 *B*，如果向量 *w* ≠ *0*（所有條目為零的矩陣），使得

$B{\overrightarrow {w}}=\lambda {\overrightarrow {w}}$

對於一些標量 λ，那麼 ${\overrightarrow {w}}$ 被稱為 *B* 的特徵向量，而 λ 被稱為 *B* 的特徵值（對應於 *w*）。

這是矩陣的一個特徵，可以利用它來輕鬆計算冪。以下是使用上面 *A*、*x* 和 *y* 的方法，我們將這兩條資訊以矩陣形式放在一起

$A{\begin{pmatrix}{\overrightarrow {x}}&{\overrightarrow {y}}\end{pmatrix}}={\begin{pmatrix}{\overrightarrow {x}}&{\overrightarrow {y}}\end{pmatrix}}{\begin{pmatrix}2&0\\0&3\end{pmatrix}}$

或者以完全數字形式寫

${\begin{pmatrix}1&-2\\1&4\end{pmatrix}}{\begin{pmatrix}2&-1\\-1&1\end{pmatrix}}={\begin{pmatrix}2&-1\\-1&1\end{pmatrix}}{\begin{pmatrix}2&0\\0&3\end{pmatrix}}$

我們鼓勵您檢查上述內容是否正確。我們所做的是將 ${\overrightarrow {x}}$ 和 ${\overrightarrow {y}}$ 合併到一個矩陣中，使用每個向量作為一列，然後我們將其乘以對角矩陣，對角矩陣的條目分別是每個特徵向量的特徵值。

如何利用這種矩陣形式快速計算 *A* 的冪？我們只需要一個簡單但巧妙的步驟 - 在等式兩邊右乘（即從右邊乘）的逆矩陣是

${\begin{pmatrix}2&-1\\-1&1\end{pmatrix}}$

我們有

${\begin{pmatrix}1&-2\\1&4\end{pmatrix}}={\begin{pmatrix}2&-1\\-1&1\end{pmatrix}}{\begin{pmatrix}2&0\\0&3\end{pmatrix}}{\begin{pmatrix}2&-1\\-1&1\end{pmatrix}}^{-1}$

現在要計算 Aⁿ，我們只需要做

$A^{n}={\begin{pmatrix}1&-2\\1&4\end{pmatrix}}^{n}=$

${\begin{pmatrix}2&-1\\-1&1\end{pmatrix}}{\begin{pmatrix}2&0\\0&3\end{pmatrix}}{\begin{pmatrix}2&-1\\-1&1\end{pmatrix}}^{-1}...{\begin{pmatrix}2&-1\\-1&1\end{pmatrix}}{\begin{pmatrix}2&0\\0&3\end{pmatrix}}{\begin{pmatrix}2&-1\\-1&1\end{pmatrix}}^{-1}$

但逆矩陣相乘得到 I，所以我們剩下的是

$A^{n}={\begin{pmatrix}1&-2\\1&4\end{pmatrix}}^{n}={\begin{pmatrix}2&-1\\-1&1\end{pmatrix}}{\begin{pmatrix}2&0\\0&3\end{pmatrix}}^{n}{\begin{pmatrix}2&-1\\-1&1\end{pmatrix}}^{-1}$

這很容易計算，因為對角矩陣的冪很容易計算（只需將每個元素乘以自身n次即可）。

示例 1

計算 A⁵，其中 A 如上所示。

解 我們得到

$A^{5}={\begin{pmatrix}2&-1\\-1&1\end{pmatrix}}{\begin{pmatrix}2&0\\0&3\end{pmatrix}}^{5}{\begin{pmatrix}2&-1\\-1&1\end{pmatrix}}^{-1}$

$A^{5}={\begin{pmatrix}2&-1\\-1&1\end{pmatrix}}{\begin{pmatrix}2^{5}&0\\0&3^{5}\end{pmatrix}}{\begin{pmatrix}1&1\\1&2\end{pmatrix}}$

$A^{5}={\begin{pmatrix}2^{6}-3^{5}&2^{6}-2\times 3^{5}\\-2^{5}+3^{5}&-2^{5}+2\times 3^{5}\end{pmatrix}}$

示例 2

令

$B={\begin{pmatrix}-13&28\\-8&17\end{pmatrix}}$

並且它的特徵向量是

${\begin{pmatrix}2\\1\end{pmatrix}}$ 和 ${\begin{pmatrix}7\\4\end{pmatrix}}$

直接計算B⁵（可選），並使用上述方法再次計算。

解答 我們首先需要確定其特徵值。我們有

${\begin{pmatrix}-13&28\\-8&17\end{pmatrix}}{\begin{pmatrix}2\\1\end{pmatrix}}={\begin{pmatrix}2\\1\end{pmatrix}}$

因此，對應於

${\begin{pmatrix}2\\1\end{pmatrix}}$

的特徵值為 1。

類似地，

${\begin{pmatrix}-13&28\\-8&17\end{pmatrix}}{\begin{pmatrix}7\\4\end{pmatrix}}={\begin{pmatrix}21\\12\end{pmatrix}}=3{\begin{pmatrix}7\\4\end{pmatrix}}$

因此，另一個特徵值為 3。

現在我們以以下形式寫出它們

${\begin{pmatrix}-13&28\\-8&17\end{pmatrix}}{\begin{pmatrix}2&7\\1&4\end{pmatrix}}={\begin{pmatrix}2&7\\1&4\end{pmatrix}}{\begin{pmatrix}1&0\\0&3\end{pmatrix}}$

現在將B作為主體

${\begin{pmatrix}-13&28\\-8&17\end{pmatrix}}={\begin{pmatrix}2&7\\1&4\end{pmatrix}}{\begin{pmatrix}1&0\\0&3\end{pmatrix}}{\begin{pmatrix}4&-7\\-1&2\end{pmatrix}}$

現在

${\begin{pmatrix}-13&28\\-8&17\end{pmatrix}}^{5}={\begin{pmatrix}2&7\\1&4\end{pmatrix}}{\begin{pmatrix}1^{5}&0\\0&3^{5}\end{pmatrix}}{\begin{pmatrix}4&-7\\-1&2\end{pmatrix}}$

因此，將右側相乘，我們得到

${\begin{pmatrix}-13&28\\-8&17\end{pmatrix}}^{5}={\begin{pmatrix}8-7\times 3^{5}&14(3^{5}-1)\\4(3^{5}-1)&-7+8\times 3^{5}\end{pmatrix}}$

總結 - 快速計算冪

給定矩陣A的特徵向量

1. 計算特徵值（如果未給出）
2. 以A = PDP^-1的形式寫出，其中D是特徵值的對角矩陣，P是特徵向量作為列
3. 使用等式右側計算Aⁿ

練習

1. 矩陣

$B={\begin{pmatrix}-8&6\\-15&11\end{pmatrix}}$

的特徵向量為

${\begin{pmatrix}2\\3\end{pmatrix}}$ 和 ${\begin{pmatrix}3\\5\end{pmatrix}}$

計算B⁵

2. 矩陣

$B={\begin{pmatrix}-8&6\\-9&7\end{pmatrix}}$

的特徵向量為

${\begin{pmatrix}1\\1\end{pmatrix}}$ 和 ${\begin{pmatrix}2\\3\end{pmatrix}}$

計算B⁵

3. 矩陣

$B={\begin{pmatrix}177&-140\\225&-178\end{pmatrix}}$

的特徵向量為

${\begin{pmatrix}4\\5\end{pmatrix}}$ 和 ${\begin{pmatrix}7\\9\end{pmatrix}}$

計算B⁵

特徵向量和特徵值

從上一節我們知道，對於一個矩陣，如果我們知道它的特徵向量，就可以求出相應的特徵值，進而快速求出矩陣的冪。所以最後的難點是尋找特徵向量。

一個矩陣A的特徵向量${\overrightarrow {x}}$ 和其對應的特徵值λ滿足以下關係式

$A{\overrightarrow {x}}=\lambda {\overrightarrow {x}}$

其中x ≠ 0，0 為零矩陣（所有元素都為零）。可以安全地假設A 是已知的，所以有兩個未知數 - ${\overrightarrow {x}}$ 和 λ。現在我們有足夠的資訊來計算出特徵值（然後得出特徵向量）

$A{\overrightarrow {x}}-\lambda {\overrightarrow {x}}=0$

$A{\overrightarrow {x}}-\lambda I{\overrightarrow {x}}=0$

$(A-\lambda I){\overrightarrow {x}}=0$

矩陣 (A - λI) 必須沒有逆矩陣，因為如果有，那麼${\overrightarrow {x}}$ = 0。因此，det(A - λI) = 0。假設

$A={\begin{pmatrix}a&b\\c&d\end{pmatrix}}$

那麼

$A-\lambda I={\begin{pmatrix}a-\lambda &b\\c&d-\lambda \end{pmatrix}}$

$0=\det(A-\lambda I)=(a-\lambda )(d-\lambda )-bc$

現在我們看到 det(A-λI) 是一個關於 λ 的多項式，並且 det(A-λI) = 0。我們已經非常熟練地解決二次方程，因此很容易計算出 λ 的值。一旦我們計算出 λ 的值，我們就可以計算出${\overrightarrow {x}}$（參見示例）。

示例 1

求解以下矩陣的特徵值和特徵向量：

$A={\begin{pmatrix}-4&15\\-2&7\end{pmatrix}}$

然後求解D 和 P 使得 A = P^-1DP。

解

我們的目標是找到${\overrightarrow {x}}$ 和 λ 使得

A${\overrightarrow {x}}$ = λ${\overrightarrow {x}}$

我們繼續

${\begin{pmatrix}-4&15\\-2&7\end{pmatrix}}{\overrightarrow {x}}=\lambda {\overrightarrow {x}}$

${\begin{pmatrix}-4-\lambda &15\\-2&7-\lambda \end{pmatrix}}{\overrightarrow {x}}=0$ (**)

det(A - λI) =

0 = (-4 - λ)(7 - λ) + 30

0 = -28 - 3λ + λ² + 30

0 = λ² - 3λ + 2

0 = (λ - 1)(λ - 2)

λ = 1, 2

現在對於每個特徵值，我們將得到一個不同的對應特徵向量。因此，我們分別考慮 λ = 1 和 λ = 2 的情況。

首先考慮 λ = 1，從（**）中得到

${\begin{pmatrix}-4-1&15\\-2&7-1\end{pmatrix}}x=0$

即

${\begin{pmatrix}-5&15\\-2&6\end{pmatrix}}{\begin{pmatrix}u\\v\end{pmatrix}}=0$

其中 $x={\begin{pmatrix}u\\v\end{pmatrix}}$ 由於 det(A - λI) = 0，我們知道上述方程沒有唯一解。但我們注意到

$x={\begin{pmatrix}3t\\1t\end{pmatrix}}$

對於任何實數 t 都是解，我們選擇 t = 1 作為我們的解，因為它是最簡單的。因此

$x={\begin{pmatrix}3\\1\end{pmatrix}}$

是對應於 λ = 1 的特徵向量。(***)

類似地，如果 λ = 2，從 (**) 我們得到

${\begin{pmatrix}-4-2&15\\-2&7-2\end{pmatrix}}x=0$

即

${\begin{pmatrix}-6&15\\-2&5\end{pmatrix}}{\begin{pmatrix}u\\v\end{pmatrix}}=0$

其中 $x={\begin{pmatrix}u\\v\end{pmatrix}}$ 我們注意到

$x={\begin{pmatrix}5t\\2t\end{pmatrix}}$

對於任何實數 t 都是解，和之前一樣，我們選擇 t = 1 作為我們的解。因此

$x={\begin{pmatrix}5\\2\end{pmatrix}}$ 是對應於 λ = 2 的特徵向量。(****)

我們總結 (***) 和 (****) 的結果，得到

$A{\begin{pmatrix}3\\1\end{pmatrix}}={\begin{pmatrix}3\\1\end{pmatrix}}$

$A{\begin{pmatrix}5\\2\end{pmatrix}}=2{\begin{pmatrix}5\\2\end{pmatrix}}$

我們將這些結果合併成一個

$A{\begin{pmatrix}3&5\\1&2\end{pmatrix}}={\begin{pmatrix}3&5\\1&2\end{pmatrix}}{\begin{pmatrix}1&0\\0&2\end{pmatrix}}$

因此

$A={\begin{pmatrix}3&5\\1&2\end{pmatrix}}{\begin{pmatrix}1&0\\0&2\end{pmatrix}}{\begin{pmatrix}3&5\\1&2\end{pmatrix}}^{-1}$

---

示例 2

a) 對矩陣 A 進行對角化，即找到可逆矩陣 P 和對角矩陣 B，使得 AP = PB

b) 計算 A⁵

$A={\begin{pmatrix}1&2\\-1&4\end{pmatrix}}$

解答 a) 我們要解 Ax = λx，其中 λ 為常數，x′ 為列向量。首先

$Ax-\lambda Ix=0$

$(A-\lambda I)x=0$

由於 'x′ ≠ 0，我們有

$det(A-\lambda I)=0$

即

$\det {\begin{pmatrix}1-\lambda &2\\-1&4-\lambda \end{pmatrix}}=0$

${\begin{matrix}(1-\lambda )(4-\lambda )+2&=&0\\\lambda ^{2}-5\lambda +6&=&0\end{matrix}}$

$\lambda =3,\ 2$

對於 λ = 3，

$(A-3I)x=0$

${\begin{pmatrix}-2&2\\-1&1\end{pmatrix}}{\begin{pmatrix}x\\y\end{pmatrix}}=0$

很明顯

${\begin{pmatrix}x\\y\end{pmatrix}}={\begin{pmatrix}1\\1\end{pmatrix}}$

是一個解。注意我們不能接受 x = 0 作為解，因為我們假設 x ≠ 0。還要注意

${\begin{pmatrix}x\\y\end{pmatrix}}={\begin{pmatrix}t\\t\end{pmatrix}}$

對於某個常數 t 也是一個解。實際上，我們可以使用 x = y = 2，3 或 4 作為解，但為了方便，我們選擇最簡單的，即 x = y = 1。

對於 λ = 2，

$(A-2I)x=0$

${\begin{pmatrix}-1&2\\-1&2\end{pmatrix}}{\begin{pmatrix}x\\y\end{pmatrix}}=0$

很明顯

${\begin{pmatrix}x\\y\end{pmatrix}}={\begin{pmatrix}2\\1\end{pmatrix}}$

是一個解。

因此

$A{\begin{pmatrix}1&2\\1&1\end{pmatrix}}={\begin{pmatrix}1&2\\1&1\end{pmatrix}}{\begin{pmatrix}3&0\\0&2\end{pmatrix}}$

是一個解，並且

$A{\begin{pmatrix}2&1\\1&1\end{pmatrix}}={\begin{pmatrix}2&1\\1&1\end{pmatrix}}{\begin{pmatrix}2&0\\0&3\end{pmatrix}}$

也是一個解。

b)

$A^{5}={\begin{pmatrix}{\begin{pmatrix}2&1\\1&1\end{pmatrix}}{\begin{pmatrix}2&0\\0&3\end{pmatrix}}{\begin{pmatrix}2&1\\1&1\end{pmatrix}}^{-1}\end{pmatrix}}^{5}$

$A^{5}={\begin{pmatrix}2&1\\1&1\end{pmatrix}}{\begin{pmatrix}2&0\\0&3\end{pmatrix}}^{5}{\begin{pmatrix}2&1\\1&1\end{pmatrix}}^{-1}$

$A^{5}={\begin{pmatrix}2&1\\1&1\end{pmatrix}}{\begin{pmatrix}2^{5}&0\\0&3^{5}\end{pmatrix}}{\begin{pmatrix}1&-1\\-1&2\end{pmatrix}}$

$A^{5}={\begin{pmatrix}2^{6}-3^{5}&2^{6}-2\times 3^{5}\\2^{5}-3^{5}&-2^{5}+2\times 3^{5}\end{pmatrix}}$

---

示例 3

求解線性遞推關係

${\begin{matrix}x_{n}&=&5x_{n-1}&-&6x_{n-2};\ {\mbox{if n}}\geq 2\\x_{1}&=&1\\x_{0}&=&0\\\end{matrix}}$

解

${\begin{pmatrix}x_{n}\\x_{n-1}\end{pmatrix}}={\begin{pmatrix}5&-6\\1&0\end{pmatrix}}^{n-1}{\begin{pmatrix}1\\0\end{pmatrix}}$

我們需要對角化

$A={\begin{pmatrix}5&-6\\1&0\end{pmatrix}}$

我們繼續

$\det {(A-\lambda I)}=0\!$

我們得到

λ = 2, 3

對於 λ = 2

$(A-2I)x=0\!$

$x={\begin{pmatrix}2\\1\end{pmatrix}}$

對於 λ = 3

$(A-3I)x=0\!$

$x={\begin{pmatrix}3\\1\end{pmatrix}}$

因此

$A={\begin{pmatrix}2&3\\1&1\end{pmatrix}}{\begin{pmatrix}2&0\\0&3\end{pmatrix}}{\begin{pmatrix}2&3\\1&1\end{pmatrix}}^{-1}$

現在

$A^{n-1}={\begin{pmatrix}2&3\\1&1\end{pmatrix}}{\begin{pmatrix}2&0\\0&3\end{pmatrix}}^{n-1}{\begin{pmatrix}-1&3\\1&-2\end{pmatrix}}$

$A^{n-1}={\begin{pmatrix}2&3\\1&1\end{pmatrix}}{\begin{pmatrix}2^{n-1}&0\\0&3^{n-1}\end{pmatrix}}{\begin{pmatrix}-1&3\\1&-2\end{pmatrix}}$

$A^{n-1}={\begin{pmatrix}-2^{n}+3^{n}&3\times 2^{n}-2\times 3^{n}\\-2^{n-1}+3^{n-1}&3\times 2^{n-1}-2\times 3^{n-1}\end{pmatrix}}$

因此

${\begin{pmatrix}x_{n}\\x_{n-1}\end{pmatrix}}={\begin{pmatrix}-2^{n}+3^{n}&3\times 2^{n}-2\times 3^{n}\\-2^{n-1}+3^{n-1}&3\times 2^{n-1}-2\times 3^{n-1}\end{pmatrix}}{\begin{pmatrix}1\\0\end{pmatrix}}$

${\begin{pmatrix}x_{n}\\x_{n-1}\end{pmatrix}}={\begin{pmatrix}-2^{n}+3^{n}\\-2^{n-1}+3^{n-1}\end{pmatrix}}$

也就是說

$x_{n}=-2^{n}+3^{n}\!$

練習

1. 計算A⁵，其中

$A={\begin{pmatrix}-12&10\\-21&17\end{pmatrix}}$

2. 計算A⁵，其中

$A={\begin{pmatrix}-6&28\\-2&9\end{pmatrix}}$

3. 解以下遞推關係

$x_{n}=3x_{n-1}-x_{n-2}\!$

$x_{1}=1\!$

$x_{0}=0\!$

解

1.

$A^{5}={\begin{pmatrix}-2922&2110\\-4431&3197\end{pmatrix}}$

2.

$A^{5}={\begin{pmatrix}-216&868\\-62&249\end{pmatrix}}$

更多應用

... 更多內容即將推出

---

習題集 > High_School_Mathematics_Extensions/Matrices/Problem Set

專案 > High_School_Mathematics_Extensions/Matrices/Project/Elementary_Matrices

反饋

你覺得怎麼樣？ 太簡單還是太難？ 資訊太多還是太少？ 我們怎樣才能改進？ 請在討論欄中留言告訴我們。 更好的是，自己編輯它，把它做得更好。