Skip to content

Interpolation and Polynomial Approximation

本页面还在施工中

Interpolation and the Lagrange Polynomial

插值是一种函数近似方法。如果能够知道待近似函数 \(f(x)\) 在 \(x_0, x_1, \cdots, x_n\) 共 \((n+1)\) 个点的准确值，那么就可以构造一个通过所有给定插值点的插值函数 (interpolating function) \(g(x)\) 对 \(f(x)\) 进行插值。常用的插值函数 \(g(x)\) 为代数多项式 (algebraic polynomials)。

一种和带 Lagrange 余项的 Taylor 展开自然契合的插值方法被称为 Lagrange 插值。定义

\[ L_{n, i}(x)=\prod_{\substack{j\neq i\\ j=0}}^n \frac{x-x_j}{x_i-x_j} \]

代表 \(n\) 阶 Lagrange 插值多项式 \(L_n(x)\) 与 \(y_i\) 相乘的乘数，对应在 \(L_n(x)\) 的第 \(i\) 项。具体而言，有

\[ L_n(x) = \sum_{i=0}^n L_{n, i}(x)y_i \]

\(n\) 阶 Lagrange 插值多项式可以精确刻画 \(n\) 阶及以下的多项式。以一阶多项式（线性函数）为例展示：

一阶 Lagrange 插值多项式

线性函数可以表示为

\[ \begin{aligned} f(x) &= \frac{y_0 - y_1}{x_0 - x_1}(x-x_0)+y_0\\ &=\frac{x-x_1}{x_0-x_1}y_0+\frac{x-x_0}{x_1-x_0}y_1\\ &=L_{1, 0}y_0 + L_{1, 1}y_1 \end{aligned} \]

给定 \(n+1\) 个插值点，并限定使用不大于 \(n\) 阶的插值多项式进行插值，那么 Lagrange 插值多项式就是唯一的插值多项式。

留做习题证明略

但是如果插值多项式的阶数可以大于 \(n\)，就可以取更高阶的插值多项式，例如

\[ P(x) = L_n(x) + p(x) \prod_{i=0}^n (x-x_i) \]

其中 \(p(x)\) 可以是任意多项式。

Remainder Analysis

在给定插值点 \(a<x_0<\cdots<x_n<b\) 并且 \(f\in C^{n+1}[a, b]\) 的条件下，对 Lagrange 插值多项式 \(L_n(x)\) 近似 \(f\) 的余项 \(R_n(x)\) 进行分析：

\[ R_n(x) = f(x) - L_n(x) \]

可以分析 \(\exists \xi_x\in (a, b)\) 使得

\[ R_n(x) = \frac{f^{(n+1)}(\xi_x)}{(n+1)!}\prod_{i=0}^n (x-x_i) \]
Proof

每个插值点上都有 \(f(x_i)=L_n(x_i)\)，因此可知每个插值点都是 \(R(x)\) 的根。于是令

\[ R_n(x) = K(x)\prod_{i=0}^n (x-x_i) \]

定义函数 \(g(t)\)

\[ g(t)=R_n(t) - K(x)\prod_{i=0}^n (t-x_i) \]

注意这里的 \(x\) 是个参数而不是变量了。可知除了 \(x_0, \cdots, x_n\) 之外，\(x\) 也是 \(g(t)\) 的根。现在我们要求 \(x\) 是不同于任何插值点的一个定值，根据广义的 Rolle 中值定理，可知 \(\exists\: \xi_x\in (a, b)\)，使得

\[ g^{(n+1)}(\xi_x)=0 \]
广义 Rolle 中值定理的说明
  • 广义 Rolle 中值定理是本书中的一个说法
  • 原来的 Rolle 中值定理，是指在闭区间连续、开区间可导的情况下，区间端点函数值相等，这样就有开区间内的一个点的导数值为零
  • 所谓广义 Rolle 中值定理，指的就是有 \(k+1\) 个点函数值相同，然后连着用 \(k\) 层的 Rolle 中值定理

设在 \(x_0 < \cdots < x_{k-1}\) 的函数值都相同，这样用一层 Rolle 中值定理就有

\[ \begin{gathered} f'(x_{01})=f'(x_{12})=\cdots=f'(x_{k-2, k-1})=0\\ x_{01}\in (x_0, x_1), \quad x_{12}\in (x_1, x_2), \quad \cdots,\quad x_{k-2, k-1}\in (x_{k-2}, x_{k-1}) \end{gathered} \]

再用一层 Rolle 中值定理，有

\[ \begin{gathered} f^{(2)}(x_{02})=f^{(2)}(x_{13})=\cdots=f^{(2)}(x_{k-3, k-1})=0\\ x_{02}\in (x_{01}, x_{12})\subset (x_0, x_2)\\ x_{12}\in (x_{12}, x_{23})\subset (x_1, x_3)\\ \cdots\\ x_{k-2, k-1}\in (x_{k-2, k-3}, x_{k-2, k-1})\subset (x_{k-3}, x_{k-1}) \end{gathered} \]

以此类推，总共使用 \(n\) 层的 Rolle 中值定理，就可以得到

\[ f^{(n)}(x_{0, k-1})=0, \quad x_{0, k-1}\in (x_0, x_{k-1}) \]
\[ \begin{aligned} g^{(n+1)}(t) &= R_n^{(n+1)}(t) - K(x)\left[\prod_{i=0}^n (t-x_i)\right]^{(n+1)} \\ &= R_n^{(n+1)}(t) - K(x)(n+1)! & \text{(仅有最高次项还有系数)}\\ &= f^{(n+1)}(t) - L_n^{(n+1)}(t) - K(x)(n+1)!\\ &= f^{(n+1)}(t) - K(x)(n+1)! & \text{(n 阶多项式求 n+1 次导)} \end{aligned} \]

也就有

\[ g^{(n+1)}(\xi_x)=0\Rightarrow K(x)=\frac{f^{(n+1)}(\xi_x)}{(n+1)!} \]

消去 \(R_n(x) = K(x)\prod_{i=0}^n (x-x_i)\) 中的 \(K(x)\) 就可以得到。

Remark

  • 估计 \(\xi_x\) 是困难的，常估计 \(|f^{(n+1)}|\) 的上界以估计截断误差的上界
  • 从余项的表达式中，可以解释为什么 \(n\) 阶 Lagrange 插值多项式对于不超过 \(n\) 阶的多项式都是精确的刻画——因为 \(f^{(n+1)}\equiv 0\)

Data Approximation and Neville's Method

Divided Differences

尽管给定 \(n+1\) 个插值点得到的 \(n\) 阶插值多项式是唯一的，除了 Lagrange 插值多项式的形式，也可以用 Newton 差商公式的形式对其进行表达。这就需要首先引入差商 (divided difference) 的概念。

Hermite Interpolation

Hermite 多项式是一种密切多项式 (osculating polynomial)，即 Hermite 多项式在给定点的导数值与给定导数值相同。Hermite 插值多项式是 Hermite 多项式的插值形式。

Hermite Polynomial

如果 \(f\in C^1[a, b]\)，给出插值点 \(x_0, \cdots, x_n\in [a, b]\)，在这些点上满足 \(P=f\) 和 \(P'=f'\) 次数最小的多项式 \(P\) 就是 Hermite 多项式，其次数最多是 \(2n+1\)，有

\[ H_{2n+1}(x)=\sum_{j=0}^n f(x_i)H_{n, j}(x)+\sum_{j=0}^n f'(x_i)\hat{H}_{n, j}(x) \]

借用 Lagrange 插值中的符号 \(L_{n, j}(x)\)，则有

\[ \begin{aligned} H_{n, j}(x) &= \left[1-2(x-x_j)L'_{n, j}(x_j)\right] L^2_{n, j}(x)\\ \hat{H}_{n, j}(x) &= (x-x_j)L^2_{n, j}(x) \end{aligned} \]

对于其误差估计，\(\exists \:\xi(x)\in (a, b)\)，如果 \(f\in C^{2n+2}[a, b]\)，那么有

\[ f(x) = H_{2n+1}(x) + \frac{(x-x_0)^2\cdots (x-x_n)^2}{(2n+2)!}f^{(2n+2)}(\xi(x)) \]

Cubic Spline Interpolation

Comments