Fibonnacii序列求解通项的线性代数方法
Fibonacci的递归通项
\[F_n = F_{n-1} + F_{n-2}
\]
递归的通项的矩阵形式
\[\left(
\begin{matrix}
F_{n+2} \\
F_{n+1}
\end{matrix}
\right)
=
\left(
\begin{matrix}
1 & 1 \\
1 & 0
\end{matrix}
\right)
\left(
\begin{matrix}
F_{n+1} \\
F_{n}
\end{matrix}
\right)
=
A\left(
\begin{matrix}
F_{n+1} \\
F_{n}
\end{matrix}
\right)
\]
\[\left(
\begin{matrix}
F_{n} \\
F_{n-1}
\end{matrix}
\right)
=A\left(
\begin{matrix}
F_{n-1} \\
F_{n-2}
\end{matrix}
\right)
=…=
A^{n-1}
\left(
\begin{matrix}
F_1 \\
F_0
\end{matrix}
\right)
\]
计算矩阵幂的方法
直接计算或矩阵对角化。可参考例题
- 矩阵对角化：若\(m \times m\)矩阵\(A\)能对角化，则存在可逆矩阵\(P\)（由\(A\)的特征向量组成）使得
\[P^{-1}AP=diag(\lambda_1,...,\lambda_m) \\
=> AP = Pdiag(\lambda_1,...,\lambda_m) \\
=> A = Pdiag(\lambda_1,...,\lambda_m)P^{-1} \\
\]
从而
\[A^k = (PDP^{-1})(PDP^{-1})...(PDP^{-1})=PD^kP^{-1}=Pdiag(\lambda^k_1,...,\lambda_m^k)P^{-1}
\]
- 由于有对角矩阵，可以把矩阵\(P\)写成列向量的形式，\(P=(\vec a_1, \vec a_2, ...,\vec a_m)\)，则上面的方程可转化为
\[A\vec a_i = \lambda_i\vec a_i, 1\leq i \leq m
\]
其中\(\vec a_i\)是特征向量，\(\lambda_i\)是特征值。
- 求矩阵\(A\)的特征向量和特征值的方法是，求解下列行列式（也是多项式）的根得到特征值，再求出特征向量，进而得到\(P\)，直接带入式子求解\(A\)。
\[det(\lambda I-A)=0\\其中I是单位矩阵（identity-matrix）
\]