数值计算方法第五章插值理论.ppt

第五章 插值法,5、样条插值,主要内容：,1、拉格朗日插值,2、牛顿插值,3、分段线性插值,4、埃米特插值,三、线性插值,五、拉格朗日插值多项式,四、抛物线插值,六、小结,问题提出：,o,x0,x1,x2,xn,y0,y1,y2,yi,xi,yn,Y(x),P(x)=?,x0,x1,x2,xn,xi,xn,y0,y1,y2,yi,yn,x0,x1,x2,xi,xn,y0,y1,y2,yi,yn,x0,x1,x2,xi,xn,xn,在工程技术上，给出一批离散的点，要求作出一条通过这些点的光滑曲线，以满足设计和加工的需要。反映在数学上，即已知函数在一些点的值，寻求它的分析表达式。,y,二 是在选定近似函数H(x)后，不要求它们通过已知样点，只要求在某种意义下它在这些样点的总偏差最小-曲线拟合法。,解决问题的方法：,一 是给出函数f(x)的一些样点值，选定某些便于计算的函数，要求它们通过已知样点，由此确定函数H(x)为f(x)的近似值-插值法;,（一）拉格朗日插值,定理1,证明,插值多项式的误差估计,称为截断误差，又称误差余项。,插值多项式与被差函数之差,定理2 设 是区间a,b上互异节点，是过该组节点的n次插值多项式。若f(x)在区间a,b上n+1次连续可导，则对a,b内任意点x,误差余项为,特别：,特别有相应的估计式,拉格朗日插值多项式,1）两个节点x0,x1的情况：,解此方程组得,则两个节点x0,x1 的一次插值多项式为,几何意义：这是过2个点的直线近似曲线，故称线性插值。,若将上式改写为两个函数的线性组合，即,其次数不超过n，且满足,对应函数值为系数作线性组合，得所要求的插值多项式。,多项式有n个根,故它必有以下形式,它们称为拉格朗日插值基函数。,所以可得插值基函数的解,称为n次拉格朗日插值多项式.记为：,当n=1时,两点一次拉格朗日插值多项式为,当n=2时,三节点处的函数值，三个插值基函数为,二次拉格朗日插值多项式为,几何意义：这是过3个点的抛物线近似曲线，故称抛物线插值。,例1、,解：,例2、,解：,例3、已知y=lnx函数的表为,x 10 11 12 13 14Y=lnx 2.3026 2.3979 2.4849 2.5649 2.6391分别用拉格朗日插值和抛物线插值求ln11.5的近似值，并估计截断误差。,解：(1)线性插值。,插值基函数是,把x=11.5代入,插值余项误差,（2）抛物线插值。,插值多项式是,把x=11.5代入,插值余项误差,function yi=Lagrange(x,y,xi)%用Lagrange插值法求解%yi=Lagrange(x,y,xi)x是节点向量，y是节点上的函数值%xi是插值点（可以是多个）,yi是返回插值m=length(x);n=length(y);p=length(xi);if m=n,error(向量x与y的长度必须一致);ends=0;for k=1:n t=ones(1,p);for j=1:n if j=k t=t.*(xi-x(j)/(x(k)-x(j);endends=s+t*y(k);endyi=s;,x=11 12;y=2.3979 2.4849;y1=Lagrange924(x,y,11.5),y1=2.4414,x=11 12 13;y=2.3979 2.4849 2.5649;y1=Lagrange924(x,y,11.5),y1=2.4423,例4、设 为n+1个互异节点，为该组节点上的Lagrange插值基函数，试证明,证明：,为插值基函数，组合系数是1。,在这n+1个互异节点处取值为1从而有,由插值问题的解知，它的n次Lagrange插值多项式是,对任意x,插值余项为,六、小结,2、牛顿插值,把线性插值公式改写为,可导出-牛顿插值公式。,定义1：,性质1 线性性质,性质2,性质3,性质4,特别有,注：特别在重节点X1的插商,若要计算四阶差商，增加一个节点，在计算一斜行，如此下去，即可求出各阶差商的值。,牛顿插值公式,由归纳法一般有,记：,易知 为满足插值条件的n次插值多项式，称为牛顿插值多项式。,由插值多项式唯一性知,余项相等,利用牛顿多项式可按表中计算,2)由差商表可得4次牛顿插值多项式为,3)牛顿插值余项为,例3 用牛顿插值公式计算例1中的ln11.5。,解：仍取下面节点，作抛物线插值,xi yi=lnxi 一阶插商 二阶插商11 2.3979 112 2.4849 0.0870 x-1113 2.5649 0.0800-0.0035(x-11)(x-12),定义1（差分）,向前差分和向后差分。,向前差分算子和向后差分算子。,二阶差分：,一般地，n-1阶差分的差分称为n阶差分,记作,阶向前差分,差分的性质：,性质1 各阶差分具有线性性质；,性质2 各阶差分可用函数值线性表示为；,性质3 各种差分之间可以互化；,注：差分和导数满足关系：,性质4 用差分表示差商；,具有差分形式（向前）的牛顿插值多项式及余项,将差分与差商的关系式代入牛顿插值余项式又得到,具有差分形式（向后）的牛顿插值多项式及余项,公式(5.4.12)称为牛顿向后插公式。,公式(5.4.12)称为牛顿向后插公式的余项。,具有差分形式（一般）的牛顿插值多项式及余项,表前公式和表后公式的介绍,公式(5.4.8)和(5.4.13)都只用到向前差分，所以只需构造向前差分表，公式(5.4.8)用表前部分，公式(5.4.13)用表后部分，所以分别称它们为表前公式和表后公式。,牛顿向后插值公式适用于计算函数表末端附近的函数值。,为了应用方便，利用向前差分表及相应的项乘积 可得Newton向前差分公式,利用向前差分表及相应的项乘积可得Newton向后差分公式,解 先构造向前差分表,由上表和公式(5.4.8)得,分段线性低次插值,一、龙格现象,二、分段线性插值,三、分段抛物线插值,四、小结,一、龙格现象,前面我们根据区间a,b上给出的节点可以得到函数f(x)的插值多项式，但并非插值多项式的次数越高，逼近函数f(x)的精度越好。其主要原因就是，由于高次插值多项式往往有数值不稳定的缺点，即对任意的插值节点，当 时，插值多项式 不一定收敛到f(x)。,这种高次插值不准确的现象称为龙格现象。,为了避免高次插值的上述缺点，我们常常采用分段低次插值的方法，即将插值区间分为若干个小区间，在每个小区间上运用前面介绍的插值方法构造低次插值多项式，以达到适当缩小插值区间长度，同样可以提高插值精度的目的。,分段低次插值的优点是公式简单，计算量小，且有较好的收敛性和稳定性，并且可以避免计算机上作高次乘幂时遇到的上溢和下溢的困难。,二、分段线性插值,从几何意义上看，分段低次插值就是用折线近似代替曲线y=f(x).,分段线性插值函数。,function yi=lineint(x,y,xi)%分段线性插值,x是插值节点向量,按行输入%y是插值节点上的函数值向量，按行输入%xi是标量，自变量m=length(x);n=length(y);if n=m,error(向量x与y的长度必须一致);endfor k=1:n-1 if x(k)=xi endend,a=-5;b=5;n=10;h=(b-a)/n;x=a:h:b;y=1./(1+x.2);xx=a:0.01:b;yy=1./(1+xx.2);m=length(xx);z=zeros(1,m);for i=1:m z(i)=lineint924(x,y,xx(i);endplot(x,y,o,xx,yy,k:,xx,z,k-);plot(xx,z-yy,k*);,三、分段抛物线插值,应用低次插值的关键是恰当选择插值节点，而选择插值节点的原则是：尽可能在插值点的邻近选取插值节点。,四、小结,（1）龙格现象；（2）分段线性插值；（3）分段抛物线插值。,埃尔米特插值,对插值函数要求在节点处与函数值限等，且导数值也相等的问题为埃尔米特插值问题。,的多项式H(x)为Hermite插值多项式。,而多项式H(x)至多为2n+1次。,采用构造插值基函数的方法求Hermite插值多项式。,事实上，若下面两组函数满足,均是至多为2n+1次多项式；,必满足插值条件，且次数必超过2n+1。,o,x,h(x),xi,Xj,hi(x),1,hj(x),h(x):hi(xi)=1,hi(xj)=0,hi(xj)=0.,基函数特征,H(x)：Hi(xj)=0,Hi(xi)=1,Hi(xj)=0.,o,o,H(x),o,o,o,o,xi,Xj,x,Hi(x),Hj(x),易推得Hermite插值多项式,特别有,两节点的三次Hermite插值多项式,注：具体计算要选节点代公式。,样条插值,样条(Splin)：是绘图员设计工具，它是富有弹性的细木条或细金属条，绘图员利用它把一些已知点连成一条光滑曲线，并使其连接处有连续的曲率.,取插值函数为样条函数-样条插值。,0,直升飞机旋转机翼外形轮廓线,某些型值点的数据,由13个点，用样条函数值的方法增加平面点数49个点，绘制出较光滑机翼外形曲线。,已知函数f(x)在n+1个节点,若插值函数S(x)满足：,S(x)是三次多项式，记Sj(x)；,（3）S(x)在a,b上二次连续可微。,则称S(x)为f(x)的三次样条插值函数,要唯一确定S(x)，还需补充边界条件，有三种：,构造S(x)的三弯矩方程方法：,参数Mi满足三弯矩方程,且结合边界条件所确定的两个方程。,构造S(x)的三斜率方程方法：,参数mj满足三转角方程,且结合边界条件所确定的两个方程。,解:若用三弯矩方程求解，由已知,及相应式子计算方程组的系数及右端项，有,代入（5-51）,用三转角方程求解，由,可解,得三转角方程,表示式,其解为,clear;x=0,1,2,3;y=0,2,3,16;pp=csape(x,y)xi=0:0.01:3;yi=ppval(pp,xi);pp1=csape(x,y,complete,1,0);pp1.coefsfnplt(pp1),pp=form:pp breaks:0 1 2 3 coefs:3x4 double pieces:3 order:4 dim:1,ans=-3.6667 4.6667 1.0000 0 8.0000-6.3333-0.6667 2.0000-15.3333 17.6667 10.6667 3.0000,clear;x=0.1,0.2,0.15,0,-0.2,0.3;y=0.95,0.84,0.86,1.06,1.50,0.72;pp=csape(x,y)xi=-0.2:0.01:0.3;yi=ppval(pp,xi);fnplt(pp)pp2=csape(x,y,second,1.0,0.3);pp2.coefs,pp=form:ppbreaks:-0.2000 0 0.1000 0.1500 0.2000 0.3000coefs:5x4 double pieces:5 order:4 dim:1,ans=11.9958 0.5000-2.7798 1.5000-72.9406 7.6975-1.1403 1.0600 279.3208-14.1847-1.7891 0.9500-269.2154 27.7134-1.1126 0.8600 42.7297-12.6689-0.3604 0.8400,x=0,2,4,5,8,12,12.8,17.2,19.9,20;y=exp(x).*sin(x);xx=0:0.25:20;yy=spline(x,y,xx);plot(x,y,ro,xx,yy)title(三次样条，y=exp(x)sin(x)，0,2,4,5,8,12,12.8,17.2,19.9,20),二元2线性插值公式,使用2线性插值；使用二元三次样条插值；使用二元三次插值；,使用2线性插值；使用二元三次样条插值；使用二元三次插值；,clear;close;x=0:4;y=2:4;z=82 81 80 82 84;79 63 61 65 81;84 84 82 85 86;subplot(2,2,1);mesh(x,y,z);title(RAW DATA);xi=0:0.1:4;yi=2:0.1:4;zspline=interp2(x,y,z,xi,yi,spline);subplot(2,2,2);mesh(xi,yi,zspline);title(SPLINE);,海底测量：表-1给出水面直角坐标（X,Y）出水高度Z，在低潮时测的。船的吃水度为5米，问在矩形域75X,200,-50Y150中行船应避免进入的区域。,clear;close;x=129 140 108 88 185 195 105 157 107 77 145 162 162 117;y=7 141 28 147 22 137 85-6-81 3 45-66 84-38;plot(x,y,o);,z=4,8,6,8,6,8,8,9,9,8,8,9,4,9;h=-z;xi=75:5:200;yi=-50:10:150;HI=griddata(x,y,h,xi,yi,cubic);%三角形三次插值；mesh(xi,yi,HI);view(-60,30);contour(xi,yi,HI,-5,-5,k),x=2,3,4,0,2,3,0,1,4;y=2,2,2,3,3,3,4,4,4;z=80,82,84,79,61,65,84,84,86;subplot(2,2,3);stem3(x,y,z);title(RAW DATA);ZI=griddata(x,y,z,xi,yi,cubic);subplot(2,2,4);mesh(xi,yi,ZI);title(GRIDDATA);,Bezier曲线,在飞机、轮船、汽车的外形设计中，由于样条函数作为设计工具缺少灵活性和直观性。睡着计算机辅助设计(CAD)的使用和发展，工程师们提出新的曲线、曲面的表示方法。法国雷诺汽车公司的工程师Bezier于1971年提出一种新的参数曲线表示方法。新方法能使设计师在工程设计中比较直观地意识到所给的条件与设计出的曲线之间的关系，能方便的控制输入参数（控制点）以改变曲线的形状。,Bezier曲线形状的定义:,Bezier曲线通过一组多边折线（控制多边形）的各顶点出来的曲线，形状趋势仿效多边折线的形状。,Bezier曲线形状特点：1、在多边折线的各顶点中，只有第一点和最后一点在曲线上，其余的点则用于定义的阶次与导数；2、多边折线的第一段和最后一段点表示出曲线在起点和终点的切线方向。,改变多边折线的顶点改变曲线形状。,例：给出四个控制点可以绘制出三次Bezier曲线，改变控制点的坐标位置，则曲线形状发生改变。,Bezier曲线的数学表达式:,其中组合系数,在工程实际中用向量函数表示平面曲线,Bezier多项式主要性质：,习题五,End,