《数值计算方法第五章插值理论.ppt》由会员分享,可在线阅读,更多相关《数值计算方法第五章插值理论.ppt(118页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、第五章第五章 插值法插值法5 5、样条插值、样条插值主要内容:主要内容:1 1、拉格朗日插值、拉格朗日插值2 2、牛顿插值、牛顿插值3 3、分段线性插值、分段线性插值4 4、埃米特插值、埃米特插值三、线性插值五、拉格朗日插值多项式四、抛物线插值六、小结问题提出:问题提出:ox0 x1x2xny0y1y2yixiynY(x)P(x)=?x0 x1x2xnxixny0y1y2yiynx0 x1x2xixny0y1y2yiynx0 x1x2xixnxn 在工程技术上,给出一批离散的点,要求作出一条通过这些点的光滑曲线,以满足设计和加工的需要。反映在数学上,即已知函数在一些点的值,寻求它的分析表达式。
2、y 二二 是在选定近似函数H(x)后,不要求它们通过已知样点,只要求在某种意义下它在这些样点的总偏差最小-曲线拟合法曲线拟合法。解决问题的方法:解决问题的方法:一一 是给出函数f(x)的一些样点值,选定某些便于计算的函数,要求它们通过已知样点,由此确定函数H(x)为f(x)的近似值-插值法插值法;(一)拉格朗日插值(一)拉格朗日插值 定理定理1证明证明插值多项式的误差估计插值多项式的误差估计 称为截断误差,又称误差余项。称为截断误差,又称误差余项。插值多项式与被差函数之差定理定理2 2 设设 是区间是区间a,ba,b上互异节点,上互异节点,是过该组节点的是过该组节点的n n次插值多项式。若次插
3、值多项式。若f(x)f(x)在区间在区间a,ba,b上上n+1n+1次连续可导,则对次连续可导,则对a,ba,b内任意点内任意点x,x,误差余项为误差余项为特别:特别有相应的估计式特别有相应的估计式拉格朗日插值多项式拉格朗日插值多项式1 1)两个节点)两个节点x x0 0,x,x1 1的情况:的情况:解此方程组得解此方程组得 则两个节点则两个节点x0,x1 的一次插值多项式为的一次插值多项式为几何意义几何意义:这是过:这是过2 2个点的直线近似曲线,故称个点的直线近似曲线,故称线性插值线性插值。若将上式改写为两个函数的线性组合,即若将上式改写为两个函数的线性组合,即 n+1n+1个节点个节点
4、x x0 0,x,x1 1,x,xn n 的情况:的情况:其次数不超过其次数不超过n n,且满足,且满足对应函数值为系数作线性组合,得所要求的插值多项式。对应函数值为系数作线性组合,得所要求的插值多项式。多项式有多项式有n n个根个根 故它必有以下形式故它必有以下形式 它们称为它们称为拉格朗日插值基函数拉格朗日插值基函数。所以可得插值基函数的解所以可得插值基函数的解 称为称为n次拉格朗日插值多项式次拉格朗日插值多项式.记为:记为:当当n=1n=1时时,两点一次拉格朗日插值多项式为两点一次拉格朗日插值多项式为xy0AB当当n=2n=2时时,三节点处的函数值,三个插值基函数为三节点处的函数值,三个
5、插值基函数为二次拉格朗日插值多项式为二次拉格朗日插值多项式为几何意义几何意义:这是过:这是过3 3个点的抛物线近似曲线,个点的抛物线近似曲线,故称故称抛物线插值抛物线插值。例1、解:例2、解:例例3 3、已知y=lnx函数的表为 x 10 11 12 13 14x 10 11 12 13 14Y=lnx 2.3026 2.3979 2.4849 2.5649 Y=lnx 2.3026 2.3979 2.4849 2.5649 2.63912.6391分别用拉格朗日插值和抛物线插值求ln11.5的近似值,并估计截断误差。解:解:(1)线性插值。插值基函数是把x=11.5代入,插值余项误差插值余项
6、误差(2 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
7、+t*y(k);endyi=s;x=11 12;y=2.3979 2.4849;y1=Lagrange924(x,y,11.5)y1=2.4414x=11 12 13;y=2.3979 2.4849 2.5649;y1=Lagrange924(x,y,11.5)y1=2.4423例例4 4、设 为n+1个互异节点,为该组节点上的Lagrange插值基函数,试证明证明证明:为插值基函数,组合系数是1。在这n+1个互异节点处取值为1从而有 由插值问题的解知,它的n次Lagrange插值多项式是 对任意x,插值余项为六、小结六、小结2 2、牛顿插值、牛顿插值把线性插值公式改写为把线性插值公式改写为
8、可导出可导出-牛顿插值公式。牛顿插值公式。定义1:性质性质1 线性性质线性性质性质性质2性质性质3性质性质4,122121iiiiiiiiixxxfxxxfxxxf+=特别有特别有注:注:特别在重节点特别在重节点X1的插商的插商一阶差商二阶差商三阶差商若要计算四阶差商,增加一个节点,在计算一斜行,若要计算四阶差商,增加一个节点,在计算一斜行,如此下去,即可求出各阶差商的值。如此下去,即可求出各阶差商的值。牛顿插值公式牛顿插值公式称为称为一次牛顿插值一次牛顿插值公式。即:公式。即:把线性插值公式改写为把线性插值公式改写为由归纳法一般有由归纳法一般有记:易知易知 为满足插值条件的为满足插值条件的n
9、 n次插值多项式,次插值多项式,称为称为牛顿插值多项式牛顿插值多项式。优点:每增加一个节点,插值多项式只增加一项,即优点:每增加一个节点,插值多项式只增加一项,即 计算量小于计算量小于LagrangeLagrange插值。插值。由插值多项式唯一性知由插值多项式唯一性知 余项相等余项相等 利用牛顿多项式可按表中计算利用牛顿多项式可按表中计算例例1给定数据表给定数据表1246741011求求4 4次牛顿插值多项式,并写出插值余项次牛顿插值多项式,并写出插值余项。解解 1)构造差商表构造差商表0123412467410112)由差商表可得由差商表可得4 4次牛顿插值多项式为次牛顿插值多项式为3)牛顿
10、插值余项为牛顿插值余项为例例3 3 用牛顿插值公式计算例用牛顿插值公式计算例1 1中的中的ln11.5ln11.5。解解:仍取下面节点,作抛物线插值仍取下面节点,作抛物线插值x xi i y yi i=lnx=lnxi i 一阶插商一阶插商 二阶插商二阶插商11 2.3979 111 2.3979 112 2.4849 0.0870 x-1112 2.4849 0.0870 x-1113 2.5649 0.0800 -0.0035 (x-11)(x-12)13 2.5649 0.0800 -0.0035 (x-11)(x-12)差分与等距节点公式差分与等距节点公式差分的定义与性质差分的定义与性
11、质定义定义1(差分)(差分)向前差分向前差分和和向向后差分。后差分。向前差分算子向前差分算子和和向后差分算子向后差分算子。二阶差分:二阶差分:一般地,一般地,n-1阶差分的差分称为阶差分的差分称为n阶差分阶差分,记作记作 阶向前差分阶向前差分差分的性质:差分的性质:性质性质1 各阶差分具有线性性质;各阶差分具有线性性质;性质性质2 各阶差分可用函数值线性表示为;各阶差分可用函数值线性表示为;性质性质3 各种差分之间可以互化;各种差分之间可以互化;注:注:差分和导数满足关系:差分和导数满足关系:性质性质4 用差分表示差商;用差分表示差商;为了应用方便,计算差分可列差分表:为了应用方便,计算差分可
12、列差分表:具有差分形式(向前)的牛顿插值多项式及余项具有差分形式(向前)的牛顿插值多项式及余项将差分与差商的关系式代入牛顿插值余项式又得到将差分与差商的关系式代入牛顿插值余项式又得到(5.4.8)式与(式与(5.4.9)式分别称为)式分别称为牛顿向前插值牛顿向前插值多项式多项式与与牛顿向前插值多项式的牛顿向前插值多项式的余项余项。具有差分形式(向后)的牛顿插值多项式及余项具有差分形式(向后)的牛顿插值多项式及余项公式公式(5.4.12)称为称为牛顿向后插公式牛顿向后插公式。公式公式(5.4.12)称为称为牛顿向后插公式牛顿向后插公式的的余余项项。具有差分形式(一般)的牛顿插值多项式及余项具有差
13、分形式(一般)的牛顿插值多项式及余项表前公式表前公式和和表后公式的介绍表后公式的介绍公式公式(5.4.8)和和(5.4.13)都只用到向前差分,所以只需构造都只用到向前差分,所以只需构造向前差分表,公式向前差分表,公式(5.4.8)用表前部分,公式用表前部分,公式(5.4.13)用表用表后部分,所以分别称它们为后部分,所以分别称它们为表前公式表前公式和和表后公式表后公式。牛顿向后插值公式适用于计算函数表末端附近的函数值。牛顿向后插值公式适用于计算函数表末端附近的函数值。为了应用方便,利用向前差分表及相应的项乘积为了应用方便,利用向前差分表及相应的项乘积 可得可得NewtonNewton向前差分
14、公式向前差分公式1t利用向前差分表及相应的项乘积利用向前差分表及相应的项乘积可得可得NewtonNewton向后差分公式向后差分公式1t例例4 已知等距节点及相应点上的函数值如下表所已知等距节点及相应点上的函数值如下表所示,试求示,试求i01230.41.50.61.80.82.21.02.8解解 先构造向前差分表先构造向前差分表i01230.40.60.81.01.51.82.22.80.30.40.60.10.20.1由上表和公式由上表和公式(5.4.8)得得分段线性低次插值分段线性低次插值一、龙格现象一、龙格现象二、分段线性插值二、分段线性插值三、分段抛物线插值三、分段抛物线插值四、小结
15、四、小结一、龙格现象一、龙格现象 前面我们根据区间前面我们根据区间a,ba,b上给出的节点可以得上给出的节点可以得到函数到函数f(x)f(x)的插值多项式,但并非插值多项式的次的插值多项式,但并非插值多项式的次数越高,逼近函数数越高,逼近函数f(x)f(x)的精度越好。其主要原因就的精度越好。其主要原因就是,由于高次插值多项式往往有数值不稳定的缺是,由于高次插值多项式往往有数值不稳定的缺点,即对任意的插值节点,当点,即对任意的插值节点,当 时,插值多时,插值多项式项式 不一定收敛到不一定收敛到f(x)f(x)。这种高次插值不准确这种高次插值不准确的现象称为的现象称为龙格现象。龙格现象。为了避免
16、高次插值的上述缺点,我们常常采用为了避免高次插值的上述缺点,我们常常采用分分段低次插值的方法,即将插值区间分为若干个小区间,段低次插值的方法,即将插值区间分为若干个小区间,在每个小区间上运用前面介绍的插值方法构造低次插在每个小区间上运用前面介绍的插值方法构造低次插值多项式,以达到适当缩小插值区间长度,值多项式,以达到适当缩小插值区间长度,同样可以同样可以提高插值精度的目的。提高插值精度的目的。分段低次插值的优点是公式简单,计算量小,且有分段低次插值的优点是公式简单,计算量小,且有较好的收敛性和稳定性,并且可以避免计算机上作较好的收敛性和稳定性,并且可以避免计算机上作高次乘幂时遇到的上溢和下溢的
17、困难。高次乘幂时遇到的上溢和下溢的困难。二、分段线性插值二、分段线性插值 从几何意义上看,分段低次插值就是用折从几何意义上看,分段低次插值就是用折线近似代替曲线线近似代替曲线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=
18、1:n-1 if x(k)=xi&xi=x(k+1)yi=(xi-x(k+1)/(x(k)-x(k+1)*y(k)+(xi-x(k)/(x(k+1)-x(k)*y(k+1);return;endenda=-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*);三、分段抛物线插值三、分段抛物线插
19、值 应用低次插值的关键是恰当选择插值节点应用低次插值的关键是恰当选择插值节点,而选择插值节点的原则是:,而选择插值节点的原则是:尽可能在插值点尽可能在插值点的邻近选取插值节点。的邻近选取插值节点。四、小结四、小结(1)龙格现象;)龙格现象;(2)分段线性插值;)分段线性插值;(3)分段抛物线插值。)分段抛物线插值。埃尔米特插值埃尔米特插值 对插值函数要求在节点处与函数值限等,对插值函数要求在节点处与函数值限等,且导数值也相等的问题为且导数值也相等的问题为埃尔米特插值埃尔米特插值问题。问题。的多项式H(x)为Hermite插值多项式。而多项式H(x)至多为2n+1次。采用构造插值基函数的方法求采
20、用构造插值基函数的方法求HermiteHermite插值多项式。插值多项式。事实上,若下面两组函数满足事实上,若下面两组函数满足 均是至多为2n+1次多项式;必满足插值条件,且次数必超过2n+1。oxh(x)xiXjhi(x)1hj(x)h(x):hi(xi)=1,hi(xj)=0,hi(xj)=0.基函数特征H(x):Hi(xj)=0,Hi(xi)=1,Hi(xj)=0.ooH(x)ooo oxiXjxHi(x)Hj(x)易推得易推得HermiteHermite插值多项式插值多项式特别有特别有两节点的三次两节点的三次HermiteHermite插值多项式插值多项式注注:具体计算要选节点代公式
21、。:具体计算要选节点代公式。样条插值样条插值样条样条(Splin):是绘图员设计工具,它是富有弹性的:是绘图员设计工具,它是富有弹性的细木条或细金属条,绘图员利用它把一些已知点连细木条或细金属条,绘图员利用它把一些已知点连成一条光滑曲线,并使其连接处有连续的曲率成一条光滑曲线,并使其连接处有连续的曲率.取插值函数为样条函数取插值函数为样条函数-样条插值样条插值。0直升飞机旋转机翼外形轮廓线直升飞机旋转机翼外形轮廓线某些型值点的数据1 2 3 -6 7 8 -11 12 13520,280,156.6,-,3.1,0,3.1,-,156.6,280,5200,-30,-36,-,-9.4,0,9
22、.4,-,36,30,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),还需补充边界条件,有三种:,还需补充边界条件,有三种:构造构造S(x)S(x)的三弯矩方程方法:的三弯矩方程方法:参数参数Mi满足三弯矩方程满足三弯矩方程 且结合边界条件所确定的两个方程。且结合边界条件所确定的两个方程。构造构造S(x)S(x)的三斜率方程方法:的三斜率方程方法:参数参数mj
23、满足三转角方程满足三转角方程 且结合边界条件所确定的两个方程。且结合边界条件所确定的两个方程。例例*已知函数表为j:0 1 2 3xj:0 1 2 3yj:0 2 3 16求满足边界条件的三次样条插值函数。解解:若用三弯矩方程求解,由已知 及相应式子计算方程组的系数及右端项,有代入(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=f
24、orm:pp breaks:0 1 2 3 coefs:3x4 double pieces:3 order:4 dim:1ans=-3.6667 4.6667 1.0000 0 8.0000 -6.3333 -0.6667 2.0000 -15.3333 17.6667 10.6667 3.0000clear;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);p
25、p2.coefspp=form:ppbreaks:-0.2000 0 0.1000 0.1500 0.2000 0.3000coefs:5x4 double pieces:5 order:4 dim:1ans=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=ex
26、p(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 6
27、1 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中行船中行船应避免进入的区域。应避免进入的区域
28、。X(m)12914010888185195105Y(m)7141281472213785Z(m)4868688X(m)15710777145162162117Y(m)-6-81345-6684-38Z(m)9988949clear;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=g
29、riddata(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曲线v 在飞机
30、、轮船、汽车的外形设计中,由于样条函数作为设计工具缺少灵活性和直观性。睡着计算机辅助设计(CAD)的使用和发展,工程师们提出新的曲线、曲面的表示方法。法国雷诺汽车公司的工程师Bezier于1971年提出一种新的参数曲线表示方法。新方法能使设计师在工程设计中比较直观地意识到所给的条件与设计出的曲线之间的关系,能方便的控制输入参数(控制点)以改变曲线的形状。Bezier曲线形状的定义曲线形状的定义:Bezier曲线通过一组多边折线(控制多边形)曲线通过一组多边折线(控制多边形)的各顶点出来的曲线,形状趋势仿效多边折线的各顶点出来的曲线,形状趋势仿效多边折线的形状的形状。Bezier曲线形状特点:曲
31、线形状特点:1 1、在多边折线的各顶点中,只有第一点和最、在多边折线的各顶点中,只有第一点和最后一点在曲线上,其余的点则用于定义的阶次后一点在曲线上,其余的点则用于定义的阶次与导数;与导数;2 2、多边折线的第一段和最后一段点表示出曲、多边折线的第一段和最后一段点表示出曲线在起点和终点的切线方向。线在起点和终点的切线方向。改变多边折线的顶点改变曲线形状。v例:给出四个控制点可以绘制出三次Bezier曲线,改变控制点的坐标位置,则曲线形状发生改变。Bezier曲线的数学表达式:其中组合系数用参数表示坐标位置相应的Bezier多项式为若给定控制多边形顶点在工程实际中用向量函数表示平面曲线 特别有:1、一次、一次Bezier曲线曲线是通过平面上两点 则有数学表达式 的直线段,2、二次二次Bezier曲线曲线是通过平面上三点 组成控制多边形,确定抛物线,组成控制多边形,确定三次曲线,3、三次三次Bezier曲线曲线是通过平面上四点 一般记Bezier曲线的数学表达式中 为基函数 Bezier多项式主要性质:习题五习题五End
限制150内