Skip to content

算法Algorithm

重心 Lagrange 插值

施工中 · 内容逐步修订

Barycentric Lagrange interpolation · Barycentric interpolation

预计算重心权后以线性成本求值 Lagrange 插值多项式,并说明节点命中、权重尺度与数值稳定性的条件。

形式陈述 ​

输入是两两互异节点 x0,…,xn、数据 y0,…,yn 和查询点 x。定义节点多项式

ω(x)=∏k=0n(x−xk)

及重心权

wj=1∏k≠j(xj−xk).

每个 Lagrange 基函数都可分解为 ℓj(x)=ω(x)wj/(x−xj):先从所有节点因子的乘积中去掉第 j 个,再除以它在 xj 处的值。因此 Lagrange 插值多项式可写成第一重心公式

p(x)=ω(x)∑j=0nwjyjx−xj.

为改善直接乘积求值的数值稳定性,利用对常数函数插值得到 ∑jwj/(x−xj)=1/ω(x),可消去显式乘积,得到通常用于求值的第二重心公式

p(x)=∑j=0nwjyjx−xj∑j=0nwjx−xj,x≠xj.

若查询点与某节点精确相等,算法必须直接返回 yj,而不是计算含零分母的商。朴素预计算全部权重耗时 O(n2)、存储 O(n);权重固定后,每个查询点需要 O(n) 次运算和 O(1) 额外空间。它不是迭代算法:处理完全部 n+1 项并完成节点命中检查,就得到了该点的输出,没有另设残差停止准则。

在第二重心公式中,所有权重同时乘非零常数不会改变结果,因此可以整体缩放以控制幅值。等距点和 Chebyshev 点具有封闭或递推权重,应使用专门表达避免形成极大乘积;一般节点若尺度跨度很大,也可通过平移缩放节点、分批构造权重或使用扩展精度降低溢出风险。

直觉

直接 Lagrange 公式为每个基函数重新乘一长串因子,许多大中间量最后才相消。重心形式先把只依赖节点的部分压进权重,再把每次查询变成两个结构相同的加权和;分子和分母共同携带尺度,很多危险的公共因子在商中自动抵消。

这种改写改善的是“给定节点与数据后怎样求值”。它不会改变插值算子本身:若节点集合使数据扰动受到巨大放大,稳定算出那个插值多项式仍可能得到糟糕的函数近似。算法稳定性与节点条件性必须分开评价。

重心插值的分子与分母贡献
例子与边界

对节点 (−1,0,1),按乘积定义算得权重 (1/2,−1,1/2),在第二公式中可整体乘二,改用 (1,−2,1)。取数据 (1,0,1),其插值多项式为 p(x)=x2。在 x=1/2 处,先计算共同项

(w0x+1,w1x,w2x−1)=(23,−4,−2).

分母为 −16/3,分子为 (2/3)⋅1−4⋅0−2⋅1=−4/3,两者相除得 1/4。图中的“节点贡献汇总”正是这两个和:贡献可以为负,并非把数据作普通凸加权平均。查询 x=0 时则直接返回中间数据 0,避免出现除零。

当 x 极接近某个 xj 时,分子和分母都含大项 1/(x−xj)。精心实现的第二公式通常仍有良好行为,但“接近”不能用一个与数据尺度无关的固定 epsilon 代替精确节点检查,否则会把本应不同的查询点错误吸附到节点上。

权重也不能逐个任意缩放。若仍用上述节点与数据,却把权重改成 (1,1,1),则第二公式变为 2x2/(3x2−1);它在节点处按极限仍能插值,却在 x=±1/3 出现极点。这是有理函数,已经不是原来的多项式。公共比例因子可以消去,各权重之间的相对比例则定义了具体问题。

高次等距插值提供另一条边界:即使重心求值避免了解 Vandermonde 系统,Lebesgue 常数仍会快速增长,端点附近的插值可能不收敛。Chebyshev 节点通过改变问题的节点几何缓解这一点,而不是换一个代数等价公式便自动解决。

推论与应用

求和顺序仍会影响两个重心和,必要时可结合成对或补偿求和;但补偿不能修复溢出的权重或病态节点。输入输出、节点尺度和求和策略应在实现说明中同时给出。

特殊余弦节点的权重结构还连接离散余弦变换与快速多项式计算。这里的核心仍是单点或批量求值;如何选择节点、估计函数误差以及构造正交系数分别由节点条件性、余项和谱逼近页面承担。

参考资料
  • Jean-Paul Berrut and Lloyd N. Trefethen, “Barycentric Lagrange Interpolation,” SIAM Review 46(3), 2004, pp. 501–517,§§3–4 重心公式、§9.2 任意权重与有理插值。
  • NIST Digital Library of Mathematical Functions, §3.3 Interpolation, accessed 2026.
  • Nicholas J. Higham, “The Numerical Stability of Barycentric Lagrange Interpolation,” IMA Journal of Numerical Analysis 24(4), 2004.
关系图谱7 个相邻概念 · 3 类关系

拖动节点调整位置。

显示关系

显示:依赖

  1. 前置三跳
  2. 前置二跳
  3. 前置一跳
  4. 当前条目
  5. 后续一跳
  6. 后续二跳
  7. 后续三跳
文字版关系按与当前条目的最短距离分组
类型化关系