跳转至

常系数齐次线性递推

简介

常系数齐次线性递推数列(又称为 C-finite 或 C-recursive 数列)是常见的一类基础的递推数列。

对于数列 和其递推式

其中 不全为零,我们的目标是在给出初值 和递推式中的 后求出 。如果 ,我们想要更快速的算法。

这里 被称为 阶的常系数齐次线性递推数列。

Fiduccia 算法

Fiduccia 算法使用多项式取模和快速幂来计算 ,时间为 ,其中 表示两个度数为 的多项式相乘的时间。

算法:构造多项式 ,那么

其中定义 为内积。

证明:我们定义 的友矩阵为

我们定义多项式

观察到

我们将这个递推用矩阵表示有

可知 的第一行为 ,根据矩阵乘法的定义得证。

表示为有理函数

对于上述数列 一定存在有理函数

。我们称其为「有理函数」是因为 是「多项式」。

证明:对于 考虑 的系数定义,这几乎就是形式幂级数「除法」的定义,

我们只需要令

那么根据 的定义,必然有

Bostan–Mori 算法

计算单项

我们的目标仍然是给出上述多项式 ,求算

Bostan–Mori 算法基于 Graeffe 迭代,对于上述多项式

因为分母 是偶函数,所以子问题只需考虑其中的一侧

我们付出两次多项式乘法的代价使得问题至少减少为原先的一半,而当 时显然有 ,时间复杂度同上。

计算连续若干项

目标是给出上述多项式 ,求算 。下面的计算中我们只需考虑对答案「有影响」的系数,这是 Bostan–Mori 算法的关键。

我们不妨假设 ,否则我们也可以通过一次带余除法使问题回到这种情况。

我们先考虑更简单的问题:

我们需要求出 然后作一次乘法并取出 的系数。令 那么我们只需求出

就可以还原出 。进而我们只需求出 再和 作一次乘法即可求出

上面的算法虽然已经可以工作,但是每一次的递归的时间复杂度与 相关,我们希望能至少在递归求算时摆脱 ,更具体的,我们先考虑求算 ,考虑

我们需要求出

那么对于 而言,我们只需求出

这是因为

我们知道 的奇偶性是一样的,所以

这样我们可以写出伪代码

但是只有这个算法还不够,我们需要重新找到一个有理函数并求算更多系数。

找到新的有理函数表示

我们知道 本身和 的一部分连续的系数比如 ,我们希望求出 ,这等价于我们要求某个 使得 的前 项与 相同。简单来说:递推关系(有理函数的分母)是不变的,我们所做的只是更换初值(有理函数的分子)。

具体的,考虑

我们现在希望将递推前进 项,那么就是

我们先用一次 计算出 ,然后我们扩展合并出 ,再重新计算一个分子使得

最后我们使用形式幂级数的除法计算出 ,时间为

参考文献

  1. Alin Bostan, Ryuhei Mori.A Simple and Fast Algorithm for Computing the -th Term of a Linearly Recurrent Sequence.