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