函数插值:对于一个未知全局信息,只知道若干点情况的函数,在保证若干点的信息正确的情况下插值补全全局信息
函数逼近:对于一个已知或未知的函数,根据其若干信息来构造另一个某个函数族(例如多项式)中的简单函数,来按某种标准逼近这个函数
函数插值
插值问题可以形式化为:在函数空间X中,有一组线性信息泛函{ϕα}α∈I,在已知某个f∈X的信息ϕα(f)时,在所选的子函数空间Y⊂X中求插值函数f∗,使得
ϕα(f∗)=ϕα(f),∀α∈I
这里的线性信息泛函指的是某个线性映射X→R,一般而言形如取某点的值或者某点的某阶导数
理论分析
假设插值空间为
Y=span{y0,…,yn},dimY=n+1
则出n+1个线性信息泛函
ϕ0,…,ϕn
插值函数在Y内,故
f∗=j=0∑najyj
那么插值条件相当于
ϕi(f∗)=j=0∑najϕi(yj)=ϕi(f)
写成矩阵形式
Va=b,Vij=ϕi(yj),bi=ϕi(f)
因此存在唯一重构函数当且仅当V非奇异,这要求n+1个线性信息泛函在Y上的限制线性无关
本身线性无关的线性信息泛函限制到某个子空间上有可能是线性相关的,例如在Pn中,任意超过n阶的高阶导数泛函都线性相关(都是零)
多项式插值
对n+1个形如ϕα(g)=g(xα)的取点值泛函上,在Pn中插值。即:已知若干个点的函数值,插值得到比点数少一阶的多项式
对函数点取值的多项式插值一定是存在唯一的,因为上一部分中的V矩阵是Vandermonde矩阵
插值结果与采样点顺序无关
Lagrange插值
定义Lagrange插值基函数:
Lα(x)=β=α,β∈I∏xα−xβx−xβ
基函数的思想来源是找到一个多项式满足Lα(xα)=1,而对其他β,Lβ(xβ)=0
这个基函数正好是n阶
根据取值泛函的线性属性,可以得到插值多项式的表达式
P(x)=α∈I∑fαLα(x)
根据高等线性代数中的理论,Lα是空间Y中线性泛函组ϕα的一组对偶基
Neville递推算法
这部分回答的问题是:如何用某种递推的方式在逐渐增加点的情况下去推出新的插值函数?其算法如下
Pi(x)=f(xi)
Pi0,i1⋯ik(x)=xik−xi0(x−xi0)Pi1⋯ik(x)+(xik−x)Pi0⋯ik−1(x)
其中Pi0i1⋯ik(x)表示在i0,⋯,ik点上插值得到的插值函数。这个看着复杂,其实很容易论证,第二行公式的思路就是在已知两个部分插值函数的取值的时候,凑出完整插值函数的取值:
- 对i0,ik之外的点,两个部分插值函数的值相等(因为是这两个函数的公共插值点),递推后值不变
- 对于只有一个插值函数插值的点,此插值函数的系数是1,另一个插值函数的系数是0
从这个算法的计算模式已经能看出均差或者差商的影子,和计算高阶均差一样,使用金字塔形计算
Newton插值公式
在Neville递推中,为了求出n阶的插值多项式,需要两个n−1阶插值多项式,最终需要计算非常多多项式
Newton插值公式的思想来源于,让n+1个点的多项式可以用前n个点的多项式加上一个补足项表示,即考虑
Pi0⋯ik(x)=Pi0⋯ik−1(x)+R(x)
这个补足项R(x)至多是k阶多项式,同时在前k个点的取值都是0,于是
R(x)=fi0⋯ik(x−xi0)(x−xi1)⋯(x−xik−1)
其中fi0⋯ik为某个常数
将上面的递推展开,即可得到Newton插值公式:
Pi0ii⋯ik=fi0+fi0i1(x−xi0)+⋯+fi0⋯ik(x−xi0)(x−xi1)⋯(x−xik−1)
下面只需要确定其中的系数
均差
上面的Newton插值公式的系数称为均差,均差是函数f在一组插值点上的某个参数,事实上就是在这组插值点上的插值多项式的顶项系数
这里“顶项系数”是我发明的词,它表示次数是插值点数减一的那一项的系数。由于在插值多项式中这一项可能不存在,所以不能称之为最高次项系数
因为在Newton公式中,唯一有这一项的就是最后一项,故其系数就是最后一项的系数
要求得插值多项式的顶项系数,考虑Neville递推:
Pi0,i1⋯ik(x)=xik−xi0(x−xi0)Pi1⋯ik(x)+(xik−x)Pi0⋯ik−1(x)
这里右端两个k−1阶多项式的顶项系数是k−1阶均差,而括号内必须取x才能达到等号左侧多项式的顶项,于是
fi0⋯ik=xik−xi0fi1⋯ik−fi0⋯ik−1
或者使用另一种记号:
f[x0,⋯,xk]=xk−x0f[x1,⋯,xk]−f[x0,⋯,xk−1]
即:k阶均差由两个只有一个元素不同的k−1阶均差相减除以其对应独有的元素的差
均差是某种意义上的离散高阶导数
根据均差是插值多项式顶项系数的概念,可以得到以下性质:
- 均差与插值点顺序无关,因为无论按什么顺序应用Newton公式,得到的顶项系数都必须相同
- 如果f本身是多项式,那么阶数高于其次数的均差都是0,因为多项式不存在更高次的顶项
Hermite插值
Hermite插值将Lagrange插值中的函数值变成函数值和可选的多阶导数,但如果引入k阶导数,必须同时引入此节点上的0至k−1阶导数,即“积木式”的,必须从低阶向高阶搭
和Lagrange插值一样,Hermite插值的解是存在且唯一的
我们希望像Newton公式那样,以递增的形式表示Hermite插值,但那样将会引入重复节点的均差,因此首先做定义:
f[x0,x1,⋯,xn]=∫0t0∫0t1⋯∫0tn−1f(n)(tn[xn−xn−1]+⋯+t1[x1−x0]+t0x0)dtn⋯dt2dt1
其中t0=1
这个定义太复杂了,看不懂怎么来的,我猜就是把之前的狭义均差定义在节点可重的情况下做了扩展,但确实太复杂了,应该也没有必要理解
重复节点均差的性质:
- 对称性:均差与节点顺序无关
- 连续性
- 中值性质
- 对实值函数,f[x0,⋯,xn]=f(n)(ξ)/n!,其中ξ介于x0,⋯,xn的两个最值之间
- 对复值函数,∣f[x0,⋯,xn]∣≤∣∣f∞,[a,b](n)/n!
重复节点均差有和狭义均差相同的递推关系,因此只要能够计算全重节点均差,就可以计算任意的重复节点均差
f[n+1x,x,⋯,x]=n!f(n)(x)
向已知均差中引入重复节点时,有以下规律:
dxdf[x0,⋯,xn,x]=f[x0,x1,⋯,xn,x,x]
dxdf[x0,⋯,xn,x,x]=2f[x0,x1,⋯,xn,x,x,x]
其中x不同于x0,⋯,xn,且这个x和求导的x并非一个含义
有了以上的均差定义,Hermite插值有和Lagrange插值完全相同的Newton公式
插值余项与误差估计
我们可以综合Newton型插值公式和均差的性质,来讨论插值余项和误差估计。假设我们要估计x处的误差(此时x是区间内任意给定点),那么我们将x插入到插值点组中,得到的新的插值点组的插值多项式将能求出准确的f(x)
于是
f(x)=P(x)+f[x0,⋯,xn,x](x−x0)⋯(x−xn)
R(x)=f[x0,⋯,xn,x](x−x0)⋯(x−xn)
定义
ω01⋯n=(x−x0)⋯(x−xn)
则根据均差中值性质,有
R(x)=(n+1)!f(n+1)(ξ)ω01⋯n(x)
Runge现象
多项式插值的Runge现象:如果在等距节点上插值,当次数过高时,插值多项式会出现尾部发散,如下图
![[Pasted image 20261113150042.png]]
Runge现象是等距节点和高次多项式插值两个因素共同导致的,因此要改善这个现象可以选择两条路径: