第二章：插值法

描述事物之间的数量关系：函数。有两种情况：一是表格形式——一组离散的数据来表示函数关系；另一种是函数虽然有明显的表达式，但很复杂，不便于研究和使用。从实际需要出发：对于计算结果允许有一定的误差，可以把函数关系用一个简单的便于计算和处理的近似表达式来代替，从而使问题得到简化。一般地，构造某种简单函数代替原来函数。插值法就是一种基本方法§0引言第二章插值（Interpolation）法(1)(2)(2)在x为特殊时,是好计算的,则(2)可转化为(1)当精确函数y=f(x)非常复杂或未知时，在一系列节点x0…xn

处测得函数值y0

=f(x0),…yn

=f(xn)，由此构造一个简单易算的近似函数g(x)

f(x)，满足条件g(xi)=f(xi)(i=0,…n)。这里的g(x)

称为f(x)的插值函数。x0x1x2x3x4xg(x)

f(x)根据实际需要，可以用各种不同的函数来近似原来的函数。最常用的插值函数是…?多项式：代数多项式最简单，计算其值只需用到加、减乘运算，且积分和微分都很方便；所以常用它来近似表示表格函数(或复杂函数),这样的插值方法叫做代数插值法，简称插值法。§1拉格朗日多项式niyxPiin,...,0,)(==求n

次多项式使得条件：无重合节点，即n=1已知x0

,x1

;

y0

,

y1

，求使得111001)(,)(yxPyxP==可见P1(x)是过(x0,y0

)和(x1,y1

)两点的直线。)(1xP101xxxx--010xxxx--=y0

+y11.1线性插值两点式)()(0010101xxxxyyyxP---+=点斜式)(001010xxxxxxy---+=(())ff1.2二次插值n=2已知x0

,x1

,x2;

y0

,

y1

,y2,求使得002,)(yxP112)(yxP==222)(yxP=,为求P2(x),将三点代入其表达式,即可得到三个方程式,从而联立方程组解出系数a0,a1,a2即可:方程组的解是否存在?若存在解,是否唯一?!当x0

,x1

,x2互异时,方程组的解存在且唯一.注：显然有,求n次插值时,由n+1个点可有n+1个方程,联立方程组即可求出插值多项式的n+1个系数.

然而,方程组的求解也并不是一件容易的事。1.2.1待定系数法

对于线性插值的两种形式解进行适当的分析,从中寻求规律而得到启发,就有了所谓的拉格朗日插值法(公式)和牛顿插值(公式).我们先来看看如何得到二次拉格朗日插值公式（和牛顿插值公式（为讨论方便，留待后述））.首先,线性插值的两点式可看作是两个特殊的一次式的一种线性组合.101xxxx--010xxxx--)(1xP=y0

+y1==10)(iiiyxl两点式l0(x)l1(x)实质上（）和（）即是满足函数表的一次插值多项式,称l0(x)和l1(x)为以x0,x1为节点的基本插值多项式，也称为线性插值的插值基函数。于是，线性插值即是用基函数的线性组合来构造的.1.2.2基函数法称为拉氏基函数，满足li(xj)=ij

显然有l0(x)+l0(x)≡1.这里，l0(x)和l1(x)具有如下性质：l0(x0)=1,l0(x1)=0,l1(x0)=0,l1(x1)=1,由此启发，我们希望二次插值也能由一些二次插值基函数来线性组合:这时，l0(x),l1(x),l2(x)都是二次多项式，且应满足满足(2.1)式的

li(x)是否存在?若存在，具有什么形式呢?（2.1）同理可得

l1(x)＝1(x－x0)(x－x2),

l2(x)＝2(x－x0)(x－x1),1＝(x1－x0)(x1－x2)12＝(x2－x0)(x2－x1)1此即二次拉格朗日插值公式,其中,l0(x),l1(x),l2(x)是满足(2.1)的特殊(基本)二次插值多项式;称为二次插值基函数.P2(x)=y0+y1+y2(x-x0)(x-x2)(x1-x0)(x1-x2)(x-x1)(x-x2)(x0-x1)(x0-x2)(x-x0)(x-x1)(x2-x0)(x2-x1)先考虑l0(x)。因l0(x)是以x1,x2

为零点的二次多项式,所以它可写成l0(x)＝0(x－x1)(x－x2),

其中0

是待定系数。又因为l0(x0)=1，所以0(x0－x1)(x0－x2)＝1，则可有0＝(x0－x1)(x0－x2)1

l0(x)＝0(x－x1)(x－x2),

n

1希望找到li(x)，i=0,…,n

使得

li(xj)=ij

；然后令==niiinyxlxP0)()(，则显然有Pn(xi)=

yi

。li(x)每个li有n

个根x0…

xi…xn=-=---=njjijiniiixxCxxxxxxCxl00)())...()...(()(-==jijiiiixxCxl)(11)(

拉格朗日多项式与有关，而与无关节点f1.3n

次插值定理(唯一性)满足的n

阶插值多项式是唯一存在的。证明：(存在性可利用Vandermonde

行列式论证)反证：若不唯一，则除了Ln(x)外还有另一n

阶多项式Pn(x)满足Pn(xi)=yi

。考察则Qn

的阶数n而Qn有个不同的根n+1x0…xn注：若不将多项式次数限制为n

，则插值多项式不唯一。例如也是一个插值多项式，其中可以是任意多项式。设节点在[a,b]内存在,考察截断误差，且f

满足条件,Rolle’sTheorem:若充分光滑，，则存在使得。推广：若使得使得存在使得Rn(x)至少有个根n+1=-=niinxxxKxR0)()()(任意固定x

xi(i=0,…,n),考察=-=niixtxKtRnt0)()()()(j(t)有n+2

个不同的根x0…

xn

x!)1()()()1(+-+nxKRxnnx注意这里是对t求导=+--++!)1)(()()()1()1(nxKLfxnnxnxx!)1()()()1(+=+nfxKxnx

1.4插值余项

(Remainder)注：

通常不能确定x

,而是估计,x(a,b)

将作为误差估计上限。当

f(x)为任一个次数n

的多项式时，,可知，即插值多项式对于次数n的多项式是精确的。例1

求经过A(0,1)，B(1,2)，C(2,3)三个插值点的插值多项式.解：三个插值节点及对应的函数值为由抛物插值公式得例2：已知分别利用sinx的1次、2次Lagrange插值计算sin50

并估计误差。解：n=1分别利用x0,x1

以及x1,x2

计算利用这里而sin50=0.7660444…)185(50sin10pL0.77614外推

(extrapolation)

的实际误差0.01001利用sin500.76008,内插

(interpolation)

的实际误差0.00596内插通常优于外推。选择要计算的x

所在的区间的端点，插值效果较好。n=2)185(50sin20pL0.76543sin50=0.7660444…2次插值的实际误差0.00061高次插值通常优于低次插值但绝对不是次数越高就越好，嘿嘿……

例3

考虑下述的插值法问题：求二次多项式P(x)，满足P(x0)=y0,其中是已给的数据并给出使这一问题的解存在且唯一的条件.解：设则由已知条件有即所以故原问题的唯一可解性就归结为上述方程组的唯一可解性而后者唯一可解的充要条件为这就是P（x）存在且唯一的条件。

Lagrange插值公式(利用插值基函数很容易得到):

含义直观,结构紧凑,在理论分析中非常方便;

计算机上实现也很容易.也有一些缺点：

一是计算量大，这是显然的；另外，还有一个更严重的缺点，当插值节点增加时，全部插值基函数均要随之变化，整个计算工作必须从头开始：不仅原来的每一项都要改变，还要增加一项计算。

为克服上述两个缺点,

努力：把插值多项式变形为便于计算的形式。希望：计算改变的过程中,尽可能能利用已有的计算结果.

下面我们将看到,这是可能的。我们可以有具有“承袭性”的所谓牛顿公式。)()(0010101xxxxyyyxP---+=)(001010xxxxxxy---+=(())fff[x0,x1]二次牛顿插值多项式我们再看线性插值的点斜式:)(00xxy-+=f[x0,x1]常数(差商)由此启发，我们希望二次插值也能类似地有有规律的组合表达式:P2(x)=0+1(x-x0)+2(x-x0)(x-x1)利用P2(x0)=y0有:0=y0,利用P2(x1)=y1有:1=0101xxxx--(())ff=f[x0,x1],利用P2(x2)=y2有:2=f[x0,x1]

(x2-x0)(x2-x1)

(x2-x0)(x2-x1)0xx2-(())ff

(x2-x0)-f[x0,x2]f[x0,x1]

x2-x1

=-=f[x0,x1,x2];P2(x)=f(x0)

+(x-x0)+(x-x0)(x-x1)

f[x0,x1]

f[x0,x1,x2]f[x0,x2]

x=x0时0注:1.事实上,从上述可看出二次牛顿插值公式是用待定系数法求得的;2.它也可看作是三个特殊函数的一种线性组合:P2(x)=f(x0)

+(x-x0)+(x-x0)(x-x1)

f[x0,x1]

f[x0,x1,x2]

f[x0,x1],

f[x0,x1,x2]f(x0),

1,(x-x0),(x-x0)(x-x1)即函数的线性组合,组合系数为本质上还是基函数法.更一般地，n+1个节点的插值多项式，我们希望由上述类似的一组特殊函数：来线性组合为：

1,(x-x0),(x-x0)(x-x1)，……，(x-x0)(x-x1)…(x-xn)那么其组合系数是什么样的呢？怎么求呢？我们同样可用待定系数法.容易发现,计算a0,a1,a2,…,an

是很有规律的.一、均差及其性质§2牛顿插值当x=x0时，Pn(x0)=a0=f0.当x=x1时，Pn(x1)=a0+a1(x1-x0)=f1,推得a1=f1-f0x1-x0当x=x2时，Pn(x2)=a0+a1(x2-x0)+a2(x2-x0)(x2-x1)=f2,推得f1-f0x1-x0-f1-f0x1-x0a2=x2-x1依次递推可得到a3,…,an.为写出系数ak的一般表达式,先引进如下均差定义.定义2

称为函数f(x)关于点x0,xk的一阶均差.称为f(x)的二阶均差.一般地,称为f(x)的k阶均差(差商).

f[x0,xk]=f(xk)-f(x0)xk-x0

f[x0,x1,xk]=f[x0,xk]-f[x0,x1]xk-x1

f[x0,x1,…,xk]=f[x0,…,xk-2,xk]-f[x0,x1,…,xk-1]xk-xk-1均差有如下的基本性质:

1ºk阶均差可表示为函数值f(x0),f(x1),…,f(xk)的线性组合,即

f[x0,x1,…,xk]=f(xj)(xj-xj+1)…(xj-xk)…(xj-xj+1)(xj-x0)∑

kj=0这个性质可用归纳法证明.这个性质也表明均差与节点的排列次序无关,称为均差的对称性,即

f[x0,x1,…,xk]=f[x1,x0,x2,…,xk]=…=f[x1,…,xk,x0]

f[x0,x1,…,xk]=f[x1,…,xk-1,xk]-f[x0,x1,…,xk-1]xk-x02º由性质1º可得:

f[x0,x1,…,xk]=f(n)(ξ)n!

3º若f(x)在[a,b]上存在n阶导数,且节点x0,x1,…,xn[a,b],则n阶均差与导数关系如下:这个公式可直接用罗尔定理证明.所以12…………n11+(x

x0)2+……+(x

x0)…(x

xn1)n1Nn(x)Rn(x)ai=

f[x0,…,xi]二、牛顿插值公式Rn(x)Nn(x)ωn+1(x)多项式Nn(x)显然满足插值条件,即Nn(xj)=f(xj),(j=1,…,n),且次数不超过n,由唯一性定理它就是前述的Ln(x),其系数为

Nn(x)称为牛顿均差插值多项式,它比拉格朗日插值多项式计算量省,且便于程序设计.注：

由唯一性可知Nn(x)Ln(x)，只是算法不同，故其余项也相同，即实际计算过程为f(x0)f(x1)f(x2)…f(xn1)f(xn)f[x0,x1]f[x1,x2]…………f[xn1,xn]f[x0,x1,x2]…………f[xn2,xn1,xn]f[x0,…,xn]

f(xn+1)f[xn,xn+1]f[xn1,xn,xn+1]f[x1,…,xn+1]f[x0,…,xn+1]均差计算可列均差表如下：

例1

依据如下函数值表建立不超过3次的拉格朗日插值多项式及牛顿插值多项式Nn(x),并验证插值多项式的唯一性.

解:(1)拉格朗日插值多项式Ln(x).插值基函数xk0124f(xk)19233拉格朗日插值多项式为:xkf(xk)

一阶均差二阶均差三阶均差0119822314343-10-8(2)牛顿插值多项式Nn(x).建立如下差商表牛顿插值多项式为:(3)唯一性验证.通过比较牛顿插值多项式和拉格朗日插值多项式,知:Nn(x)=Ln(x)这一事实与插值多项式的唯一性一致.2已知等距节点三、Newton等距插值1、差分定义简记为简记为简记为向前差分向后差分中心差分前差算子后差算子高阶向前差分高阶向后差分如2、高阶差分又如3、前差与后差的关系一般有再定义前移算子不变算子后移算子则有因此4差商与差分的关系m阶向前差商与m阶向前差分的关系查看全部m阶向后差商与m阶向后差分的关系又所以5、差分的计算6、等距节点的Newton插值已知等距节点得令由Newton插值公式其中参照即前插公式同理可得后插公式（P27)§3厄尔米特插值不仅要求函数值重合，而且要求若干阶导数也重合。即：要求插值函数

(x)

满足

(xi)=f(xi),’(xi)=f’(xi),…,(mi)(xi)=f

(mi)(xi).注：

N

个条件可以确定阶多项式。N

1要求在1个节点x0处直到m0

阶导数都重合的插值多项式即为Taylor多项式其余项为一般只考虑f

与f’的值。

当较大时用待定系数法求是困难的令为次多项式且满足其中且满足令为次多项式所以

为Hermite插值多项式。Kronecker（克罗内克）符号柏林科学院院士，巴黎科学院通讯院士，伦敦皇家学会外籍会员。主张分析学应奠基于算术，而算术的基础是整数。克罗内克名言：“上帝创造了整数，其余都是人做的工作”令则其中又则由（1）（2）得所以其中则所以令则又由得所以例已知求三次多项式满足解所以验证：练习：（P43（19））求四次多项式满足令解：在点0，1，2上做Lagrange插值函数则因此所以§4分段低次插值RememberwhatIhavesaid?IncreasingthedegreeofinterpolatingpolynomialwillNOTguaranteeagoodresult,sincehigh-degreepolynomialsareoscillating.例：在[5,5]上考察的Ln(x)。取

-5

-4

-3

-2

-1

0

1

2

3

4

5

-0.5

0

0.5

1

1.5

2

2.5

n

越大，端点附近抖动越大，称为Runge现象Ln(x)f(x)分段低次插值

分段线性插值

在每个区间上，用1阶多项式

(直线)逼近f(x):记，易证：当时，一致失去了原函数的光滑性。

分段Hermite插值

/*Hermitepiecewisepolynomials*/给定在上利用两点的y及y’构造3次Hermite函数导数一般不易得到。Howcanwemakeasmoothinterpolationwithoutaskingtoomuchfromf?Headache…2、分段线性插值设函数在节点：上的函数值为：记步