为什么要列表?
数据逐点到来时,每加一个节点都重新构造全部拉格朗日(Lagrange)基函数,会掩盖可以重用的部分。牛顿(Newton)形式保留旧多项式,只增加一项;这一项在所有旧节点都为零,其系数由差商给出。三角表只用减法和除法便能算出这些系数。
定义 7.6.1
(差商表)
设 互不相同,数据为 。令 ,并对 、 定义
因此 ,即这些数据的差商。对角线上的 给出
构造此多项式不需要知道节点之间的函数值。 只是记录给定数据的记号,并不要求额外求函数值。
为什么这些系数能插值?
定理 7.6.2
(牛顿插值公式)
对互不相同的节点 ,多项式 (其中 )是唯一一个次数至多为 且对所有 满足 的多项式。
证明
(相邻插值多项式之差)
记 为连续节点 上次数至多为 的唯一插值多项式。它的 系数是该组节点的差商: 时显然成立;利用内维尔(Neville)递推式将 写成两个重叠的低次插值多项式的组合,比较 的系数,就得到上面的差商递推式。
于是 次数至多为 ,并在 处为零,故为 的常数倍。由于 次数更低,这个常数就是 的系数 。将这些差相加便得到牛顿公式;即使最高次系数为零,证明仍然成立。
证明透视
加入新节点时发生什么?
加入与旧节点不同的 和数值 时,旧系数保持不变。只需算出新增的最后一行,直到 ,再加上 。新项在旧节点为零,而递推式确保新多项式也符合新数据。这是精确运算的结论;数据舍入或重复计算可能改变实际算得的系数。
节点互不相同这一假设用在每个分母 中,不能随意去掉。
反例模式
重复节点会使差商表失效
一个诱人的说法是:任意 对数据都有一个次数至多为 的插值多项式,而差商表能把它算出来。取 ,,,。任何函数(无论是否多项式)都不可能在同一点 同时取值 和 。差商表的第一个条目会是 ,即除以零,所以失效并非公式的偶然缺陷。节点互不相同使每个分母非零。若要处理重复节点,数据须相容,并需要另一种构造,本单元不讨论。
差商表与嵌套求值
例题 7.6.3
(四个数据点)
取 。差商表为
| 0 | 0 | 1 | |||
| 1 | 1 | 2 | 1 | ||
| 2 | 2 | 5 | 3 | 1 | |
| 3 | 3 | 10 | 5 | 1 | 0 |
例如 ,。因此 。末系数为零说明四个数据点已落在一个二次多项式上,不能说明未知的原函数在节点之间也是二次函数。
在 处,用嵌套形式求值:
从 开始,依次对 替换 。预先得到差值 后,共需 次乘法和 次加法。
例题 7.6.4
(不等距节点)
取节点 ,数据依次为 。一阶差商为 和 ;二阶差商为 。因此 ,。检验:、、。在 处嵌套求值得 ,与 一致。
例题 7.6.5
(加入一个新系数为零的节点)
在上一例的数据后面加入 ,并保持旧系数不变。新的一阶差商为 ,二阶差商为 ,三阶差商为 。新增项为 ,故仍有 ,而且 。这个结论只针对这四个数据值,并不适用于所有与它们相符的函数。
原位计算及更新顺序
初始化数组 。对每个 ,按 的递减顺序更新:
定理 7.6.6
(原位更新的正确性与代价)
采用递减更新时,第 轮之后, 的 ,而 的 。因此最后每个 。构造共需 次除法和 个数组存储位置。
证明
(递减更新的不变式)
第 轮之前,对所有 有 。设第 轮之前,数组满足: 时 , 时 。在第 轮中, 由 递减到 。更新 时,这一轮还没有改动 ,因为 稍后才轮到,或在 时根本不会被更新。所以两个操作数是 与 ,新值就是 。下标小于 的单元没有被改动,而 此时已算好,故第 轮之后不变式成立。第 轮做 次除法,总数为 ;除节点外只需存储数组 。
每个目标点的嵌套求值需 次运算。
常见错误
(递增更新会混合两列)
上例前三个数的第一轮必须得到 。如果先将 覆盖为 ,递增更新就错误地算出 。这不是单纯改变节点顺序,而是使用已覆盖的操作数进行了不同计算。
精确运算中,节点顺序不影响唯一的插值多项式,但可能改变牛顿系数和中间计算。浮点运算中,不同顺序可能造成不同的舍入误差;节点相近时,除法也会对数据扰动敏感。节点处残差小本身不能保证节点之间准确,也不能给出数值误差界;稳定性和条件性需要另行分析。
练习与解答
快速检查
(取节点 ,数据依次为 。求差商系数及插值多项式在 处的值。)
先算两个一阶差商,再算一个二阶差商。
解答 · 答案
一阶差商为 和 ,二阶差商为 。因此 ,。于是 ,与 一致。
快速检查
(对任意三个不同节点 ,解释为何改变顺序可能改变 ,却不改变插值多项式。)
用前两个节点表示 。
解答 · 答案
常数项后的第一个系数是前两个节点间的斜率,更换前两个节点可能改变斜率。但最终两个次数至多为二的多项式插值同一组三个数据,因唯一性而在精确运算中相同。
快速检查
(五个节点的差商表需要多少次除法?)
在代价结论中取 。
解答 · 答案
五个节点即 ,差商表需要 次除法:四轮分别是 次。
快速检查
(若两个节点重合,表中哪个分母会变为零?这说明什么?)
留意 。
解答 · 答案
当 时分母 为零。这表示数据不能按互异节点的插值处理:同一点上的两个不同值互相矛盾,而相同的值也需要另一种构造。