常系数齐次线性递推

简介

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

对于数列 ${(a_{j})}_{j \geq 0}$ 和其递推式

a_{n} = \sum_{j = 1}^{d} c_{j} a_{n - j}, (n \geq d)

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

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

Fiduccia 算法

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

算法：构造多项式 $Γ (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 Γ (x), A (x) ⟩

其中定义 $⟨ (\sum_{j = 0}^{n - 1} f_{j} x^{j}), (\sum_{j = 0}^{n - 1} g_{j} x^{j}) ⟩ := \sum_{j = 0}^{n - 1} f_{j} g_{j}$ 为内积。

证明：我们定义 $Γ (x)$ 的友矩阵为

C_{Γ} := [\begin{matrix} c_{d} \\ 1 & c_{d - 1} \\ ⋱ & ⋮ \\ 1 & c_{1} \end{matrix}]

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

B_{b} := {[\begin{matrix} b_{0} & b_{1} & \dots & b_{d - 1} \end{matrix}]}^{⊺}

观察到

\underset{C_{Γ}}{\underset{⏟}{[\begin{matrix} c_{d} \\ 1 & c_{d - 1} \\ ⋱ & ⋮ \\ 1 & c_{1} \end{matrix}]}} \underset{B_{b}}{\underset{⏟}{[\begin{matrix} b_{0} \\ b_{1} \\ ⋮ \\ b_{d - 1} \end{matrix}]}} = \underset{B_{x b mod Γ}}{\underset{⏟}{[\begin{matrix} c_{d} b_{d - 1} \\ b_{0} + c_{d - 1} b_{d - 1} \\ ⋮ \\ b_{d - 2} + c_{1} b_{d - 1} \end{matrix}]}}

且

\begin{aligned} C_{Γ} & = [\begin{matrix} B_{x mod Γ} & B_{x^{2} mod Γ} & \dots & B_{x^{d} mod Γ} \end{matrix}], \\ {(C_{Γ})}^{2} & = [\begin{matrix} B_{x^{2} mod Γ} & B_{x^{3} mod Γ} & \dots & B_{x^{d + 1} mod Γ} \end{matrix}], \\ \dots \\ {(C_{Γ})}^{k} & = [\begin{matrix} B_{x^{k} mod Γ} & B_{x^{k + 1} mod Γ} & \dots & B_{x^{k + d} mod Γ} \end{matrix}] \end{aligned}

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

[\begin{matrix} a_{k} \\ a_{k + 1} \\ ⋮ \\ a_{k + d - 1} \end{matrix}] = \underset{{({(C_{Γ})}^{⊺})}^{k} = {({(C_{Γ})}^{k})}^{⊺}}{\underset{⏟}{{[\begin{matrix} 1 \\ ⋱ \\ 1 \\ c_{d} & c_{d - 1} & \dots & c_{1} \end{matrix}]}^{k}}} [\begin{matrix} a_{0} \\ a_{1} \\ ⋮ \\ a_{d - 1} \end{matrix}]

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

表示为有理函数

对于上述数列 ${(a_{j})}_{j \geq 0}$ 一定存在有理函数

\frac{P (x)}{Q (x)} = \sum_{j \geq 0} a_{j} x^{j}

且 $Q (x) = x^{d} Γ (x^{- 1})$ ，$\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 协议之条款下提供，附加条款亦可能应用