知道一个多项式在若干点处的值,就得到了关于其系数的方程。这些值究竟能确定多少信息?次数上界起决定性作用:若没有次数上界,就可以加上一个在所有选定点处都取零的非零多项式,而所有数据都不会改变。插值构造出唯一的低次代表元,并把求值与多项式商环联系起来。
由函数值构造多项式
定义 9.1.1
(拉格朗日(Lagrange)基多项式)
设 是一个域, 是 中互不相同的元素(节点)。对每个 ,定义
由于节点互不相同,每个分母都非零;又因为 是域,所以分母可逆。在 处每个因子都等于 1,而在任何其他节点 处有一个分子为零。因此 。
定理 9.1.2
(插值多项式的存在唯一性)
设 为域, 互不相同,并设 。则恰有一个次数至多为 的多项式 (包括零多项式)使 对每个 成立,即
证明
(用拉格朗日基证存在性,用因式定理证唯一性)
存在性:该和的次数至多为 ,且因为 ,有 。唯一性:若 是另一个这样的多项式,则 在全部 个互不相同的节点处取零。反复应用因式定理得 。能被该乘积整除的非零多项式次数至少为 ,而 的次数至多为 。因此 。这一论证涵盖了零多项式的情形,而无需为它指定次数。
证明透视
唯一性论证用到什么
不平凡的一步,是由 个各自的根推出单一的整除关系 。写 。在 处得 ,而 ,所以能推出 ,是因为域没有零因子;对其余每个节点重复同一消去,这用到各节点互不相同。然后以次数计算收尾:次数为 的多项式的非零倍式,次数不可能低于 。若没有次数上界,结论只是 ,其中 ,唯一性便不成立。
例题 9.1.3
( 上的插值)
在 上,给定 ,,。令 ,,。前两个基多项式为
其中在 中 。因此 。直接代入得到模 5 下的 。第三个基多项式的系数为零,因此在这个和中不需要它。唯一性不依赖于 ;它由上面的因式定理论证得出。
例题 9.1.4
(常数数据(边界情形))
取任何至少有三个元素的域 、三个互不相同的节点,以及数据 。定理保证有次数至多为 的多项式,但常数多项式 已有这些值,且次数为 。由唯一性,,因此 。界 只是上界,并非实际次数。
反例模式
插值需要域
断言:在任何交换环上,在互不相同的节点处插值都是唯一的。在 中取节点 与 ,两者不同。多项式 非零,次数为 ,但 ,。所以数据 既被 吻合,也被 吻合。证明恰好在用到域的地方失效:分母 在 中不可逆,所以 并不存在;而 是零因子关系,透视中的消去步骤无法排除它。
快速检查
(在 上,求次数至多为 且 、 的多项式。)
使用 。
解答 · 答案
,而第二项的系数为 ,所以在 中 。验算:,。
快速检查
(域上一个次数至多为 的多项式在四个互不相同的点处取零。它是什么?)
把根的个数与次数比较。
解答 · 答案
它是零多项式:四个互不相同的根给出次数为 的因式 ,而次数至多为 的非零多项式不可能有这个因式。
其他所有解的形式
命题 9.1.5
(全部插值多项式)
令 ,并设 为次数至多为 的插值多项式。多项式 对所有 满足 ,当且仅当
证明
(每个解与 相差 的倍式)
每个多项式 在选定节点处都与 取相同的值。反之,若 取这些值,则每个 都是 的根,所以由同一个因式定理论证得 。
例题 9.1.6
(一个三次的解)
在 上,取第一个例子的数据,,。取 得 。于是模 5 有 、、,所以 虽然是三次,却与 有相同的值,与命题一致。
用商环的语言来说,求值诱导出一个环同态
其中 中的运算按坐标进行。由于 的倍式在每个节点处都取零,该映射是良定义的。由因式定理论证知它是单射,由插值知它是满射,因此它是同构。特别地,当 时该商环有零因子:例如 ,但这两个类都不为零。商环不必是域也可以很有用。
有限域与一个必要的区分
在 上,在全部 个域元素处进行插值,可以把每个函数 表示为唯一一个次数小于 的多项式。但形式多项式 与 是不同的,却在 上定义了同一个函数:对非零的 ,在乘法群中应用拉格朗日(Lagrange)定理得 ,并且 。因此,在有限域上取值相等本身并不意味着作为形式多项式相等。正是次数上界保证了代表元的唯一性。
常见错误
(作为函数相等,不等于作为多项式相等)
在 上,多项式 与 在 处取相同的值(即 ),但在 中 。只有当两个多项式的次数都低于域的元素个数(这里即低于 )时,才可由它们在每个域元素处取值相同推出两者相等。
快速检查
( 上次数至多为 的多项式共有多少个?定理如何解释这个数目?)
先数系数的选法,再数三个节点处的值组。
解答 · 答案
共有 个(三个系数,每个有五种选择)。在三个固定节点处插值,给出这些多项式与 组值 之间的双射,两者的个数相同。