程序员最近都爱上了这个网站  程序员们快来瞅瞅吧!  it98k网:it98k.com

本站消息

站长简介/公众号

  出租广告位,需要合作请联系站长

+关注
已关注

分类  

暂无分类

标签  

暂无标签

日期归档  

2022-02(82)

2022-03(77)

2022-04(80)

2022-05(1)

2022-06(40)

最短线性递推式求解与有理函数重建

发布于2023-01-20 03:32     阅读(1005)     评论(0)     点赞(11)     收藏(0)


这一算法来自于我们对“线性递推式拟合”的视角转换,其后得到的算法是自然的。

引理 1. 如果两个有理分式 p 1 / q 1 , p 2 / q 2 p_1/q_1, p_2/q_2 p1/q1,p2/q2 均有 deg ⁡ p < n , deg ⁡ q ≤ n \deg p<n, \deg q\leq n degp<n,degqn 且展开式 p 1 / q 1 ≡ p 2 / q 2 ( m o d x 2 n ) p_1/q_1 \equiv p_2/q_2 \pmod {x^{2n}} p1/q1p2/q2(modx2n),那么 p 1 / q 1 = p 2 / q 2 p_1/q_1 = p_2/q_2 p1/q1=p2/q2

证明. 通分,等价于 p 1 q 2 = q 1 p 2 p_1q_2=q_1p_2 p1q2=q1p2,由两边次数均 < 2 n <2n <2n,而同余式保留了全部信息。

这一引理告诉我们,若一个 n n n 阶线性递推式确实拟合了其前 2 n 2n 2n 项,那么通分之后就一定是“最小”的。

为了解决这一问题,我们首先将问题适当泛化:

「有理函数重建」(Rational Function Reconstruction):给定域上的多项式 f ( x ) , M ( x ) f(x),M(x) f(x),M(x),设 deg ⁡ M = n \deg M = n degM=n,当多项式 p , q p,q p,q 满足 deg ⁡ q ≤ n − k , deg ⁡ p < k \deg q \leq n-k, \deg p < k degqnk,degp<k 时,若 p ≡ q f ( m o d M ) p\equiv qf \pmod M pqf(modM),那么称 p , q p,q p,q 是一个 ( k , n − k ) (k,n-k) (k,nk) 有理逼近。

接下来,我们将发现任何一个 k k k,都存在 ( k , n − k ) (k,n-k) (k,nk) 有理逼近。将同余式写作 p ≡ q f + M t p\equiv qf + Mt pqf+Mt,这诱导我们考虑欧几里得过程:最初有
[ f M ] = [ 1 0 0 1 ] [ f M ]

[fM]
=
[1001]
[fM]
[fM]=[1001][fM]
在欧几里得的过程中,有中间量
[ A B ] = [ X A Y A X B Y B ] [ f M ]
[AB]
=
[XAYAXBYB]
[fM]
[AB]=[XAXBYAYB][fM]

不妨设 k − 1 = deg ⁡ A ≥ deg ⁡ B = m k-1=\deg A \ge \deg B=m k1=degAdegB=m,那么我们接下来进行多项式取模,就应当逐步将 A A A 的度数从 < k <k <k 降到 < m <m <m,然后交换 A , B A,B A,B。此时我们归纳假设 deg ⁡ X A , deg ⁡ X B ≤ n − k \deg X_A, \deg X_B \leq n-k degXA,degXBnk,那么由于辗转相除 A − d B A-dB AdB 的系数有 deg ⁡ d < k − m \deg d < k-m degd<km,可知 f f f 的系数 X A − d X B X_A-dX_B XAdXB,那么新的系数为 X A − d X B , X B X_A-dX_B,X_B XAdXB,XB。度数均 < n − m < n-m <nm
我们现在设 k ′ = m + 1 , m ′ = deg ⁡ ( A − d B ) k'=m+1,m'=\deg (A-dB) k=m+1,m=deg(AdB),也就有新的系数的度数均 ≤ n − k ′ \le n-k' nk。注意我们每次辗转相除后得到的 ( k , n − k ) (k,n-k) (k,nk) 有理逼近的 k k k 是一段区间,且刚好拼出了 1 ∼ n 1\sim n 1n 的所有整数。取对应的 p = A , q = X A p=A,q=X_A p=A,q=XA 即可。

辗转相除过程的这个序列通过 HALF-GCD 算法可以在 Θ ( n log ⁡ 2 n ) \Theta(n\log ^2n) Θ(nlog2n) 时间内计算。严格来说,我们是通过 HALF-GCD 算法计算出的矩阵列,可以算出任何一个阶段的有理函数重建。但对于我们对线性递推式的计算而言,只做 n n n 消到 n / 2 n/2 n/2 这第一轮刚好足够我们求出信息。

不过这里似乎 p , q p,q p,q 是可能有 x x x 的幂的,但如果将引理 1 稍微改改就会发现,如果我们给的数列真的有一个递推式,那就算 p , q p,q p,q x x x 的幂,通分之后肯定还是正确的。



所属网站分类: 技术文章 > 博客

作者:bbjbbh

链接:http://www.phpheidong.com/blog/article/477324/a53f6ee78ede769962a3/

来源:php黑洞网

任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任

11 0
收藏该文
已收藏

评论内容:(最多支持255个字符)