矩阵的 n 次方和斐波那契数列通项式

斐波那契数列大家应该非常熟悉, 这是一个典型的递归定义的数列. 那么这样一个递归定义的数列的通项式是怎样的, 它又是如何推导出来的呢? 这里我们从寻找矩阵的 n 次方说起.

矩阵的 n 次方

首先只有方阵才有与自己相乘, 所以我们实际讨论的是方阵的 n 次方. 为了高效地求得一个 \(m\times m\) 的矩阵 \(A\) 的 n 次方 \(A^n\), 我们的做法是找到一个矩阵 \(P\) 和一个对角矩阵 \(B\), 使得 \(B=P^{-1}AP\). 这个过程称为矩阵的对角化(Diagonalize). 因为有 \(B=P^{-1}AP\), 必然有 \(A=PBP^{-1}\). 所以

\[A^n = (PBP^{-1})^n = (PBP^{-1})(PBP^{-1})...(PBP^{-1}) = PB^nP^{-1}\]

因为 \(B\) 是对角矩阵, 所以我们就可以很快地求出 \(A^n\) 了.

为了对角化矩阵, 我们需要找到所有的实数 \(\lambda\) 和非零单位向量 \(v\) 使得

\[Av=\lambda v \tag 1\]

成立. 实数 \(\lambda\) 就被称为矩阵 \(A\) 的特征值, 与之对应的向量 \(v\) 就被称为矩阵 \(A\) 的特征向量. 这也就是说对于向量 \(v\) 来说, 乘上矩阵 \(A\) 和乘上实数 \(\lambda\) 的效果是一样的.

我们在 \(Av=\lambda v\) 右边乘上单位矩阵 \(I\), 可以转换成 \((A-\lambda I)v=0\). 把 \(v\) 看作未知数, 这就是个齐次线性方程. 因为 \(v\) 是非零向量, 也就是说这个方程要有非零解; 而 \((A-\lambda I)\) 是方阵, 这样的齐次线性方程有非零解的条件就是 \(|A-\lambda I|=0\). 解这个方程就可得到若干个特征值 \(\lambda_1, \lambda_2, ...\). 然后把这些特征值带入 (1) 式, 就可得到每个特征值对应的特征向量.

\(A = \begin{pmatrix} 4 & -12\\ -12 & 11 \end{pmatrix}\) 为例. 首先我们解方程 \(|A-\lambda I|=0\)

\[ \begin{align} \begin{vmatrix} 4 - \lambda & -12\\ -12 & 11 - \lambda \end{vmatrix} = 0 \\ (4 - \lambda)(11 - \lambda) - 144 = 0 \\ \lambda^2 - 15\lambda - 100 = 0 \\ (\lambda - 20)(\lambda + 5) = 0 \\ \lambda_1 = 20, \lambda_2 = -5 \end{align} \]

得到两个特征值 \(\lambda_1 = 20, \lambda_2 = -5\). 然后我们分别将 \(\lambda_1, \lambda_2\) 代入 (1) 式, 得到关于每个特征向量的方程. 注意到特征向量是单位向量, 因此每个方程都有唯一解.

对于 \(\lambda_1 = 20\),

\[ \begin{align} & \left\{\begin{matrix} \begin{pmatrix} 4 & -12\\ -12 & 11 \end{pmatrix} \begin{pmatrix} x_1\\y_1 \end{pmatrix} = 20 \begin{pmatrix} x_1\\y_1 \end{pmatrix} \\ x_1^2 + y_1^2 = 1 \end{matrix}\right. \Leftrightarrow \left\{\begin{matrix} 4x_1 - 12y_1 = 20x_1\\ -12x_1 + 11y_1 = 20y_1\\ x_1^2 + y_1^2 = 1 \end{matrix}\right. \Leftrightarrow \left\{\begin{matrix} 4x_1 + 3y_1 = 0 \\ x_1^2 + y_1^2 = 1 \end{matrix}\right. \\ \\ & v_1 = \begin{pmatrix} x_1 \\ y_1 \end{pmatrix} = \begin{pmatrix} 3/5 \\ -4/5 \end{pmatrix} \end{align} \]

对于 \(\lambda_1 = -5\),

\[ \begin{align} & \left\{\begin{matrix} \begin{pmatrix} 4 & -12\\ -12 & 11 \end{pmatrix} \begin{pmatrix} x_2\\y_2 \end{pmatrix} = -5 \begin{pmatrix} x_2\\y_2 \end{pmatrix} \\ x_2^2 + y_2^2 = 1 \end{matrix}\right. \Leftrightarrow \left\{\begin{matrix} 4x_2 - 12y_2 = -5x_2\\ -12x_2 + 11y_2 = -5y_2\\ x_2^2 + y_2^2 = 1 \end{matrix}\right. \Leftrightarrow \left\{\begin{matrix} 3x_2 - 4y_2 = 0 \\ x_2^2 + y_2^2 = 1 \end{matrix}\right. \\ \\ & v_2 = \begin{pmatrix} x_2 \\ y_2 \end{pmatrix} = \begin{pmatrix} 4/5 \\ 3/5 \end{pmatrix} \end{align} \]

求得特征向量和特征值之后, 我们就可以对角化矩阵了. 假设一个 \(m\times m\) 的矩阵 \(A\) 有 m 个不同的特征值和特征向量, 我们以特征向量为列向量构造矩阵 \(P = (v_1, v_2, ..., v_m)\). 那么有

\[ \begin{align} AP &= A(v_1, v_2, ..., v_m) \\ &= (Av_1, Av_2, ..., Av_m) \\ &= (\lambda_1 v_1, \lambda_2 v_2, ..., \lambda_m v_m) \\ &= (v_1, v_2, ..., v_m)\begin{pmatrix} \lambda_1 & & & \\ & \lambda_2 & & \\ & & ... & \\ & & & \lambda_m \end{pmatrix} \end{align} \]

我们记对角矩阵 \(\begin{pmatrix} \lambda_1 & & & \\ & \lambda_2 & & \\ & & ... & \\ & & & \lambda_m \end{pmatrix}\)\(B\), 所以有 \(AP = PB\). 因为 \(A\) 有 m 个不同的特征值, 所以这些特征值对应的特征向量是线性无关的(证明略). 因此矩阵 \(P\) 的逆存在, 所以有 \(A=PBP^{-1}\)\(B=P^{-1}AP\). 这就完成了矩阵的对角化.

我们还以 \(A = \begin{pmatrix} 4 & -12\\ -12 & 11 \end{pmatrix}\) 为例, \(A\) 有两个特征值 \(\lambda_1 = 20, \lambda_2 = -5\) 和与之对应的特征向量 \(v_1 = \begin{pmatrix} 3/5 \\ -4/5 \end{pmatrix}, v_2 = \begin{pmatrix} 4/5 \\ 3/5 \end{pmatrix}\). 因此 \(P = \begin{pmatrix} 3/5 & 4/5 \\ -4/5 & 3/5 \end{pmatrix}\)\(B = \begin{pmatrix} 20 & 0 \\ 0 & -5 \end{pmatrix}\). 可以计算出

\[ \begin{align} A^n &= \begin{pmatrix} 3/5 & 4/5 \\ -4/5 & 3/5 \end{pmatrix} \begin{pmatrix} 20^n & 0 \\ 0 & -5^n \end{pmatrix} \begin{pmatrix} 3/5 & 4/5 \\ -4/5 & 3/5 \end{pmatrix}^{-1} \\ &= \frac{1}{25} \begin{pmatrix} 9 \cdot 20^n + 12(-5)^n & -12 \cdot 20^n + 12(-5)^n \\ -12 \cdot 20^n + 12(-5)^n & -16 \cdot 20^n + 9(-5)^n \end{pmatrix} \end{align} \]

斐波那契数列的通项式

斐波那契数列 \(F_n\) 定义 \(F_1 = F_2 = 0\), 且 \(F_n = F_{n-1} + F_{n-2}\). 因此我们有

\[ \begin{align} \begin{pmatrix} F_{n+2} \\ F_{n+1} \end{pmatrix} &= \begin{pmatrix} F_{n+1} + F_n \\ F_{n+1} \end{pmatrix} \\ &= \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} F_{n+1} \\ F_n \end{pmatrix} \\ &= \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^2 \begin{pmatrix} F_n \\ F_{n-1} \end{pmatrix} \\ &... \\ &= \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n \begin{pmatrix} F_2 \\ F_1 \end{pmatrix} \\ &= \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n \begin{pmatrix} 1 \\ 1 \end{pmatrix} \tag 2 \end{align} \]

问题转换成求矩阵 \(\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}\) 的 n 次方.

那么我们首先求解方程 \(|A-\lambda I| = 0\):

\[ \begin{align} \begin{vmatrix} 1 - \lambda & 1 \\ 1 & -\lambda \end{vmatrix} &= 0 \\ \lambda^2 - \lambda - 1 &= 0 \\ \lambda_1 = \frac{1+\sqrt 5}{2} &, \lambda_2 = \frac{1-\sqrt 5}{2} \end{align} \]

又根据 (1) 式, 有

\[ \begin{align} \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} x_1 \\ y_1 \end{pmatrix} = \lambda_1 \begin{pmatrix} x_1 \\ y_1 \end{pmatrix} \\ \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} x_2 \\ y_2 \end{pmatrix} = \lambda_2 \begin{pmatrix} x_2 \\ y_2 \end{pmatrix} \end{align} \]

可得 \(v_1 = \begin{pmatrix} \lambda_1 \\ 1 \end{pmatrix}, v_2 = \begin{pmatrix} \lambda_2 \\ 1 \end{pmatrix}\). 所以 \(P = \begin{pmatrix} \lambda_1 & \lambda_2 \\ 1 & 1 \end{pmatrix}, B = \begin{pmatrix} \lambda_1 & 0 \\ 0 & \lambda_2 \end{pmatrix}\).

接下来求 \(A^n\):

\[ \begin{align} A^n &= \begin{pmatrix} \lambda_1 & \lambda_2 \\ 1 & 1 \end{pmatrix} \begin{pmatrix} \lambda_1^n & 0 \\ 0 & \lambda_2^n \end{pmatrix} \begin{pmatrix} \lambda_1 & \lambda_2 \\ 1 & 1 \end{pmatrix}^{-1} \\ &= \begin{pmatrix} \lambda_1 & \lambda_2 \\ 1 & 1 \end{pmatrix} \begin{pmatrix} \lambda_1^n & 0 \\ 0 & \lambda_2^n \end{pmatrix} \frac{1}{\sqrt 5}\begin{pmatrix} 1 & -\lambda_2 \\ -1 & \lambda_1 \end{pmatrix} \\ &= \frac{1}{\sqrt 5} \begin{pmatrix} \lambda_1^{n+1} & \lambda_2^{n+1} \\ \lambda_1^n & \lambda_2^n \end{pmatrix} \begin{pmatrix} 1 & -\lambda_2 \\ -1 & \lambda_1 \end{pmatrix} \\ &= \frac{1}{\sqrt 5} \begin{pmatrix} \lambda_1^{n+1} - \lambda_2^{n+1} & \lambda_1^n - \lambda_2^n \\ \lambda_1^n - \lambda_2^n & \lambda_1^{n-1} - \lambda_2^{n-1} \end{pmatrix} \end{align} \]

由 (2) 式得

\[ \begin{align} \begin{pmatrix} F_{n+2} \\ F_{n+1} \end{pmatrix} &= \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n \begin{pmatrix} 1 \\ 1 \end{pmatrix} = \frac{1}{\sqrt 5} \begin{pmatrix} \lambda_1^{n+1} - \lambda_2^{n+1} & \lambda_1^n - \lambda_2^n \\ \lambda_1^n - \lambda_2^n & \lambda_1^{n-1} - \lambda_2^{n-1} \end{pmatrix} \begin{pmatrix} 1 \\ 1 \end{pmatrix} \\ &= \frac{1}{\sqrt 5} \begin{pmatrix} \lambda_1^{n+1} - \lambda_2^{n+1} + \lambda_1^n - \lambda_2^n \\ \lambda_1^n - \lambda_2^n + \lambda_1^{n-1} - \lambda_2^{n-1} \end{pmatrix} = \frac{1}{\sqrt 5} \begin{pmatrix} \lambda_1^n(\lambda_1+1) - \lambda_2^n(\lambda_2 + 1) \\ \lambda_1^{n-1}(\lambda_1+1) - \lambda_2^{n-1}(\lambda_2 + 1) \end{pmatrix} \\ &= \frac{1}{\sqrt 5} \begin{pmatrix} \lambda_1^n\lambda_1^2 - \lambda_2^n\lambda_2^2 \\ \lambda_1^{n-1}\lambda_1^2 - \lambda_2^{n-1}\lambda_2^2 \end{pmatrix} = \frac{1}{\sqrt 5} \begin{pmatrix} \lambda_1^{n+2} - \lambda_2^{n+2} \\ \lambda_1^{n+1} - \lambda_2^{n+1} \end{pmatrix} \end{align} \]

最后我们得到斐波那契数列的通项公式为

\[ F_n = \frac{1}{\sqrt 5}(\lambda_1^n - \lambda_2^n) = \frac{(\frac{1+\sqrt 5}{2})^2 - (\frac{1-\sqrt 5}{2})^2}{\sqrt 5} \]


参考资料


矩阵的 n 次方和斐波那契数列通项式
https://luyuhuang.tech/2020/03/16/fibonacci-sequence.html
Author
Luyu Huang
Posted on
March 16, 2020
Licensed under