当前位置：首页 > news >正文

【学习笔记】线性递推数列

news 来源：原创 2024/4/19 12:23:08

$1.1$ 定义：对于无限数列 ${a_0,a_1,a_2,...\}$ 和有限非空数列 ${r_0,r_1,r_2,...,r_{m-1}\}$ ，若对于任意 $p≥m−1p\ge m-1$ ，有 $∑k=0m−1ap−krk=0\sum_{k=0}^{m-1}a_{p-k}r_k=0$ ， $r_0=1$ ，我们称数列 $r$ 为数列 $a$ 的线性递推式。我们称存在线性递推式的无线序列为线性递推数列。 $r_0=1$ 说明 $a_p=-(a_{p-1}r_1+...+a_{p-m+1}r_{m-1})$ ，就是所谓的递推式。

$1.2$ 对于无限数列 ${a_0,a_1,a_2,...\}$ 和有限非空序列 ${r_0,r_1,r_2,...,r_{m-1}\}$ ，设数列 $a$ 和数列 $r$ 所对应的生成函数为 $A$ 和 $R$ ，数列 $r$ 为数列 $a$ 的线性递推式等价于存在次数不超过 $m - 2$ 的多项式 $S$ 满足 $A R + S = 0$ 。对于有限数列 ${a_0,a_1,a_2,...,a_{n-1}\}$ ，则为 $AR+S=0(modxn)AR+S=0\pmod{x^n}$ 。

$1.3$ Berlekamp-Massey 算法，先考虑有限的情形。该算法找一个阶数最小的 $R$ ，使得 $AR=S(modxn)AR=S\pmod{x^n}$ ，且 $S$ 的阶数小于 $R$ 的阶数。具体做法是对于 $i = 2, 3, ..., n$ ，在 $mod{x^i}$ 的意义下递推求出 $R_i$ 和 $S_i$ 。

假设已经知道 $modxi−1\bmod\ {x^{i-1}}$ 的答案是 $R_i$ ，那么求 $modxi\bmod\ {x^i}$ 的答案 $R_i$ 。

$1.3.1$ 先检验一下是否有 $ARi−1=Si−1(modxi)AR_{i-1}=S_{i-1}\pmod{x^i}$ ，如果是，那么 $R_i=R_{i-1}$

$1.3.2$ 如果不是，那么有 $ARi−1−Si−1=dxi−1(modxi)(1)AR_{i-1}-S_{i-1}=dx^{i-1}\pmod{x^i}(1)$ 。考虑上次是再 $p (p < i)$ 增长的递推式，当时有 $ARp−1−Sp−1=cxp−1(modxp)(2)AR_{p-1}-S_{p-1}=cx^{p-1}\pmod{x^p}(2)$ 。

$(2)$ 同时乘 $x^{i-p}dc^{-1}$ ，有 $xi−pdc−1(ARp−1−Sp−1)=dxi−1(modxi)(3)x^{i-p}dc^{-1}(AR_{p-1}-S_{p-1})=dx^{i-1}\pmod{x^i}(3)$

$(1)−(3):A(Ri−1−xi−pdc−1Rp−1)=Si−1−xi−pdc−1Sp−1(modxi)(1)-(3):A(R_{i-1}-x^{i-p}dc^{-1}R_{p-1})=S_{i-1}-x^{i-p}dc^{-1}S_{p-1}\pmod{x^i}$

令 $R_i=R_{i-1}-x^{i-p}dc^{-1}R_{p-1}$ ， $S_i=S_{i-1}-x^{i-p}dc^{-1}S_{p-1}$ 即可。

初始 $R_0=1,S_0=0$ ，如果 $A_0$ 到 $A_{i-2}$ 都是 $0$ ，而 $A_{i-1}$ 不为零，此时修改递推式，让 $R_{i}=1+x^i$ ， $S_i=A_{i-1}x^{i-1}$ 即可。

其最短性不再赘述。由于初值和递推过程中， $S_i$ 次数小于 $R_i$ 次数，所以最后得到的结果中， $S$ 的次数也是小于 $R$ 的次数的。复杂度 $O(n^2)$ 。

对于无限长的数列 ${a_0,a_1,a_2,...\}$ ，若它的最短线性递推式阶数不超过 $s$ ，那么 ${a_0,a_1,a_2,...,a_{s+s-1}\}$ 的最短线性递推式即为 $a$ 的最短线性递推式。

$1.4$ 设已知 $a_{i+1}=-(a_{i-n+1}b_n+a_{i-n+2}b_{n-1}+...+a_ib_1)$ ，且已知 $a1∼na_{1\sim n}$ ， $b1∼nb_{1\sim n}$ ，求 $a_k$ 的值。

我们知道 $A R = S$ ，所以 $A=SRA=\frac{S}{R}$ 。

问题转化为，求 $P(x)Q(x)\frac{P(x)}{Q(x)}$ 的第 $n$ 项。因为 $F(x)=P(x)Q(−x)Q(x)Q(−x)F(x)=\frac{P(x)Q(-x)}{Q(x)Q(-x)}$ ，所以 $Q (x) Q (- x)$ 只有偶数项不为 $0$ ，设 $P(x)Q(-x)=E(x^2)+xO(x^2)$ ， $V (x) = Q (x) Q (- x)$ ，所以得到分解 $P(x)Q(x)=E(x2)V(x2)+xO(x2)V(x2)\frac{P(x)}{Q(x)}=\frac{E(x^2)}{V(x^2)}+x\frac{O(x^2)}{V(x^2)}$ ，只需按 $n$ 的奇偶性递归到一侧即可。递归到常数项时答案就是分子分母常数项相除。

复杂度 $O(nlog⁡nlog⁡k)O(n\log n\log k)$ 。

$1.5$ 求向量/矩阵的最短递推式

考虑将向量/矩阵转化为标量序列的最短线性递推式。具体做法是随机一个向量 $v$ 与每个向量相乘，矩阵的情况也类似。

$1.6$ 求矩阵的最小多项式

相当于求矩阵 ${I,M,M^2,...\}$ 的线性递推式，我们知道 $M$ 的最小多项式阶数 $≤n\le n$ （特征多项式），所以只需对矩阵 ${I,M,M^2,...,M^{2n}\}$ 应用 $BM$ 算法即可。

$1.7$ 求矩阵的特殊多项式

由于特征多项式是一个 $n$ 阶多项式，所以可以带入 $n + 1$ 个值进去，求 $n$ 个行列式的值，然后插值。复杂度 $O(n^4)$ 。

相关文章：