《五章代数插值.ppt》由会员分享,可在线阅读,更多相关《五章代数插值.ppt(88页珍藏版)》请在三一办公上搜索。
1、代数插值,插值法是一种古老的数学方法。早在1000多年前,我国历法上已经记载了应用一次插值和二次插值的实例。,下表是2004年8月11日男子赛跑奥运会纪录,试建立当今成年男子赛跑所需时间与距离之间的函数关系,并测算男子1000米赛跑奥运会纪录大概为多少?,例题1,其中p(x)称为插值函数,f(x)称为被插值函数。xi称为节点。,要求:在节点xi 处的函数值相等,即p(xi)=yi=f(xi).,所谓插值就是:,欲求:一个简单函数 p(x)用于逼近 f(x),,这种问题称为插值问题。,已知:函数 f(x)在n+1个互异点xi 处的函数值(或变量间的一组对应数据)yi=f(xi)(i=0,1,2,
2、,n),,一、插值的基本概念:,若取插值函数p(x)为多项式,则称为代数插值。,满足条件pn(xi)=yi=f(xi).,定义:设函数f(x)在区间a,b上有定义,且已知它在n+1个互异节点ax0 x1 xi b,处的函数值yi=f(xi)(i=0,1,2,,n),若存在一个次数不超过n的多项式,pn(x)=a0+a1x+anxn,则称pn(xi)为f(x)的n次插值多项式。,插值函数的存在唯一性:,满足条件pn(xi)=yi=f(xi).,定理:已知函数f(x)在n+1个互异节点ax0 x1 xi b处的函数值yi=f(xi)(i=0,1,2,,n),,pn(x)=a0+a1x+anxn,那
3、么存在唯一一个次数不超过n的多项式:,证明:设所要构造的插值多项式为:,由插值条件,得到如下线性代数方程组:,此方程组的系数行列式为,范德蒙行列式!,D 0,,因此,Pn(x)由a0,a1,an唯一确定。,图11 插值多项式,拉格朗日(Lagrange)、牛顿(Newton)、埃特金(Aitken)、埃尔密特(Hermite)分别给出了不同的解决方法。,常用的插值方法有:,二、插值方法,(一)拉格朗日插值,拉格朗日(Lagrange)插值的基本思想是,把Ln(x)的构造问题转化为n+1个插值基函数li(x)(i=0,1,n)的构造。,求通过两点A(x0,y0),B(x1,y1)的一条直线,,1
4、.线性插值,即n=1的情况,已知函数y=f(x)在两个点x0,x1上的值为y0,y1,,要求多项式y=L1(x),使L1(x0)=y0,L1(x1)=y1。,其几何意义为,一次插值多项式,其中,由直线两点式方程可知,通过点(x0,y0)和(x1,y1)的直线方程为,写为:L1(x)=l0(x)y0+l1(x)y1,它也可变形为,显然有:l0(x0)=l1(x1)=1,l0(x1)=l1(x0)=0,,L1(x0)=y0,L1(x1)=y1,我们称l0(x)为点x0的一次插值基函数,l1(x)为点x1的一次插值基函数。,插值函数L1(x)是这两个插值基函数的线性组合,其组合系数就是对应点上的函数
5、值。,它们在对应的插值点上取值为1,而在另外的插值点上取值为0。即 li(xj)=ij,,可写为 L1(x)=l0(x)y0+l1(x)y1,线性插值公式,2.抛物插值,即n=2的情况,线性插值只利用两对值(x0,y0)及(x1,y1)求得y=f(x)的近似值,误差较大。,L2(x0)=y0,L2(x1)=y1,L2(x2)=y2,现用过三点(x0,y0),(x1,y1)及(x2,y2)的二次曲线L2(x)近似代替y=f(x)。要求,L2(x)是x的二次函数,称为二次插值多项式。通过三点的插值问题称为二次插值或抛物插值。,与线性插值插值类似的,,设 L2(x)=l0(x)y0+l1(x)y1+
6、l2(x)y2,其中li(xj)是二次多项式,且li(xj)=ij,则有,3.一般情况,我们看到,两个插值点可求出一次插值多项式L1(x),而三个插值点可求出二次插值多项式L2(x)。当插值点增加到n+1个时,我们可以利用Lagrange插值方法写出n次插值多项式 Ln(x),如下所示:,这种形式的插值称作为拉格朗日(Lagrange)插值。,插值余项,定理 若f(x)在包含着插值节点 x0,x1,xn的区间a,b上 n+1 次可微分,则对任意 x,xa,b,有与x有关的(ab)存在,使得,定义:称插值函数的误差Rn(x)=f(x)-Ln(x)为插值多项式Ln(x)的余项。,函数值表,例 设
7、f(x)=lnx,并假定已给出值表试近似计算ln(0.6)的值,并指出精度。,解:利用3次Lagrange 插值公式,简单计算过程如下:,综合上述,我们有:,真值:ln(0.6)=-0.510826,,近似值:L3(0.6)=-0.509975,,真误差:ln(0.6)-L3(0.6)=-0.000851,,估计的上界:|ln(0.6)-L3(0.6)|0.00391,下表是2004年8月11日男子赛跑奥运会纪录,试建立当今成年男子赛跑所需时间与距离之间的函数关系,并测算男子1000米赛跑奥运会纪录大概为多少?,例题,1.插值:T(x)=2.72197+0.0576262x+0.0001447
8、15x2-9.4010-8x3+2.2629210-11x4,T(1000)=133.689,2、差商与牛顿插值,在插值过程中,希望为用较小的计算量获得较为精确的插值多项式。但是Lagrange有一个弱点,那就是通过一定数量的插值节点计算出插值多项式后,如果再加入新的节点求插值多项式则须重新计算,而前面的计算结果全部失效了。,为了继续利用前面的结果,我们考虑Newton插值。,定义:设函数f(x)在xi处的函数值f(xi)为xi点的零阶差商,记作 fxi=f(xi);,xi,xj点的一阶差商;,xi,xj,xk点的二阶差商;,x0,x1,xn点的n阶差商;,差商的性质,1)对称性:fxi,xj
9、=fxj,xi(差商值与其中变量的顺序无关);,2)差商可写为函数值的线性组合:,3)如果f(x)的k阶差商fx0,x1,xk-1,x是x的m 次多项式,则k+1阶差商fx0,x1,xk-1,xk,x 是 x 的 m-1 次多项式,,5)如果f(x)在含有x0,x1,xn的区间具有n阶导数,则在该区间内至少存在一点,使得,4)如果f(x)是x的n次多项式,则阶差商fx0,x1,xk-1,x,当k n时是x的n-k次多项式,k n 时恒为零。,Nn(x),Rn(x),ai=,f x0,xi,牛顿插值多项式,Nn(x)=fx0+(x-x0)fx0,x1+(x-x0)(x-x1)fx0,x1,x2+
10、(x-x0)(x-x1)(x-xn-1)fx0,x1,xn,Nn+1(x)=Nn(x)+(x-x0)(x-x1)(x-xn)fx0,x1,xn+1,余项:,差商表,第一建立差商表:,Newton的方法步骤:,第二写出牛顿插值多项式,Nn(x)=fx0+(x-x0)fx0,x1+(x-x0)(x-x1)fx0,x1,x2+(x-x0)(x-x1)(x-xn-1)fx0,x1,xn,Nn+1(x)=Nn(x)+(x-x0)(x-x1)(x-xn)fx0,x1,xn+1,练习:1 已知f(-1)=2,f(1)=1,f(2)=1,求f(x)的二次Newton插值多项式。,解:设x0=-1,x1=1,x
11、2=2,则,Newton插值例题1:,试写出Newton插值多项式N3(x)和N4(x),在钢线碳含量对电阻的效应的研究中,获得数据如下:,并计算N3(0.4)和N4(0.4)的值。,解:建立Newton插商表,写出牛顿插值多项式:,N4(x)=N3(x)+(x-x0)(x-x1)(x-x2)(x-x 3)fx0,x1,x2,x3,x4,N3(x)=fx0+(x-x0)fx0,x1+(x-x0)(x-x1)fx0,x1,x2+(x-x0)(x-x1)(x-x2)fx0,x1,x2,x3,=15+15(x-0.1)-6.666667(x-0.1)(x-0.3)+5.555569(x-0.1)(x
12、-0.3)(x-0.55),N3(0.4)=19.2750,N3(x)+16.825138(x-0.1)(x-0.3)(x-0.55)(x-0.70),N4(0.4)=19.297714,练习:2.现有一组实验数据如下表,1分别用线性插值与二次插值计算f(1.64)的近似值;2写出f(x)的三次插值多项式;3写出f(x)的三次牛顿(Newton)插值多项式,L1(1.640000)=24.741999;L2(1.640000)=24.649599,3.差分与等距节点公式,向前差分,向后差分,中心差分,其中,当节点等距分布时:,(k 个差分因子),记 fi=f(xi)=f(x0+ih),差分的重
13、要性质:,性质3:若 f(x)是 m 次多项式,则 是,性质1:常数的差分等于零,性质2:差分算子为线性算子,次多项式,且,性质4:,这个性质类比于,性质5:,(类比于分部积分法则),性质6:当节点xk是等距时,差分差商存在着关系:,差分值可由函数值算出:,其中,牛顿公式,牛顿前差公式,其中,例.给出函数y=f(x)=shx在x0.5,0.8的部分函数值如下:,试求x=0.52处的函数f(x)的近似值(0.5437538),牛顿后差公式,将节点顺序倒置:,注:一般当 x 靠近 x0 时用前插,靠近 xn 时用后插,故两种公式亦称为表初公式和表末公式。,4.埃特金插值公式,埃特金(Aitken)
14、插值的构造是基于这样的直观想象:平面上的两个点可以连成一条直线,对应一个线性函数;把线性函数看作形式点,经线性组合,可构成二次函数;把二次函数再看作形式点,经线性组合,可构成三次函数。,引入记号:,节点为 的k次 插值多项式:,节点为 的k次 插值多项式:,即满足,即满足,1 记号:,2 逐步插值法的思想,高阶L-插值多项式用低阶L-插值多项式的组合得到,例 已知线性插值,求节点为 的,(抛物线插值),令,满足,则有,验证,Aitken 插值表,例已知f(-1)=2,f(1)=1,f(2)=1,求f(x)的Aitken插值多项式。解:设x0=-1,x1=1,x2=2,(x0,y0)与(x1,y
15、1)作线性插值,(x0,y0)与(x2,y2)作线性插值,(x1,p0,1)与(x2,p0,2)作线性插值,例的Aitken插值表,取等距节点xi=-5+i(i=0,1,10),试建立插值多项式L10(x),并作图形,观察L10(x)对f(x)的逼近效果。,5.分段插值,插值多项式与函数图形比较如下:,Rung现象,为了避免Runge现象的发生,我们很自然地会想到把区间-5,5等分为10个小区间,在每一个小区间内应用低次插值。但由于每个小区间只有两个端点(插值节点),按照我们已知的方法,得到的将是一个分段线性插值函数。,分段低次插值,分段线性插值,在每个区间 xi,xi+1 上,用1阶多项式(
16、直线)逼近 f(x):,y=p(x),6、埃尔米特插值,(2)H(xi)=yi=f(xi),H(xi)=yi=f(xi).,定义:已知函数f(x)在n+1个互异点xi 处的函数值和一阶导数值:,若存在 一个函数H(x),满足:,则H(x)称为f(x)在n+1个互异点xi 的埃尔米特(Hermite)插值多项式。,(1)H(x)是一个次数不超过2n+1的多项式;,yi=f(xi),yi=f(xi)(i=0,1,2,,n),(1),定理:埃尔米特(Hermite)插值多项式是存在且唯一的。证明从略。,Hermite插值多项式的构造,-(3),-(4),显然满足条件(3),(4)的多项式(2)的次数
17、不大于2n+1次,且满足插值条件(1).,1.求解 hk(x)(k=0,1,2,,n),由条件(3)知xi(i=0,1,2,,n,ik)是 hk(x)的二重零点.且 hk(x)是2n+1次多项式,为此设:,hk(x)(ax+b)lk2(x),其中lk(x)为Lagrange插值基多项式,为使hk(xk)(axk+b)lk2(xk)(axk+b)=1;,hk(xk)2(axk+b)lk(xk)lk(xk)+a lk2(xk)2(axk+b)lk(xk)+a=2lk(xk)+a=0,故hk(x)1-2 lk(xk)(x-xk)lk2(x),2.求解,由条件(4)知 xi(i=0,1,2,,n,ik
18、)是 的二重零点,且 是2n+1次多项式.为此设:,结合插值条件(4)可得:,于是有,于是可得Hermilte插值多项为,其中,特别当n1 时,插值条件为:,于是有:,例1.,解:,作为多项式插值,三次已是较高的次数,次数再高就有可能发生Runge现象,因此,对有n+1节点的插值问题,我们可以使用分段两点三次Hermite插值,7、样条函数插值,“样条”这个词本来是指在飞机或轮船设计过程中,为了描绘出光滑的外形曲线所用的一种工具,即一个具有弹性的细长条。使用时,用压铁在一些点上固定,其它地方自已弯曲,然后画出一条光滑曲线。,事实上,在作了某些近似简化后,样条的数学模型并不复杂,它只是分段的三次
19、多项式曲线:在相邻两块压铁之间是三次多项式曲线;在压铁处,左右两段曲线的切线和曲率是连续的。,定义:设对y=f(x)在区间a,b上给定一组节点,a=x0 x1 x2 xn=b 和相应的函数值y0,y1,yn,,如果存在函数s(x)具有如下性质:,(1)在每个子区间xj-1,xj(j=1,2,n)上s(x)是不高于三次的多项式;,(2)s(x),s(x),s(x)在a,b上连续;则称s(x)为三次样条函数。,如再有,(3)s(xj)=yj(j=0,1,2,n),则称s(x)为y=f(x)的三次样条插值函数。,f(x),H(x),S(x),注:三次样条与分段 Hermite 插值的根本区别 在于S
20、(x)自身光滑,不需要知道 f 的导数值(除了在2个端点可能需要);而Hermite 插值依赖于f 在所有插值点的导数值。,三次样条插值多项式的构造方法,设f(x)是定义在 a,b区间上的一个二次连续可微函数,,为分划:,S(x)在 xi-1,xi 上是线性函数,用一次插值有表达式:,在每一个小区间xi-1,xi i=1,n 上都是三次多项式,,Mi是待定参数,其中,将上式两次积分得:,Ai 和Bi 为积分常数。,因为,所以它满足方程:,求 Mi,确定S(x)的表达式。对上式求导有:,于是,各项除以hi+hi+1,并记,则(*)式可以写为,(*),边界条件,最后一个方程。若取 M0=Mn=0,
21、称为三次自然样条。,有,(2)给定两端点导数值,一般地,仅有插值条件是不够的,还需考虑边界条件,边界条件根据问题实际情况给出。,分别补充为方程组()式的第一个和最后一个方程组。,解方程组,经补充后的方程组为,其中,对端点条件(1),有,对端点条件(2),有,(6.10)是一个三对角方程组,可用追赶法解之。,此方程组系数严格对角占优!从而存在唯一解。,求出了Mi(i=0,1,n),也就求得了S(x)在各个小区间的表达式Si(x)(i=0,1,2,n),若取等距节点 hi=h,i=1,n 1,算 法:,(1)i=1,2,n,hi=xi xi-1,(2)i=1,2,n,(3)解n 1阶三对角方程组,
22、得,M1,M2,Mn-1,代入端点条件计算M0,Mn,(4),若取,计算,上机实习题,设函数,试用三次样条函数作插值,并与L10(x)或N10(x)作比较。,取等距节点 xi=x0+ih i=0,1,20,端点条件,应用实例,例 要在程控铣床上加工直升飞机的旋转机翼,外形的截面形状见图1-4。外形头部有一段圆弧B1B2,圆的半径R=6.92mm,tan=0.305,B1,B2的坐标为B1(0.52,5.288),B2(2.6,-3.615),截面上轮廓线18个点的坐标如表1-8所示。旋转机翼外形截面图如图1-4所示。由于图中有些点很密,所以只有一部分点可以看到。,图1-4 直升飞机旋转机翼外形截面图,解:要用程控铣床加工工件必须计算出整个工件外形曲线足够密的点的坐标值。根据所给条件,头部圆弧B1B2可由圆的方程直接计算出点的坐标,其余部分必须根据给出的点的坐标。,我们要利用插值方法计算加密点的坐标。,x0=Rcos=6.619 y0=Rsin=2.0186于是,圆的方程为(x-6.619)2+(y-2.0186)2=R2=47.886,现在先讨论头部圆弧B1B2的计算方法。根据所给条件,可求得圆心坐标(x0,y0)如下:,