Alioth_ 的博客

Alioth_ 的博客

常系数齐次线性递推的优化

posted on 2020-03-14 21:04:48 | under 知识点 |

首先要求$f\times A^n$ $A$为转移矩阵

然后$A^n$直接求的话由于递推的阶数很大不能直接算

设$$ A^n=P(A)G(A)+R(A) $$$P,G,R$为关于$A$的多项式

然后把$G$作为矩阵的特征多项式 由$Cayley-Hamilton\ theorem$可知$G(A)=0$

那么$A^n \equiv R(A)\ mod\ G(A)$ 然后$G(\lambda )=det(\lambda I-A)$可以通过把这个新矩阵的行列式在第一列展开得到(注意这个转移矩阵是第一列从上到下为$a_1\rightarrow a_k$然后初始矩阵(向量)为$f_k\rightarrow f_1$,方程是$f_k=\sum\limits_ia_{k-i}f_i$,那么每乘一次 向量右移一位 第一位变成新的值)

$\lambda I-A$就是这个矩阵

$$ G(\lambda)=\sum_{i=0}^{k}a^{k-i}\lambda^i $$ 然后直接多项式取余得到$R$的各项系数 即把$A^n$当作关于$A$的多(单)项式 这样 $A^n$用$A^0$到$A^{k-1}$表示出来了 因为$G=0,A^n=R(A)$ 即$$ A^n=\sum_{i=0}^{k-1}r_iA^i $$ 那么$$ ans=\sum_{i=0}^{k-1}r_if_{i} $$