作业帮 > 数学 > 作业

如何将递推关系转化为矩阵

来源:学生作业帮 编辑:作业帮 分类:数学作业 时间:2024/06/09 00:53:54
如何将递推关系转化为矩阵
比如说F[x+2]=Af[x+1]+Bf[x]+C
那么如何构造矩阵使用快速幂加速为LOG(N)呢?
令G[x] = (f[x+2],f[x+1],f[x])^T
那么可以写出一阶递推关系
G[x+1] = M G[x]
其中
M =
A B C
1 0 0
0 1 0
然后G[n] = M^n G[0],M^n只需要O(logn)的计算量
再问: 3Q