高中数学扩展/矩阵/线性递推关系再探

高中数学扩展

---

补充章节 — 素数和模算术 — 逻辑

数学证明 — 集合论和无限过程 — 计数和生成函数 — 离散概率

矩阵 — 进一步的模算术 — 数学规划 — 马尔可夫链

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

反馈

你觉得怎么样？ 太简单还是太难？ 信息太多还是太少？ 我们怎样才能改进？ 请在讨论栏中留言告诉我们。 更好的是，自己编辑它，把它做得更好。