代数插值--补充知识.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,代数插值,1,多项式插值问题,2,lagrange,插值多项式,3,差商及,Newton,插值多项式,4,分段插值多项式,5,三次样条,(Spline),插值多项式,1,某化学反应中,在有限个时刻,t,(min),，,测,得生成物质量浓度,y,(10,-3,g/cm,3,),的如下数据,那么在时刻,t=5分，t=18,分时的浓度是多少？,t,i,1,2,3,4,6,8,10,12,14,16,y,i,4.00,6.41,8.01,8.79,9.53,9.86,10.33,10.42,10.53,10.61,下面主要讨论利用插值方法寻求函数的近似问题。,用函数来表示变量间的数量关系广泛应用于各学科领域,但在实际问题中,往往是通过实验、观测以及计算等方法,获得函数在一些点上的函数值。如何通过这些离散数据找出函数的一个满足精度要求且便于使用的近似表达式,是经常遇到的问题。例如：,2,1 多项式插值问题,设函数,y=f(x),在区间,a,b,连续,给定,n+1,个点,已知,f,(,x,k,),=y,k,(,k=0,1,n,),在函数类中寻找一函数,(x),作为,f(x),的近似表达式,使满足,这时称,y=f(x),为,被插值函数,(x),称为,插值函数,x,k,称为,插值节点,式(2)称为,插值条件,寻求插值函数,(x),的方法称为,插值方法,.,一、,插值问题,a x,0,x,1,x,n,b,(1),(,x,k,)=,f,(,x,k,)=,y,k,k=0,1,n,(2),3,在构造插值函数时，函数类的不同选取,P,对应各种不同的插值方法，这里我们主要研究函数类 是代数多项式,，即所谓的多项式插值问题。,多项式插值,，,从几何角度看，就是寻求,n,次代数曲线,y=p,n,(,x,),通过个,n+1,点,(,x,k,y,k,)(,k=0,1,n,),作为,f(x),的,近似(如下图).,二、多项式插值问题,4,(4),用,P,n,表示所有次数不超过n的多项式函数类，若,p,n,(x),P,n,，,则,p,n,(,x,)=,a,0,+a,1,x+a,n,x,n,是由,n+1,个系数唯一确定的。当满足如下的插值条件时,得到关于系数,a,0,、a,1、,、,a,n,的线性方程组,p,n,(,x,k,)=,f,(,x,k,)=,y,k,k=0,1,n,(3),5,其系数行列式为,Vandermonde,(范德蒙)行列式,只要,i,j,就有,x,i,x,j,因而,V,(,x,0,x,1,x,n,)0,于是方程组(4)有唯一解,也就是说,当节点不重合时,n+1,个节点的插值条件能唯一确定一个,n,次插值多项式,从而有:,定理1,给定,n+1,个互异节点,x,0,x,1,x,n,上的函数值,y,0,y,1,y,n,则满足插值条件,p,n,(x,k,)=f(x,k,)=y,k,k=0,1,n,的,n,次插值多项式,p,n,(x),存在且唯一。,6,这样只要求解方程组,拉格朗日插值多项式,牛顿插值多项式,便可确定插值多项式,p,n,(,x,),，但相对来讲计算较复杂。然而，插值多项式的唯一性保证了无论用什么方法获得满足插值条件的多项式都是同一个多项式,p,n,(,x,),，因此可以采用其它更简便的方法来确定多项式。下面就介绍几种常用的方法：,(4),7,2,Lagrange插值多项式,的函数值,已知,y=f(x),在,n+1,个点,构造,n,次多项式,p,n,(x),使得,从而得到,f(x),的近似计算式,8,一、线性插值,（n=1）,求解,L,1,(x)=a,1,x+a,0,已知,使得,f(x),L,1,(x),x,x,0,x,1,.,根据点斜式得到,如果令,则称,l,0,(x),l,1,(x),为一次插值多项式的基函数。这时：,并称其为一次Lagrange插值多项式。,f(x),L,1,(x)=y,0,l,0,(x)+y,1,l,1,(x),9,二、抛物线插值,（n=2）,求解,L,2,(x)=a,2,x,2,+a,1,x+a,0,使得,f(x),L,2,(x),x,x,0,x,2,.,关于二次多项式的构造采用如下方法：令,已知,并由插值条件,得到,L,2,(,x,),=A,(,x-x,1,)(,x-x,2,),+B,(,x-x,0,)(,x-x,2,),+C,(,x-x,0,)(,x-x,1,),L,2,(,x,0,),=y,0,L,2,(,x,1,)=,y,1,L,2,(,x,),=y,2,10,于是得到,则有,这时：,f(x),L,2,(x)=y,0,l,0,(x)+y,1,l,1,(x)+y,2,l,2,(x),紧凑格式,如果令,并称其为二次Lagrange 插值多项式。,11,另外，如果再引进记号,则其导数为,而且,于是,12,这样，就得到二次拉格朗日插值多项式的三种表示形式,紧凑格式,这样就得到在区间,a,b,上关于,f,(,x,),的近似计算式,基函数表示,3,(x),表示式,下面给出,n,次拉格朗日插值多项式的构造,。,13,三、,n,次Lagrange插值多项式,已知n+1组离散数据,按照二次Lagrange插值多项式的构造方法，令：,将插值条件,L,n,(x,0,)=y,0,代入，得到：,同理，由插值条件,L,n,(x,1,)=y,1,，,得到：,14,由插值条件,L,n,(x,n,)=y,n,得,将,代入下式：,得到：,15,也就是,16,紧凑格式,基函数表示,引进基函数,则有,17,还有一种表示式,n+1,(x),表示式,其中,n+1,(,x,)=(,x-x,0,)(,x-x,1,)(,x-x,n,).,从而就得到了在区间,a,b,上的关于函数,f(x),的n次多项式近似计算式：,关于这样的近似计算，需要在计算机上进行，一般我们 利用紧凑格式设计程序，程序的流程图如下：,18,开 始,输入,y=0，j=0,t=,1,j=n?,N,j=,j+1,输出,y,Y,结 束,19,例：,某化学反应中,在有限个时刻,t,(min),，,测,得生成物质量浓度,y,(10,-3,g/cm,3,),的如下数据,那么在时刻,t=5分，t=16.4,分时的浓度是多少？,t,i,1,2,3,4,6,8,10,12,14,16,y,i,4.00,6.41,8.01,8.79,9.53,9.86,10.33,10.42,10.53,10.61,解：,编写程序进行计算,1).先编写Lagrange插值算法子程序,2).再编写主程序Lagrange2调用子程序。,3).计算在t=5，t=16.4的浓度值，并画出曲线图。,20,%lagrange.m,function,y=lagrange(x0,y0,x),n=length(x0);m=length(x);,for,k=1:m,z=x(k);,s=0.0;,for,j=1:n,p=1.0;,for,i=1:n,if,i=j,p=p*(z-x0(i)/(x0(j)-x0(i);,end,end,s=p*y0(j)+s;,end,y(k)=s;,end,%lagrange2.m,x0=1 23 4 6 8 10 12 14 16;,y0=4.00 6.41 8.01 8.79 9.53 9.86 10.33,10.42 10.53 10.61;,x=1:0.1:16;,y=lagrange(x0,y0,x);,x1=5;,x2=16.4;,y1=lagrange(x0,y0,x1),y2=lagrange(x0,y0,x2),plot(x0,y0,.k,markersize,20),hold on,plot(x,y,-r,markersize,30),hold on,plot(x1,y1,*b,markersize,8),hold on,plot(x2,y2,*b,markersize,8),legend(原数值点,Lagrange曲线,2),21,计算结果：,y(5)=9.2300,y(16.4)=6.5872,22,例1 已知,分别用线性插值和二次插值计算 sin0.3367.,解：设,1）.取,x,0,x,1,作线性插值,于是,关于误差，由,得到：,23,2）.取,x,0,x,1,x,2,作二次插值,得到,关于误差，由,得到,24,四、插值余项（误差估计）,定理2：,设,f,(,x,)C,n,a,b,f,(,n+1,),(,x,),在,(,a,b,),内存在,，,x,0,x,1,x,n,是,a,b,中的,n+1,个互异节点,，则当,x,a,b,时,n,次,Lagrange,插值多项式的截断误差为,：,(5),证明,：令,x,是,a,b,中任意固定的数，如果,x,是插值节点,x,i,则,(5),左右两端均为零，等式,(5),成立,。,如果,x,不是节点,x,i,，,作辅助函数如下：,n+1,(,x,)=(,x-x,0,)(,x-x,1,)(,x-x,n,).,25,其中,n+1,(,x,)=(,x-x,0,)(,x-x,1,)(,x-x,n,).,可以检验,同理可得,而且,可知 在区间,a,b,内有,n+2,个零点:,x,0,、,x,1,、,x,n,、,x,.,由,Rolle,定理可知，的导函数 在(a,b)内有,n+1,个零点：,再利用,Rolle,中值定理可知 在(,a,b,)内有,n,个零点。,以此类推，可知 在,(,a,b,),内至少有,1,个零点：,26,即,而根据,求得,于是,从而得到误差估计式,27,对于误差估计式,当,n=1,时,如果,存在，则可以估计误差限：,28,于是，得到如下,Lagrange,插值多项式及其误差估计,这里,f,(,x,),=L,n,(,x,),+R,n,(,x,),当,f(x),L,n,(,x,),时，误差为,R,n,(,x,)。,29,实验作业：,编写,Lagrange,插值多项式计算程序进行实际计算,已知函数y=f(x)的如下离散数据,x,0,1,2,y,2,3,12,1).试用线性插值求函数在 x=1.5处的近似值。,2).试用二次插值求函数在 x=1.5处的近似值。,30,3 差商及Newton插值多项式,一、差商及其性质,Lagrange,插值多项式的优点是格式整齐规范，但其缺点是：当需要增加节点时，其基函数都要发生变化，需要重新计算，这在实际计算中会影响效率。下面介绍的,Newton,插值法会弥补这一不足,。,1.差商的定义,设,y=f(x),在,n+1,个互异点,x,0,x,1,x,n,处的函数值为,：,则称,为,f(x),关于点,x,i,x,j,的一阶差商。,称,为,f(x),关于点,x,i,x,j,x,k,的二阶差商。,31,一般地，称,为,f(x),关于点 的,k,阶差商,。,例如，已知,f(x),在,的函数值为：,可以求得,32,2.,差商的性质,性质1：,k,阶差商,是由函数值,的线性组合而成，即,其中,证明：以,k=2,进行证明。由,得到,33,由,得到,从而,34,证明：以,k=1,为例,性质2:差商具有对称性,即,k,阶差商,f,x,0,x,1,x,k-1,x,k,中，任意调换,x,i,x,j,的次序，其值不变。,以,k=2,为例,35,性质3：若,f(x),为,n,次多项式，则,f,x,x,0,为关于,x,的,n-1,次多项式。,证明：已知,由于,故,类似的可以得到：,也就是说，对多项式求一次差商，次数降低一次。,36,3.差商的计算,为构造,Newton,插值多项式方便起见，计算差商时，采用列表的方式进行。,37,例,2,已知函数,y=f(x),的如下离散数据,(1,0)、(2,2)、(4,12)、(5,20)、(6,70),，试求其各阶差商.,解：列差商表计算,x,y,一阶差商,二阶差商,三阶差商,四阶差商,1,0,2,2,4,12,5,20,6,70,2,5,8,50,1,1,21,0,5,1,38,二、,Newton,插值多项式,对于区间a,b内的离散点 及相应的函数值 ，计算如下差商：,可以求得：,39,依次将下式带入上式得到：,40,则可以将函数,f(x),表示成：,令：,容易验证,因此,N,n,(x),满足插值条件，是一个,n,次插值多项式。,41,并称,为n次Newton插值多项式。,如果,f(x),N,n,(x),则误差为：,由Newton插值多项式的结构可以看出，在构造Newton插值多项式时，必须首先计算各阶差商。,关于Newton插值多项式，有以下几个特点：,42,1,.Newton,插值多项式与,Lagrange,插值多项式的误差相同,这是因为Newton插值多项式与Lagrange插值多项式满足相同的插值条件,因此，Newton插值多项式与Lagrange插值多项式的误差相同。这样，由,得到,这个表达式给出了,n+1,阶差商与,n+1,阶导数之间的关系式。,N,n,(,x,i,)=,f,(,x,i,),i=0,1,n,L,n,(,x,i,)=,f,(,x,i,),i=0,1,n,43,例3 已知,，试求其如下差商,解：由差商与导数的关系式,得到,44,2.,Newton插值多项式具有递推式,由 Newton插值多项式,可知,所以，具有递推公式：,由此可知：当求出n次插值多项式后，再增加一个节点时，只需要增加一项的计算即可。,45,例3 已知,f(x),的五组数据(,1.0)、(2,2)、(3,12)、(4,42)、(5,116),求,N,4,(x),。如果再增加一个节点(6,282),求出,N,5,(x),，并计算,N,4,(1.5)、N,5,(1.5),.,解：先由前五组数据列差商表,1,0,2 2,3 12,4 42,5 116,2,10,30,74,4,10,22,2,4,0.5,得到：,如果，再增加一点(6,282),就在上表中增加一行计算差商。,6 282,166,46,8,1,0.1,46,由Newton公式的递推式得到：,得到：,实验练习：已知离散数据,(1,0)、(2,2)、(4，12）、(5,20),求三次牛顿插值多项式，增加一点(6,70)后，,再求出四次牛顿插值多项式。,47,本节要点,1.,掌握差商及其性质，导数与差商的关系,2.,掌握,Newton,插值多项式的构造方法及具体结构,3.,掌握,Newton,插值多项式的误差结果,4.编写,Newton,插值多项式计算程序进行实际计算,实验作业题,如何实现差商表和,Newton,插值多项式的程序设计,。,48,for(j=0;j=j+1-1;i-),y0i=(y0i-y0i-1)/(x0i-x0i-i);,第一步：计算差商,Newton插值多项式程序设计,x,j,y,j,一阶差商,二阶差商,三阶差商,F,j,x,0,y,0,F,0,x,1,y,1,f,x,0,x,1,F,1,x,2,y,2,f,x,1,x,2,f,x,0,x,1,x,2,F,2,x,3,y,3,f,x,2,x,3,f,x,1,x,2,x,3,f,x,0,x,1,x,2,x,3,F,3,for i=1:n-1,for j=n:-1:i+1,y0(j)=(y0(j)-y0(j-1)/(x0(j)-x0(j-i);,end,end,49,for(k=0;k=m;k+),zk=y00;,for(j=1;j=n;j+),t=1.0;,for(i=0;i=j-1;i+),t=t*(xk-x0i);,zk=zk+t*y0j;,第一步：计算m个点的函数值,for k=1:m,z(k)=y0(1);,for i=2:n,t=1.0;,for j=1:1:i-1,t=t*(x(k)-x0(j);,end,z(k)=z(k)+t*y0(i);,end,end,for(j=0;j=j+1-1;i-),y0i=(y0i-y0i-1)/(x0i-x0i-i);,50,关于离散数据：,构造了,lagrange,插值多项式：,Newton,插值多项式：,根据问题需要，有时还需要构造分段插值多项式，下面加以介绍,51,4 分段插值多项式,4.1 高次插值的龙格现象,根据插值条件构造的插值多项式作为函数的近似,有很大局限性，插值多项式的次数随着节点个数的增高而升高，但高次插值多项式的近似效果并不理想，看下面的例子。,取等距节点,对于,求出,可构造Lagrange,插值多项式,L,n,(x).,52,n=10,时，插值多项式,L,10,(x),的计算结果见下图：,53,从图中可见，在,x=0,附近,L,10,(,x,),对,f,(,x,),有较好的近似，而点,x,距零点越远，近似效果越差，以至于完全失真。实际上，当,n,时，在,|,x,|0.36.,范围内,L,10,(,x,),收敛于,f,(,x,),而在这个区间外,L,10,(,x,),是不收敛的。这个现象被称为,Runge,（龙格）现象,。,Runge,现象表明，为减小近似误差，盲目地提高插值多项式次数是不可取的，实际上，,很少采用高于7次的插值多项式,。因此，只能通过缩小插值区间的办法达到减小误差的目的，这就是下面要讨论的低次分段插值多项式。,54,4.2 分段线性插值,为了提高近似程度，可以考虑用分段线性插值来逼,近原函数。,设,y=f(x),在节点,a=x,0,x,1,x,n,=b,处的函数值为,y,i,=,f,(,x,i,),i=0,1,2,n.,55,这时的插值函数为分段函数：,在区间 上的线性函数为,误差为：,56,易见,S(x),是平面上以点,(,x,i,y,i,)(,i=0,1,2,.,n,),为节点的折线。有如下的特点：,1）,S(x),在,x,i-1,x,i,上为次数不超过一次的多项式。,若,，,由线性插值的误差公式：,2）,S(x),C,a,b,;,3）,S(x),C,1,x,i-1,x,i,;,得到,57,则有：,令,可以按如下的方式考虑：,关于整体误差：,58,于是,当,h 0,时，分段线性插值,S(x),收敛于,f(x),。,值的注意的是：分段线性插值虽然有很好的收敛性质，但却不是光滑的。也就是说，,S(x),的导数不一定存在！,若记,则对任一,x,a,b,都有,下面我们就考虑在节点处可导的插值多项式的构造。,59,4.3,分段,Hermite,插值,分段线性插值多项式,S(x),在插值区间,a,b,上只能保证连续性，而不光滑。要想得到在插值区间上光滑的分段插值多项式，可采用分段,Hermite,插值。,如果已知函数,y=f(x),在节点,a=x,0,x,1,x,n,=b,处的函数值和导数值：,则在小区间,x,i-1,x,i,上有四个插值条件：,故能构造一个三次多项式,H,i,(,x,),并称其为,三次埃尔米特,(Hermite),插值多项式,。,y,k,=f,(,x,k,),y,k,=,f,(,x,k,),k=0,1,n,y,i-1,=f,(,x,i-1,),y,i,=,f,(,x,i,),y,i-1,=f,(,x,i-1,),y,i,=,f,(,x,i,),60,其中,H,i,(,x,),x,x,i-1,x,i,满足条件,：,这时，在整个,a,b,上可以用分段三次,Hermite,插值多项式来逼近,f(x),。,61,关于,H,i,(,x,),的构造，我们可以通过基函数来进行,：,由插值条件：,可以给出基函数满足的条件：,62,由于,i-1,(,x,),满足条件,：,我们称,为三次,Hermite,插值基函数。,所以,i-1,(,x,),应该具有形式,：,下面来求基函数：,再将 代入可得,而且,63,将,得到,类似地有,代入下式：,64,代入下式,得到,这样，便求出了分段三次,Hermite,插值多项式：,65,关于误差，若,f(x),在,a,b,具有,4,阶连续导数，可推得,其中,如果记,则有：,即,66,关于整体误差，若,f(x),C,4,a,b,则可按如下方式考虑：,记,则有：,于是,当,h 0,时，,R(x)0.,说明分段三次Hermite插值,H,(,x,),收敛于,f(x),。,67,上节中的分段低次插值有很好的收敛性，但其光滑性不够理想，为了提高光滑性，就得增加节点上的导数插值条件，这显然是困难的。,由,H(x),的表达式，可以的知它有如下特性：,（2）,H(x),C,1,a,b,;,（3）,H,(,x,),C,2,x,i-1,x,i,.,（,1）,H,(,x,),在,a,b,上是分段函数，且在每个,x,i-1,x,i,是一个三次多项式;,比分段线性插值的光滑性要好一些。,理想的结果是：构造一个多项式，在不增加已知条件的情况下，既有好的逼近效果，又有好的光滑性。下一节讨论这样的问题。,68,本节问题,2.分段线性插值有何优缺点？如何估计误差？,4.如何分段线性插值算法的程序设计？,1.何为高次插值的,Runge,现象，应如何避免？,3.分段三次,Hermite,插值有何优缺点,如何估计误差,5.如何构造满足以下条件的插值多项式并估计误差？,69,5,三次样条插值,前面讨论的分段线性插值，逼近程度好，但光滑性差。分段三次,Hermite,插值，逼近程度好，光滑性也比较好，但需要增加更多的条件，不实用。,理想的结果是：在不增加更多条件的情况下，构造出的插值多项式，既不出现Runge现象，也有很好的逼近程度，还有很好的光滑性。,下面讨论的样条函数就具有这样的特性！,70,所谓三次样条一词来源于一种绘图工具：绘图尺，柔软富有弹性，作图时可以用它作出不同弯曲程度的曲线。,当我们用直尺作曲线时，得到左图的形状；当用样条尺作图时，会得到右图的形状，具有好的光滑性。并称其为样条函数。,71,5.1,样条(,Spline）,函数的定义,已知函数,y=f,(,x,),在节点,a=x,0,x,1,x,n,=b,处的函数值为,如果函数,S,(,x,),满足条件：,（1）,S(x),是一个分段的,m,次多项式且,S(x,k,)=y,k,；,则称,S(x),是,m,次样条插值函数。,（2）,S(x),在,a,b,具有,m-1,阶连续导数,。,1.m次样条函数的定义,y,k,=f,(,x,k,),k=0,1,2,n,72,2.,三次样条函数的定义,已知函数,y=f,(,x,),在节点,a=x,0,x,1,x,n,=b,处的函数值为,如果函数,S(x),满足条件：,（1）,S(x),是一个分段的三次多项式,S(x,k,)=y,k,；,则称,S(x),是三次样条插值函数。,（2）,S(x),在,a,b,具有二阶连续导数。,y,k,=f,(,x,k,),k=0,1,2,n,73,S(x),的具体形式为：,其中,S,i,在上,x,i-1,x,i,是三次多项式,有四个待定常数。这样,S,(,x,),共有,4n,个待定常数要确定。也就是说，需要,4n,个条件来确定这些系数,。,根据已知条件及三次样条函数的性质，一共有,已知条件。还缺两个条件，通过增加边界条件来补充。,(n+1),+(n-1),+(n-1),+(n-1),=4n-2,74,常用的边界条件有以下几种：,边界条件,1：,边界条件,2：,边界条件,3：,假定函数,y=f(x),是以,b-a,为,周期的周期函数，这时要求,S(x),也是周期函数，即,这样我们便可以具体求出样条函数来,。,75,5.2,样条函数的求解,1.,三转角算法,由,n+1,组数据,只要求出在区间,x,i-1,x,i,上的三次多项式,S,i,(x),i=1,2,n,即可,。,加边界条件构成的三次样条函数为分段函数,a=x,0,x,1,x,n,=b,y,k,=f,(,x,k,),k=,0,1,2,n,76,已知,S,i,(,x,),满足条件,由于,S,i,(,x,),是三次多项式，还缺少两个条件。在这里假设,S,i,(x),在两个端点的导数值已知：,(2.1),(2.2),(2.1)、(2.2),满足三次,Hermite,插值多项式的条件，故可以得到,：,77,上式给出了,S,i,(x),的表达式，但是表达式中的,m,i-1,和,m,i,还是未知的，还需要求出,m,i-1,、,m,i,来才具体求出了三次样条函数。,这时，根据三次样条函数的定义：,S(x),在,a,b,上具有二阶连续导函数，可知在节点,x,i,处,78,而：,于是，由,两边求导得：,79,于是,同理可得,80,根据二阶导数连续性条件,即,及,得到,81,用,除等式两侧得到,将等式,合并整理得：,82,令：,于是,这是一个方程组，可以进一步写为：,83,式,（2.3）,给出了,n+1,个未知数,m,0,m,1,m,n,的,n-1,个方程，若要求解出来，还需要补充两个方程，这时可以考虑所给定的边界条件。,（2.3）,84,得到,这样，我们只需要求出,m,0,m,1,m,n,即可,。,边界条件,1：,这时方程,改写为：,85,或者，表示为矩阵方程,(2.4),由于,k,+,k,=1,方程,（2.4）,的系数矩阵是严格对角占优矩阵，方程,（2.4）,有惟一解，并可用追赶法求解。,86,便得到三次样条函数：,解出,m,0,m,1,m,n,以后，代入下式,87,也就是：,边界条件2：,已知：,故可以得到,88,将,与前面得到的方程组,结合，可以给出求解,m,0,m,1,m,n,的方程组：,89,求解此方程组，也可以求出三次样条函数。,(2.5),或者表示为矩阵方程,90,由第一个等式和第二个等式得到,y,0,=y,n,m,0,=m,n,边界条件,3：,周期边界条件,由第三个等式说明,再由,91,即：,得到,由,m,0,=m,n,整理为,92,在等式,两边同除以,得到,令,得到,93,结合得到,与,将,94,并将,表示为矩阵方程：,(2.6),其系数矩阵称作周期三对角矩阵，也是严格对角占优，因而方程组有唯一解。,95,三次样条函数三转角算法的实现流程,Step1:,输入节点,x,0,x,1,x,n,函数值,y,0,y,1,y,n、,边界条件及,x.,Step3:,根据边界条件，求解相应的方程得到,m,0,m,1,m,n,Step2:计算,Step4:,判断,x,x,i-1,x,i,?,Step5:,计算,y s,i,(,x,),Step6:,输出,y,96,三次样条函数曲线图,97,设,例2-4 已知函数,y=f(x),的如下数据,试求 其在区间0,3上的三次样条插值函数,S,(x),。,解 这里边界条件是,求得,98,已知,由方程组,及,得到方程组,解得,99,这样便求得,代入表达式,便得到所求的三次样条函数,100,本节,(,5-1、2,),要点,什么是三次样条函数？,三次样条函数的边界条件是如何给出的？,三次样条函数的三转角算法是如何构造的？,如何设计程序实现三转角算法？画出流程图。,三对角线性方程组和一般线性方程组如何求解？,完成,P49,习题,2-12,、,2-13,。,101,2.,三弯矩算法,只要求出在区间,x,i-1,x,i,上的三次多项式,S,i,(x),i=1,2,n,即可,。,在这里我们采用另一种方法进行求解，并称为,三弯矩算法,。,加边界条件构成的三次样条函数为分段函数,a=x,0,x,1,x,n,=b,y,k,=f,(,x,k,),k=,0,1,2,n,对于离散点及其上的函数值：,102,已知,S,i,(x),满足条件,S,i,(x,i-1,),=,y,i-1,，S,i,(x,i,),=,y,i,(2.1),在此假设,S,i,”,(,x,i-1,),=,M,i-1,S,i,”,(,x,i,),=,M,i,(2.2),对于,三次多项式,S,i,(,x,),，,其二阶导函数,S,i,(,x,i-1,),为线性函数，故可设,积分两次得到,(2.3),103,可以求得,：,再由条件,S,i,(x,i-1,),=,y,i-1,，S,i,(x,i,),=,y,i,(2.1),(2.3),代入,(2.3),得到,：,再根据,：,S,i,(,x,),S,i+1,(,x,),及,104,这时,于是根据,得到,也就是,105,两边同除以,上式得,令,则有,这是含有n-1个方程的线性方程组，具体形式为：,106,该线性方程组含有n+1个未知量，要解出唯一的一组解来，还需要补充两个方程，这可以有边界条件来实现。,边界条件,1：,也就是,由,得,107,即,再由,得,即,结合,可以得到求解,M,0,、M,1,、M,n,的线性方程组。,108,其中,方程组,(2.6),的矩阵形式为,109,边界条件,2：,这说明,这时方程组,直接转化为恰定方程组,110,矩阵形式为,边界条件,3：,由,111,即,得,代入,得,112,令,则,结合,113,得,矩阵形式为,114,针对三种边界条件求解相应的方程组,115,得到,M,0,、M,1,、M,n,后代入,就可以得到三次样条函数,并把以上算法称作,三弯矩算法,。,116,例,2-5,求三次样条插值函数,S(x)，,满足自然边界条件,(,S,”,(,x,0,)=,S,”,(,x,n,)=0)，,已知离散数据如下：,i,0,1,2,3,4,x,i,0.25,0.30,0.39,0.45,0.53,y,i,0.500,0.5477,0.6245,0.6708,0.2780,解：,已知,M,0,=M,4,=0,，先求出步长,h,1,=0.05,h,2,=0.09,h,3,=0.06,h,4,=0.08,再计算,117,代入方程组,得到,解得,M,0,=0,M,1,=-1.8806,M,2,=-0.8836,M,3,=-1.0261,M,4,=0,.,118,代入,得到,119,5.3 三次,样条插值函数的误差估计,1.,如果,f(x),C,a,b,，且划分的网格比,其中,一致有界，则当,时，,S(,x,),一致收敛于,f(,x,),.,2.,如果,f(,x,),C,4,a,b,，且,S(,x,),满足边界条件,I、II,则,即,h,0,时，,如果划分比,一致有界，,120,5.4 三次,样条插值函数的程序设计,1.,三对角方程求解的追赶法,#include,#include,int cetrd(double b,int n,int m,double d),int k,j;,double s;,if,(m!=(3*n-2),printf(errorn);return(-2);,for,(k=0;k=0;k-),dk=dk-b3*k+1*dk+1;,return(2);,121,2.,调用追赶法解方程组,#include,#include,main(),int i;,static double b13=13.0,12.0,11.0,10.0,9.0,8.0,7.0,6.0,5.0,4.0,3.0,2.0,1.0;,static double d5=3.0,0.0,-2.0,6.0,8.0;,i=crtrd(b,5,13,d);,if,(i=0;i=4;i+),printf(“x(%d)=%en”,i,di);,122,本节,(,5),问题,一、何为三次样条函数？三次样条插值多项式有何优点？,二、如何通过,Hermite,插值多项式求解三次样条插值函数？,三、在构造三次样条插值函数时，如何使用边界条件？,四、如何在计算机上实现三次样条函数的近似计算？,五、上机实习任务,1.分段线性插值；2.分段,Hermite,插值,3.三次样条插值：边界条件,I,、边界条件,II,123,练 习 二,2-1,当,x=,1，-1，2,时，,f(x),分别为,0，-3，4,，求,f(x),的二次插值多项式,p,2,(x),。,2-2,设,l,i,(x),是以,x,k,=x,0,+kh,k=0,1,2,3,为插值节点的,3次插值基函数，求 。,2-3,设,l,0,(x),l,1,(x),l,n,(x),是以,x,0,x,1,x,n,为节点的,n,次,Lagrange,插值基函数，求证,（1）,（2）,124,2-4,设,f(x),C,2,a,b,，且,f(a)=f(b)=0,，,其中,证明,2-5,利用 在,x=100,121,144,点的函数值，用插值方法求 的近似值，并由误差公式给出误差界，同时与实际误差作比较。,2-6,在,-4x-4,上给出,f(x)=e,x,的等距节点函数表，利用与距离最近的三点作二次插值作为的,e,2,近似，使其误差不超过,10,-6,，问函数表的步长应多少？,125,2-7 证明n阶差商有下列性质,(1),若,F(x)=f(x)+g(x),，则,F,x,0,x,1,x,n,=,f,x,0,x,1,x,n,+,g,x,0,x,1,x,n,（2）,若,f(x),P,m,(,m,次多项式,),m,n,则,f,x,0,x,1,x,n-1,x,Pm-n.,2-8,f(x)=x,5,+4x,4,+3x+1,求差商,f,2,0,2,1,.,2,5,和,f,2,0,2,1,.,2,6,.,2-9,设,f(x)=x,5,+x,3,+1,取,x,0,=-1,x,1,=-0.8,x,2,=0,x,3,=0.5,x,4,=1,试作出,f(x),关于,x,0,x,1,x,4,的差商 表,给出,f(x),关于,x,0,x,1,x,4,的,Newton,插 值多项式,并给出插值误差。,126,2-11,给定插值条件式,f(0)=0,f(1)=1,f(2)=0,f(3)=1,分别求出边界条件为,或,的三次样条函数的分段表达式。,2-10 设,f(x)=x,4,+2x,3,+5,，,在区间,-3,2,上对节点,x,0,=-3,x,1,=-1,x,2,=1,x,3,=3,求出,f(x),的分段三次,Hermite,插值多项式在每个小区间,x,i,x,i+1,的表达式及误差公式。,127,