《第1章插值方法精选文档.ppt》由会员分享，可在线阅读，更多相关《第1章插值方法精选文档.ppt（74页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第1章插值方法本讲稿第一页，共七十四页1.1 拉格朗日插值公式拉格朗日插值公式 拉格朗日插值公式的基本思想是:把Pn(x)的构造问题转化为n+1个插值基函数Li(x)（i=0,1,n)的构造。插值函数Pn(x)是这n1插值基函数的线性组合，其组合系数就是对应点上的函数值。本讲稿第二页，共七十四页拉格朗日插值的算法：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-Xj)/(Xk-Xj)t S+t*Yk SOutput S本讲稿第三页，共七十四页绘制拉格朗日插值基函数图形绘制拉格朗日插值基函数图形输入插值
2、节点输入插值节点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(k)+l(i,k)next Inext k 确定坐标确定坐标 绘制图形绘制图形本讲稿第四页，共七十四页1.牛顿插值公式牛顿插值公式牛顿插值公
3、式的基本思想是牛顿插值公式的基本思想是:把把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)=f(x)=f(xi i)=Y)=Yi i i=0,1,2,i=0,1,2,n,n 称为牛顿插值公式。称为牛顿插值公式。本讲稿第五页，共七十四页1.
4、牛顿插值公式牛顿插值公式 为了简化上式，引进记号：为了简化上式，引进记号：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,xn n为插值节点的为插值节点的基函数基函数。如果增加一个新节点，只需增加一个新项如果增加一个新节点，只需增加一个新项 a an n n n(x)本
5、讲稿第六页，共七十四页1.牛顿插值公式牛顿插值公式其系数为各阶差商：本讲稿第七页，共七十四页不保留各阶差商的中间结果：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)/(x(i)-x(i-j)差商表差商表X f(x)一阶差商 二阶差商 三阶差商X0 f(x0)X1 f(x1)f(x0,x1)X2 f(x2)f(x1,x
6、2)f(x0,x1,x2)X3 f(x3)f(x2,x3)f(x1,x2,x3)f(x0,x1,x2,x3)本讲稿第八页，共七十四页牛顿插值的算法(不保留各阶差商的中间结果）：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本讲稿第九页，共七十四页input 请输入的值：to xxuse sj n=reccount()dime x(n),y(n)k=1do while.not.eof()x(k)=ax y(k)=ay k=k+
7、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中本讲稿第十页，共七十四页牛顿插值的算法(保留并输出各阶差商）：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)
8、=(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本讲稿第十一页，共七十四页1.3埃特金插值公式埃特金插值公式 埃特金插值公式的基本思想是：平面上的两个点可以连成一埃特金插值公式的基本思想是：平面上的两个点可以连成一条线，对应一个线性函数；把线性函数看作形式点，经线性条线，对应一个线性函数；把线性函数看作形式点，经线性组合，可以构成二次函数；把二次函数看作形式点，经线性组合，可以构成二次函数；把二次函数看作形式点，经线性组合，可以构成三次函数。因次埃特金插值公式也叫组合，可以构成三次函数。因次埃特金插值公式也叫逐步线逐步
9、线性插值性插值。过两点（过两点（X0,Y0),(X1,Y1）的一次线性插值函数为）的一次线性插值函数为:本讲稿第十二页，共七十四页1.3埃特金插值公式埃特金插值公式过两点（X0,Y0),(X2,Y2）的一次线性插值函数为:过（X1,P0,1(x),(X2,P0,2(x)两形式上的点的线性插值函数为:本讲稿第十三页，共七十四页1.3埃特金插值公式埃特金插值公式 对于一般情况：过两个形式点（对于一般情况：过两个形式点（Xn-1,P0,1,2,n-1（x）和）和（Xn,P0,1,n-2,n(x)）的线性插值函数为）的线性插值函数为:本讲稿第十四页，共七十四页1.3埃特金插值公式埃特金插值公式 Y(i
10、)=(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)本讲稿第十五页，共七十四页埃特金插值的算法：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
11、-1)/(x(i)-x(k-1)*(x-x(k-1)Output y(n)本讲稿第十六页，共七十四页1.4 存在唯一性定理存在唯一性定理 定理1 有惟一的n次多项式Pn(x)，满足条件：Pn(xi)=yi（i=0,1,n)本讲稿第十七页，共七十四页1.5 插值余项插值余项 设设Pn(x)是在点是在点X0,X1,，Xn处关于处关于f(x)f(x)的插值多项式，当的插值多项式，当X X XiXi时，时，f(x)f(x)与与 Pn(x)的偏差的偏差Rn(x)f(x)f(x)Pn(x)，称为插，称为插值余项。值余项。定理定理 2 若若f(x)f(x)在在包含插值节点包含插值节点X X0,X,X1,，X
12、 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)本讲稿第十八页，共七十四页随着插值次数的增高,插值余项的变化因被插值函数的不同而异。例如对于被插值函数 在两个端点x=5和x=-5的附近插值函数P10(x)与原函数 偏离很远。而在-2，2范围内，P10(x)能较好地逼近f(x)。这说明插值多项式这说明插值多项式P P1010(x)(x)对对f(x)f(x)的近似效果
13、并不是随着插值次的近似效果并不是随着插值次数的增高而增高的数的增高而增高的。随着插值次数的增高，在段点处插值函数与原函数偏离原大的现象称为高次插值的龙格现象高次插值的龙格现象。高次插值的高次插值的SinSin现象现象说明的是插值次数越高插值多项式Pn(x)对函数Sin(x)的逼近效果越好。当插值函数高到一定的次数后，插值函数的曲线和原函数的曲线就完全重叠。本讲稿第十九页，共七十四页输入插值节点输入插值节点xi(0,n)计算插值节点上的原函数计算插值节点上的原函数yi(0,n)输入插值点的个数输入插值点的个数mh=(xn-x0)/(m-1)计算插值点上的插值基函数计算插值点上的插值基函数l、插值
14、函数、插值函数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确定坐标确定坐标绘制图形绘制图形本讲稿第二十页，共七十四页 1.6 分段三次埃尔米特插值分段三次埃尔米特插值为了避免龙格现象的发生，我们很自然地会想到为了避免龙格现象的发生，我们很自然地会想到把区间把区间5，5等分为等分为1
15、0个小区间，在每一个个小区间，在每一个小区间内应用低次插之。但因为每个小区间只有小区间内应用低次插之。但因为每个小区间只有两个端点，按照我们已知的方法，得到的将是一两个端点，按照我们已知的方法，得到的将是一个分段线性插值函数，这显然不能满足对任意一个分段线性插值函数，这显然不能满足对任意一个曲线函数的逼近要求。要想在每一个区间得到个曲线函数的逼近要求。要想在每一个区间得到一个曲线函数，不仅要利用插值节点处的函数值，一个曲线函数，不仅要利用插值节点处的函数值，还要用到插值节点处的导数值，这就是还要用到插值节点处的导数值，这就是分段三次分段三次埃尔米特埃尔米特（Hermite）插值问题。）插值问题
16、。本讲稿第二十一页，共七十四页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)h3(x)+f(xi+1)h4(x)hk(x)(k=1,2,3,4)称为称为埃尔米特插值的插值基函数埃尔米特插值的插值基函数。根据插值函数根据插值函数H(x)所满足的条件，可
17、以确定插值基函数，从而确所满足的条件，可以确定插值基函数，从而确定插值函数。定插值函数。本讲稿第二十二页，共七十四页本讲稿第二十三页，共七十四页本讲稿第二十四页，共七十四页本讲稿第二十五页，共七十四页本讲稿第二十六页，共七十四页本讲稿第二十七页，共七十四页1.6 分段三次埃尔米特插值分段三次埃尔米特插值 本讲稿第二十八页，共七十四页1.6 分段三次埃尔米特插值分段三次埃尔米特插值 本讲稿第二十九页，共七十四页分段三次埃尔米特插值的算法：输入插值节点输入插值节点xi(i=0,n)计算插值节点上的原函数计算插值节点上的原函数f(xi)和其和其输入插值点的个数输入插值点的个数mfor i=0 to
18、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 本讲稿第三十页，共七十四页1.7 三次样条插值三次样条插值 “样条样条”是指在工业设计过程中为了描绘出光是指在工业设计过程中为了描绘出光滑的外形曲线所用的一种工具，即一个具有弹性滑的外形曲线所用的一种工具，即一个具有弹性的细长木条。的细长木条。绘图员首先把一串有序点标在平面上，让样条依次绘图员首先把一串有序点标在平面上，让样条依次通过这串点，并在每个点上压
19、一块重的压铁，然后通过这串点，并在每个点上压一块重的压铁，然后用铅笔沿着这样一根样条绘出一条光滑的曲线。用铅笔沿着这样一根样条绘出一条光滑的曲线。本讲稿第三十一页，共七十四页1.7 三次样条插值三次样条插值 人们由此得到启发：如果建立起样条的数学模型，人们由此得到启发：如果建立起样条的数学模型，并编成程序存放在计算机中，那么只要输入一串有并编成程序存放在计算机中，那么只要输入一串有序点列的坐标，再经过一些简单的计算，绘图机便序点列的坐标，再经过一些简单的计算，绘图机便能划出一条光滑的曲线。能划出一条光滑的曲线。这样的数学模型经简化后为分段三次多项式，在这样的数学模型经简化后为分段三次多项式，在
20、节点处左右两端的曲线的切线和曲率是连续的，节点处左右两端的曲线的切线和曲率是连续的，这种模型称为三次样条函数。这种模型称为三次样条函数。本讲稿第三十二页，共七十四页1.7 三次样条插值三次样条插值 定义：给定定义：给定a,ba,b的划分：的划分：a=xa=x0 0 xx1 1 xxn n=b,=b,如果函数如果函数S(x)S(x)在区间在区间a,ba,b上满足以下条件：上满足以下条件：1.1.在每一个子区间（在每一个子区间（X Xi i,X,Xi+1i+1）(i=1,2,(i=1,2,n-1),n-1)上上S(x)S(x)是三次是三次多项式；多项式；2.S(x)2.S(x)在区间在区间a,ba
21、,b上具有连续的二阶导数；上具有连续的二阶导数；3.S(x)=Y3.S(x)=Yi i(i=0,1,2,(i=0,1,2,n),S(x,n),S(x0 0)=y)=y0 0,S(x,S(xn n)=y)=yn n我们称我们称S(x)S(x)为三次样条函数。为三次样条函数。本讲稿第三十三页，共七十四页其中其中本讲稿第三十四页，共七十四页本讲稿第三十五页，共七十四页其中其中本讲稿第三十六页，共七十四页本讲稿第三十七页，共七十四页本讲稿第三十八页，共七十四页本讲稿第三十九页，共七十四页本讲稿第四十页，共七十四页本讲稿第四十一页，共七十四页本讲稿第四十二页，共七十四页本讲稿第四十三页，共七十四页本讲稿
22、第四十四页，共七十四页本讲稿第四十五页，共七十四页本讲稿第四十六页，共七十四页本讲稿第四十七页，共七十四页本讲稿第四十八页，共七十四页本讲稿第四十九页，共七十四页本讲稿第五十页，共七十四页本讲稿第五十一页，共七十四页本讲稿第五十二页，共七十四页本讲稿第五十三页，共七十四页1.8 应用实例应用实例 例：要在程控铣床上加工直升飞机的旋转机翼，给出了例：要在程控铣床上加工直升飞机的旋转机翼，给出了1818个点个点的外形轮廓，以及头部外形的轮廓为半径的外形轮廓，以及头部外形的轮廓为半径R=6.92mmR=6.92mm，TanTan 0.305,B1(0.52,5.288),B2(2.6,-3.615)
23、.0.305,B1(0.52,5.288),B2(2.6,-3.615).本讲稿第五十四页，共七十四页 本讲稿第五十五页，共七十四页 解解:要在程控铣床上加工工件要在程控铣床上加工工件,必须计算出整个外形必须计算出整个外形曲线足够密的点的坐标值。根据所给条件，头部曲线足够密的点的坐标值。根据所给条件，头部圆弧圆弧B B1 1B B2 2可由圆的方程直接计算出点的坐标，其余部可由圆的方程直接计算出点的坐标，其余部分必须根据给出的点，利用插值方法计算加密点的坐分必须根据给出的点，利用插值方法计算加密点的坐标。标。本讲稿第五十六页，共七十四页现在先讨论头部圆弧现在先讨论头部圆弧B1B2的计算方法。根
24、据所给条件，的计算方法。根据所给条件，可求得圆心坐标（可求得圆心坐标（X0，Y0)如下如下:本讲稿第五十七页，共七十四页本讲稿第五十八页，共七十四页 下面主要讨论如何根据表函数，应用插值多项式，下面主要讨论如何根据表函数，应用插值多项式，计算曲线上点的坐标。由于上下轮廓处理方法是计算曲线上点的坐标。由于上下轮廓处理方法是一样的，因此我们只讨论上轮廓的计算。一样的，因此我们只讨论上轮廓的计算。我们己知上轮廓线我们己知上轮廓线1818个点的坐标，加上与头部连接的个点的坐标，加上与头部连接的B B1 1，点共有，点共有1919个点。为了在整个区间加密函数值，个点。为了在整个区间加密函数值，是不是必须
25、按上面所讲的是不是必须按上面所讲的1919个点做一个个点做一个1818次的插次的插值多项式值多项式?这取决于对插值函数的性质分析。在这取决于对插值函数的性质分析。在解决实际问题中，关键的一点就是要善于对具体解决实际问题中，关键的一点就是要善于对具体问题进行具体的析。为此，先作出差商表以便分问题进行具体的析。为此，先作出差商表以便分析。析。本讲稿第五十九页，共七十四页 从差商表可以看到，除插值区间两端外，四阶差商均从差商表可以看到，除插值区间两端外，四阶差商均近似于近似于0 0，而在区间，而在区间28.65,50728.65,507中，三阶差商中，三阶差商也近似于也近似于0 0，这说明被插值函数
26、并不是一条高次，这说明被插值函数并不是一条高次曲线。曲线。实际上，三阶差商也近似于实际上，三阶差商也近似于0 0的部分，曲线与二次的部分，曲线与二次抛抛线近似。如果用高次多项式近似，不仅计算抛抛线近似。如果用高次多项式近似，不仅计算量增大，效果反而不好。量增大，效果反而不好。因此，对这种情况我们一般不采用高阶插值，也因此，对这种情况我们一般不采用高阶插值，也就是说不去做就是说不去做1818次插值多项式，而是采用分段插值次插值多项式，而是采用分段插值的办法。的办法。本讲稿第六十页，共七十四页 即根据被插值函数的不同变化趋势，把整个插值区即根据被插值函数的不同变化趋势，把整个插值区间分成若干段，分
27、别采用低次插值多项式做各段的间分成若干段，分别采用低次插值多项式做各段的近似函数，然后再由各段插值多项计算各段加密点近似函数，然后再由各段插值多项计算各段加密点的坐标。的坐标。根据本例给出的曲线图形和差商表的情况，这个问根据本例给出的曲线图形和差商表的情况，这个问题可将区间分成三段考虑，即题可将区间分成三段考虑，即0.52,28.65,28.650.52,28.65,28.65，507,507507,507，520520。本讲稿第六十一页，共七十四页 现在先考虑区间现在先考虑区间28.65,507 28.65,507。由于三阶差商近似于由于三阶差商近似于0 0，故可考虑用二次插值，即，故可考虑
28、用二次插值，即每相邻三个点每相邻三个点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=28.65=28.65，X X5 5=39.62=39.62，x x6 6=50.65=50.65，确定二次插值多项式，由，确定二次插值多项式，由NewdonNewdo
29、n插值多项式，有插值多项式，有:本讲稿第六十二页，共七十四页本讲稿第六十三页，共七十四页基本上能满足加工精度要求。从差商表看到，在区间基本上能满足加工精度要求。从差商表看到，在区间xx4 4，x x1717 中三阶差商都比中三阶差商都比0.0000230.000023小。因此，不必每个小。因此，不必每个区间都进行分析，即可认为在这一段采用二次插值是合区间都进行分析，即可认为在这一段采用二次插值是合适的。由适的。由NewdonNewdon插值公式得：插值公式得：这里这里K=4K=4，5 5，1616。用这个公式计算区间。用这个公式计算区间XX4 4,X,X1717 上的函数值，上的函数值，即用即
30、用Y=PY=P2 2(x)(x)的值作为的值作为Y=f(x)Y=f(x)的近似值。这就解决了区间的近似值。这就解决了区间X4,X17这一段曲线点的加密计算问题。这一段曲线点的加密计算问题。本讲稿第六十四页，共七十四页 下面讨论与头部连接部分的计算，也就是区间下面讨论与头部连接部分的计算，也就是区间xx0 0，x x4 4 这一段。这一段。当区间当区间x=xx=x0 0时曲线与圆弧时曲线与圆弧B Bl lB B2 2相连接，通常除了要相连接，通常除了要求函数值相等外，还必须要求在求函数值相等外，还必须要求在B B1 1处相切，即导数处相切，即导数值必须相等。因此，我们将区间值必须相等。因此，我们
31、将区间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)使其满足条件使其满足条件:本讲稿第六十五页，共七十四页本讲稿第六十六页，共七十四页本讲稿第六十七页，共七十四页本讲稿第六十八页，共七十四页本讲稿第六十九页，共七十四页本讲稿第七十页，共七十四页通过上面分段插值的方法，可以把整个机翼截面通过上面分段插值的方法，可以把整个机翼截面曲线加密点的坐标计算出来。具体计算只要根据曲线加密点的坐标计算出来。具体计算只要根据各段所得到的让算公式拍成程序，在计算机上进各段所得到的让算公式拍成程序，在计算机上进行计算即可。行计算即可。本讲稿第七十一页，共七十四页 至于计算结果是否满足要求，还应通过实践检验。至于计算结果是否满足要求，还应通过实践检验。分段插值只能保证插值曲线的连续性，不能保证分段插值只能保证插值曲线的连续性，不能保证曲线的光滑性，即导数不连续。曲线的光滑性，即导数不连续。如果对精度要求高，就可以采用样条函数。如果对精度要求高，就可以采用样条函数。本讲稿第七十二页，共七十四页本讲稿第七十三页，共七十四页本讲稿第七十四页，共七十四页