数值分析学习笔记（二） 函数的多项式插值与逼近

（未完待续…）

使用多项式逼近函数在数值分析中属于基本问题，这是因为多项式具有良好的性质，其函数值的计算只要通过有限次加减乘除即可完成，且导数和原函数仍是多项式。多项式在函数逼近中的地位可以由Weierstrass逼近定理体现，其证明过程参见Weierstrass逼近定理证明。

【Weierstrass逼近定理】对于$f(x) \in C[a,b]$，有

$$\forall \varepsilon > 0, \exists P(x), s.t.||f(x) - P(x)||_{\infty} < \varepsilon$$

这一定理说明，定义在闭区间上的连续函数可以使用多项式来逼近，并且逼近的效果可以充分好。

用多项式逼近一般函数的方法可以分为两种：多项式插值和多项式逼近。

多项式插值

多项式插值问题的描述

一个多项式插值问题的一般性描述如下：

对于定义在区间$[a,b]$中的一般函数$f(x)$，已知其在区间上$n+1$个不同点$x_0,x_1,…,x_n$处的函数值为

$$y_i = f(x_i),i=0,1,...,n$$

需要在区间$[a,b]$上求一个多项式$P(x)$，使得

$$P(x_i)=y_i,i=0,1,...,n$$

在这一描述中，$x_0,x_1,…,x_n$称为插值节点，$f(x)$称为被插函数，$P(x)$称为插值多项式，$P(x_i)=y_i$称为插值条件。对于这一描述，需要解决两个问题：满足这一描述的多项式是否存在？如果多项式存在，是否唯一？下述定理解决了存在性和唯一性的问题，其证明过程参见插值多项式的存在性和唯一性证明。

【定理】当$n+1$个插值节点$x_0,x_1,…,x_n$互不相同时，一定存在唯一的次数不超过$n$的多项式$P(x)$满足条件$P(x_i)=y_i$.

该定理给出了通过解线性代数方程组得到多项式$P(x)$的系数的方法，但是计算量较大，该计算问题一般也是病态的，所以并不适合求解插值多项式$P(x)$。下面介绍求解插值多项式的更有效的方法。

记所有次数不超过$n$的实系数多项式组成的线性空间为$\mathbb{P}_n$，那么多项式插值问题实际上就是寻找元素$P(x)$，使其满足$P(x_i)=y_i$。

Lagrange插值

构造思路

为寻找满足$P(x_i)=y_i$的多项式$P(x)\in \mathbb{P}_n$，自然地希望构造一组$\mathbb{P}_n$的基函数$\{l_i(x)\}_{i=0}^n$，满足

$$l_i(x_j)=\delta_{ij}= \begin{cases} 1,&&i=j \\ 0,&&i\neq j \end{cases}$$

容易构造出$l_i(x)$的表达式为

$$l_i(x)=\frac{\prod_{j=0,j\neq i}^{n}{(x-x_j)}}{\prod_{j=0,j\neq i}^{n}{(x_i-x_j)}}$$

这样，由$\{l_i(x)\}$构造的多项式$P(x)$称为$n$次Lagrange插值多项式$L_n(x)$，有

$$L_n(x)=\sum_{i=0}^{n}y_i \cdot l_i(x)$$

余项与收敛性分析

使用$L_n(x)$逼近$f(x)$的截断误差定义为$R_n(x)=f(x)-L_n(x)$，称为余项。

下面不加证明地分别给出关于余项与收敛性的定理。

【定理】对于被插函数$f(x) \in C^{(n+1)}[a,b]$和互不相同的插值节点$x_0,x_1,…,x_n$，有

$$\forall x \in [a,b], \exists \xi \in [a,b], s.t. R_n(x) = \frac{f^{(n+1)}{(\xi)}}{(n+1)!}(x-x_0)(x-x_1)\cdots (x-x_n)$$

【定理】对于复函数$f(z)$，如果存在$r_0 > \frac{3}{2}(b-a)$，使得$f(z)$在$B_{r_0}(\frac{a+b}{2})$内解析，则$L_n(x)$在$[a,b]$内一致收敛于$f(x)$，其中$B_{r_0}(\frac{a+b}{2})$指在复平面上圆心在$\frac{a+b}{2}$且半径为$r_0$的圆

Newton插值

构造思路

对于Lagrange插值方法来说，已知$n$次插值多项式$L_{n+1}$，如果想要再增加一个插值节点$x_{n+1}$，就需要重新计算$\{l_i(x)\}$，效率较低。为了解决这一问题，自然地想到差分的方法，即构造一组新的$\mathbb{P}_n$的基函数，能够通过差分的方式由低阶基函数向高阶基函数构造。这样，在增加新的插值节点时，只需要多构造一个更高阶的基函数即可，不需要重新计算所有基函数。根据这一思路，递归地构造$n$阶差商$f[x_0,x_1,…,x_n]$。

• $0$阶差商：$f[x_i] = f(x_i), i=0,1,…,n$

• $k$阶差商：

  $$f[x_i,x_{i+1},...,x_{i+k}]=\frac{f[x_{i+1},x_{i+2},...,x_{i+k}]-f[x_i,x_{i+1},...,x_{i+k-1}]}{x_{i+k}-x_i}$$

这样递归定义的差商具有如下性质（不加证明给出）

【性质1】$f(x)$在节点$x_0,x_1,…,x_n$上的$n$阶差商的解析式为

$$f[x_0,x_1,...,x_n]=\sum_{i=0}^{n}{\frac{f(x_i)}{\sum_{j=0,j\neq i}^{n}(x_i-x_j)}}$$

【性质2】差商的值与节点的排列顺序无关，不妨设$\{i_0,i_1,…,i_n\}$是$\{0,1,…,n\}$的任意排列，则

$$f[x_0,x_1,...,x_n]=f[x_{i_0},x_{i_1},...,x_{i_n}]$$

【性质3】如果$f(x)$存在$n$阶导数，则

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

注意到，一组差商$\{f[x_0],f[x_0,x_1],…,f[x_0,x_1,…,x_n]\}$是$\mathbb{P}_n$的一组基，由此构造的多项式$P(x)$称为$n$次Newton插值多项式$N_n(x)$，有

$$N_n(x) = \sum_{i=0}^{n}{(f[x_0,x_1,...,x_i]\prod_{j=0}^{i-1}{(x-x_j)})}$$

根据【性质3】，不难发现

$$N_{n+1}(x) - N_n(x) = f[x_0,x_1,...,x_{n+1}]\prod_{i=0}^{n}{(x-x_i)} = \frac{f^{(n+1)}(\xi_1)}{(n+1)!}\prod_{i=0}^{n}{(x-x_i)}$$

这与下述Lagrange插值余项的形式很相似

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

可以发现，当增加一个插值节点$x_{n+1}$，插值多项式从$N_n(x)$变为$N_{n+1}(x)$时，增加的部分与$n$阶Lagrange插值多项式$L_n(x)$对应的余项同阶（都为$n+1$阶），是对原有逼近结果的一种”修正“，这就是Newton插值包含的”差分“含义。因此，Newton可以通过逐渐添加插值节点的方式，逐渐增加更高阶的部分，从而逐渐逼近函数$f(x)$。

余项分析

Newton插值多项式的余项为

$$f(x) - N_n(x) = R_n(x) = f[x,x_0,x_1,...,x_n]\prod_{i=0}^{n}{(x-x_i)}$$

由于插值多项式的唯一性，Newton插值多项式的余项与Lagrange插值多项式的余项实际上是同一余项的不同表现形式，而前者在$f(x)$的导数不存在时仍有意义，适用范围更广。

分段低次多项式插值

Runge现象

从Lagrange插值和Newton插值的余项分析中可以发现，采用更高阶的插值方法，得到的插值多项式$P(x)$的余项越小，也就更加逼近函数$f(x)$。但是，虽然$P(x)$在很多个点上严格等于$f(x)$，但整体的逼近效果不一定好。记

$$h=\max_{0 \leq i \leq n-1}{|x_{i+1}-x_i|}$$

作为表示插值节点疏密程度的参数。注意到$h\rightarrow 0$意味着$n\rightarrow \infty$，而$n\rightarrow \infty$不一定有$h\rightarrow 0$。这样，我们采用等距插值节点

$$\begin{aligned} x_i = a + ih &&(i=0,1,2,...,n;h=\frac{b-a}{n}) \end{aligned}$$

时，$h\rightarrow 0$与$n\rightarrow\infty$等价，此时Lagrange插值得到的插值多项式记为$L_h(x)$。根据函数逼近理论，不加证明地认为：即使$f(x)$无穷次可微，也不能得出

$$\forall x \in [a,b], \lim_{h\rightarrow 0}{|L_h(x)-f(x)|} = 0$$

这种现象称为Runge现象。这说明高次的插值多项式的数值稳定性很差，计算的舍入误差会被高阶多项式迅速放大，最终对计算结果产生灾难性的影响。

分段线性插值

既然不能使用高次的插值多项式逼近函数，可以将原先的区间$[a,b]$分割成$n$个子区间$[x_i,x_{i+1}]$，在每个子区间内函数的变化程度可能相较于原区间更小，因此可以分段对每个子区间使用低次的插值多项式逼近函数。

分段线性插值问题的确切描述如下：

对于定义在区间$[a,b]$中的一般函数$f(x)$，已知其在区间上$n+1$个不同点$x_0,x_1,…,x_n$处的函数值为

$$y_i = f(x_i),i=0,1,...,n$$

需要在区间$[a,b]$上求一个分段线性插值函数$\phi_h(x)$，使得

【条件1】$\phi_h(x) \in C[a,b]$

【条件2】在每个子区间$x_i,x_{i+1}$上$\phi_h(x) \in \mathbb{P}_1$

【条件3】$\phi_h(x_i)=y_i,i=0,1,…,n$

不妨记满足【条件2】的所有函数构成的线性空间为$\Phi_h$，为了构造分段线性插值函数$\phi_h(x)$，一个自然的想法是首先构造$\Phi_h$的一组基函数$\{l_i(x)\}_{i=0}^n$，再通过【条件3】对基函数配置系数，最终得到$\phi_h(x)$。

在每个子区间内，由于$\phi_h(x) \in \mathbb{P}_1$，则应该有$l_i(x)\in \mathbb{P}_1$。于是，可以使用Lagrange插值的思想构造基函数如下

$$l_0(x) = \begin{cases} \frac{x-x_1}{x_0-x_1}, & x\in[x_0,x_1] \\ 0, & x\notin[x_0,x_1] \end{cases}$$ $$l_i(x) = \begin{cases} \frac{x-x_{i-1}}{x_i-x_{i-1}}, & x\in[x_{i-1},x_i] \\ \frac{x-x_{i+1}}{x-x_i}, & x\in[x_i, x_{i+1}] \\ 0, & x\notin[x_{i-1},x_{i+1}] \\ \end{cases}$$ $$l_n(x) = \begin{cases} \frac{x-x_{n-1}}{x_n-x_{n-1}}, & x\in[x_{n-1},x_n] \\ 0, & x\notin[x_{n-1},x_{n}] \\ \end{cases}$$

因此，分段线性插值函数$\phi_h(x)$可以写为

$$\phi_h(x)=\sum_{i=0}^{n}{y_i \cdot l_i(x)}$$

这样构造出的插值函数$\phi_h(x)$，【条件1】由【条件3】中隐含的“相邻区间的共同端点的函数值相同”满足，【条件2】由求得的$\mathbb{P}_1$的基函数满足，【条件3】由基函数的系数满足。

下面不加证明地给出分段线性插值的余项分析

【定理】设被插函数$f(x) \in C^2[a,b]$，则

$$|f(x)-\phi_h(x)|\leq \frac{Mh^2}{8},x\in[a,b]$$

其中$M=\max_{x\in[a,b]}|f^{\prime\prime}(x)|$.

此定理说明，对于二阶连续的被插函数$f(x)$，分段线性插值函数$\phi_h(x)$一致收敛到被插函数$f(x)$。

Hermite插值

分段线性插值函数具有一个明显的缺点，即不够光滑，因此可以在插值数据中添加被插函数在插值节点上的导数值，这样的插值问题称为Hermite插值。特别地，对于分段三次Hermite插值，其插值函数不仅本身连续，一阶导数也连续，比分段线性插值函数更加光滑。

作为示例，下面仅讨论分段三次Hermite插值，其具体描述如下

对于定义在区间$[a,b]$中的一般函数$f(x)$，已知其在区间上$n+1$个不同点$x_0,x_1,…,x_n$处的函数值和导数值为

$$y_i = f(x_i),m_i=f^{\prime}(x_i),i=0,1,...,n$$

需要在区间$[a,b]$上求一个分段三次Hermite插值函数$H_h(x)$，使得

【条件1】$H_h(x) \in C^1[a,b]$

【条件2】在每个子区间$x_i,x_{i+1}$上$H_h(x) \in \mathbb{P}_3$

【条件3】$H_h(x_i)=y_i,H_h^{\prime}(x_i)=m_i,i=0,1,…,n$

同样使用Lagrange插值的思想构造满足【条件2】的一组基函数$\{h_i,\hat{h}_i\}_{i=0}^n$如下，其基本思路见两点三次Hermite插值的求解过程

$$h_0(x) = \begin{cases} (1+2\frac{x-x_0}{x_1-x_0})(\frac{x-x_1}{x_0-x_1})^2, & x\in[x_0,x_1] \\ 0, & x\notin[x_0,x_1] \end{cases}$$ $$\hat{h}_0(x) = \begin{cases} (x-x_0)(\frac{x-x_1}{x_0-x_1})^2, & x\in[x_0,x_1] \\ 0, & x\notin[x_0,x_1] \end{cases}$$ $$h_i(x) = \begin{cases} (1+2\frac{x-x_i}{x_{i-1}-x_i})(\frac{x-x_{i-1}}{x_i-x_{i-1}})^2, & x\in[x_{i-1},x_i] \\ (1+2\frac{x-x_i}{x_{i+1}-x_i})(\frac{x-x_{i+1}}{x_i-x_{i+1}})^2, & x\in[x_i,x_{i+1}] \\ 0, & x\notin[x_{i-1},x_{i+1}] \end{cases}$$ $$\hat{h}_i(x) = \begin{cases} (x-x_{i-1})(\frac{x-x_i}{x_{i-1}-x_i})^2, & x\in[x_{i-1},x_i] \\ (x-x_i)(\frac{x-x_{i+1}}{x_i-x_{i+1}})^2, & x\in[x_i,x_{i+1}] \\ 0, & x\notin[x_{i-1},x_{i+1}] \end{cases}$$ $$h_n(x) = \begin{cases} 0, & x\notin[x_{n-1},x_n]\\ (1+2\frac{x-x_n}{x_{n-1}-x_n})(\frac{x-x_{n-1}}{x_n-x_{n-1}})^2, & x\in[x_{n-1},x_n] \end{cases}$$ $$\hat{h}_n(x) = \begin{cases} 0, & x\notin[x_{n-1},x_n]\\ (x-x_{n-1})(\frac{x-x_n}{x_{n-1}-x_n})^2, & x\in[x_{n-1},x_n] \end{cases}$$

因此，分段三次Hermite插值函数$H_h(x)$可以写为

$$H_h(x)=\sum_{i=0}^{n}{[y_ih_i(x)+m_i\hat{h}_i(x)]}$$

这样构造出的插值函数$H_h(x)$，【条件1】中的“函数连续”和“一阶导数连续”分别由【条件3】中隐含的“相邻区间的共同端点的函数值相同”和“相邻区间的共同端点的一阶导数值相同”满足，【条件2】由求得的$\mathbb{P}_3$的基函数满足，【条件3】由基函数的系数满足。

下面不加证明地给出分段三次Hermite插值的余项分析

【定理】设被插函数$f(x) \in C^4[a,b]$，则

$$|f(x)-H_h(x)|\leq \frac{Mh^4}{384},x\in[a,b]$$

其中$M=\max_{x\in[a,b]}|f^{(4)}(x)|$.

此定理说明，分段三次Hermite插值函数$H_h(x)$的截断误差的量级为$O(h^4)$。

样条插值

$k$次样条插值问题的描述为：

对于定义在区间$[a,b]$中的一般函数$f(x)$，已知其在区间上$n+1$个不同点$x_0,x_1,…,x_n$处的函数值为

$$y_i = f(x_i),i=0,1,...,n$$

需要在区间$[a,b]$上求一个分段线性插值函数$S_k(x)$，使得

【条件1】$S_k(x) \in C^{k-1}[a,b]$

【条件2】在每个子区间$[x_i,x_{i+1}],i=0,1,…,n-1$上$S_k(x) \in \mathbb{P}_k$

【条件3】$S_k(x_i)=y_i,i=0,1,…,n$

值得注意的是，分段线性插值就是一次样条插值。而三次样条插值函数与Hermite插值函数同为分段三次多项式插值函数，不仅在每个插值节点的一阶导数连续，在每个插值节点的二阶导数也连续，比Hermite插值函数更加光滑。

作为示例，下面仅讨论三次样条插值函数$S_3(x)$。

为寻找同时满足【条件1】、【条件2】和【条件3】的插值函数$S_3(x)$，首先联想到条件更弱的分段三次Hermite插值。根据分段三次Hermite插值的分析，一定存在插值函数$S_3(x) \in C^1[a,b]$满足【条件2】和【条件3】，即一定存在满足【条件2】和【条件3】，且一阶导数存在的插值函数。

不妨设$S_3^{\prime}(x_i)=m_i$，其中$m_i$是未知数。这样，可以利用分段三次Hermite插值的基函数将$S_3(x)$表示为

$$S_3(x)=\sum_{i=0}^{n}[y_ih_i(x)+m_i\hat{h}_i(x)]$$

自此，【条件2】和【条件3】已由基函数与其系数满足，而【条件1】则需要通过定下作为未知数的$m_i$来满足。也就是说，需要找到一组$m_i$，以$y_i$和$m_i$作为参数，利用分段三次Hermite插值得到的$S_3(x) \in C^2[a,b]$。

可以求出$S_3(x)$在每个子区间中的二阶导数表达式，记$\Delta x_i = x_{i+1} - x_i$，则有

$$\begin{aligned} S^{\prime\prime}_3(x)=&[\frac{6}{\Delta x_i^2} - \frac{12}{\Delta x_i^3}(x_{i+1} - x)]y_i + [\frac{6}{\Delta x_i^2} - \frac{12}{\Delta x_i^3}(x - x_i)]y_{i+1} + \\[] &[\frac{2}{\Delta x_i} - \frac{6}{\Delta x_i^2}(x_{i+1} - x)]m_i - [\frac{2}{\Delta x_i} - \frac{6}{\Delta x_i^2}(x - x_i)]m_{i+1},x\in[x_i,x_{i+1}] \end{aligned}$$

于是可以得到

$$\begin{aligned} S_3^{\prime\prime}(x_i+0) &= -\frac{6}{\Delta x_i^2}y_i + \frac{6}{\Delta x_i^2}y_{i+1} - \frac{4}{\Delta x_i}m_i - \frac{2}{\Delta x_i}m_{i+1} \\ S_3^{\prime\prime}(x_i-0) &= \frac{6}{\Delta x_{i-1}^2}y_{i-1} - \frac{6}{\Delta x_{i-1}^2}y_i + \frac{2}{\Delta x_{i-1}}m_{i-1} + \frac{4}{\Delta x_{i-1}}m_i \end{aligned}$$

要使$S_3(x) \in C^2[a,b]$，只要

$$S_3^{\prime\prime}(x_i+0) = S_3^{\prime\prime}(x_i-0), i=1,2,...,n-1$$

由于一组$m_i$共有$n+1$个未知数，而上述方程共有$n-1$个，因此还需要在$x_0$和$x_n$处各增加两个边界条件。这样的边界条件有很多种，而常用的边界条件共有下列三种

• 固支边界条件：$S_3^{\prime}(x_0)=f^{\prime}(x_0),S_3^{\prime}(x_n)=f^{\prime}(x_n)$
• 自然边界条件：$S_3^{\prime\prime}(x_0)=0,S_3^{\prime\prime}(x_n)=0$
• 周期边界条件：$S_3^{\prime}(x_0)=S_3^{\prime}(x_n),S_3^{\prime\prime}(x_0)=S_3^{\prime\prime}(x_n)$

上诉三种边界条件任取其一，就能够与之前的方程组一起求解$m_i$。值得注意的是，加入边界条件的方程组的系数矩阵是三对角方程组或其变形，可以使用追赶法快速求解。

在求解得到一组$m_i$后，就可以利用分段三次Hermite插值的方法得到满足【条件1】、【条件2】和【条件3】的插值函数$S_3(x)$。

下面不加证明地给出三次样条插值的余项分析

【定理】设被插函数$f(x) \in C^4[a,b]$，则

$$|f^{(k)}(x)-S_3^{(k)}(x)|\leq C_k|f^{(4)}(x)|h^{4-k},k=0,1,2$$

其中$C_k$为常数.

多项式逼近

多项式逼近问题的描述

多项式逼近与多项式插值不同，并非寻求某一函数与原函数在某些点上严格相等，而是寻求在某一范数的意义下，与原函数误差最小的某一函数，其一般性描述如下：

对于定义在区间$[a,b]$中的一般函数$f(x)$及某一范数$||\cdot ||$，寻找$P_0(x) \in \mathbb{P}_n$，使得

$$||P_0(x) - f(x)||= \min_{P \in \mathbb{P}_n}||P(x)-f(x)||$$

常用的范数有

• $L^{\infty}$范数：$||\cdot||_{\infty}$，$||f||_{\infty}=\max_{[a,b]}|f(x)|$
• $L^1$范数：$||\cdot||_1$，$||f||_1=\int_a^b|f(x)|\text{d}x$
• $L^p$范数：$||\cdot||_p$，$||f||_p=(\int_a^b|f(x)|^p\text{d}x)^{\frac{1}{p}}$

最佳一致逼近

当范数取为$L^{\infty}$范数时，多项式逼近问题称为最佳一致逼近问题。

对于最佳一致逼近问题，首先要解决存在性和唯一性的问题。设$f(x)\in C[a,b]$，令

$$\Delta(P)=\max_{x}|f(x)-P(x)|, P(x) \in \mathbb{P}_n$$

为$P(x)$与$f(x)$的偏差，令

$$E_n = \inf_{P\in \mathbb{P}_n}{\Delta (P)}$$

为$\mathbb{P}_n$对$f(x)$的最小偏差或最佳逼近。显然有$E_n \geq E_{n+1} \geq \cdots$，并且由Weierstrass定理保证$\lim_{n\rightarrow\infty}E_n=0$。

最佳一致逼近问题需要关心的存在性与一致性的问题是：是否存在$P_0 \in \mathbb{P}_n$，使得$\Delta(P_0)=E_n$；如果存在，称$P_0$为$f(x)$在$\mathbb{P}_n$中的最佳一致逼近多项式，那么这样的$P_0$是否唯一？

【Borel存在定理】对$\forall f(x) \in C[a,b]$，$\exists P_0 \in \mathbb{P}_n$，使得

$$\Delta (P_0) = E_n$$

由Weierstrass逼近定理，有

$$\forall \frac{1}{m} > 0, \exists P_m \in \mathbb{P}_n, s.t. E_n \leq \Delta(P_m) \leq E_n + \frac{1}{m}$$

最小二乘问题

最小二乘问题是一类

最佳平方逼近

正交多项式

有理插值与逼近