函数插值:对于一个未知全局信息,只知道若干点情况的函数,在保证若干点的信息正确的情况下插值补全全局信息
函数逼近:对于一个已知或未知的函数,根据其若干信息来构造另一个某个函数族(例如多项式)中的简单函数,来按某种标准逼近这个函数

函数插值

插值问题可以形式化为:在函数空间XX中,有一组线性信息泛函{ϕα}α∈I\{\phi_\alpha\}_{\alpha\in I},在已知某个f∈Xf\in X的信息ϕα(f)\phi_\alpha(f)时,在所选的子函数空间Y⊂XY\subset X中求插值函数f∗f^*,使得

ϕα(f∗)=ϕα(f),∀α∈I\phi_{\alpha}(f^*)=\phi_\alpha(f),\quad \forall\alpha\in I

这里的线性信息泛函指的是某个线性映射X→RX\to \mathbb R,一般而言形如取某点的值或者某点的某阶导数

理论分析

假设插值空间为

Y=span{y0,…,yn},dim⁡Y=n+1Y={\rm span}\{y_0,\ldots,y_n\},\quad \dim Y=n+1

则出n+1n+1个线性信息泛函

ϕ0,…,ϕn\phi_0,\ldots,\phi_n

插值函数在YY内,故

f∗=∑j=0najyjf^*=\sum_{j=0}^na_jy_j

那么插值条件相当于

ϕi(f∗)=∑j=0najϕi(yj)=ϕi(f)\phi_i(f^*)=\sum_{j=0}^na_j\phi_i(y_j)=\phi_i(f)

写成矩阵形式

Va=b,Vij=ϕi(yj),bi=ϕi(f)Va=b,\quad V_{ij}=\phi_i(y_j),\quad b_i=\phi_i(f)

因此存在唯一重构函数当且仅当VV非奇异,这要求n+1n+1个线性信息泛函在YY上的限制线性无关

本身线性无关的线性信息泛函限制到某个子空间上有可能是线性相关的,例如在Pn\mathbb P_n中,任意超过nn阶的高阶导数泛函都线性相关(都是零)

多项式插值

对n+1n+1个形如ϕα(g)=g(xα)\phi_\alpha(g)=g(x_\alpha)的取点值泛函上,在Pn\mathbb P_n中插值。即:已知若干个点的函数值,插值得到比点数少一阶的多项式

对函数点取值的多项式插值一定是存在唯一的,因为上一部分中的VV矩阵是Vandermonde矩阵

插值结果与采样点顺序无关

Lagrange插值

定义Lagrange插值基函数:

Lα(x)=∏β≠α,β∈Ix−xβxα−xβL_\alpha(x)=\prod_{\beta\neq\alpha,\beta\in I}\frac{x-x_\beta}{x_\alpha-x_\beta}

基函数的思想来源是找到一个多项式满足Lα(xα)=1L_\alpha(x_\alpha)=1,而对其他β\beta,Lβ(xβ)=0L_\beta(x_\beta)=0
这个基函数正好是nn阶

根据取值泛函的线性属性,可以得到插值多项式的表达式

P(x)=∑α∈IfαLα(x)P(x)=\sum_{\alpha\in I}f_\alpha L_\alpha(x)

根据高等线性代数中的理论,LαL_\alpha是空间YY中线性泛函组ϕα\phi_\alpha的一组对偶基

Neville递推算法

这部分回答的问题是:如何用某种递推的方式在逐渐增加点的情况下去推出新的插值函数?其算法如下

Pi(x)=f(xi)P_i(x)=f(x_i)

Pi0,i1⋯ik(x)=(x−xi0)Pi1⋯ik(x)+(xik−x)Pi0⋯ik−1(x)xik−xi0P_{i_0,i_1\cdots i_k}(x)=\frac{(x-x_{i_0})P_{i_1\cdots i_{k}}(x)+(x_{i_k}-x)P_{i_0\cdots i_{k-1}}(x)}{x_{i_k}-x_{i_0}}

其中Pi0i1⋯ik(x)P_{i_0i_1\cdots i_k}(x)表示在i0,⋯ ,iki_0,\cdots,i_k点上插值得到的插值函数。这个看着复杂,其实很容易论证,第二行公式的思路就是在已知两个部分插值函数的取值的时候,凑出完整插值函数的取值:

  • 对i0,iki_0,i_k之外的点,两个部分插值函数的值相等(因为是这两个函数的公共插值点),递推后值不变
  • 对于只有一个插值函数插值的点,此插值函数的系数是1,另一个插值函数的系数是0

从这个算法的计算模式已经能看出均差或者差商的影子,和计算高阶均差一样,使用金字塔形计算

Newton插值公式

在Neville递推中,为了求出nn阶的插值多项式,需要两个n−1n-1阶插值多项式,最终需要计算非常多多项式

Newton插值公式的思想来源于,让n+1n+1个点的多项式可以用前nn个点的多项式加上一个补足项表示,即考虑

Pi0⋯ik(x)=Pi0⋯ik−1(x)+R(x)P_{i_0\cdots i_{k}}(x)=P_{i_0\cdots i_{k-1}}(x)+R(x)

这个补足项R(x)R(x)至多是kk阶多项式,同时在前kk个点的取值都是00,于是

R(x)=fi0⋯ik(x−xi0)(x−xi1)⋯(x−xik−1)R(x)=f_{i_0\cdots i_k}(x-x_{i_0})(x-x_{i_1})\cdots(x-x_{i_{k-1}})

其中fi0⋯ikf_{i_0\cdots i_k}为某个常数

将上面的递推展开,即可得到Newton插值公式:

Pi0ii⋯ik=fi0+fi0i1(x−xi0)+⋯+fi0⋯ik(x−xi0)(x−xi1)⋯(x−xik−1)P_{i_0i_i\cdots i_k}=f_{i_0}+f_{i_0i_1}(x-x_{i_0})+\cdots+f_{i_0\cdots i_k}(x-x_{i_0})(x-x_{i_1})\cdots(x-x_{i_{k-1}})

下面只需要确定其中的系数

均差

上面的Newton插值公式的系数称为均差,均差是函数ff在一组插值点上的某个参数,事实上就是在这组插值点上的插值多项式的顶项系数

这里“顶项系数”是我发明的词,它表示次数是插值点数减一的那一项的系数。由于在插值多项式中这一项可能不存在,所以不能称之为最高次项系数
因为在Newton公式中,唯一有这一项的就是最后一项,故其系数就是最后一项的系数

要求得插值多项式的顶项系数,考虑Neville递推:

Pi0,i1⋯ik(x)=(x−xi0)Pi1⋯ik(x)+(xik−x)Pi0⋯ik−1(x)xik−xi0P_{i_0,i_1\cdots i_k}(x)=\frac{(x-x_{i_0})P_{i_1\cdots i_{k}}(x)+(x_{i_k}-x)P_{i_0\cdots i_{k-1}}(x)}{x_{i_k}-x_{i_0}}

这里右端两个k−1k-1阶多项式的顶项系数是k−1k-1阶均差,而括号内必须取xx才能达到等号左侧多项式的顶项,于是

fi0⋯ik=fi1⋯ik−fi0⋯ik−1xik−xi0f_{i_0\cdots i_k}=\frac{f_{i_1\cdots i_{k}}-f_{i_0\cdots i_{k-1}}}{x_{i_k}-x_{i_0}}

或者使用另一种记号:

f[x0,⋯ ,xk]=f[x1,⋯ ,xk]−f[x0,⋯ ,xk−1]xk−x0f[x_0,\cdots,x_k]=\frac{f[x_1,\cdots,x_{k}]-f[x_0,\cdots,x_{k-1}]}{x_k-x_0}

即:kk阶均差由两个只有一个元素不同的k−1k-1阶均差相减除以其对应独有的元素的差

均差是某种意义上的离散高阶导数

根据均差是插值多项式顶项系数的概念,可以得到以下性质:

  • 均差与插值点顺序无关,因为无论按什么顺序应用Newton公式,得到的顶项系数都必须相同
  • 如果ff本身是多项式,那么阶数高于其次数的均差都是0,因为多项式不存在更高次的顶项

Hermite插值

Hermite插值将Lagrange插值中的函数值变成函数值和可选的多阶导数,但如果引入kk阶导数,必须同时引入此节点上的00至k−1k-1阶导数,即“积木式”的,必须从低阶向高阶搭

和Lagrange插值一样,Hermite插值的解是存在且唯一的

我们希望像Newton公式那样,以递增的形式表示Hermite插值,但那样将会引入重复节点的均差,因此首先做定义:

f[x0,x1,⋯ ,xn]=∫0t0∫0t1⋯∫0tn−1f(n)(tn[xn−xn−1]+⋯+t1[x1−x0]+t0x0)dtn⋯dt2dt1f[x_0,x_1,\cdots,x_n]=\int_0^{t_0}\int_0^{t_1}\cdots\int_0^{t_{n-1}}f^{(n)}(t_n[x_n-x_{n-1}]+\cdots+t_1[x_1-x_0]+t_0x_0)dt_n\cdots dt_2 dt_1

其中t0=1t_0=1

这个定义太复杂了,看不懂怎么来的,我猜就是把之前的狭义均差定义在节点可重的情况下做了扩展,但确实太复杂了,应该也没有必要理解

重复节点均差的性质:

  • 对称性:均差与节点顺序无关
  • 连续性
  • 中值性质
    • 对实值函数,f[x0,⋯ ,xn]=f(n)(ξ)/n!f[x_0,\cdots,x_n]=f^{(n)}(\xi)/n!,其中ξ\xi介于x0,⋯ ,xnx_0,\cdots,x_n的两个最值之间
    • 对复值函数,∣f[x0,⋯ ,xn]∣≤∣∣f∞,[a,b](n)/n!|f[x_0,\cdots,x_n]|\leq ||f^{(n)}_{\infty,[a,b]}/n!

重复节点均差有和狭义均差相同的递推关系,因此只要能够计算全重节点均差,就可以计算任意的重复节点均差

f[x,x,⋯ ,x⏟n+1]=f(n)(x)n!f[\underbrace{x,x,\cdots,x}_{n+1}]=\frac{f^{(n)}(x)}{n!}

向已知均差中引入重复节点时,有以下规律:

ddxf[x0,⋯ ,xn,x]=f[x0,x1,⋯ ,xn,x,x]\frac{d}{dx}f[x_0,\cdots,x_n,x]=f[x_0,x_1,\cdots,x_n,x,x]

ddxf[x0,⋯ ,xn,x,x]=2f[x0,x1,⋯ ,xn,x,x,x]\frac{d}{dx}f[x_0,\cdots,x_n,x,x]=2f[x_0,x_1,\cdots,x_n,x,x,x]

其中xx不同于x0,⋯ ,xnx_0,\cdots,x_n,且这个xx和求导的xx并非一个含义

有了以上的均差定义,Hermite插值有和Lagrange插值完全相同的Newton公式

插值余项与误差估计

我们可以综合Newton型插值公式和均差的性质,来讨论插值余项和误差估计。假设我们要估计xx处的误差(此时xx是区间内任意给定点),那么我们将xx插入到插值点组中,得到的新的插值点组的插值多项式将能求出准确的f(x)f(x)

于是

f(x)=P(x)+f[x0,⋯ ,xn,x](x−x0)⋯(x−xn)f(x)=P(x)+f[x_0,\cdots,x_n,x](x-x_0)\cdots(x-x_n)

R(x)=f[x0,⋯ ,xn,x](x−x0)⋯(x−xn)R(x)=f[x_0,\cdots,x_n,x](x-x_0)\cdots(x-x_n)

定义

ω01⋯n=(x−x0)⋯(x−xn)\omega_{01\cdots n}=(x-x_0)\cdots(x-x_n)

则根据均差中值性质,有

R(x)=f(n+1)(ξ)(n+1)!ω01⋯n(x)R(x)=\frac{f^{(n+1)}(\xi)}{(n+1)!}\omega_{01\cdots n}(x)

Runge现象

多项式插值的Runge现象:如果在等距节点上插值,当次数过高时,插值多项式会出现尾部发散,如下图

![[Pasted image 20261113150042.png]]

Runge现象是等距节点和高次多项式插值两个因素共同导致的,因此要改善这个现象可以选择两条路径:

  • 改变节点分布
  • 将高次多项式改为分片低次多项式