常系数齐次线性递推
source link: https://xiaocairush.github.io/math/linear-recurrence/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
常系数齐次线性递推
问题¶
给定一个线性递推数列 {fi} 的前 k 项 f0…fk−1,和其递推式 fn=∑i=1kfn−iai 的各项系数 ai,求 fn。
前置知识¶
做法¶
定义 F(∑cixi)=∑cifi,那么答案就是 F(xn)。
由于 fn=∑i=1kfn−iai,所以 F(xn)=F(∑i=1kaixn−i),所以 F(xn−∑i=1kaixn−i)=F(xn−k(xk−∑i=0k−1ak−ixi))=0。
设 G(x)=xk−∑i=0k−1ak−ixi。
那么 F(A(x)+xnG(x))=F(A(x))+F(xnG(x))=F(A(x))。
那么就可以通过多次对 A(x) 加上 xnG(x) 的倍数来降低 A(x) 的次数。
也就是求 F(A(x)modG(x))。A(x)modG(x) 的次数不超过 k−1,而 f0..k−1 已经给出了,就可以算了。
问题转化成了快速地求 xnmodG(x),只要将 普通快速幂 中的乘法与取模换成 多项式乘法 与 多项式取模 就可以在 O(klogklogn) 的时间复杂度内解决这个问题了。
矩阵的解释¶
该算法由 Fiduccia 在 1985 年提出,对于 t≥0 我们定义列向量 vt 为
那么不难发现
而因为 vt+k 中每一行都满足这个递推关系,我们将 vt+k 描述为一个线性组合如
发现若能将两边的 vt 消去后得到多项式 Γ(x)=xk−∑i=1kaixk−i 满足 Γ(M)=O 其中 O 为一个 k×k 的零矩阵。
假设我们要求 Mn 可以构造多项式 f(x)=xn 那么 f(M)=Mn,而现在我们可将 f(x) 写成 f(x)=Q(x)Γ(x)+R(x) 而其中零矩阵是没有贡献的,那么 f(M)=R(M)。
但是注意矩阵乘法不满足消去律,此处我们定义矩阵 M 的特征多项式为 Γ(x)=det(xI−M),其中 I 为一个 k×k 的单位矩阵。Cayley-Hamilton 定理指出 Γ(M)=O,我们观察 M 的形式较为特殊,为下 Hessenberg 矩阵,其特征多项式比起一般矩阵更容易计算。
我们从右下角的 2×2 矩阵开始计算特征多项式
右下角 3×3 矩阵按照第一行的余子式展开有
观察并归纳有
至此我们可以使用上面的结论。令 g(x)=f(x)modΓ(x) 有 g(M)=Mn。而 deg(g(x))<k 显然,令 g(x)=g0+g1x+⋯+gk−1xk−1 那么
我们关注 v0,v1,…,vk−1 的第一行就是 f0,f1,…,fk−1 已知,那么 fn 可在 O(k) 时间简单得到。求出 g(x) 则可用快速幂和多项式取模与上述解释是一样的。该算法常数较大,使用生成函数可以得到一个常数更小的算法,见 一种新的线性递推计算方法。
Recommend
-
2
浅谈递推数列(一):递推数列的基础知识 发表于 2021-07-23 分类于
-
6
联系我们:有道技术团队助手:ydtech01 / 邮箱:[[email protected]]相信了解算法同学经常会说动态规划太难了,看到题目完全不知从何下手,或者是...
-
5
联系我们:有道技术团队助手:ydtech01 / 邮箱:[ydtech@r...
-
3
本文翻译自:
-
5
要不是考到了,我还没发现这玩意我不是很会…… 多项式取模; 矩阵快速幂。 # 常系数齐次线性递推描述的是这么一个问题,给定数列 c1,c2,…,ck 以及数列 f 的前 k 项 f0,...
-
2
什么是齐次坐标? 22 September 2020 编辑: 马海东 在计算机图形学里面会经常碰到几何体的平移,旋转,缩放以及投影变换. 一般情况下会涉及到齐次坐标与变换矩阵. 为了后续对变换矩阵内容的讲解, 在这里先简要的介绍一下...
-
5
线性递推数列 ...
-
4
约瑟夫问题 约瑟夫问题是个著名的问题:N个人围成一圈,第一个人从1开始报数,报M的将被杀掉,下一个人接着从1开...
-
6
递推递归与排列组合 排列组合问题在暴力枚举的情况一般有3种情况 我们在此记个数为N 情况一:打印n个数的全排列: N=n!N=n!
-
3
tf的lookTransform和齐次变换矩阵的关系推导 | 沉默杀手tf的lookTransform和齐次变换矩阵的关系推导 2022-12-13|Word count: 775|Readi...
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK