动机
Lagrange 公式解决了存在性问题:在指定次数以内,有唯一多项式通过互异节点的数据。但实际计算还有不同问题。新增一次测量时,是否需要从头计算?能否不展开单项式系数,直接计算高次插值多项式?如果可以决定测量位置,节点应放在哪里?这些问题分别涉及更新、求值和实验设计,不能把一个公式当成所有准确性问题的答案。
Newton 形式清楚显示增加节点所添加的一项;重心形式将同一多项式重组为方便的求值公式;Chebyshev 节点使插值余项中的某个最坏节点乘积最小。然而,三者都不能消除数据误差本身。因此本节始终区分未知函数的近似、插值映射的条件,以及计算公式的舍入。
定义
定义 5.1.1
(差商与 Newton 形式)
设 是互异实节点,输入数据记作 。差商递归定义为
差商只是数据的代数组合;记号并不假设输入来自可微函数。Newton 插值式为
空乘积为一。求值时从最后一个系数开始,依次乘 再加下一个系数,得到嵌套算法,不必先转成单项式形式。若数据按节点顺序到达,已有系数可保留,仅需计算新的差商列。
定义 5.1.2
(重心权重与第二重心公式)
定义节点多项式及重心权重
所有权重非零。对于非节点,第二重心公式是
全部权重乘同一个非零常数不改变商。在节点应直接定义并返回 ,而非真的除以零。表面奇点来自表示,不属于多项式。
完整差商表包含三角形排列的差及除法,预处理运算量随节点数平方增长;系数备妥后,每个目标点的 Newton 嵌套求值只需线性运算量。一般重心权重的直接乘积构造也需要平方预处理,之后每次求值为线性。这里计算的是算术操作数,不能解释为准确性或位复杂度保证。同一组节点对应多个数据向量时可重用权重;节点改变后,权重也必须更新。
定义 5.1.3
(Lebesgue 常数与最佳近似误差)
在包含节点的紧致区间 上,以 表示连续函数的插值,定义
Lebesgue 常数 是一致数据范数下的插值算子范数,表示整个区间上最坏的绝对数据误差放大。它由节点决定,并不等于浮点求值算法的误差常数。 则问所有次数不超过 的多项式中,最佳近似能有多好;最佳多项式未必通过采样点。
概念视角结构
表示、算子与最佳近似
Newton 式与重心式表示同一个线性插值算子。Lebesgue 常数研究算子的敏感度,最佳近似研究多项式空间能否接近未知函数。下面定理中的不等式将两者联系起来,却不把它们混为一谈。高效求值公式也因此不能被误读为准确性定理。
定理/命题
定理 5.1.4
(Newton 系数与重心恒等式)
Newton 公式给出唯一插值多项式,其第 个节点乘积的系数正是前 个节点的差商。第二重心公式与这个多项式相同,非节点处的精确分母为 ,因此非零。对于 上连续函数,
若每个输入样本的绝对误差不超过 ,再加上最多 的数据误差。
定理 5.1.5
(Chebyshev 节点使首一节点乘积最小)
设整数 ,以 定义 Chebyshev 多项式。它的次数为 ,首项系数为 。在 上,所有首一 次实多项式的最小一致范数为 ,由 达到。其根为
将节点仿射映到 ,最小节点乘积范数为 。若 且 ,对应插值满足
最后一个结论固定次数后优化导数型上界。次数增长时 也会改变,所以不能据此说任意光滑函数的误差都趋零。使节点乘积最小与使 Lebesgue 常数最小也是不同问题。
这里 表示节点数,对应前文的 ;插值多项式次数至多 ,可记为 。被优化的 次对象是节点乘积,而非插值多项式。
若只知道函数有三阶连续导数,即使增加样本,也不能直接使用需要十一阶导数的界。无限可微函数的高阶导数最大值也可能迅速增长。反过来,保守上界很大并不证明实际插值很差;它可能只是无法认证一次准确计算。报告结果时应区分已证明的上界、实际观察的误差,以及启发式预期。
证明思路或证明
差商为什么是 Newton 系数
证明
(首项系数满足差商递归)
前 个节点的 Lagrange 插值式,其 系数为
这个表达式满足差商递归。取节点 的表达式,减去节点 的表达式,再除 。对内部数据 ,提取公共乘积后剩下
两个端点系数直接计算也成立。从 归纳,即得 。再比较前 节点与前 节点的插值多项式:差在前 节点为零,次数至多 ,所以是节点乘积的常数倍。旧多项式次数较低,故这个常数正是新多项式的首项系数 。逐次添加便得 Newton 式。这个证明还说明差商对节点和数据的配对排列是对称的,虽然计算表使用了某个顺序。
有理式为什么仍是多项式
证明
(以节点多项式除两个 Lagrange 恒等式)
Lagrange 基底满足 。将插值式除以 ,得到重心分子。插值保持常数函数,因此 ;再除以 ,得到分母恒等式。两者相除便证明公式。这里讨论精确分母,并未宣称数值计算得到的分母绝不会发生舍入问题。在节点附近分子分母都可能很大,节点处应直接返回输入值。
证明
(插值重现所有次数不超过 的多项式)
对任意 ,有 ,所以
第二项的范数至多为 。用三角不等式,再对 取下确界,便得最佳近似不等式。对数据扰动使用相同的绝对权重和,得到额外的 。误差可以具有任意符号及相关性,不需要概率独立假设。
反例模式
插值不等于最佳逼近
一个诱人的说法是:插值多项式本身就是 中的最佳一致逼近,因此因子 是多余的。取 上的 、 和节点 。此时 ,,在 处取到。若直线 满足 ,就需要 ,但 ,矛盾;常数 的误差恰为 ,所以 。由于 ,定理的上界 取等号。若改用节点 ,插值多项式是常数 ,恰好达到 :差距取决于节点。
交错极值如何给出最优节点乘积
证明
(交错符号强迫过多的根)
余弦恒等式给出 ,起点为 。归纳可得次数及首项系数。在 上,,并在 交替取值 。
设某首一多项式 的范数严格小于 。差 的最高次项抵消,次数至多 。在这 个相邻极值点,因 , 的符号与 相反,故交替。介值定理在每两个相邻点之间给出一个根,总共 个互异根,与次数矛盾。因此任何首一多项式的范数都不能更小,而 确实达到该值。其根互异,所以它正是这些节点的首一乘积。仿射变换带来因子 ,结合插值余项便得导数误差界。
证明透视
交错证明究竟优化什么
论证由三个要素组成,各有确定的位置。首一假设只用一次:它令 与 的最高次项抵消,所以 的次数至多为 。等振荡性质提供 个点 ,在这些点 。严格假设 使 非零,且符号为 。若只有 ,某些 可能为零,符号计数便需要另外的论证。
介值定理接着在相邻 之间的 个互不相交开区间内各给出一个根。次数至多 而有 个相异根的多项式恒为零,所以 ;但其范数恰为 ,与严格不等式矛盾,论证就此闭合。转到 只用仿射变换及导数余项。因此证明只在一致范数中优化节点乘积:它不涉及 Lebesgue 常数,也不涉及浮点求值。
例题详解
例题 5.1.6
(新增样本时保留原有计算)
节点 的值为 ,第一差商为一,故 。新增节点 、值 ,新的第一差商为三,第二差商为 。因此
在 ,嵌套求值得 。只增加一项能节省计算,但不能消除节点聚集或不确定数据的敏感性。
例题 5.1.7
(重心权重与数据放大)
节点 的权重为 ,也可统一缩放成 。在 ,未缩放的分母为 ;数据 的分子为 ,商为 。Lagrange 权重是 ,绝对和为 ,故样本误差可被放大到 。改变表示没有改变问题的条件。
例题 5.1.8
(三个节点的两种选择)
的根为 ,节点乘积为 ,范数为 。等距节点 给出 ,在 的极值绝对值是 。若 ,两者分别给出 与约 的上界。不过任意二次函数在两组节点上都完全准确,说明上界比较并非每个函数的严格误差比较。
常见错误
反例模式
增加等距插值次数可能更差
考虑 。在 取等距节点,于 ,四次插值约为 ,十次插值约为 ,而真值约为 。绝对误差由约 增到 。这个有限计算展示 Runge 现象,并非渐近发散的完整证明;但已经否定“次数增加必然更准确”的无条件说法。
另外三个错误关乎公式的使用方式,而非公式本身的内容。
常见错误
(把“重心”当作稳定性证书)
公式的名称不是误差分析。用长乘积计算权重可能上溢或下溢,近节点求值仍需处理,舍入后的节点也定义了扰动问题。节点设计处理近似与条件;稳定的实现还必须处理算术。
常见错误
(分别缩放个别重心权重)
只能移除公共因子。节点 、数据 时,缩放权重 在 给出 ,正是正确值。若只把最后一个权重改为 ,则得 。改动后的商一般是有理函数,而不是插值多项式。
常见错误
(把区间内的界用于外推)
Lebesgue 常数和余项界都是在包含节点的区间上取最大值,对区间以外没有任何保证。节点 时,Lagrange 权重绝对值之和在 上处处为一,但在 为二;外推需要独立分析。
总结
差商支持逐点扩充的 Newton 构造。重心公式来自 Lagrange 恒等式,节点处应单独返回样本。Lebesgue 常数控制确定性数据误差,并联系最佳近似。Chebyshev 根优化固定次数下的首一节点乘积及相应导数上界;次数增长、条件及浮点稳定性仍需独立论证。
练习
快速检查
(节点 的数据为 。建立差商表,写 Newton 式并在 求值。若这些数据来自二次函数,会有什么结论?)
先求两个一阶差商,再求一个二阶差商。
解答 · 答案
第一差商是 和 ,第二差商为 。因此 ,。若原函数是二次函数,唯一性说明它与插值多项式处处相同,不再存在未知导数余项。
快速检查
(求节点 的重心权重。在 求插值值及精确的最坏绝对误差放大系数;在 的系数又是多少?)
在每个目标点计算两个 Lagrange 函数。
解答 · 答案
权重为 ,可作公共缩放。在零点的 Lagrange 系数为 ,所以值为平均数,放大系数为一。在二点的系数为 ,放大系数为二,误差 达到 。这个线性例子已显示外推增加敏感度。
快速检查
(求区间 上的两个 Chebyshev 根及首一节点乘积。若 ,求定理给出的一致误差界,并与端点节点 比较。)
把 的根 仿射映到 。
解答 · 答案
将 映到 ,得 。节点乘积为 ,范数为 ,故余项界为 。端点节点的乘积为 ,范数为一,界为四。这些是上界,并非每个函数都达到的误差。
快速检查
(设 、,每个样本绝对误差不超过 。给出合并的一致误差界。同一多项式换另一种精确表示能否改善这个界?)
使用第一个定理中的合并不等式。
解答 · 答案
近似项为 ,数据项为 ,总和为 。另一种精确表示不改变算子或其范数,但可以改变计算成本及未包含在此界内的算术误差。