New Recursive Divided-Difference Interpolation Method

技术摘要：一种新型递归差分插值法

问题陈述
多项式插值是数值分析中的一项基本工具，但在确定标准单项式基底（$P_n(x) = a_n x^n + \dots + a_0$）下的插值多项式系数方面，存在着持久的计算挑战。虽然牛顿插值形式在利用差分构造插值多项式方面具有较高的计算效率，但将其转换为单项式基底通常需要依赖两种低效策略：

1. 显式展开： 对牛顿基底多项式进行代数展开并合并同类项，这随着次数的升高会增加算术运算量和复杂度。
2. 范德蒙德方程组： 求解线性方程组 $Va = y$，而已知对于高次多项式，该方法由于范德蒙德矩阵条件的指数级增长而具有数值不稳定性。

现有的递归算法（如经典的牛顿法）仅确定牛顿基底的系数，并在找到这些系数后即告终止。它们并未利用差分的递归结构来直接得出单项式系数，而是通过中间的代数展开或线性方程组求解来实现。

方法论
作者提出了一种新的递归算法，通过迭代重建差分表，直接从插值数据中确定单项式系数。该方法基于以下原理运行：

• 递归差分表： 作者定义了一个递归结构，其中差分表中每一列的所有元素都会被保留，而不仅仅是经典牛顿插值中使用的第一个元素。
• 通过不变性识别系数： 其核心理论见解在于，当递归计算的差分列在所有元素上都产生一个常数值时（即 $\Delta^{(k)}_1 = \Delta^{(k)}_2 = \dots = \Delta^{(k)}_{n-k+1}$），该常数值恰好对应于单项式基底中最高次项（$x^k$）的系数。
• 迭代降阶： 一旦确定了最高次项系数（$a_k$），算法会从原始插值值（$y_i$）中减去该项 $a_k x^k$ 的贡献。这生成了一组对应于 $k-1$ 次多项式的新的零阶差分值。
• 重构： 随后构建一个新的差分表，并重复此过程以识别下一个最高次系数（$a_{k-1}$）。该过程按顺序向下持续进行，直到常数项 $a_0$。

主要贡献

1. 直接确定单项式： 本文引入了一种无需显式展开牛顿多项式或求解范德蒙德方程组即可计算单项式系数的方法。
2. 递归降阶策略： 作者开发了一种策略，通过减去每步确定的最高次项贡献，将插值问题转化为一系列低阶插值问题。
3. 理论证明： 该方法得到了严密的数学证明支持，包括：
   • 引理 3.1： 建立了所提议的递归差分在插值多项式中的表示形式。
   • 定理 3.2： 证明了递归差分表中常数列对应于特定单项式系数的充分必要条件。
4. 算法实现： 提供了一个逐步迭代算法（算法 3.1），详细说明了如何通过重建表格和更新零阶差分，从而从 $a_n$ 到 $a_0$ 逐一分离出系数。

结果
论文通过数值实验验证了所提方法的有效性：

• 正确性： 使用三次多项式（$y = 2x^3 + 3x^2 + 5x + 7$）进行的数值示例展示了逐步递归重构的过程。算法通过观察每次降阶步骤后差分列中的常数值，成功识别出了系数 $a_3=2, a_2=3, a_1=5$ 和 $a_0=7$。
• 准确性： 重构的系数与多项式的精确系数相匹配，证实了该方法的理论有效性。
• 效率： 该方法证明了可以直接从插值数据中确定系数，避免了传统转换方法所需的中间代数展开。

意义与主张
作者将这项工作定位为一种对差分的全新计算解释。他们声称，该方法在差分与单项式系数之间建立了直接的递归联系，从根本上改变了差分的角色——使其不再仅仅用于构造牛顿多项式，而是作为重构单项式系数的中间量。

论文明确指出，本研究并未针对现有方法（如范德蒙德求解器或基底转换算法）进行计算复杂度和数值稳定性的对比分析。相反，它将该方法呈现为一种新的替代性递归计算方案。作者指出，未来的研究将针对不同节点分布下的算法计算复杂度、数值稳定性和效率进行探讨，并将其与现有方法进行比较。其主要贡献在于提出了理论框架，并论证了可以通过数据降阶递归地导出单项式系数，而无需辅助线性代数或多项式展开。