乘积树快速多项式插值

形式陈述

设 $K$ 为域， $u_0,\ldots,u_{n-1}\in K$ 两两不同，给定值 $y_0,\ldots,y_{n-1}$ 。令

M(x)=\prod_{i=0}^{n-1}(x-u_i).

因为

M'(u_i)=\prod_{j\ne i}(u_i-u_j)\ne0,

唯一的次数小于 $n$ 的插值多项式可写为

f(x)=\sum_{i=0}^{n-1} \frac{y_i}{M'(u_i)}\frac{M(x)}{x-u_i}.

算法先建子乘积树得到 $M$ ，求形式导数 $M'$ ，再调用快速多点求值一次得到全部 $M'(u_i)$ 。叶子权重置为 $c_i=y_i/M'(u_i)$ 。若结点的左右子积为 $M_L,M_R$ ，局部线性组合分别为 $F_L,F_R$ ，则向上合并

F=F_LM_R+F_RM_L.

根处正好得到上述 Lagrange 和。建树、求值与合并各花 $O(M(n)\log n)$ 次域运算，总成本仍为 $O(M(n)\log n)$ 。这是一种实现多项式插值的快速通用途径，而不是新的存在唯一性定理。

直觉

朴素 Lagrange 公式为每个 $i$ 单独构造 $n-1$ 个线性因子的乘积，重复了大量工作。乘积树已经保存所有点集区块的乘积；叶子 $i$ 需要“除掉自己的那一个因子”，向上合并时只要把左侧答案乘右侧整块、右侧答案乘左侧整块，就能一次补齐对方所有因子。每个层级的总次数受控，因而可使用快速乘法。

分母 $M'(u_i)$ 不是装饰性的归一化。 $M(x)/(x-u_i)$ 在点 $u_i$ 的值恰为 $M'(u_i)$ ，在其他点则因含对应线性因子而为零；除以它以后才得到在 $u_i$ 取 $1$ 、在其他输入点取 $0$ 的基函数。算法把“基函数的全局性质”拆成叶子权重与树上乘积两部分，各自只算一次。

例子与边界

在有理数域上取点值

(u_i,y_i)=(0,1),(1,2),(2,5).

根积为 $M=x(x-1)(x-2)=x^3-3x^2+2x$ ，所以

M'(0)=2,\qquad M'(1)=-1,\qquad M'(2)=2.

叶子权重为 $1/2,-2,5/2$ 。代入合并式，

\begin{aligned} f(x) &=\frac12(x-1)(x-2)-2x(x-2)+\frac52x(x-1)\\ &=x^2+1. \end{aligned}

复算可得 $f(0)=1,f(1)=2,f(2)=5$ 。这个例子同时显示中间权重可出现分数，即使输入点值全是整数；若目标只是整数系数，算法仍需在某个允许这些除法的域中工作，或采用分母控制版本。

“点两两不同”在一般环上应加强为每个差 $u_i-u_j$ 都是单位。比如在 $\mathbb Z/6\mathbb Z$ 中，点 $0$ 与 $2$ 虽不同，差 $2$ 不可逆， $M'(0)$ 也未必可除，插值可能不唯一或无解。重复点需要给出导数等 Hermite 数据，不能把零分母交给异常处理后继续。

浮点数上还有稳定性边界。显式权重可能极大，树状精确运算的复杂度优势不自动带来良好条件数；数值插值通常选择 Chebyshev 点、barycentric 公式或正交基。这里的结论针对域上的精确算术，若改用近似数，误差分析必须与代数运算数分开。

推论与应用

同一向上合并其实计算了线性映射“点值向量到系数向量”。把叶子权重换成一般模数下的局部剩余类，就得到多项式 Chinese remainder 重构；将其与向下的多模约简配对，可在多个商环之间快速转换。批量 rational interpolation、Reed–Solomon 编解码中的某些子程序以及符号求和也会复用这一结构。

若点集固定而 $y_i$ 多次变化，子积树与 $M'(u_i)^{-1}$ 可以预处理，之后每个新向量只做向上组合。反之，若只有一次很小的插值，Newton 差商的 $O(n^2)$ 简单实现可能更快。算法选择应同时说明点集是否复用、乘法阈值和内存预算；只比较渐近指数会遗漏预处理带来的真实取舍。

参考资料

Joachim von zur Gathen and Jürgen Gerhard, Modern Computer Algebra, 3rd ed., Cambridge University Press, 2013, Ch. 10.
Arne Storjohann, CS 487/687 Symbolic Computation: Script 7—Fast Evaluation and Interpolation, University of Waterloo lecture notes.
Alin Bostan and Éric Schost, “Polynomial Evaluation and Interpolation on Special Sets of Points,” Journal of Complexity 21(4), 2005, pp. 420–446.

形式陈述 ​

反向链接

形式陈述