插值方法精选课件.ppt

《插值方法精选课件.ppt》由会员分享，可在线阅读，更多相关《插值方法精选课件.ppt（81页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、关于插值方法第一页，本课件共有81页第二页，本课件共有81页第三页，本课件共有81页第四页，本课件共有81页第五页，本课件共有81页第六页，本课件共有81页第七页，本课件共有81页1.1 拉格朗日插值公式拉格朗日插值公式 拉格朗日插值公式的基本思想是:把Pn(x)的构造问题转化为n+1个插值基函数Li(x)（i=0,1,n)的构造。插值函数Pn(x)是这n1插值基函数的线性组合，其组合系数就是对应点上的函数值。第八页，本课件共有81页拉格朗日插值的算法：Input X,(Xi,Yi),I=1,1,n0S,1kFOR K=1 TO n t=1 FOR j=1 TO n jk .F.T.t*(X-

2、Xj)/(Xk-Xj)t S+t*Yk SOutput S第九页，本课件共有81页绘制拉格朗日插值基函数图形绘制拉格朗日插值基函数图形输入插值节点输入插值节点xi(0,n)输入插值点的个数输入插值点的个数 mh=(xm-x0)/(m-1)计算计算m个插值点上的插值基函数个插值点上的插值基函数l(i,k)和和 ll(k)=l(i,k)for k=0 to m xx(k)=x0+k*h ll(k)=0 for i=0 to n l(i,k)=1 for j=0 to n if ji l(i,k)=l(i,k)*(xx(k)-x(j)/(x(i)-x(j)end if next j ll(k)=ll

3、(k)+l(i,k)next Inext k 确定坐标确定坐标 绘制图形绘制图形第十页，本课件共有81页1.牛顿插值公式牛顿插值公式牛顿插值公式的基本思想是牛顿插值公式的基本思想是:把把P Pn n(x)(x)设设计为递推形式。计为递推形式。P Pn n(x)(x)P Pn-1n-1(x)+a(x)+an n(x-x(x-x0 0)(x-x)(x-xn-1n-1)=a =a0 0+a+a1 1(x-x(x-x0 0)+a)+a2 2(x-x(x-x0 0)(x-x)(x-x1 1)+)+a +an n(x-x(x-x0 0)(x-x)(x-xn-1n-1)满足满足P Pn n(x(xi i)=

4、f(x)=f(xi i)=Y)=Yi i i=0,1,2,ni=0,1,2,n 称为牛顿插值公式。称为牛顿插值公式。第十一页，本课件共有81页1.牛顿插值公式牛顿插值公式 为了简化上式，引进记号：为了简化上式，引进记号：0 0(x)=1 i i(x)=(x-xi-1i-1)i-1i-1(x)=(x-xx-x0 0)(x-x)(x-x1 1)(x-x)(x-xi-1i-1)i=1,2 i=1,2，n n P Pn n(x)(x)a a0 0 0 0(x)+a+a1 1 1 1(x)+a+an n n n(x)0 0(x),1 1(x),n n(x)称为牛顿插值以称为牛顿插值以x0 0,x1 1,

5、xn n为插值节点的为插值节点的基函数基函数。如果增加一个新节点，只需增加一个新项如果增加一个新节点，只需增加一个新项 a an n n n(x)第十二页，本课件共有81页1.牛顿插值公式牛顿插值公式其系数为各阶差商：第十三页，本课件共有81页不保留各阶差商的中间结果：For j=1 to n(计算各阶差商）For i=0 to n-j(计算J阶差商 中的每个差商）(Y(i+1)-Y(i)/(x(j+i)-x(i)Y(i)保留各阶差商的中间结果：For j=1 to n(计算各阶差商）For i=j to n(计算J阶差商 中的每个差商）y(j,i)=(y(j-1,i)-y(j-1,i-1)/

6、(x(i)-x(i-j)差商表差商表X f(x)一阶差商 二阶差商 三阶差商X0 f(x0)X1 f(x1)f(x0,x1)X2 f(x2)f(x1,x2)f(x0,x1,x2)X3 f(x3)f(x2,x3)f(x1,x2,x3)f(x0,x1,x2,x3)第十四页，本课件共有81页牛顿插值的算法(不保留各阶差商的中间结果）：Input X,(Xi,Yi),I=0,1,2,ny0y,1tFOR j=1 TO n t=t*(x-xj-1)FOR i=0 TO n-j yi=(yi+1-yi)/(xj+i-xi)y+t*Y0 yOutput y第十五页，本课件共有81页input 请输入的值：t

7、o xxuse sj n=reccount()dime x(n),y(n)k=1do while.not.eof()x(k)=ax y(k)=ay k=k+1 skipenddot=1s=y(1)j=1do while j=n t=t*(xx-x(j)i=1 do while i=n-j y(i)=(y(i+1)-y(i)/(x(j+i)-x(i)i=i+1 enddo s=s+t*y(1)j=j+1enddo?F(+str(xx,6,4)+)=+str(s,10,6)return*牛顿插值的程序：插值点数据存放在数据库文件SJ中第十六页，本课件共有81页牛顿插值的算法(保留并输出各阶差商）：

8、Input X,(Xi,Y0,i),I=0,1,2,nY0,iy,1tFOR j=1 TO n t=t*(x-xj-1)FOR i=j TO n y(j,i)=(y(j-1,i)-y(j-1,i-1)/(x(i)-x(i-j)y+t*Y(j,j)yOutput y(j,i),x,y第十七页，本课件共有81页1.3埃特金插值公式埃特金插值公式 埃特金插值公式的基本思想是：平面上的两个点可以连埃特金插值公式的基本思想是：平面上的两个点可以连成一条线，对应一个线性函数；把线性函数看作形式点，成一条线，对应一个线性函数；把线性函数看作形式点，经线性组合，可以构成二次函数；把二次函数看作形式经线性组合，

9、可以构成二次函数；把二次函数看作形式点，经线性组合，可以构成三次函数。因次埃特金插值点，经线性组合，可以构成三次函数。因次埃特金插值公式也叫公式也叫逐步线性插值逐步线性插值。过两点（过两点（X0,Y0),(X1,Y1）的一次线性插值函数为）的一次线性插值函数为:第十八页，本课件共有81页1.3埃特金插值公式埃特金插值公式过两点（X0,Y0),(X2,Y2）的一次线性插值函数为:过（X1,P0,1(x),(X2,P0,2(x)两形式上的点的线性插值函数为:第十九页，本课件共有81页1.3埃特金插值公式埃特金插值公式 对于一般情况：过两个形式点（对于一般情况：过两个形式点（Xn-1,P0,1,2,

10、n-1（x）和）和（Xn,P0,1,n-2,n(x)）的线性插值函数为）的线性插值函数为:第二十页，本课件共有81页1.3埃特金插值公式埃特金插值公式 Y(i)=(x-x(i)/(x(k-1)-x(i)*y(k-1)+(x-x(k-1)/(x(i)-x(k-1)*y(i)或 y(i)=y(k-1)+(y(i)-y(k-1)/(x(i)-x(k-1)*(x-x(k-1)埃特金插值表埃特金插值表X f(x)X0 f(x0)X1 f(x1)P0,1(x)X2 f(x2)P0,2(x)P0,1,2(x)X3 f(x3)P0,3(x)P0,1,3(x)P0,1,2,3(x)第二十一页，本课件共有81页埃

11、特金插值的算法：Input X,(Xi,Yi),I=0,1,2,nFOR k=1 TO n FOR i=k TO n y(i)=y(k-1)+(y(i)-y(k-1)/(x(i)-x(k-1)*(x-x(k-1)Output y(n)第二十二页，本课件共有81页1.4 存在唯一性定理存在唯一性定理 定理1 有惟一的n次多项式Pn(x)，满足条件：Pn(xi)=yi（i=0,1,n)第二十三页，本课件共有81页1.5 插值余项插值余项 设设Pn(x)是在点是在点X0,X1,，Xn处关于处关于f(x)f(x)的插值多项式，当的插值多项式，当X X XiXi时，时，f(x)f(x)与与 Pn(x)的

12、偏差的偏差Rn(x)f(x)f(x)Pn(x)，称为，称为插值余项。插值余项。定理定理 2 若若f(x)f(x)在在包含插值节点包含插值节点X X0,X,X1,，X Xn的区间的区间a,ba,b上上n+1n+1次可微分，则对任意次可微分，则对任意x,xx,x a,b,a,b,有与有与x x有关的有关的(a(a b)b)存在，使得：存在，使得：R Rn(x)=(x)=f(x)f(x)Pn(x)其中其中(x)=(x-x0)(x-x1)(x-xn)第二十四页，本课件共有81页随着插值次数的增高,插值余项的变化因被插值函数的不同而异。例如对于被插值函数 在两个端点x=5和x=-5的附近插值函数P10(

13、x)与原函数 偏离很远。而在-2，2范围内，P10(x)能较好地逼近f(x)。这说明插值多项式这说明插值多项式P P1010(x)(x)对对f(x)f(x)的近似效果并不是随着的近似效果并不是随着插值次数的增高而增高的。插值次数的增高而增高的。随着插值次数的增高，在段点处插值函数与原函数偏离原大的现象称为高次插值的龙格现象高次插值的龙格现象。高次插值的高次插值的SinSin现象现象说明的是插值次数越高插值多项式Pn(x)对函数Sin(x)的逼近效果越好。当插值函数高到一定的次数后，插值函数的曲线和原函数的曲线就完全重叠。第二十五页，本课件共有81页输入插值节点输入插值节点xi(0,n)计算插值

14、节点上的原函数计算插值节点上的原函数yi(0,n)输入插值点的个数输入插值点的个数mh=(xn-x0)/(m-1)计算插值点上的插值基函数计算插值点上的插值基函数l、插值函数、插值函数ll(k)和原函数和原函数yy(k)for k=0 to m xx(k)=x0+i*h ll(k)=0 for i=0 to n l=1 for j=0 to n if ji l=l*(xx(k)-x(j)/(x(i)-x(j)end if next j ll(k)=ll(k)+l*y(i)next I yy(k)=1/(1+xx(k)*xx(k)next k确定坐标确定坐标绘制图形绘制图形第二十六页，本课件共有

15、81页 1.6 分段三次埃尔米特插值分段三次埃尔米特插值为了避免龙格现象的发生，我们很自然地会想为了避免龙格现象的发生，我们很自然地会想到把区间到把区间5，5等分为等分为10个小区间，在每一个小区间，在每一个小区间内应用低次插之。但因为每个小区间只有个小区间内应用低次插之。但因为每个小区间只有两个端点，按照我们已知的方法，得到的将是一个两个端点，按照我们已知的方法，得到的将是一个分段线性插值函数，这显然不能满足对任意一个曲分段线性插值函数，这显然不能满足对任意一个曲线函数的逼近要求。要想在每一个区间得到一个曲线函数的逼近要求。要想在每一个区间得到一个曲线函数，不仅要利用插值节点处的函数值，还要

16、用线函数，不仅要利用插值节点处的函数值，还要用到插值节点处的导数值，这就是到插值节点处的导数值，这就是分段三次埃尔米特分段三次埃尔米特（Hermite）插值问题。）插值问题。第二十七页，本课件共有81页1.6 分段三次埃尔米特插值分段三次埃尔米特插值 已知已知xi,f(xi),f(xi)(i=0,1,2,n)，求三次插值函数求三次插值函数H(x)H(x)满足：满足：H(xi)=f(xi)，H(xi)=f(xi)(i=0,1,2,n)在任意的子区间在任意的子区间Xi,Xi+1,i(0,1,2,n-1)上上构造插值函数构造插值函数 H(x)=f(xi)h1(x)+f(xi)h2(x)+f(xi)h

17、3(x)+f(xi+1)h4(x)hk(x)(k=1,2,3,4)称为称为埃尔米特插值的插值基函数埃尔米特插值的插值基函数。根据插值函数根据插值函数H(x)所满足的条件，可以确定插值基函数，从所满足的条件，可以确定插值基函数，从而确定插值函数。而确定插值函数。第二十八页，本课件共有81页第二十九页，本课件共有81页第三十页，本课件共有81页第三十一页，本课件共有81页第三十二页，本课件共有81页第三十三页，本课件共有81页1.6 分段三次埃尔米特插值分段三次埃尔米特插值 第三十四页，本课件共有81页1.6 分段三次埃尔米特插值分段三次埃尔米特插值 第三十五页，本课件共有81页分段三次埃尔米特插

18、值的算法：输入插值节点输入插值节点xi(i=0,n)计算插值节点上的原函数计算插值节点上的原函数f(xi)和其和其输入插值点的个数输入插值点的个数mfor i=0 to n-1 h=(xi+1-xi)/(m-1)for k=0 to m x=xi+h*k ll(k)=h1f(xi)+h2f(xi+1)+h3f(xi)+h4f(xi+1)yy(k)=1/(1+x2)next k 绘制曲线绘制曲线 next i 第三十六页，本课件共有81页1.7 三次样条插值三次样条插值 “样条样条”是指在工业设计过程中为了描绘出光是指在工业设计过程中为了描绘出光滑的外形曲线所用的一种工具，即一个具有弹性滑的外形

19、曲线所用的一种工具，即一个具有弹性的细长木条。的细长木条。绘图员首先把一串有序点标在平面上，让样条依次绘图员首先把一串有序点标在平面上，让样条依次通过这串点，并在每个点上压一块重的压铁，然后通过这串点，并在每个点上压一块重的压铁，然后用铅笔沿着这样一根样条绘出一条光滑的曲线。用铅笔沿着这样一根样条绘出一条光滑的曲线。第三十七页，本课件共有81页1.7 三次样条插值三次样条插值 人们由此得到启发：如果建立起样条的数学模型，人们由此得到启发：如果建立起样条的数学模型，并编成程序存放在计算机中，那么只要输入一串有并编成程序存放在计算机中，那么只要输入一串有序点列的坐标，再经过一些简单的计算，绘图机便

20、序点列的坐标，再经过一些简单的计算，绘图机便能划出一条光滑的曲线。能划出一条光滑的曲线。这样的数学模型经简化后为分段三次多项式，在节这样的数学模型经简化后为分段三次多项式，在节点处左右两端的曲线的切线和曲率是连续的，这种点处左右两端的曲线的切线和曲率是连续的，这种模型称为三次样条函数。模型称为三次样条函数。第三十八页，本课件共有81页1.7 三次样条插值三次样条插值 定义：给定定义：给定a,ba,b的划分：的划分：a=xa=x0 0 xx1 1xxn n=b,=b,如果函数如果函数S(x)S(x)在区间在区间a,ba,b上满足以下条件：上满足以下条件：1.1.在每一个子区间（在每一个子区间（X

21、 Xi i,X,Xi+1i+1）(i=1,2,n-1)(i=1,2,n-1)上上S(x)S(x)是是三次多项式；三次多项式；2.S(x)2.S(x)在区间在区间a,ba,b上具有连续的二阶导数；上具有连续的二阶导数；3.S(x)=Y3.S(x)=Yi i(i=0,1,2,n),S(x(i=0,1,2,n),S(x0 0)=y)=y0 0,S(x,S(xn n)=y)=yn n我们称我们称S(x)S(x)为三次样条函数。为三次样条函数。第三十九页，本课件共有81页其中其中第四十页，本课件共有81页第四十一页，本课件共有81页其中其中第四十二页，本课件共有81页第四十三页，本课件共有81页第四十四

22、页，本课件共有81页第四十五页，本课件共有81页第四十六页，本课件共有81页第四十七页，本课件共有81页第四十八页，本课件共有81页第四十九页，本课件共有81页第五十页，本课件共有81页第五十一页，本课件共有81页第五十二页，本课件共有81页第五十三页，本课件共有81页第五十四页，本课件共有81页第五十五页，本课件共有81页第五十六页，本课件共有81页第五十七页，本课件共有81页第五十八页，本课件共有81页第五十九页，本课件共有81页1.8 应用实例应用实例 例：要在程控铣床上加工直升飞机的旋转机翼，给出了例：要在程控铣床上加工直升飞机的旋转机翼，给出了1818个点的外形轮廓，以及头部外形的轮

23、廓为半径个点的外形轮廓，以及头部外形的轮廓为半径R=6.92mmR=6.92mm，TanTan 0.305,B1(0.52,5.288),B2(2.6,-3.615).0.305,B1(0.52,5.288),B2(2.6,-3.615).第六十页，本课件共有81页 第六十一页，本课件共有81页 解解:要在程控铣床上加工工件要在程控铣床上加工工件,必须计算出整个外必须计算出整个外形曲线足够密的点的坐标值。根据所给条件，头形曲线足够密的点的坐标值。根据所给条件，头部圆弧部圆弧B B1 1B B2 2可由圆的方程直接计算出点的坐标，其可由圆的方程直接计算出点的坐标，其余部分必须根据给出的点，利用插

24、值方法计算加余部分必须根据给出的点，利用插值方法计算加密点的坐标。密点的坐标。第六十二页，本课件共有81页现在先讨论头部圆弧现在先讨论头部圆弧B1B2的计算方法。根据所给条的计算方法。根据所给条件，可求得圆心坐标（件，可求得圆心坐标（X0，Y0)如下如下:第六十三页，本课件共有81页第六十四页，本课件共有81页 下面主要讨论如何根据表函数，应用插值多项式，下面主要讨论如何根据表函数，应用插值多项式，计算曲线上点的坐标。由于上下轮廓处理方法是计算曲线上点的坐标。由于上下轮廓处理方法是一样的，因此我们只讨论上轮廓的计算。一样的，因此我们只讨论上轮廓的计算。我们己知上轮廓线我们己知上轮廓线1818个

25、点的坐标，加上与头部连个点的坐标，加上与头部连接的接的B B1 1，点共有，点共有1919个点。为了在整个区间加密函个点。为了在整个区间加密函数值，是不是必须按上面所讲的数值，是不是必须按上面所讲的1919个点做一个个点做一个1818次的插值多项式次的插值多项式?这取决于对插值函数的性质分析。这取决于对插值函数的性质分析。在解决实际问题中，关键的一点就是要善于对具体在解决实际问题中，关键的一点就是要善于对具体问题进行具体的析。为此，先作出差商表以便分析。问题进行具体的析。为此，先作出差商表以便分析。第六十五页，本课件共有81页 从差商表可以看到，除插值区间两端外，四阶从差商表可以看到，除插值区

26、间两端外，四阶差商均近似于差商均近似于0 0，而在区间，而在区间28.65,50728.65,507中，三中，三阶差商也近似于阶差商也近似于0 0，这说明被插值函数并不是一，这说明被插值函数并不是一条高次曲线。条高次曲线。实际上，三阶差商也近似于实际上，三阶差商也近似于0 0的部分，曲线与二次抛的部分，曲线与二次抛抛线近似。如果用高次多项式近似，不仅计算量增抛线近似。如果用高次多项式近似，不仅计算量增大，效果反而不好。大，效果反而不好。因此，对这种情况我们一般不采用高阶插值，也因此，对这种情况我们一般不采用高阶插值，也就是说不去做就是说不去做1818次插值多项式，而是采用分段次插值多项式，而是

27、采用分段插值的办法。插值的办法。第六十六页，本课件共有81页 即根据被插值函数的不同变化趋势，把整个插值区即根据被插值函数的不同变化趋势，把整个插值区间分成若干段，分别采用低次插值多项式做各段的间分成若干段，分别采用低次插值多项式做各段的近似函数，然后再由各段插值多项计算各段加密点近似函数，然后再由各段插值多项计算各段加密点的坐标。的坐标。根据本例给出的曲线图形和差商表的情况，这个问根据本例给出的曲线图形和差商表的情况，这个问题可将区间分成三段考虑，即题可将区间分成三段考虑，即0.52,28.65,28.650.52,28.65,28.65，507,507507,507，520520。第六十七

28、页，本课件共有81页 现在先考虑区间现在先考虑区间28.65,507 28.65,507。由于三阶差商近似于由于三阶差商近似于0 0，故可考虑用二次插值，即，故可考虑用二次插值，即每相邻三个点每相邻三个点X Xk k,X,Xk+1k+1,X,Xk+2k+2为插值点做一个二次插值为插值点做一个二次插值多项式，作为多项式，作为XXk k,X,Xk+2k+2 区间上函数区间上函数Y=f(x)Y=f(x)的近似的近似值。值。这样处理能否满足精度要求，还要估计误差。我们以这样处理能否满足精度要求，还要估计误差。我们以区间区间x4x4，x6x6为例进行分析，以插值点为例进行分析，以插值点 x x4 4=2

29、8.65=28.65，X X5 5=39.62=39.62，x x6 6=50.65=50.65，确定二次插值多项式，由，确定二次插值多项式，由NewdonNewdon插值多项式，有插值多项式，有:第六十八页，本课件共有81页第六十九页，本课件共有81页基本上能满足加工精度要求。从差商表看到，在区间基本上能满足加工精度要求。从差商表看到，在区间xx4 4，x x1717 中三阶差商都比中三阶差商都比0.0000230.000023小。因此，不必每个区小。因此，不必每个区间都进行分析，即可认为在这一段采用二次插值是合间都进行分析，即可认为在这一段采用二次插值是合适的。由适的。由NewdonNew

30、don插值公式得：插值公式得：这里这里K=4K=4，5 5，1616。用这个公式计算区间。用这个公式计算区间XX4 4,X,X1717 上的函数上的函数值，即用值，即用Y=PY=P2 2(x)(x)的值作为的值作为Y=f(x)Y=f(x)的近似值。这就解决了区间的近似值。这就解决了区间X4,X17这一段曲线点的加密计算问题。这一段曲线点的加密计算问题。第七十页，本课件共有81页 下面讨论与头部连接部分的计算，也就是区间下面讨论与头部连接部分的计算，也就是区间xx0 0，x x4 4 这一段。这一段。当区间当区间x=xx=x0 0时曲线与圆弧时曲线与圆弧B Bl lB B2 2相连接，通常除了要

31、相连接，通常除了要求函数值相等外，还必须要求在求函数值相等外，还必须要求在B B1 1处相切，即导处相切，即导数值必须相等。因此，我们将区间数值必须相等。因此，我们将区间xx0 0，x x4 4 分成分成两段两段xx0 0，x x2 2 和和xx2 2，x x4 4 讨论。讨论。首先讨论首先讨论xx0 0，x x2 2 区间。在区间区间。在区间xx0 0，x x2 2 上构造插上构造插值多项式值多项式P(x)P(x)使其满足条件使其满足条件:第七十一页，本课件共有81页第七十二页，本课件共有81页第七十三页，本课件共有81页第七十四页，本课件共有81页第七十五页，本课件共有81页第七十六页，本

32、课件共有81页通过上面分段插值的方法，可以把整个机翼截面曲线通过上面分段插值的方法，可以把整个机翼截面曲线加密点的坐标计算出来。具体计算只要根据各段所得加密点的坐标计算出来。具体计算只要根据各段所得到的让算公式拍成程序，在计算机上进行计算即可。到的让算公式拍成程序，在计算机上进行计算即可。第七十七页，本课件共有81页 至于计算结果是否满足要求，还应通过实践检验。至于计算结果是否满足要求，还应通过实践检验。分段插值只能保证插值曲线的连续性，不能保分段插值只能保证插值曲线的连续性，不能保证曲线的光滑性，即导数不连续。证曲线的光滑性，即导数不连续。如果对精度要求高，就可以采用样条函数。如果对精度要求高，就可以采用样条函数。第七十八页，本课件共有81页第七十九页，本课件共有81页第八十页，本课件共有81页感感谢谢大大家家观观看看第八十一页，本课件共有81页