跳至主要內容

斐波那契数列的矩阵形式

数学

斐波那契数列 Fn=Fn−1+Fn−2F_n=F_{n-1}+F_{n-2} 是二阶线性齐次差分方程：写成矩阵幂后，通项公式可直接由矩阵的特征值与对角化读出。需先掌握线性差分方程的求解。

1. 斐波那契数列的矩阵形式表示

斐波那契数列的定义递推式为：

Fn=Fn−1+Fn−2F_n = F_{n-1} + F_{n-2}

且初始条件为：

F0=0,F1=1F_0 = 0, \quad F_1 = 1

要将其转换为矩阵形式，可以引入状态向量：

vn⃗=[FnFn−1]\vec{v_n} = \begin{bmatrix} F_n \\ F_{n-1} \end{bmatrix}

那么递推关系可以改写为矩阵形式：

vn+1⃗=[1110]vn⃗\vec{v_{n+1}} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \vec{v_n}

这个矩阵：

T=[1110]T = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}

称为斐波那契矩阵。

2. 为什么矩阵是 2 阶？

  • 斐波那契数列的递推关系涉及到前两项，因此矩阵需要反映两个状态。
  • 矩阵的阶数通常等于递推关系的阶数。例如：
    • 一阶递推关系对应一阶矩阵（标量）。
    • 二阶递推关系对应二阶矩阵。

更一般地，形如：

an=c1an−1+c2an−2+⋯+ckan−ka_n = c_1 a_{n-1} + c_2 a_{n-2} + \dots + c_k a_{n-k}

的递推关系可以写成一个 k×kk \times k 的矩阵。

3. 高阶递推的友矩阵（以三阶为例）

一般 kk 阶线性递推 an=c1an−1+c2an−2+⋯+ckan−ka_n=c_1a_{n-1}+c_2a_{n-2}+\dots+c_ka_{n-k} 对应一个 k×kk\times k 的友矩阵（companion matrix，勿与伴随矩阵 adjugate 混淆）：

C=[c1c2⋯ck−1ck10⋯0001⋯00⋮⋮⋱⋮⋮00⋯10]C=\begin{bmatrix}c_1&c_2&\cdots&c_{k-1}&c_k\\1&0&\cdots&0&0\\0&1&\cdots&0&0\\\vdots&\vdots&\ddots&\vdots&\vdots\\0&0&\cdots&1&0\end{bmatrix}

以三阶递推 an=an−1+an−2+2an−3a_n=a_{n-1}+a_{n-2}+2a_{n-3}（初值 a0=3, a1=1, a2=3a_0=3,\ a_1=1,\ a_2=3）为例：

定义状态向量 vn=[anan−1an−2]\mathbf{v}_n=\begin{bmatrix}a_n\\a_{n-1}\\a_{n-2}\end{bmatrix}，代入递推关系：

vn=[an−1+an−2+2an−3an−1an−2]=[112100010][an−1an−2an−3]=C vn−1\mathbf{v}_n=\begin{bmatrix}a_{n-1}+a_{n-2}+2a_{n-3}\\a_{n-1}\\a_{n-2}\end{bmatrix}=\begin{bmatrix}1&1&2\\1&0&0\\0&1&0\end{bmatrix}\begin{bmatrix}a_{n-1}\\a_{n-2}\\a_{n-3}\end{bmatrix}=C\,\mathbf{v}_{n-1}

即友矩阵

C=[112100010]C=\begin{bmatrix}1&1&2\\1&0&0\\0&1&0\end{bmatrix}

由初值向量 v2=(a2,a1,a0)T=(3,1,3)T\mathbf{v}_2=(a_2,a_1,a_0)^T=(3,1,3)^T，通项为 vn=C n−2 v2\mathbf{v}_n=C^{\,n-2}\,\mathbf{v}_2。若状态向量按 (an,an+1,an+2)T(a_n,a_{n+1},a_{n+2})^T 排列，同一递推的矩阵写成系数落于末行的等价形式 [010001c1c2c3]\begin{bmatrix}0&1&0\\0&0&1\\c_1&c_2&c_3\end{bmatrix}，特征值不变（详见递推式矩阵的特征值分析）。

4. 斐波那契矩阵的性质与递推关系的联系

1. 特征值与解的形式：

  • 斐波那契矩阵 TT 的特征方程为：

    det⁡(T−λI)=λ2−λ−1=0\det(T - \lambda I) = \lambda^2 - \lambda - 1 = 0

    解得特征值：

    λ1=1+52,λ2=1−52\lambda_1 = \frac{1 + \sqrt{5}}{2}, \quad \lambda_2 = \frac{1 - \sqrt{5}}{2}

    这两个特征值对应斐波那契数列的解形式：

    Fn=C1λ1n+C2λ2nF_n = C_1 \lambda_1^n + C_2 \lambda_2^n

2. 震荡行为分析：

  • 由于斐波那契矩阵的特征值是实数且非复数，共轭对不会出现。这意味着斐波那契数列没有震荡行为。
  • 如果矩阵的特征值是复数，共轭根形式会引入振荡（如三角函数成分）。

3. 矩阵幂与快速计算：

  • TnT^n 可以快速计算斐波那契数列，体现了矩阵幂在递推关系中的作用：

    Tn=PΛnP−1T^n = P \Lambda^n P^{-1}

    其中 PP 是特征向量矩阵，Λ\Lambda 是对角矩阵；这即是对角化的应用。

矩阵 TT 的性质

  • 特征值：矩阵的特征值描述了递推关系的“增长模式”或“振荡行为”。如果存在复特征值，意味着递推关系可能存在周期性或振荡行为。
  • 实特征值：描述指数增长或衰减，特征值大于 1 表示增长，特征值小于 1 表示衰减。
  • 主导特征值：模最大的特征值决定了递推关系长期增长趋势。例如，三阶递推 an=an−1+an−2+2an−3a_n = a_{n-1} + a_{n-2} + 2a_{n-3}（见递推式矩阵的特征值分析）的矩阵有实特征值 λ1=2\lambda_1 = 2 与复数特征值 λ2,3=−12±32i\lambda_{2,3} = -\frac{1}{2} \pm \frac{\sqrt{3}}{2} i，主导特征值为 22，表明其主要表现为指数增长叠加振荡。

递推关系的性质如何反映在矩阵上？

  • 矩阵的阶数：等于递推关系涉及的项数，反映了递推式的复杂度。
  • 矩阵的特征值：描述递推关系的增长速度和振荡频率。
  • 矩阵的可对角化性：如果矩阵可对角化，则递推关系可以写成特征值的简单幂函数形式，极大简化了计算。
  • 特征向量：特征向量的线性组合构成递推关系的解。矩阵对角化的过程实质上是将递推关系分解为“独立的模式”。
链接到当前文件 4