多项式插值与 Runge 现象 · 高次不是越准 · 数值计算的艺术

给一堆点，穿过它们的多项式唯一存在。但一个惊人的反直觉：在等距点上用高次多项式插值，边缘会剧烈震荡，点越多越糟——这就是 Runge 现象。这一章用代码复现它，并给出两条解药。

多项式插值与 Runge 现象 · 高次不是越准

进入第四站：逼近。问题很日常——手上有一堆离散的点 $(x_i, y_i)$ （实验测量、采样数据），怎么「连成」一条能求任意点值的曲线？这一章讲最经典的多项式插值，以及它一个会颠覆直觉的著名陷阱。

插值：穿过每一个点

插值（interpolation） 要求曲线精确穿过每一个给定点。多项式插值有个漂亮的定理： $n$ 个点，存在唯一的一条 $n-1$ 次多项式穿过它们全部。 2 个点定一条直线，3 个点定一条抛物线，以此类推。

import numpy as np

xs = np.array([0., 1., 2., 3.])
ys = np.array([1., 2., 0., 5.])
p = np.polyfit(xs, ys, len(xs) - 1)     # 3 次多项式,穿过 4 个点
print(np.polyval(p, xs))                # [1. 2. 0. 5.] —— 精确还原
print(np.polyval(p, 1.5))               # 插值求 x=1.5 处的值

看起来很美：点越多、多项式次数越高，应该拟合得越准吧？——恰恰相反。

Runge 现象：点越多，边缘越崩

拿一个看着人畜无害的函数 $f(x)=\dfrac{1}{1+25x^2}$ ，在 $[-1,1]$ 上取等距点做高次插值，看误差随点数怎么变：

f = lambda x: 1 / (1 + 25 * x**2)
xx = np.linspace(-1, 1, 400)            # 密网格,用来量误差

for n in [5, 11, 21]:
    xs = np.linspace(-1, 1, n)          # n 个等距节点
    p = np.polyfit(xs, f(xs), n - 1)    # n-1 次插值多项式
    err = np.max(np.abs(np.polyval(p, xx) - f(xx)))
    print(f"n={n:2d} 个点: 最大误差 = {err:.2f}")

n= 5 个点: 最大误差 = 0.44
n=11 个点: 最大误差 = 1.92     ← 变大了!
n=21 个点: 最大误差 = 59.82    ← 爆炸!

点越多，误差越大，而且大得离谱。 21 个点时，插值多项式在区间边缘剧烈震荡，误差高达 60（而函数本身值域只在 $[0,1]$ ）。这就是 Runge 现象：等距点上的高次多项式插值，会在两端疯狂摆动，且越高次越糟。

Runge 现象的教训：「用更高次多项式穿过更多点」是个陷阱。 高次多项式为了精确穿过每一个等距点，不得不在点与点之间（尤其边缘）大幅扭动。这不是舍入误差、也不是病态——是等距高次插值这件事本身的数学性质。所以现实中，几乎没人用高于三四次的多项式做插值。「拟合不好就加高次数」的直觉，在这里是错的。

解药一：换节点（Chebyshev）

Runge 现象怪的是等距节点。如果把节点在两端加密（中间稀、边缘密），震荡就被压住了——这种特殊分布叫 Chebyshev 节点：

for n in [11, 21]:
    k = np.arange(n)
    xs = np.cos((2*k + 1) * np.pi / (2*n))   # Chebyshev 节点:两端密集
    p = np.polyfit(xs, f(xs), n - 1)
    err = np.max(np.abs(np.polyval(p, xx) - f(xx)))
    print(f"n={n} Chebyshev 节点: 最大误差 = {err:.4f}")
# n=11: 0.10   n=21: 0.017   ← 现在点越多越准了!

同样是高次多项式，只是换了节点分布，误差就从爆炸变成了随点数稳步下降。问题不在多项式，在你怎么选点——这是数值逼近里一个深刻又实用的洞见。

[1] Trefethen.《Approximation Theory and Approximation Practice》—— Runge 现象与 Chebyshev 节点权威。
[2] Burden & Faires.《Numerical Analysis》, §3.1-3.2 —— 多项式插值。
[3] NumPy 文档.「numpy.polyfit / polyval.」https://numpy.org/doc/stable/ —— 多项式拟合与求值。

多项式插值与 Runge 现象 · 高次不是越准