c++ - 有理函数级数展开的最佳算法

Question

我需要用 C++ 编写函数代码，它可以有效地找到给定有理函数 (P(x)/Q(x)) 的泰勒级数系数。

函数参数将是多项式的幂(分母和分母相等)，两个具有多项式系数和展开项数的数组。

我的想法如下。 考虑身份

P(x) / Q(x) = R(x) + ...

其中 R(x) 是一个多项式，其项数等于我需要找到的系数数。然后我可以将两边与 Q(x) 相乘并得到

P(x) = R(x) * Q(x)

R(x) * Q(x) - P(x) = 0

因此，所有系数都应为零。这是用 O(n^3) 算法求解的方程组。 O(n^3) 没有我想要的那么快。

有没有更快的算法？

我知道级数的系数满足线性递推关系。 这让我觉得 O(n) 算法是可能的。

Answer 1

我将要描述的算法在数学上由 formal power series 证明是合理的.每个具有泰勒级数的函数都有一个正式的幂级数。反之则不然，但如果我们用泰勒级数对函数进行运算并得到一个具有泰勒级数的函数，那么我们可以对形式幂级数进行相同的运算并得到相同的答案。

形式幂级数的长除法算法如long division您可能在学校学到的算法。我将在示例 (1 + 2 x)/(1 - x - x^2) 中对其进行演示，其系数等于 Lucas numbers .

分母必须有一个非零常数项。我们从写分子开始，它是第一个残差。

             --------
1 - x - x^2 ) 1 + 2 x

[ 我们将残差的最低阶项 (1) 除以分母的常数项 (1)，并将商放在最上面。

              1
             --------
1 - x - x^2 ) 1 + 2 x

现在我们将 1 - x - x^2 乘以 1 并从当前残差中减去它。

              1
             --------
1 - x - x^2 ) 1 + 2 x
              1 -   x - x^2
              -------------
                  3 x + x^2

再做一次。

              1 + 3 x
             --------
1 - x - x^2 ) 1 + 2 x
              1 -   x -   x^2
              ---------------
                  3 x +   x^2
                  3 x - 3 x^2 - 3 x^3
                  -------------------
                        4 x^2 + 3 x^3

再一次。

              1 + 3 x + 4 x^2
             ----------------
1 - x - x^2 ) 1 + 2 x
              1 -   x -   x^2
              ---------------
                  3 x +   x^2
                  3 x - 3 x^2 - 3 x^3
                  -------------------
                        4 x^2 + 3 x^3
                        4 x^2 - 4 x^3 - 4 x^4
                        ---------------------
                                7 x^3 + 4 x^4

再一次。

              1 + 3 x + 4 x^2 + 7 x^3
             ------------------------
1 - x - x^2 ) 1 + 2 x
              1 -   x -   x^2
              ---------------
                  3 x +   x^2
                  3 x - 3 x^2 - 3 x^3
                  -------------------
                        4 x^2 + 3 x^3
                        4 x^2 - 4 x^3 - 4 x^4
                        ---------------------
                                7 x^3 + 4 x^4
                                7 x^3 - 7 x^4 - 7 x^4
                                ---------------------
                                       11 x^4 + 7 x^5

单独的除法有点无聊，因为我使用了一个带前导 1 的除数，但是如果我使用了，比方说，2 - 2 x - 2 x^2，则商中的所有系数将除以 2。