在本篇笔记中，我们研究如何将一些散点采用多项式拟合，以及如何采用多项式近似地刻画一些复杂的或未知的函数。

# 插值和多项式逼近

若存在一个点集 (统计数据的集合) $\{(x_0,y_0),(x_1,y_1),\dots,(x_n,y_n)\}$, 其中 $\forall i,j,\;x_i\neq x_j$. 我们希望采用一个多项式函数拟合统计数据，或者说拟合某个连续函数。对于此，我们有几个问题需要依次讨论：

1. 是否存在足够接近的多项式函数；
2. 如何给出多项式函数的表达式；
3. 多项式拟合函数的拟合误差是多少；
4. 如何快速计算多项式拟合函数。

# Weierstrass 逼近定理

对 $f(x) \in C[a,b]$ 及 $\forall \varepsilon > 0$, $\exists P(x) \in \mathbb{R}[x]$ 使得 $|f(x) - P(x)| < \varepsilon$, $\forall x\in [a,b]$. 该定理称为魏尔斯特拉斯逼近定理 (Weierstrass Approximation Theorem). 该定理说明，对任何一个连续函数 $f(x)$, 都存在一系列多项式函数 $\{P_i(x)\}$ 一致逼近 $f(x)$.

# Lagrange 插值公式

# 公式

一般的 Lagrange 插值公式为：

$$P(x) = \sum_{k=0}^nf(x_k)L_{n,k}(x)$$

其中

$$L_{n,k}(x) := \prod_{\substack{i=0 \\ i\neq k}}^n\frac{x-x_i}{x_k-x_i}$$

称为基函数 (basis function). 若不发生混淆，可以将 $L_{n,k}$ 简记为 $L_k$.

# 误差估计

Lagrange 插值多项式的余项为

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

# Neville 方法

Neville 方法是用来简化拉格朗日插值项计算的，其采用了递归的方法。首先，我们引入记号：

1. $P_{x_{i_1},x_{i_2},\dots,x_{i_k}}$ 表示采用点 $x_{i_1},x_{i_2},\dots,x_{i_k}$ 进行插值。
2. $Q_{i,j}$ 表示在 $j+1$ 个节点 $x_{i-j},x_{i-j+1},\dots,x_{i-1},x_i$ 上进行插值的多项式。

于是根据插值多项式的性质，可以得到

$$Q_{k,0} = P_k = f(x_k)$$

作为插值迭代的初值，

$$Q_{i,j} = \frac{(x-x_{i-j})Q_{i,j-1} - (x-x_i)Q_{i-1,j-1}}{x_i - x_{i-1}}, \quad j < i$$

作为插值迭代的递推式。

这样，就可以利用迭代得到 $Q_{n,n} = P(x)$ 即最终的插值多项式。该方法就被称为 Neville 方法。

# 差商

差商 (divided difference) 是一种简单的递归式函数记法。规则如下：

$$\begin{aligned} & f[x_i] = f(x_i) \\ & f[x_i,x_{i+1}] = \frac{f[x_{i+1}] - f[x_i]}{x_{i+1}-x_i} \\ & f[x_i,x_{i+1}, x_{i+2}] = \frac{f[x_{i+1},x_{i+2}] - f[x_i, x_{i+1}]}{x_{i+2}-x_i} \\ & \cdots \\ & f[x_i,x_{i+1},\dots,x_{i+k}] = \frac{f[x_{i+1},x_{i+2},\dots,x_{i+k}] - f[x_i,x_{i+1},\dots,x_{i+k-1}]}{x_{i+k}-x_i} \end{aligned}$$

差商的大小是可以估计的，有

$$f[x_0,x_1,\dots,x_n] = \frac{f^{(n)}(\xi)}{n!},\;\xi \in (x_0,x_n)$$

# Hermite 插值

# 密切多项式

令 $x_0,x_1,\dots,x_n$ 是区间 $[a,b]$ 内 $n+1$ 个不同的点，对 $m_i \in \mathbb{N}$, $i = 0,1,\dots,n$, 记 $m = \max\{m_i\}_{i=0}^n$, 并假设 $f \in C^m[a,b]$, 则 $f$ 的密切多项式 (osculating polynomial) $P$ 是满足

$$P^{(j)}(x_i) = f^{(j)}(x_i),\quad \forall i = 0,1,\dots,n,\ j=0,1,\dots,m_i$$

的次数最低的多项式。

可以看出，密切多项式是一个相当泛化的概念，其对每一个插值点都要求了不同的导数相等阶数 $m_i$. 这样的定义一般不具有特别显著的意义。如果我们要求诸 $m_i$ 存在一定的关系，那么将更易研究。

# Hermite 多项式

$\forall i = 0,1,\dots,n$, $m_i = 1$ 的密切多项式就是埃尔米特多项式 (Hermite polynomial). 其次数最高为 $2n+1$, 采用下式给出：

$$H_{2n+1}(x) = \sum_{j=0}^nf(x_j)H_{n,j}(x) + \sum_{j=0}^nf'(x_j)\hat{H}_{n,j}(x)$$

其中

$$\begin{aligned} & H_{n,j}(x) = (1-2(x-x_j)L_{n,j}'(x_j))L_{n,j}^2(x)\\ & \hat{H}_{n,j}(x) = (x-x_j)L_{n,j}^2(x) \end{aligned}$$

估计误差

$$f(x)-H_{2n+1}(x) = \frac{\prod_{i=0}^n(x-x_i)^2}{(2n+2)!}f^{2n+2}(\xi),\;\xi \in (a,b)$$

# 差商形式

$$H_{2n+1}(x) = \sum_{k=0}^{2k+1}f[z_0,\dots,z_k]\prod_{i=0}^k(x-x_i)$$

# 龙格震荡与样条插值

前述的插值都是基于单一函数的插值。我们希望一个函数满足 $2n$ 个条件，那么其次数将达到 $2n-1$. 这样高次的函数带来的插值不能反映数据点原本的特征。这种现象在机器学习上称为过拟合 (over-fitting), 在数值分析中则称为龙格现象 (Runge phenomenon).

这两种现象的问题背景有所不同。在数值分析中，我们的基本要求仍然是满足上述的条件，不能使插值函数原理插值点。

因此，我们尝试采用分段函数进行插值。这样就可以降低插值函数的次数了。这种方式称为样条插值 (piecewise polynomial interpolation).