插值方法介绍

1. 插值法定义

Tips

学习数值方法需要同学们有一定的数理基础（微积分，线性代数等），本教程需要用到大量的数学证明和分析，请不要对此感到诧异。

前文提到，数值方法广泛应用于人工智能和机器学习（在一些高校通常是人工智能专业的必修课）、控制系统、物理模拟以及计算机图形学等领域。这是因为它在处理现实问题和优化问题上反复展现出惊人的有效性，而这一过程离不开数学的参与。正因如此，数值方法堪称计算机科学中与数学关联性最强的分支之一。

回想一下你在初高中物理实验课上的经历：当你测量完一组数据（比如弹簧的伸长量与拉力、或者小车的位移与时间）并在坐标纸上点下一个个离散的坐标点时，老师一定会提醒你：“要画一条平滑的曲线。”

这种“连点成线”的直觉，其实就是数值方法中插值法（Interpolation）的本质。在现实世界中，我们通过实验或观测得到的数据往往是离散的一张“函数表”，但是许多实际问题都用函数 $y=f(x)$ 来表示某种内在规律的数量关系，其中相当一部分函数是通过实验或计算得到的，并且只是 $[a,b]$ 上一系列点 $x_i$ 的函数值。

为了研究函数的变化规律，我们的需求往往不在表上的函数值，比如说预测，观察变化趋势。因此，我们希望根据给定的函数表做一个既能反映函数 $f(x)$ 的特性，又便于计算的简单函数 $p(x)$ ，用 $p(x)$ 近似 $f(x)$ 。

设函数 $y=f(x)$ 在区间 $[a,b]$ 上有定义，且

a \le x_0 < x_1 < \dots < x_n \le b

已知在点 $x_0, x_1, \dots, x_n$ 上的值 $y_0, y_1, \dots, y_n$ 若存在一简单函数 $p(x)$ ，使下列成立

p(x_i) = y_i , \quad i = 0, 1, 2 \dots, n \qquad (2.1)

就称 $p(x)$ 为 $f(x)$ 的插值函数，点 $x_0, x_1 \dots, x_n$ 称为插值节点，包含插值节点的区间 $[a,b]$ 称为插值区间，

$(2.1)$ 称为插值条件，求插值函数 $p(x)$ 的方法称为插值法。

若 $p(x)$ 为次数不超过 $n$ 的代数多项式，即

p(x) = a_0 + a_1x + \dots + a_nx^n \qquad (2.2)

(注：在本章节我们只介绍拉格朗日插值法，牛顿插值法和埃尔米特插值法，它们都是多项式插值法。）

在这里，同学们可能会存在一些疑惑：

插值的曲线函数 $p(x)$ 可能会有很多种形状，真的有唯一的曲线 $p(x)$ 吗?

如果唯一的 $p(x)$ 存在，那么应该用什么方法去解出它？

如何衡量 $p(x)$ 和原函数之间的误差？

2. 多项式插值存在唯一性定理

对于给定的 $n+1$ 个互不相同的节点 $(x_0, y_0), (x_1, y_1), \dots, (x_n, y_n)$ ，其中 $x_i$ 互不相同。则存在唯一的次数不超过 $n$ 的多项式 $P_n(x)$ ，使得：

P_n(x_i) = y_i, \quad i = 0, 1, \dots, n

将在点 $x_0, x_1, \dots, x_n$ 上的值 $y_0, y_1, \dots, y_n$ ，逐点带入（2.2）提到的代数多项式。首先需要确定自己的目标，如果代数多项式是唯一的，那么以下的线性方程组需要有唯一解。

\begin{cases} a_0 + a_1x_0 + a_2x_0^2 + \dots + a_nx_0^n = y_0 \\ \quad \dots \quad \dots \\ a_0 + a_1x_n + a_2x_n^2 + \dots + a_nx_n^n = y_n \end{cases} \tag{2.3}

这是一个关于待定系数 $a_0, a_1, \dots, a_n$ 的 $n+1$ 元线性方程组。要证明插值多项式的存在唯一性，本质上只需要证明上述方程组存在唯一解。根据线性代数的知识，若要证明这个方程组有唯一解，则需要证明其系数矩阵构成的行列式的值不为零。

将其系数行列式列出：

V_n(x_0, x_1, \dots, x_n) = \begin{vmatrix} 1 & x_0 & x_0^2 & \dots & x_0^n \\ 1 & x_1 & x_1^2 & \dots & x_1^n \\ \dots & \dots & \dots & \dots & \dots \\ 1 & x_n & x_n^2 & \dots & x_n^n \end{vmatrix}

这个是经典的Vandermond行列式，这里我们不证，感兴趣的同学可以自己尝试。直接利用现成的结论：

V_n(x_0, x_1, \dots, x_n) = \prod_{i=1}^{n} \prod_{j=0}^{i-1} (x_i - x_j)

由于 $i \neq j$ 时 $x_i \neq x_j$ ，故所有因子 $x_i - x_j \neq 0$ ，这个结论是显然的，如果 $x_i = x_j$ ，就构不成函数了。

于是 $V_n(x_0, x_1, \dots, x_n) \neq 0$ ，即方程组有唯一解，插值的多项式函数 $p(x)$ 是唯一存在的。

需要强调的是，虽然插值的多项式函数是唯一存在的，但在计算机工程实践中，我们可以选择不同的构造策略来实现它。不同的方法代表了不同的计算复杂度、数值稳定性和扩展性，这也是下方我们将展开探讨的核心内容。

3. 插值余项定理

为了分析插值误差，先回顾泰勒展开。设函数 $f(x)$ 在包含 $x_0$ 的区间 $(a, b)$ 内具有 $n+1$ 阶导数，则对区间内任意一点 $x$ ，有：

f(x) = \sum_{k=0}^{n} \frac{f^{(k)}(x_0)}{k!}(x - x_0)^k + R_n(x)

其展开形式为：

f(x) = f(x_0) + f'(x_0)(x - x_0) + \frac{f''(x_0)}{2!}(x - x_0)^2 + \dots + \frac{f^{(n)}(x_0)}{n!}(x - x_0)^n + R_n(x)

其中，拉格朗日型余项为：

R_n(x) = \frac{f^{(n+1)}(\xi)}{(n+1)!}(x - x_0)^{n+1}

其中 $\xi$ 介于 $x$ 与 $x_0$ 之间。需要注意的是，泰勒公式是利用单点 $x_0$ 附近的信息来逼近函数，而插值法则是利用多个节点上的已知数据构造近似函数。因此，对应的误差项也应体现所有插值节点的影响。插值余项可写为：

R_n(x) = \frac{f^{(n+1)}(\xi)}{(n+1)!} \mathbf{\prod_{i=0}^{n} (x - x_i)}

① 函数本身的变化程度： $f^{(n+1)}(\xi)$

它表示原函数在某点处的 $(n+1)$ 阶导数，反映了函数变化的剧烈程度。

如果原函数足够平滑，例如低次多项式，高阶导数可能为 0，此时插值误差会显著减小，甚至为 0。如果原函数变化十分剧烈，则高阶导数可能较大，即使采用相同的插值方法，误差也会明显增大。

② 插值阶数对误差的影响： $\frac{1}{(n+1)!}$

随着 $n$ 的增加，分母 $(n+1)!$ 以阶乘速度增长。在其他条件不变时，增加节点数通常有助于减小误差。有的同学可能会觉得，只要插值阶数n取的越大那么得到的值就越准确，但真的是这样吗？

这里先卖个关子，后继的小节会有专门关于它的内容，但现在先请同学们自己思考一下。如果你想要更直观的现象，可以运行下列的Python代码，看一下结果吧！

我们需要用到 numpy 和scipy进行数值计算，以及 matplotlib 进行可视化。如果你先前没有安装这些库，可以运行下列的pip指令。

pip install numpy scipy matplotlib

example.py

import numpy as np
import matplotlib.pyplot as plt
from scipy.interpolate import lagrange

def runge_func(x):
    return 1 / (1 + 25 * x**2)

x_fine = np.linspace(-1, 1, 500)
y_true = runge_func(x_fine)

plt.figure(figsize=(10, 6))
plt.plot(x_fine, y_true, 'k--', label='True Function (Runge)', lw=2)

# 3. 尝试不同的插值阶数 n
degrees = [6, 10, 14]

for n in degrees:
    # 在 [-1, 1] 区间内进行等距采样
    x_nodes = np.linspace(-1, 1, n + 1)
    y_nodes = runge_func(x_nodes)

    # 使用拉格朗日插值构造多项式
    poly = lagrange(x_nodes, y_nodes)

    # 计算插值多项式在细分点上的值
    y_poly = poly(x_fine)

    plt.plot(x_fine, y_poly, label=f'n={n} (Lagrange)')


plt.ylim(-0.2, 1.2)
plt.title("Runge's Phenomenon: The Curse of High-Degree Polynomials", fontsize=14)
plt.xlabel("x")
plt.ylabel("y")
plt.legend()
plt.grid(True, linestyle=':', alpha=0.6)
plt.show()

③ 节点分布的几何影响： $\omega_{n+1}(x) = \prod (x - x_i)$

数学含义：它表示点 $x$ 与各个插值节点 $x_i$ 的距离乘积。
直观理解：它反映了节点分布对误差的影响。
- 当 $x$ 恰好取某个插值节点时，上式中有一项为 0，因此误差为 0。
- 当 $x$ 远离已知节点时，该乘积通常会增大，从而使误差变大。
- 一般而言，区间边缘处的乘积项往往比中间区域更大，因此插值多项式在区间两端的误差通常更明显。

然而，在实际问题中，我们通常无法像泰勒展开那样直接获得待插值函数的高阶导数，因此需要借助不同的插值构造方法来满足不同的计算需求。这也是后续各小节要讨论的核心问题。

插值方法介绍

1. 插值法定义

2. 多项式插值存在唯一性定理

3. 插值余项定理

① 函数本身的变化程度：f(n+1)(ξ)f^{(n+1)}(\xi)f(n+1)(ξ)

② 插值阶数对误差的影响：1(n+1)!\frac{1}{(n+1)!}(n+1)!1​

③ 节点分布的几何影响：ωn+1(x)=∏(x−xi)\omega_{n+1}(x) = \prod (x - x_i)ωn+1​(x)=∏(x−xi​)

On this page

① 函数本身的变化程度： $f^{(n+1)}(\xi)$

② 插值阶数对误差的影响： $\frac{1}{(n+1)!}$

③ 节点分布的几何影响： $\omega_{n+1}(x) = \prod (x - x_i)$