【高等数值分析】多项式插值

1. 预备理论

假设有离散的 \(\{x_0,x_1,...,x_n\}\) 插值节点，以及对应的函数值 \(\{f(x_0),....,f(x_n)\}\)，希望用函数 \(\phi(x)\) 来近似 \(f(x)\)，使其满足插值条件 \(\phi(x_i)=f(x_i),i=0,...,n\)。一般选择多项式插值函数 \(p(x)=a_0+a_1x+\cdots+a_n x^n \in {\mathcal P}_n\)。

根据插值条件 \(f(x_i)=\phi(x_i)\) 列出来 \(n+1\) 个等式，再由 Hilbert 阵的非奇异性质，可以证明插值函数 \(p(x)\) 存在且唯一。但同时也由于 Hilbert 的病态性，使得这种直接暴力求解的方式不好使。后面给出几种更好用的方法。

2. Lagrange插值

采用了类似“正交基”的想法，如果有 \(n+1\) 个插值节点，就先给出 \(n+1\) 个“正交基函数”，然后再用线性组合即可得到插值函数。

选择基底函数为 \[ l_i(x) = \prod_{k=0,k\ne i}^n \frac{x-x_k}{x_i-x_k} = \begin{cases} 1, & x=x_i \\ 0, & x=x_k,k\ne i \end{cases} \] 对应构造的插值函数为 \(L_n(x)=\sum_{i=0}^n f(x_i)l_i(x)\)，插值余项 \[ R_n(x)\triangleq f(x)-L_n(x) = \frac{f^{(n+1)}(\xi)}{(n+1)!}w_{n+1}(x) \] 其中 \(\xi(x)\in[a,b]\)，\(w_{n+1}(x)=\prod_{k=0}^n(x-x_k)\)。

插值余项的证明：\(\forall x\in[a,b]\)，将其看作新增插值节点，那么我们构造一个新的Lagrange插值函数 \[ l_{n+1}(t) = R_n(x)\frac{w_{n+1}(t)}{w_{n+1}(x)} =\begin{cases} R_n(x), & t=x \\ 0, & t=x_0,...,x_n \end{cases} \] 那么我们取 \(L_{n+1}(t) = L_n(t) + l_{n+1}(t)\)，可以验证其满足 \(L_{n+1}(x_i)=f(x_i), t\in \{x,x_0,...,x_n\}\)，也就是说他是新的插值函数，插值节点为 \(\{x,x_0,...,x_n\}\)。此时插值余项为 \(R_{n+1}(t)=f(t)-L_{n+1}(t)=R_n(t)-l_{n+1}(t)\)，其满足 \(R_{n+1}(t)=0,t\in \{x,x_0,...,x_n\}\)，反复应用 Rolle 定理，即可得到存在 \(\xi\in[a,b]\) 使得 \(R_{n+1}^{(n+1)}(\xi)=f^{(n+1)}(\xi)-\frac{(n+1)!}{w_{n+1}(x)}R_n(x)\)，证毕。

3. Newton插值

3.1 Newton插值及其余项

前面Lagrange插值方法存在的一个问题在于，如果新增一个插值节点，所有的基底函数 \(l_i(x)\) 都要重新计算。Newton插值就是要克服这个问题，其思路在前面“插值余项的证明”过程中已经显现了，也就是每次新增一个插值节点，多项式的阶数会 +1，那么我们就增加一个 \(n+1\) 次多项式来弥补。具体方法如下。 \[ N_n(x) = N_{n-1}(x) + a_n w_n(x) \] 其中 \(N_{n-1}(x)\) 为 \(\{x_0,...,x_{n-1}\}\) 的Newton插值函数，现在新增节点 \(x_n\)，其插值函数 \(N_n(x)\) 只需要添加一个 \(n\) 阶多项式 \(a_n w_n(x)\)，由 \(N_n(x_n)=f(x_n)\) 可以推出 \(a_n = \frac{f(x_n)-N_{n-1}(x_n)}{w_n(x_n)}\)，记为均差 \(a_n=f[x_0,...,x_n]\)（实际上就是 \(x^{n+1}\) 的系数，因此与节点的排列次序无关）。

由此得到Newton插值方法 \[ N_n(x) = \sum_{k=0}^n f[x_0,...,x_k] w_k(x) \] 实际计算过程中均差可以递归计算 \[ f[x_0,...,x_n] = \frac{f[x_1,...,x_n] - f[x_0,...,x_{n-1}]}{x_n-x_0} \] 证明：取 \(P_{n-1}(x)\in{\mathcal P}_{n-1}\) 满足 \(P_{n-1}(x_i)=f(x_i),i=0,1,...,n-1\)， \(Q_{n-1}(x)\in{\mathcal P}_{n-1}\) 满足 \(Q_{n-1}(x_i)=f(x_i),i=1,2,...,n\)。构造 \(P_n(x)=\frac{x-x_0}{x_n-x_0}Q_{n-1}(x) + \frac{x_n-x}{x_n-x_0}P_{n-1}(x) \quad(\bigstar)\)，可以验证满足 \(P_n(x_i)=f(x_i),i=0,...,n\)。考虑 \((\bigstar)\) 式等号两侧 \(x^n\) 的系数，即可得证。

插值余项为 \[ R_n(x) = f[x_0,...,x_n,x]\prod_{i=0}^n (x-x_i) \] 证明：类似Lagrange中的方法，同样是将 \(x\) 看作一个新的插值节点即可。证毕。

3.2 高阶项

插值条件中除了直接给出函数值 \(f(x_i)\)，有时候也会给出 \(f'(x_i)\) 或者更高阶的导数值，那么此时的均差该如何计算呢？对于高阶项，如果有 \(x_0\le x_1\le \cdots \le x_n\)，那么均差的计算方法为 \[ f[x_0,...,x_n] = \begin{cases} \frac{f[x_1,...,x_n] - f[x_0,...,x_{n-1}]}{x_n-x_0}, & x_n\ne x_0 \\ \frac{f^{(n)}(x_0)}{n!}, & x_n=x_0 \end{cases} \] 在解题过程中，主要还是用列表法，可以参考数值分析相关的教材。

4. Hermite插值

Hermite插值方法就是在Lagrange方法的基础上，再利用上插值节点的（高阶）导数值，用更少的插值节点获得更高阶的插值多项式。例如构造基函数 \(\alpha_i,\beta_i\in {\mathcal P}_{2n+1},i=0,1,...,n\) 满足 \[ \begin{cases} \alpha_i(x_j) = \delta_{ij}, & \alpha'_i(x_j)=0 \\ \beta_i(x_j)=0, & \beta'_i(x_j) = \delta_{ij} \end{cases} \] 构造的多项式即为 \[ H_{2n+1}(x) = \sum_{i=0}^n [f_i\alpha_i(x) + f'(x_i)\beta_i(x)] \] 具体细节略。

5. 样条插值

前面的方法都会出现 Runge 现象，也就是由于多项式本身的性质，插值函数阶数越高，边缘处振荡越严重，误差较大。样条插值的思路就是分段插值，并且只利用低阶多项式（如一阶、二阶、三阶）。其中一阶就是分段线性插值，用的比较多的还是三次样条插值。

三次样条插值的总体思路就是利用插值节点的函数值、一阶导、二阶导列出方程组来求解系数。不过为了使方程适定，需要再添加两个约束条件（增加两个方程），一般可选的有

• 固支边界条件：\(S'_3(x_0)=f'(x_0),S'_3(x_n)=f'(x_n)\)；
• 自然边界条件：\(S''_3(x_0)=S''_3(x_n)=0\)；
• 周期边界条件：\(S_3(x_0)=S_3(x_n)=f_0, S'_3(x_0)=S'_3(x_n), S''_3(x_0)=S''_3(x_n)\)。

具体细节略。