← 全部笔记

高等代数

多项式插值与重心形式

文章目录

来源 谢启鸿、姚慕生, 高等代数学习指导书, 第4版, 第5章, 印刷页 246–247, 281, 285. PDF页码 = 印刷页码 + 10。 来源PDF 根据已目视核对的扫描件整理;简洁证明及明确标出的推广为整理者补充。 本篇的补充性质由旧专题笔记迁入;未另赋教材题号或页码。

互异节点的存在唯一性

在域 F\mathbb F 上给定互异节点 x0,…,xnx_0,\ldots,x_n 和值 yjy_j。

插值定理 存在唯一的次数不超过 nn 的多项式,满足 L(xj)=yjL(x_j)=y_j。

证明。 令 ℓj(x)=∏i≠j(x−xi)/(xj−xi)\ell_j(x)=\prod_{i\ne j}(x-x_i)/(x_j-x_i),则 ℓj(xi)=δij\ell_j(x_i)=\delta_{ij},故 L=∑jyjℓjL=\sum_j y_j\ell_j 给出存在性。两个解之差次数不超过 nn,却有 n+1n+1 个互异零点,只能为零。

同样的唯一性给出 ∑jℓj=1\sum_j\ell_j=1。按系数解方程的观点见 Vandermonde行列式与插值;一般互素模数的推广见 多项式的中国剩余定理。

插值余项

取实节点,ff 在包含节点与评价点 xx 的闭区间上具有 n+1n+1 阶连续导数。若 xx 不是节点,令 ω(t)=∏j=0n(t−xj)\omega(t)=\prod_{j=0}^n(t-x_j)。则存在节点与 xx 的最小包含区间内部的 ξ\xi,使 f(x)−L(x)=f(n+1)(ξ)(n+1)!ω(x).f(x)-L(x)=\frac{f^{(n+1)}(\xi)}{(n+1)!}\omega(x). 证明。 用 c=(f(x)−L(x))/ω(x)c=(f(x)-L(x))/\omega(x) 构造 f(t)−L(t)−cω(t)f(t)-L(t)-c\omega(t)。它在 n+2n+2 个互异点为零,重复使用Rolle定理,其 n+1n+1 阶导数在某点为零。节点处余项直接为零。

若该区间上 ∣f(n+1)∣≤M|f^{(n+1)}|\le M,则误差不超过 M∣ω(x)∣/(n+1)!M|\omega(x)|/(n+1)!。

重心形式

预先计算 wj=(∏i≠j(xj−xi))−1w_j=(\prod_{i\ne j}(x_j-x_i))^{-1}。非节点处, L(x)=ω(x)∑jwjyjx−xj=∑jwjyj/(x−xj)∑jwj/(x−xj).L(x)=\omega(x)\sum_j\frac{w_jy_j}{x-x_j} =\frac{\sum_j w_jy_j/(x-x_j)}{\sum_j w_j/(x-x_j)}. 第二个等式由 ∑jℓj=1\sum_j\ell_j=1 得到。节点处返回 yjy_j,不能直接代入分式。

预计算权重后,单点求值需线性数量的算术操作;直接计算所有权重则需二次数量的操作。不能把预处理与求值的成本混为一谈。代数等价的Lagrange与Newton形式给出同一个多项式,Newton形式用差商,增加节点时较便于更新;重心形式则保持对称节点表达。

节点选择与高次插值

高次等距插值对某些光滑函数会出现Runge现象,但不是所有函数的误差都趋于无穷,也不能只用节点多项式的一句话解释全部行为。节点分布、函数及实现共同影响误差;重心表示也不能消除插值问题本身的条件敏感性。

实际问题可比较Chebyshev型节点、分段低次插值和正交多项式逼近。代数公式本身不能保证任意浮点实现的稳定性,靠近节点时还应正确处理可去奇点。