首页 > 其他 > 详细

常系数线性递推

时间:2019-12-27 21:22:48      阅读:85      评论:0      收藏:0      [点我收藏+]

常系数齐次线性递推

给定\(a_0,\cdots,a_{k-1},f_0,\cdots,f_{k-1}\),且\(\forall i\in[k,+\infty),a_i=\sum\limits_{j=1}^kf_ja_{i-j}\),求\(a_n\)

一眼看上去有点像分治NTT。

Part.1

设转移矩阵为\(\mathbf A\)
矩阵快速幂的浪费之处在于我们求出了连续\(k\)项,但是我们实际只关心一项。
假如说我们现在构造出了一组\(c_0,\cdots,c_{k-1}\),使得\(\mathbf A^n=\sum\limits_{i=0}^{k-1}c_i\mathbf A^i\)
那么答案\((\mathbf f\mathbf A^n)_0=\sum\limits_{i=0}^{k-1}c_i(\mathbf f\mathbf A^i)_0=\sum\limits_{i=0}^{k-1}c_if_i\)
也就是说如果我们能够构造出一组\(c\),那么我们就能够在\(O(n)\)的时间内求出答案。

Part.2

接下来考虑如何求出\(c\)
先把\(\mathbf A^n\)写成这样的形式:\(\mathbf A^n=Q(\mathbf A)G(\mathbf A)+R(\mathbf A)\)
其中\(R(\mathbf A)=\sum\limits_{i=0}^{k-1}c_i\mathbf A^i\)
那么可以设\(G(\mathbf A)=\sum\limits_{i=0}^kg_i\mathbf A^i\)
如果\(G(\mathbf A)=0\)那么就有\(\mathbf A^n\equiv R(\mathbf A)(\mod G(\mathbf A))\)了。
也就是说如果我们能够构造出一组\(g\),那么我们就能够在\(O(k\log k\log n)\)的时间内求出\(c\)

Part.3

接下来考虑如何求出\(g\)
注意到刚才的过程对于任意矩阵都是成立的。
也就是说如果对于任意一个矩阵而言都能轻松找到\(g\)那么矩阵就没用了。
所以\(g\)肯定不是什么好找的东西。然后让我们进入线性代数的内容。
先给出结论:\(\forall i\in[0,k),g_i=-f_{k-1-i},g_k=1\)
下面将给出推导过程。

Part.4

先复述几个定义:
对于\(k\)阶方阵\(\mathbf A\),若数\(\lambda\)\(k\)维非零向量\(\mathbf x\)使得\((\mathbf A-\lambda\mathbf E)\mathbf x=\mathbf0\)成立,则称\(\lambda\)\(\mathbf A\)的特征值,\(\mathbf x\)\(\mathbf A\)的特征向量。
上面这个方程有解的充要条件是\(\det(\mathbf A-\lambda\mathbf E)=0\)
\(f(\lambda)=\det(\mathbf A-\lambda\mathbf E)\),不难发现这是个关于\(\lambda\)\(n\)次多项式,而它的\(k\)个解就是\(\mathbf A\)\(n\)个特征值。
手玩\(\mathbf A\)可以得到\(f(\lambda)=(-1)^k(\lambda^k-\sum\limits_{i=0}^{k-1}a_{k-i-1}\lambda^i)\)
实际上取个反并不会让\(k\)个解变动,所以我们把它的特征多项式看做\(f(\lambda)=\lambda^k-\sum\limits_{i=0}^{k-1}a_{k-i-1}\lambda^i\)也没问题。

Cayley-Hamilton定理

一个矩阵的特征多项式是它的化零多项式。
就是\(f(\mathbf A)=\mathbf0\)
所以我们就成功求得了\(g\)

常系数线性递推

原文:https://www.cnblogs.com/cjoierShiina-Mashiro/p/12109447.html

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