斐波拉契数列（Fibonacci sequence）

Fk+2=Fk+1+Fk , k=0,1,2...F_{k+2}=F_{k+1}+F_k\ ,\ k=0,1,2...

0,1,1,2,3,5,8...0,1,1,2,3,5,8...

设 uk=[Fk+1Fk]u_k=\left[ \begin{array}{c} F_{k+1}\\ F_k\\ \end{array} \right] ，则 uk+1u_{k+1} 和 uku_k 的关系是

uk+1=[Fk+2Fk+1]=[1110][Fk+1Fk]=Auku_{k+1}=\left[ \begin{array}{c} F_{k+2}\\ F_{k+1}\\ \end{array} \right] =\left[ \begin{matrix} 1& 1\\ 1& 0\\ \end{matrix} \right] \left[ \begin{array}{c} F_{k+1}\\ F_k\\ \end{array} \right] =Au_k

所以可以得出

uk=Auk−1=A2uk−2=Aku0u_k=Au_{k-1}=A^2u_{k-2}=A^ku_0

可以求出矩阵 AA 的特征值和对应的特征向量

λ1=1+52           λ2=1−52\lambda _1=\frac{1+\sqrt{5}}{2}\ \ \ \ \ \ \ \ \ \ \ \lambda _2=\frac{1-\sqrt{5}}{2}

x1=[1+521]=[λ11]           x1=[1−521]=[λ21]x_1=\left[ \begin{array}{c} \frac{1+\sqrt{5}}{2}\\ 1\\ \end{array} \right] =\left[ \begin{array}{c} \lambda _1\\ 1\\ \end{array} \right] \ \ \ \ \ \ \ \ \ \ \ x_1=\left[ \begin{array}{c} \frac{1-\sqrt{5}}{2}\\ 1\\ \end{array} \right] =\left[ \begin{array}{c} \lambda _2\\ 1\\ \end{array} \right]

因此，矩阵 AA 可以进行对角化分解

A=SΛS−1=[λ1λ211][λ100λ2][λ1λ211]−1A=S\varLambda S^{-1}=\left[ \begin{matrix} \lambda _1& \lambda _2\\ 1& 1\\ \end{matrix} \right] \left[ \begin{matrix} \lambda _1& 0\\ 0& \lambda _2\\ \end{matrix} \right] \left[ \begin{matrix} \lambda _1& \lambda _2\\ 1& 1\\ \end{matrix} \right] ^{-1}

所以

uk=Aku0=SΛkS−1u0u_k=A^ku_0=S\varLambda ^kS^{-1}u_0

从而得出

uk=λ1kλ1−λ2[λ11]−λ2kλ1−λ2[λ21]=[Fk+1Fk]u_k=\frac{\lambda _1^k}{\lambda _1-\lambda _2}\left[ \begin{array}{c} \lambda _1\\ 1\\ \end{array} \right] -\frac{\lambda _{2}^{k}}{\lambda _1-\lambda _2}\left[ \begin{array}{c} \lambda _2\\ 1\\ \end{array} \right] =\left[ \begin{array}{c} F_{k+1}\\ F_k\\ \end{array} \right]

Fk=1λ1−λ2(λ1k−λ2k)=15[(1+52)k−(1−52)k]  for k≥0F_k=\frac{1}{\lambda _1-\lambda _2}\left( \lambda _{1}^{k}-\lambda _{2}^{k} \right) =\frac{1}{\sqrt{5}}\left[ \left( \frac{1+\sqrt{5}}{2} \right) ^k-\left( \frac{1-\sqrt{5}}{2} \right) ^k \right]\ \ for\ k\ge 0

In general

对于 n 阶，常系数，线性齐次差分方程

Gk+n=a1Gk+n−1+a2Gk+n−2+⋅⋅⋅+anGkG_{k+n}=a_1G_{k+n-1}+a_2G_{k+n-2}+\cdot \cdot \cdot +a_nG_k

初始条件是 Gn−1,⋅⋅⋅,G1,G0G_{n-1},\cdot \cdot \cdot ,G_1,G_0

对于非齐次的差分方程，比如

Fk+2=Fk+1+Fk+2F_{k+2}=F_{k+1}+F_k+2

可以通过“平移”消除掉常数项

设 FkF_k 有一个特解是常数 cc 即 Fk=cF_k=c ，代入上式 c=c+c+2c=c+c+2 解得 c=−2c=-2

所以就可以设 Fk=Gk−2F_k=G_k-2 ，原方程就转换为

Gk+2=Gk+1+GkG_{k+2}=G_{k+1}+G_k

就转换为了齐次的差分方程

  1. 设

uk=[Gk+n−1Gk+n−2⋮Gk]u_k=\left[ \begin{array}{c} G_{k+n-1}\\ G_{k+n-2}\\ \vdots\\ G_k\\ \end{array} \right]

uk+1=[Gk+nGk+n−1⋮Gk+1]=[a1a2⋯an−1an10⋯0001⋯00⋮⋮⋱0000010][Gk+n−1Gk+n−2⋮Gk]=An×nuku_{k+1}=\left[ \begin{array}{c} G_{k+n}\\ G_{k+n-1}\\ \vdots\\ G_{k+1}\\ \end{array} \right] =\left[ \begin{matrix} a_1& a_2& \cdots& a_{n-1}& a_n\\ 1& 0& \cdots& 0& 0\\ 0& 1& \cdots& 0& 0\\ \vdots& \vdots& \ddots& 0& 0\\ 0& 0& 0& 1& 0\\ \end{matrix} \right] \left[ \begin{array}{c} G_{k+n-1}\\ G_{k+n-2}\\ \vdots\\ G_k\\ \end{array} \right] =A_{n\times n}u_k

  1. 如果矩阵 AA 可以对角化分解，则进行对角化分解

A=SΛS−1=[x1x2⋯xn][λ1λ2⋱λn][x1x2⋯xn]−1A=S\varLambda S^{-1}=\left[ \begin{matrix} x_1& x_2& \cdots& x_n\\ \end{matrix} \right] \left[ \begin{matrix} \lambda _1& & & \\ & \lambda _2& & \\ & & \ddots& \\ & & & \lambda _n\\ \end{matrix} \right] \left[ \begin{matrix} x_1& x_2& \cdots& x_n\\ \end{matrix} \right] ^{-1}

其中 xx 为 AA 的特征向量，λ\lambda 为对应的特征值

  1. uk=Aku0=SΛkS−1u0=SΛkcu_k=A^ku_0=S\varLambda ^kS^{-1}u_0=S\varLambda ^kc

展开写

uk=[x1x2⋯xn][λ1kλ2k⋱λnk][c1c2⋮cn]u_k=\left[ \begin{matrix} x_1& x_2& \cdots& x_n\\ \end{matrix} \right] \left[ \begin{matrix} \lambda _{1}^{k}& & & \\ & \lambda _{2}^{k}& & \\ & & \ddots& \\ & & & \lambda _{n}^{k}\\ \end{matrix} \right] \left[ \begin{array}{c} c_1\\ c_2\\ \vdots\\ c_n\\ \end{array} \right]

其中 c=S−1u0c=S^{-1}u_0 ，可以理解为用 AA 的特征向量 x1,x2,⋯xnx_1,x_2,\cdots x_n 的线性组合表示出向量 u0u_0 时的系数

u0=[Gn−1Gn−2⋮G0]=c1x1+c2x2+⋯+cnxn=[x1x2⋯xn][c1c2⋮cn]u_0=\left[ \begin{array}{c} G_{n-1}\\ G_{n-2}\\ \vdots\\ G_0\\ \end{array} \right] =c_1x_1+c_2x_2+\cdots +c_nx_n=\left[ \begin{matrix} x_1& x_2& \cdots& x_n\\ \end{matrix} \right] \left[ \begin{array}{c} c_1\\ c_2\\ \vdots\\ c_n\\ \end{array} \right]

  1. 最后就可以写出 GkG_k 的表达式，是 UkU_k 的最后一项

差分方程稳定性

稳定性由矩阵 AA 的特征值决定，所有特征值满足：∣λi∣<1\left| \lambda _i \right|< 1 此时是稳定的

对于实数特征值：

  • 0<λ<10<\lambda <1 单调衰减
  • −1<λ<0-1<\lambda <0 振荡衰减

对于复数特征值：λ=∣λ∣eiθ\lambda =\left| \lambda \right|e^{i\theta} 其中 ∣λ∣\left| \lambda \right| 为模/幅值，θ\theta​ 为辐角

  • ∣λ∣<1\left| \lambda \right|<1 衰减，θ\theta 为角频率（单位是rad/step），θ2π\frac{\theta}{2\pi} 为频率（单位是cycles/step），对于 step 为时间间隔时，θΔt\frac{\theta}{\varDelta t} 为角频率，θ2πΔt\frac{\theta}{2\pi\varDelta t} 为频率

References