函数插值与多项式逼近
在科学计算和工程应用中，我们经常遇到一个问题：一个函数 $f(x)$ 可能形式复杂、计算成本高，或者我们只知道它在一系列离散点上的函数值。为了方便地分析和计算，我们希望找到一个更简单的函数 $P(x)$ 来近似替代 $f(x)$。
什么是好的逼近？
一个好的逼近函数 $P(x)$ 通常应满足以下条件：
- 易于计算：$P(x)$ 的形式应足够简单，例如多项式或分段多项式，使其值的计算、微分和积分都易于实现。
- 精确度高：在关心的区间内，$P(x)$ 与 $f(x)$ 的误差要尽可能小。
- 插值性：在给定的数据点 $(x_i, y_i)$ 上，我们通常要求 $P(x_i) = y_i$。这就是“插值”的核心要求。
在众多逼近函数中，多项式由于其良好的性质（易于计算、微分和积分，且根据魏尔斯特拉斯逼近定理，任何连续函数都可以用多项式一致逼近），成为最常用的插值函数。
插值多项式的存在性与唯一性
定理：给定 $n+1$ 个互不相同的节点 $(x_0, y_0), (x_1, y_1), \ldots, (x_n, y_n)$，其中 $y_i = f(x_i)$，存在唯一一个次数不超过 $n$ 的多项式 $P_n(x)$，满足插值条件：
$$P_n(x_i) = y_i, \quad \text{for } i = 0, 1, \ldots, n $$
证明思路：
- 存在性：我们可以通过构造性的方法（例如后面的拉格朗日插值法）直接给出一个满足条件的多项式，从而证明其存在。
- 唯一性 (反证法)：
- 假设存在两个不同的、次数不超过 $n$ 的多项式 $P_n(x)$ 和 $Q_n(x)$ 都满足插值条件。
- 构造一个新的多项式 $D(x) = P_n(x) - Q_n(x)$。
- 由于 $P_n(x_i) = y_i$ 和 $Q_n(x_i) = y_i$，我们有 $D(x_i) = y_i - y_i = 0$ 对所有 $i=0, \ldots, n$ 成立。
- 这意味着 $D(x)$ 至少有 $n+1$ 个不同的根 $(x_0, x_1, \ldots, x_n)$。
- 根据代数基本定理，一个非零多项式的根的个数不能超过其次数。由于 $P_n(x)$ 和 $Q_n(x)$ 的次数都不超过 $n$，所以 $D(x)$ 的次数也不超过 $n$。
- 一个次数不超过 $n$ 的多项式却拥有 $n+1$ 个根，唯一的可能性是这个多项式为零多项式，即 $D(x) \equiv 0$。
- 因此，$P_n(x) = Q_n(x)$，这与我们最初的假设（两个多项式不同）相矛盾。所以，插值多项式是唯一的。
基函数与插值方法
构造插值多项式的核心思想是选择一组合适的基函数 (Basis Functions)。对于次数为 $n$ 的多项式空间，我们可以选择不同的基底来表示 $P_n(x)$。
方法一：范德蒙插值 (Vandermonde Interpolation)
这是最直接的思路。我们选择最自然的基底：$\{1, x, x^2, \ldots, x^n\}$。
设插值多项式为：
$$P_n(x) = a_0 + a_1 x + a_2 x^2 + \cdots + a_n x^n $$
将 $n+1$ 个插值条件 $P_n(x_i) = y_i$ 代入，得到一个关于系数 $a_j$ 的线性方程组：
$$\begin{cases} a_0 + a_1 x_0 + a_2 x_0^2 + \cdots + a_n x_0^n = y_0 \\ a_0 + a_1 x_1 + a_2 x_1^2 + \cdots + a_n x_1^n = y_1 \\ \vdots \\ a_0 + a_1 x_n + a_2 x_n^2 + \cdots + a_n x_n^n = y_n \end{cases} $$
写成矩阵形式为 $V a = y$：
$$\begin{pmatrix} 1 & x_0 & x_0^2 & \cdots & x_0^n \\ 1 & x_1 & x_1^2 & \cdots & x_1^n \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & x_n & x_n^2 & \cdots & x_n^n \end{pmatrix} \begin{pmatrix} a_0 \\ a_1 \\ \vdots \\ a_n \end{pmatrix} = \begin{pmatrix} y_0 \\ y_1 \\ \vdots \\ y_n \end{pmatrix} $$
这个系数矩阵被称为范德蒙矩阵。由于所有节点 $x_i$ 互不相同，范德蒙矩阵是可逆的，因此系数向量 $a$ 存在且唯一。
- 缺点：当 $n$ 较大时，范德蒙矩阵的条件数会非常大，导致数值求解非常不稳定。因此，这种方法在实际中很少使用。
方法二：拉格朗日插值 (Lagrange Interpolation)
拉格朗日插值的思想是选择一组更巧妙的基函数，使得系数的求解变得异常简单。
它构造了 $n+1$ 个拉格朗日基多项式 $l_j(x)$，每个基多项式 $l_j(x)$ 的次数为 $n$，且具有以下优美的性质：
$$l_j(x_i) = \delta_{ij} = \begin{cases} 1, & \text{if } i = j \\ 0, & \text{if } i \neq j \end{cases} $$
为了实现这个性质，$l_j(x)$ 必须在除 $x_j$ 外的所有节点 $x_i$ 处取零，因此它可以写成：
$$l_j(x) = C \cdot (x-x_0)(x-x_1)\cdots(x-x_{j-1})(x-x_{j+1})\cdots(x-x_n) $$
再利用 $l_j(x_j) = 1$ 来确定常数 $C$，得到：
$$l_j(x) = \prod_{i=0, i \neq j}^{n} \frac{x - x_i}{x_j - x_i} $$
有了这组基函数，插值多项式就可以直接写出：
$$P_n(x) = \sum_{j=0}^{n} y_j l_j(x) $$
验证一下，当 $x=x_i$ 时，$P_n(x_i) = \sum_{j=0}^{n} y_j l_j(x_i) = y_i l_i(x_i) = y_i$，完全满足插值条件。
- 优点：公式结构清晰，理论分析方便。
- 缺点：每当增加或删除一个插值节点时，所有的基函数都需要重新计算，计算量较大。
方法三：牛顿插值 (Newton Interpolation)
牛顿插值法克服了拉格朗日插值的缺点，使得在增加节点时可以方便地进行递推。
它使用的基函数是：
$$\{1, (x-x_0), (x-x_0)(x-x_1), \ldots, \prod_{i=0}^{n-1}(x-x_i)\} $$
插值多项式形式为：
$$P_n(x) = c_0 + c_1(x-x_0) + c_2(x-x_0)(x-x_1) + \cdots + c_n \prod_{i=0}^{n-1}(x-x_i) $$
系数 $c_k$ 可以通过一种称为差商 (Divided Differences) 的递推方法来确定。
差商的定义：
- 零阶差商：$f[x_i] = f(x_i) = y_i$
- 一阶差商：$f[x_i, x_j] = \frac{f[x_j] - f[x_i]}{x_j - x_i}$
- k阶差商：$f[x_i, x_{i+1}, \ldots, x_{i+k}] = \frac{f[x_{i+1}, \ldots, x_{i+k}] - f[x_i, \ldots, x_{i+k-1}]}{x_{i+k} - x_i}$
牛顿插值多项式的系数 $c_k$ 就是差商的对角线元素：
$$c_k = f[x_0, x_1, \ldots, x_k] $$
因此，牛顿插值多项式为：
$$P_n(x) = f[x_0] + f[x_0, x_1](x-x_0) + \cdots + f[x_0, \ldots, x_n]\prod_{i=0}^{n-1}(x-x_i) $$
- 优点：增加新节点时，只需在原有基础上增加一项，之前的计算结果可以复用，非常适合动态增加数据点的场景。
插值误差与收敛性
插值误差估计
设 $P_n(x)$ 是函数 $f(x)$ 在节点 $x_0, \ldots, x_n$ 上的插值多项式。如果 $f(x)$ 在包含这些节点的区间内有 $n+1$ 阶连续导数，那么对于任意 $x$，其插值误差 $R_n(x) = f(x) - P_n(x)$ 可以表示为：
$$R_n(x) = \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{i=0}^{n} (x - x_i) $$
其中 $\xi$ 是一个依赖于 $x$ 且位于插值节点所构成的最小区间内的某个点。
这个公式告诉我们，误差取决于三个因素：
- 函数的高阶导数：如果函数的高阶导数增长很快，误差可能会很大。
- 插值区间的长度：$(x-x_i)$ 项表明，离插值节点越远，误差可能越大。
- 插值多项式的次数 $n$。
插值收敛性与龙格现象 (Runge’s Phenomenon)
一个自然的问题是：是不是只要不断增加插值节点的数量（即提高多项式次数 $n$），插值多项式就会越来越逼近原函数？
答案是：不一定。
对于某些函数，即使它们是无限光滑的，当在等距节点上使用高次多项式插值时，在区间的边缘部分可能会出现剧烈的振荡，导致误差不仅不减小，反而急剧增大。这种现象被称为龙格现象。
一个经典的例子是在区间 $[-1, 1]$ 上对函数 $f(x) = \frac{1}{1+25x^2}$ 进行等距节点插值。
结论：高次多项式插值（特别是使用等距节点时）是数值不稳定的。在实际应用中，为了避免龙格现象，通常采用以下策略：
- 分段低次插值：将整个区间分成若干小段，在每个小段上使用低次多项式（如线性或三次样条插值）。这是最常用和最稳健的方法。
- 非均匀节点：使用特殊的节点分布，如切比雪夫节点，可以有效地减小和避免龙格现象。