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,degq≤n 且展开式 

 
  
   
    
     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​/q1​≡p2​/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
  
 
p1​q2​=q1​p2​,由两边次数均 

 
  
   
    <
   
   
    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
  
 
degq≤n−k,degp<k 时,若 

 
  
   
    p
   
   
    ≡
   
   
    q
   
   
    f
   
   
   
   
    (
   
   
    
     m
    
    
     o
    
    
     d
    
   
   
   
    M
   
   
    )
   
  
  
   p\equiv qf \pmod M
  
 
p≡qf(modM),那么称 

 
  
   
    p
   
   
    ,
   
   
    q
   
  
  
   p,q
  
 
p,q 是一个 

 
  
   
    (
   
   
    k
   
   
    ,
   
   
    n
   
   
    −
   
   
    k
   
   
    )
   
  
  
   (k,n-k)
  
 
(k,n−k) 有理逼近。

接下来,我们将发现任何一个

    k
   
  
  
   k
  
 
k,都存在 

 
  
   
    (
   
   
    k
   
   
    ,
   
   
    n
   
   
    −
   
   
    k
   
   
    )
   
  
  
   (k,n-k)
  
 
(k,n−k) 有理逼近。将同余式写作 

 
  
   
    p
   
   
    ≡
   
   
    q
   
   
    f
   
   
    +
   
   
    M
   
   
    t
   
  
  
   p\equiv qf + Mt
  
 
p≡qf+Mt,这诱导我们考虑欧几里得过程:最初有

 
  
   
    
     
      [
     
     
      
       
        
         
          f
         
        
       
      
      
       
        
         
          M
         
        
       
      
     
     
      ]
     
    
    
     =
    
    
     
      [
     
     
      
       
        
         
          1
         
        
       
       
        
         
          0
         
        
       
      
      
       
        
         
          0
         
        
       
       
        
         
          1
         
        
       
      
     
     
      ]
     
    
    
     
      [
     
     
      
       
        
         
          f
         
        
       
      
      
       
        
         
          M
         
        
       
      
     
     
      ]
     
    
   
   
     \begin{bmatrix} f\\ M \end{bmatrix}= \begin{bmatrix} 1 & 0\\ 0 & 1\\ \end{bmatrix} \begin{bmatrix} f\\ M \end{bmatrix} 
   
  
 [fM​]=[10​01​][fM​]

在欧几里得的过程中,有中间量

      [
     
     
      
       
        
         
          A
         
        
       
      
      
       
        
         
          B
         
        
       
      
     
     
      ]
     
    
    
     =
    
    
     
      [
     
     
      
       
        
         
          
           X
          
          
           A
          
         
        
       
       
        
         
          
           Y
          
          
           A
          
         
        
       
      
      
       
        
         
          
           X
          
          
           B
          
         
        
       
       
        
         
          
           Y
          
          
           B
          
         
        
       
      
     
     
      ]
     
    
    
     
      [
     
     
      
       
        
         
          f
         
        
       
      
      
       
        
         
          M
         
        
       
      
     
     
      ]
     
    
   
   
     \begin{bmatrix} A\\ B \end{bmatrix}= \begin{bmatrix} X_A & Y_A\\ X_B & Y_B\\ \end{bmatrix} \begin{bmatrix} f\\ M \end{bmatrix} 
   
  
 [AB​]=[XA​XB​​YA​YB​​][fM​]

不妨设

    k
   
   
    −
   
   
    1
   
   
    =
   
   
    deg
   
   
    ⁡
   
   
    A
   
   
    ≥
   
   
    deg
   
   
    ⁡
   
   
    B
   
   
    =
   
   
    m
   
  
  
   k-1=\deg A \ge \deg B=m
  
 
k−1=degA≥degB=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​,degXB​≤n−k,那么由于辗转相除 

 
  
   
    A
   
   
    −
   
   
    d
   
   
    B
   
  
  
   A-dB
  
 
A−dB 的系数有 

 
  
   
    deg
   
   
    ⁡
   
   
    d
   
   
    <
   
   
    k
   
   
    −
   
   
    m
   
  
  
   \deg d < k-m
  
 
degd<k−m,可知 

 
  
   
    f
   
  
  
   f
  
 
f 的系数 

 
  
   
    
     X
    
    
     A
    
   
   
    −
   
   
    d
   
   
    
     X
    
    
     B
    
   
  
  
   X_A-dX_B
  
 
XA​−dXB​,那么新的系数为 

 
  
   
    
     X
    
    
     A
    
   
   
    −
   
   
    d
   
   
    
     X
    
    
     B
    
   
   
    ,
   
   
    
     X
    
    
     B
    
   
  
  
   X_A-dX_B,X_B
  
 
XA​−dXB​,XB​。度数均 

 
  
   
    <
   
   
    n
   
   
    −
   
   
    m
   
  
  
   < n-m
  
 
<n−m。

我们现在设

     k
    
    
     ′
    
   
   
    =
   
   
    m
   
   
    +
   
   
    1
   
   
    ,
   
   
    
     m
    
    
     ′
    
   
   
    =
   
   
    deg
   
   
    ⁡
   
   
    (
   
   
    A
   
   
    −
   
   
    d
   
   
    B
   
   
    )
   
  
  
   k'=m+1,m'=\deg (A-dB)
  
 
k′=m+1,m′=deg(A−dB),也就有新的系数的度数均 

 
  
   
    ≤
   
   
    n
   
   
    −
   
   
    
     k
    
    
     ′
    
   
  
  
   \le n-k'
  
 
≤n−k′。注意我们每次辗转相除后得到的 

 
  
   
    (
   
   
    k
   
   
    ,
   
   
    n
   
   
    −
   
   
    k
   
   
    )
   
  
  
   (k,n-k)
  
 
(k,n−k) 有理逼近的 

 
  
   
    k
   
  
  
   k
  
 
k 是一段区间,且刚好拼出了 

 
  
   
    1
   
   
    ∼
   
   
    n
   
  
  
   1\sim n
  
 
1∼n 的所有整数。取对应的 

 
  
   
    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 的幂,通分之后肯定还是正确的。
标签:

本文转载自: https://blog.csdn.net/EI_Captain/article/details/115840021
版权归原作者 Entropy Increaser 所有, 如有侵权,请联系我们删除。

“最短线性递推式求解与有理函数重建”的评论:

还没有评论