常系数齐次线性递推
Midvoy_尺
2019-08-21 20:14:25
1.**递推式**
$f_{n}=a_{1}\times$
$f_{n-1}+a_{2}$
$\times$
$f_{n-2}$
$...+$
$a_{k}$
$\times$
$f_{n-k}$
其中$a_{1},a_{2}...a_{k}$,为常数则称数列
$f_{n}$
为线性递推数列
$ps:f_{n}$
即使不是线性递推方程但满足任何一个线性递推多项式即可,
例如
$f_{n}$−$f_{n-1}=1$
不是线性递推方程但可得到
$f_{n}-2\times\;f_{n-1}+f_{n-2}=0$
因此${f_n}$为线性递推数列
2.**k阶常系数线性递推方程**:
$H_{n}-a_{1}\times\;H_{n-1}-a_2\times\;H_{n-2}-...-a_k\times\;H_{n-k}=f_{n}$
$H_{0}=b_0,H_{1}=b_1,H_{2}=b_2,...,H_{k-1}=b_{k-1}$
其中$a_1,a_2,...,a_k$为常数,$a_k\neq0$,这个方程称为**k阶常系数线性递推方程**
$b_0,b_1,...,b_{k-1}$为$k$个初值(边界).
当$f_{n}=0$时称这个递推方程为**齐次方程**.
3.定义$f_n$的**特征方程**:
设一常系数线性齐次递推方程如下:
$H_n-a_1\times\;H_{n-1}-a_2\times\;H_{n-2}-...-a_k\times\;H_{n-k}=0.....(1)$
$H_0=b_0,H_1=b_1,H_2=b_2,...,H_{k-1}=b_{k-1}$
其解的形式为$H_n=...$;
则方程:
$x^k-a_1\times\;x^{k-1}-...-a_k=0$
为该递推方程的特征方程
特征方程的根为递推方程的**特征根**.
由基本代数定理:
$C_x=0$的解(称为特征根)有k个,设为$q_1,q_2...q_k$
4.定理&推论:
递推方程及其特征根的关系:
定理[1]:
[1].设1是非零复数,则q^n是递推方程(1)的解当且仅当q为它的特征根.
证:$H_n=q^n$
$\Leftarrow\Rightarrow\;q^n -a_1\times\;q^{n-1}-a_2\times\;q^{n-2}-...-a_k\times\;q^{n-k}=0$(代入)
$ \;\;\;\;\;(H_n-a_1\times\;H_{n-1} -a_2\times\;H_{n-2} -... -a_k\times\;H_{n-k}=0)$(递推方程)
$\Leftarrow\Rightarrow\;q^{n-k}\times\;(q^k-a_1\times\;q^{k-1}-a_2\times\;q^{k-2}-...-a_k)=0$(提出q^(n-k))
$\Leftarrow\Rightarrow\;q^k-a_1\times\;q^{k-1}-a_2\times\;q^{k-2}-...-a_k=0$(除去$q^{n-k}$)
$ \;\;\;\;\;(x^k-a_1\times\;x^{k-1}-a_2\times\;x^{k-2}-...-a_k=0)$(特征方程)
$\Leftarrow\Rightarrow\;q$为它的特征根
定理[2]:
[2].设$h_1(n)$和$h_2(n)$是递推方程$(1)$的解,$c_1,c_2$为任意常数,则$c_1\times\;h_1(n)+c_2\times\;h_2(n)$也是这个递推方程的解.
证:代入即可
由以上[1][2]可得推论:
若$q_1,q_2,...,q_k$为$(1)$的特征根,则$c_1\times\;q_1^n+c_2\times\;q_2^n+...+c_k\times\;q_k^n$是该递推方程的解,其中$c_1,c_2,...,c_k$为任意常数.
总结:$ c_1\times\;q_1^n+c_2\times\;q_2^n+...+c_k\times\;q_k^n $为该递推方程的解(最多$k$个根).
## 是否还有其他形式的解?
**通解**的定义:
[4].若对$(1)$由不同的初值确定的每一个解$h(n)$都存在一组常数$c_1',c_2',...c_k'$,使得
$h(n)=c_1'\times\;q_1^n+c_2'\times\;q_2^n+...+c_k'\times\;q_k^n$
成立(即常数$c_1',c_2',...c_k'$固定已得,变化),则称$c_1\times\;q_1^n+c_2\times\;q_2^n+...+c_k\times\;q_k^n$为该递推方程的通解
下面的定理说明,当k个特征根彼此不等时,上述的解就是递推方程$(1)$的**通解**
[3].设$q_1,q_2,...,q_k$是递推方程$(1)$的不同特征根,则$H(n)=c_1\times\;q_1^n+c_2\times\;q_2^n+...+c_k\times\;q_k^n$为该递推方程的通解
证:根据推论知H(n)为解,将初值代入:
$c_1+c_2+...+c_k=b_0$
$c_1\times\;q_1+c_2\times\;q_2+...+c_k\times\;q_k=b_1$
$\ldots\ldots$
$c_1\times\;q_1^{k-1}+c_2\times\;q_2^{k-1}+...+c_k\times\;q_k^{k-1}$
如果有唯一一组解$c_1',c_2',...c_k'$,则说明$h(n)=c_1'\times\;q_1^n+c_2'\times\;q_2^n+...+c_k'\times\;q_k^n$
### 附注:
特征根中若有重根,使用线性无关的解来构造通解
[4]设$q_1,q_2,...,q_t$是递推方程(1)的不相等的特征根,$q_i$的重数为$e_i$,其中$i=1,2,...,t$令
$H_i(n)=(c_{i1}+c_{i2}\times\;n+...+c_{ie_{i}}\times\;n^{e_{i}-1})\times\;q_i^n$
则该递推方程通解为:
$H(n)=\sum_{i=1}^t H_i(n)$
总结思路:
1.写出特征方程
2.解出特征根
3.写出代入特征根的通解
4.代入初值写出线性方程组
5.解出常数$c$
6.代入通解出通项
[例]求解斐波那契数列的递推方程
解:
线性递推方程$f_{n}=f_{n-1}+f_{n-2}$的特征方程为
$q^2-q-1=0$
特征方程有两个实根
$q_1=\frac{ 1+\sqrt{5 } }{ 2 }$,$q_1=\frac{ 1-\sqrt{5 } }{ 2 }$
因此线性递推方程的通解为
$F_n=c_1\times(\frac{ 1+\sqrt{5 } }{ 2 })^n+c_2\times(\frac{ 1+\sqrt{5 } }{ 2 })^n$
将 $F_0=F_1=1$代入上式求得
$c_1=\frac{\sqrt{ 5 }}{ 5 },c_2=-\frac{\sqrt{ 5 }}{ 5 }$
因此斐波那契数列的通项公式为
$F_n=\frac{\sqrt{ 5 }}{ 5 }\times((\frac{ 1+\sqrt{5 } }{ 2 })^n-(\frac{ 1-\sqrt{5 } }{ 2 })^n)$