简单地讲,并不是所有函数都长得很像多项式。
总存在一些不像多项式的,如果你强行按照等距节点的方式取插值多项式,就可能出现这问题。
首先,不是舍入误差,而是系统误差(应该是这个名字?总之就是多项式插值本身的性质)
详细算一下这个误差。
一般的插值余项公式为
这里 为插值区间 中的插值节点, 为 区间中一点。
Runge现象说的是,对 在区间 上进行n次多项式插值,当 时, 。更确切的说,当 时, ,当 时, , 。
解释这一现象,直接计算
很困难,因为微分项 不太容易直接求导计算。为方便起见,令 .
复变函数中的Cauchy积分公式 可以很方便的计算 的值,故将插值余项公式延拓到复平面上,并应用Cauchy积分公式,得
其中 是区域的边界,区域应满足在中解析且所有插值节点都在中。(注意, 的奇点为 故区域不能包含 )
化简,得到
所以现在的关键就是通过分析函数 在 时的性态,选择一个围道 ,来估计积分的值。
的图象大概是这样的(来自【2】)
这是当 时,三个节点分别取0,1,2i 时的图象。随着r的增大,图象逐渐外扩。当r足够大时, 的图象很接近一个包含所有节点的圆。因此我们可以选取 作为积分的围道
有一个很好的结论:此时对 内部任意的 , ( 且 )而对于 外部任意的 , ( 且 )
于是,当 不包含 的奇点 时,可以直接选取 做围道计算 ,此时
随着 变大,曲线 与 轴正方向交点向右移动。当恰好经过 时,曲线 与 轴正方向交点为 .也就是说,当 时,可以选取 使 在 内部而 在外部,这时误差估计满足上式,插值多项式收敛。
而当 时,奇点 在 的内部,因此需在奇点附近挖“洞”,记“洞”的边缘为,此时有
此时插值多项式发散。
为什么将等距节点换成Chebyshev节点时就不会出现发散的情况呢?因为Chebyshev节点对应的 在经过奇点 时是一个以 为焦点的椭圆,因此对于任意 ,都可找到一个r,使得 包含 而不包含 ,和上面同理,插值多项式收敛。
参考材料
【1】James F. Epperson , "On the Runge Example " , Amer. Math. Monthly, 94(1987), 329-341
这篇文章以本科知识的角度解释了Runge现象,并附加了几个例子。
【2】Phillip J. Davis, Interpolation and Approximation, Dover, New York, 1975
这本书的第三章、第四章详细的讨论了高次多项式插值的余项和收敛性。