首页 > 其他 > 详细

常系数齐次线性递推

时间:2018-12-08 17:39:43      阅读:160      评论:0      收藏:0      [点我收藏+]

本博客部分参考自dtz的博客Troywar的博客

前言:

为什么要来学这个鬼畜的东西呢……因为模拟赛出了一道板题(好吧这实际上就是BZOJ4162):

技术分享图片

技术分享图片

看到的时候我非常兴奋,这不是一道sb矩阵快速幂题吗?连邻接矩阵都直接给出来了;

结果一看数据范围,算了算$n^3logk=1.25e10$,emmm我咋不知道矩阵快速幂有什么优化方法?

于是我就自闭了,写了50滚粗(然后一个点1008ms一个点1114ms少了20,气傻了)

然后才知道这是个常系数齐次线性递推模板题……

常系数齐次线性递推

0.预备知识:

有一个数列递推式为:

$$S_i=\sum\limits_{j=1}^{k}a_jS_{i-j}$$

要求数列第$n$项,矩阵快速幂相信大家都会……但是朴素的矩阵快速幂时间复杂度是$O(k^3logn)$的(听说有些神秘方法可以优化到$O(k^{log_27}n)$但是没啥用),当$k$比较大的时候就GG了,因此需要一些优化。

1.特征多项式和Cayley-Hamilton定理

设$A$是一个$n$阶矩阵,且数$\lambda$和非零列向量$x$满足

$$Ax=\lambda x (1)$$

则称$\lambda$为矩阵$A$的特征值,$x$为矩阵$A$的特征向量;

稍微变式可以得到

$$(A-\lambda I)x=0$$

其中$I$表示单位矩阵;

此式有非零解当且仅当其行列式

$$|A-\lambda I|=0 (2)$$

(1)式可以看成一个关于$\lambda$的一元$n$次方程,称为矩阵$A$的特征方程,(2)式是关于$\lambda$的$n$次多项式,称为矩阵$A$的特征多项式,记为$\phi(\lambda)$;

注意这里的“特征多项式”指的是广义的多项式,未知数不一定是一个数或字母,也可以是向量或者矩阵;

那么对于任意一个矩阵$A$的特征多项式$\phi(\lambda)$,都有

$$\phi(A)=0(Caylay-Hamilton定理)$$

证明:$\phi(A)=|A-AI|=|0|=0$

2.求解特征多项式

沿用上面的定义,设数列$S$的递推矩阵$A$的特征多项式为$\phi(\lambda)$,则:

$$\phi(\lambda)=|A-\lambda I|=\begin{bmatrix}\lambda&0&\cdots&0&0\\ 0&\lambda&\cdots&0&0\\ \cdots&\cdots&\cdots&\cdots&\cdots\\ 0&0&\cdots&\lambda&0\\ 0&0&\cdots&0&\lambda\end{bmatrix}-\begin{bmatrix}0&0&\cdots&0&a_k\\ 1&0&\cdots&0&a_{k-1}\\ 0&1&\cdots&0&a_{k-2}\\ \cdots&\cdots&\cdots&\cdots&\cdots\\ 0&0&\cdots&1&a_1\end{bmatrix}$$

$$=\begin{bmatrix}\lambda&0&\cdots&0&-a_k\\ -1&\lambda&\cdots&0&-a_{k-1}\\ 0&-1&\cdots&0&-a_{k-2}\\ \cdots&\cdots&\cdots&\cdots&\cdots\\ 0&0&\cdots&-1&\lambda-a_1\end{bmatrix}$$

把$\phi(\lambda)$按最后一列$(j=k)$拉普拉斯展开得

$$\phi(\lambda)=\sum\limits_{i=1}^{k}a_{k-i+1}(-1)^{i+k}\phi(\lambda)_{i,k}$$

其中$\phi(\lambda)_{i,k}$表示$(i,k)$的代数余子式;

化简得:

$$\phi(\lambda)=(-1)^k(\lambda^k-\sum\limits_{i=1}^{k}a_i\lambda^{k-i})$$

常系数齐次线性递推

原文:https://www.cnblogs.com/dcdcbigbig/p/10086518.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!