求生必备知识

1、第第1章章 插值方法插值方法 插值法是一种古老的数学方法。早在插值法是一种古老的数学方法。早在10001000多年前，我国历法上已经记载了应用一多年前，我国历法上已经记载了应用一次插值和二次插值的实例。次插值和二次插值的实例。拉格朗日（拉格朗日（LagrangeLagrange）、牛顿）、牛顿（NewtonNewton）、埃特金（）、埃特金（AitkenAitken）分别给出了）分别给出了不同的解决方法。不同的解决方法。 1.1 拉格朗日插值公式 1.2 牛顿插值公式 1.3 埃特金插值公式1.4 存在惟一性定理1.5 插值余项1.6 分段三次埃尔米特插值 1.7 三次样条插值1.8 应用实例

2、1.1 拉格朗日插值公式拉格朗日插值公式 拉格朗日（拉格朗日（Lagrange）插值公式）插值公式(以下统称为以下统称为Lagrange插值公式插值公式)的基本思想是，把的基本思想是，把pn(x)的构造问题转的构造问题转化为化为n+1个插值基函数个插值基函数li(x)(i=0,1,n)的构造。的构造。 图图11 插值多项式插值多项式 1.1.n n=1=1的情况的情况 已知函数已知函数y y= =f f( (x x) )在点在点x x0 0, ,x x1 1上的值为上的值为y y0 0, ,y y1 1， 要 求 多 项 式， 要 求 多 项 式y y= =p p1 1( (x x) ) ，

3、使， 使p p1 1( (x x0 0)=)=y y0 0, ,p p1 1( (x x1 1)=)=y y1 1。其几何意义，就是。其几何意义，就是通过两点通过两点A A( (x x0 0, ,y y0 0),),B B( (x x1 1, ,y y1 1) )的一条直线，的一条直线，如图如图1 12 2所示。所示。 图图12 一次插值多项式一次插值多项式 由直线两点式可知，通过由直线两点式可知，通过A，B的直线方程为的直线方程为 它也可变形为它也可变形为p1(x)=l0(x)y0+l1(x)y1 显然有：显然有：l0(x0)=l1(x1)=1，l0(x1)=l1(x0)=0，p1(x0)=

4、y0，p1(x1)=y1 )(1001010 xpxxxxyyyy(1.1)010110100)(,)(xxxxxlxxxxxl其中其中 我们称我们称l0(x)为点为点x0的一次插值基函数，的一次插值基函数，l1(x)为为点点x1的一次插值基函数。它们在对应的插值点上取的一次插值基函数。它们在对应的插值点上取值为值为1，而在另外的插值点上取值为，而在另外的插值点上取值为0。插值函数。插值函数p1(x)是这两个插值基函数的线性组合，其组合系数是这两个插值基函数的线性组合，其组合系数就是对应点上的函数值。这种形式的插值称作为拉就是对应点上的函数值。这种形式的插值称作为拉格朗日（格朗日（Lagran

5、ge）插值。）插值。 2.n=2的情况的情况 线性插值只利用两对值线性插值只利用两对值(x0,y0)及及(x1,y1)求得求得y=f(x)的近似值，误差较大。的近似值，误差较大。 p2(x0)=y0,p2(x1)=y1,p2(x2)=y2 p2(x)是是x的二次函数，称为二次插值多项式。的二次函数，称为二次插值多项式。通过三点的插值问题称为二次插值或抛物插值。通过三点的插值问题称为二次插值或抛物插值。3.一般情况一般情况我们看到，两个插值点可求出一次插值多项我们看到，两个插值点可求出一次插值多项式式p1(x)，而三个插值点可求出二次插值多项式，而三个插值点可求出二次插值多项式p2(x)。当插值

6、点增加到当插值点增加到n+1个时，我们可以利用个时，我们可以利用Lagrange插值方法写出插值方法写出n次插值多项次插值多项式式pn(x)，如下所示：，如下所示：knknknkjjjkjkknyxxxxxlyxp)()()(000 1.2 牛顿插值公式牛顿插值公式 xf(x)一阶差商一阶差商二阶差商二阶差商三阶差商三阶差商x0f(x0)x1f(x1)f(x0,x1)x2f(x2)f(x1,x2)f(x0,x1,x2)x3f(x3)f(x2,x3)f(x1,x2,x3)f(x0,x1,x2,x3)差商表差商表Newton插值算法如下：插值算法如下：inputx,(xi,yi),i=0,1,n。

7、y=y0,t=1。forj=1,n dot=t*(x-xj-1) for i=0,n-j doend y=y+y0*t endoutput (x,y),(xi,yi),i=0,1,n。 iijiixxyyyi1 Newton插值算法中的插值算法中的j循环由循环由三部分组成：计算三部分组成：计算(x-xj)的累积，存的累积，存入入t单元；内套一个单元；内套一个i循环用来依次计循环用来依次计算差商表中的各阶差商，存入算差商表中的各阶差商，存入yi单元；单元；y单元用于存放单元用于存放Newton公式中各项累公式中各项累加之和。加之和。 例例3 已知已知f(-1)=2,f(1)=1,f(2)=1，求

8、，求f(x)的的Newton插值多项式。插值多项式。解：解： 设设x0=-1,x1=1,x2=2, 则则 21) 1(121),(010110 xxyyxxf01211),(121221xxyyxxf61) 122/ 1(0),(),(),(021021210（）xxxxfxxfxxxf1.3 埃特金插值公式埃特金插值公式 埃特金埃特金( (Aitken) )插值公式插值公式( (以下统称以下统称为为Aitken插值公式插值公式) )的构造是基于这样的的构造是基于这样的直观想象：平面上的两个点可以连成一直观想象：平面上的两个点可以连成一条直线条直线, , 对应一个线性函数；把线性函对应一个线性

9、函数；把线性函数看作形式点数看作形式点, , 经线性组合经线性组合, , 可构成二可构成二次函数；把二次函数再看作形式点次函数；把二次函数再看作形式点, 经线经线性组合性组合, 可构成三次函数。可构成三次函数。 xf(x)x0f(x0)x1f(x1)P0,1(x)x2f(x2)P0,2(x)P0,1,2(x)x3f(x3)P0,3(x)P0,1,3(x)P0,1,2,3(x)Aitken 插值表插值表从从Aitken插值公式向算法转化要插值公式向算法转化要考虑的问题是：考虑的问题是：(1) 插值公式右端插值公式右端n-1次多项式应次多项式应如何处理；如何处理；(2) 插值表中的元素应设置多少插

10、值表中的元素应设置多少个存储单元；个存储单元；(3) 插值表中第插值表中第k列第列第i行元素的行元素的计算公式。计算公式。 Aitken插值算法如下：插值算法如下：input x,(xi,yi),i=0,1,n 1 kL：for i=k,k+1,n doendifknthen k+1 k, go to Lifk=n,output yn n 1ikkikikyxxxxyyy)(1111Aitken插值算法为二重循环。外循插值算法为二重循环。外循环为环为k循环，用于计算循环，用于计算Aitken插值表中插值表中的第的第k列；内循环列；内循环为为i循环，用于计算循环，用于计算Aitken插值表中的第

11、插值表中的第k列中的第列中的第i个元素。个元素。 例例4已知已知f(-1)=2,f(1)=1,f(2)=1,求求f(x)的的Aitken插值多项式。插值多项式。 解：设解：设x0=-1,x1=1,x2=2 23211111112)(1 , 0 xxxxp3512112122)(2,0 xxxxp) 83(61)(121)(212)(22 , 01 , 02 , 1 , 0 xxxpxxpxxpxf(x)-121121232x)832(61 xx35x例例4的的Aitken插值表插值表1.4 存在惟一性定理存在惟一性定理 Lagrange插值公式、插值公式、Newton和和Aitken插值插值多

12、项式是同一个函数。事实上多项式是同一个函数。事实上, 我们有以下一个我们有以下一个定理。定理。 定理定理1 有惟一的有惟一的n次多项式次多项式pn(x)，满足条件：，满足条件： pn(xi)=yi(i=0,1,n)（1.3） 1.5 插值余项插值余项 定理定理2 若若f(x)在包含着插值节点在包含着插值节点x0,x1,xn的的区间区间a,b上上n+1次可微分次可微分, 则对任意则对任意x,xa,b,有与有与x有关的有关的(ab)存在存在, 使得使得 其中其中(x)=(x-x0)(x-x1)(x-xn)。 )()!1()()()();()1(nnfnxxpxfxfE 例例 设设f(x)=lnx,

13、 并假定已给出值表试近并假定已给出值表试近似计算似计算ln(0.6)的值，并指出精度。的值，并指出精度。 解：利用解：利用3次次Lagrange 插值公式插值公式, 简单计算过简单计算过程如下：程如下： 值表值表x0.40.50.70.8lnx-0.916291-0.693147-0.356675-0.22314400391. 0)4 .234)(0004. 0(241)6 . 0 ;E4 .234)4 . 0/(6)(max,/6509975. 0)8 . 0(l61)7 . 0ln(32)5 . 0ln(32)4 . 0ln(61)6 . 0ln(61)6 . 0(),7 . 0)(5 .

14、 0)(4 . 0(012. 01)(32)6 . 0(),8 . 0)(5 . 0)(4 . 0(006. 01)(32)6 . 0(),8 . 0)(7 . 0)(4 . 0(006. 01)(61)6 . 0(),8 . 0)(7 . 0)(5 . 0(012. 01)(4)4(8 . 0, 4 . 04)4(33221100fxfxfnlxxxxllxxxxllxxxxllxxxxl（从而可得。所以又因为 综合上述综合上述, 我们有我们有真值：真值：ln(0.6)=-0.510826，近似值：近似值：p3(0.6)=-0.509975， 真误差：真误差：ln(0.6)-p3(0.6)=

15、-0.000851，估计的上界：估计的上界：|ln(0.6)-p3(0.6)| 0.00391 例例 给定给定 (x-5,5)。取等距节点取等距节点xi=-5+i(i=0,1,10), 试建立插值多项式试建立插值多项式L10(x), 并作图形并作图形, 观察观察L10(x)对对f(x)的逼近效果。的逼近效果。 211)(xxf所示。画出的图形如图解：31)()()()()()()()()()(101101011010010 xxxxxxxxxxxxxxxxxlxlxfxLiiiiiiiiiiii图图1-3 例例6的图形的图形1.6 分段三次埃尔米特插值分段三次埃尔米特插值 为了避免为了避免Ru

16、nge现象的发生现象的发生, 我们很自我们很自然地会想到把区间然地会想到把区间-5, 5等分为等分为10个小区个小区间间, 在每一个小区间内应用低次插值。但由在每一个小区间内应用低次插值。但由于每个小区间只有两个端点（插值节点）于每个小区间只有两个端点（插值节点）, 按照我们按照我们已知的方法已知的方法, 得到的将是一个分段得到的将是一个分段线性插值函数。线性插值函数。 已知已知xi,f(xi),f(xi)(i=0,1,n),求分段三次插值求分段三次插值函数函数H(x)满足满足H(xi)=f(xi),H(xi)=f(xi)(i=0,1,n) 为 了 得 到 插 值 函 数为 了 得 到 插 值

17、 函 数 , 考 虑 任 意 子 区 间考 虑 任 意 子 区 间xi,xi+1,i(0,1,n-1), 采用采用Lagrange插值函数插值函数结构结构, 在第在第i个子区间上个子区间上H(x)=f(xi)h1(x)+f(xi+1)h2(x)+f(xi)h3(x)+f(xi+1)h4(x) 这样，就把这样，就把H(x)的构造问题转化为四个插值的构造问题转化为四个插值基函数基函数hk(x)(k=1,2,3,4)的构造问题。的构造问题。 1.7 三次样条插值三次样条插值 “样条样条”这个词本来是指在飞机或轮船设计这个词本来是指在飞机或轮船设计过程中为了描绘出光滑的外形曲线所用的一过程中为了描绘出

18、光滑的外形曲线所用的一种工种工具，即一个具有弹性的细长木条。具，即一个具有弹性的细长木条。事实上，在作事实上，在作了某些近似简化后，样条的数学模型并不复杂，了某些近似简化后，样条的数学模型并不复杂，它只是分段的三次多项式曲线：在相邻两块压铁它只是分段的三次多项式曲线：在相邻两块压铁之间是三次多项式曲线；在压铁处，之间是三次多项式曲线；在压铁处，左右两段曲左右两段曲线的切线和曲率是连续的。线的切线和曲率是连续的。 定义定义 给定给定a,b的分划：的分划：a=x0 0 x1 1xn n=b, 如果函数如果函数s(x)在区间在区间a,b上满足以下条件：上满足以下条件： （1）在每一个子区间（）在每一

19、个子区间（xi i,xi+1i+1）(i=0,1,n-1) 上上s(x)是三次多项式；是三次多项式； （2） s(x)在区间在区间a,b上具有二阶连续导数；上具有二阶连续导数； （3）s(xi i)=yi i(i=0,1,n),s(x0 0)=y0,s(xn n)=yn n。我我们就称们就称s(x)为三次样条函数。为三次样条函数。 1.8 应用实例应用实例 例例9 要在程控铣床上加工直升飞机的旋要在程控铣床上加工直升飞机的旋转机翼，外形的截面形状见图转机翼，外形的截面形状见图1-4。外形头部有。外形头部有一 段 圆 弧一 段 圆 弧 B1B2， 圆 的 半 径， 圆 的 半 径 R=6.92mm，tan=0.305,B1,B2的坐标为的坐标为B1(0.52,5.288)，B2(2.6,-3.615)，截面上轮廓线，截面上轮廓线18个点的坐标如个点的坐标如表表1-8所示。旋转机翼外形截面图如图所示。旋转机翼外形截面图如图