常系数齐次线性递推

简介

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

对于数列 ${\left(a_j\right)}_{j\ge 0}$ 和其递推式

$$a_n=\sum _{j=1}^d{c}_j{a}_{n-j},(n\ge d)$$

其中 $c_j$ 不全为零，我们的目标是在给出初值 $a_0,\dots ,a_{d-1}$ 和递推式中的 $c_1,\dots ,c_d$ 后求出 $a_k$。如果 $k\gg d$，我们想要更快速的算法。

这里 ${\left(a_j\right)}_{j\ge 0}$ 被称为 $d$ 阶的常系数齐次线性递推数列。

Fiduccia 算法

Fiduccia 算法使用多项式取模和快速幂来计算 $a_k$，时间为 $O(\mathsf{M}(d)\log k)$，其中 $O(\mathsf{M}(d))$ 表示两个次数为 $O(d)$ 的多项式相乘的时间。

算法：构造多项式 $\mathrm{\Gamma }(x):=x^d-\sum _{j=0}^{d-1}{c}_{d-j}{x}^j$ 和 $A(x):=\sum _{j=0}^{d-1}{a}_j{x}^j$，那么

$$a_k=⟨x^{k}mod\mathrm{\Gamma }(x),A(x)⟩$$

其中定义 $⟨\left(\sum _{j=0}^{n-1}{f}_j{x}^j\right),\left(\sum _{j=0}^{n-1}{g}_j{x}^j\right)⟩:=\sum _{j=0}^{n-1}{f}_j{g}_j$ 为内积。

证明：我们定义 $\mathrm{\Gamma }(x)$ 的友矩阵为

$$C_{\mathrm{\Gamma }}:=\left[\begin{array}{cccc}& & & c_d\\ 1& & & c_{d-1}\\ & \ddots & & ⋮\\ & & 1& c_1\end{array}\right]$$

我们定义多项式 $b(x):=\sum _{j=0}^{d-1}{b}_j{x}^j$ 和

$$B_b:={\left[\begin{array}{cccc}{b}_0& b_1& \cdots & b_{d-1}\end{array}\right]}^{⊺}$$

观察到

$$\underset{C_{\mathrm{\Gamma }}}{\underbrace{\left[\begin{array}{cccc}& & & c_d\\ 1& & & c_{d-1}\\ & \ddots & & ⋮\\ & & 1& c_1\end{array}\right]}}\underset{B_b}{\underbrace{\left[\begin{array}{c}{b}_0\\ b_1\\ ⋮\\ b_{d-1}\end{array}\right]}}=\underset{B_{xbmod\mathrm{\Gamma }}}{\underbrace{\left[\begin{array}{c}{c}_d{b}_{d-1}\\ b_0+c_{d-1}{b}_{d-1}\\ ⋮\\ b_{d-2}+c_1{b}_{d-1}\end{array}\right]}}$$

且

$$\begin{array}{rl}{C}_{\mathrm{\Gamma }}& =\left[\begin{array}{cccc}{B}_{xmod\mathrm{\Gamma }}& B_{x^{2}mod\mathrm{\Gamma }}& \cdots & B_{x^{d}mod\mathrm{\Gamma }}\end{array}\right],\\ {\left(C_{\mathrm{\Gamma }}\right)}^2& =\left[\begin{array}{cccc}{B}_{x^{2}mod\mathrm{\Gamma }}& B_{x^{3}mod\mathrm{\Gamma }}& \cdots & B_{x^{d+1}mod\mathrm{\Gamma }}\end{array}\right],\\ \cdots \\ {\left(C_{\mathrm{\Gamma }}\right)}^k& =\left[\begin{array}{cccc}{B}_{x^{k}mod\mathrm{\Gamma }}& B_{x^{k+1}mod\mathrm{\Gamma }}& \cdots & B_{x^{k+d}mod\mathrm{\Gamma }}\end{array}\right]\end{array}$$

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

$$\left[\begin{array}{c}{a}_k\\ a_{k+1}\\ ⋮\\ a_{k+d-1}\end{array}\right]=\underset{{\left({\left(C_{\mathrm{\Gamma }}\right)}^{⊺}\right)}^k={\left({\left(C_{\mathrm{\Gamma }}\right)}^k\right)}^{⊺}}{\underbrace{{\left[\begin{array}{cccc}& 1& & \\ & & \ddots & \\ & & & 1\\ c_d& c_{d-1}& \cdots & c_1\end{array}\right]}^k}}\left[\begin{array}{c}{a}_0\\ a_1\\ ⋮\\ a_{d-1}\end{array}\right]$$

可知 ${\left({\left(C_{\mathrm{\Gamma }}\right)}^k\right)}^{⊺}$ 的第一行为 $B_{x^{k}mod\mathrm{\Gamma }}$，根据矩阵乘法的定义得证。

表示为有理函数

对于上述数列 ${\left(a_j\right)}_{j\ge 0}$ 一定存在有理函数

$$\frac{P(x)}{Q(x)}=\sum _{j\ge 0}{a}_j{x}^j$$

且 $Q(x)=x^d\mathrm{\Gamma }\left(x^{-1}\right)$，$\deg{P}

---

本页面最近更新：2024/10/30 21:50:12，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：Tiphereth-A, Enter-tainer, hly1204, QAQAutoMaton, Marcythm, 97littleleaf11, ksyx, shuzhouliu, abc1763613206, c-forrest, CCXXXI, Early0v0, EndlessCheng, fps5283, Great-designer, H-J-Granger, hsfzLZH1, huayucaiji, Ir1d, kenlig, ouuan, ouuan, SamZhangQingChuan, sshwy, StudyingFather, test12345-pupil, thredreams, TrisolarisHD, untitledunrevised, Xeonacid
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用