《数值分析第六章插值与逼近》由会员分享，可在线阅读，更多相关《数值分析第六章插值与逼近（66页珍藏版）》请在金锄头文库上搜索。
1、第6章 插值与逼近,1 多项式插值问题,设函数y=(x)在区间a,b上连续，给定n+1个点 a x0 x1 xn b (6.1),已知(xk)=yk(k=0,1,n),在函数类P中寻找一函数(x)作为(x)的近似表达式,使满足,(xk)=(xk)=yk ,k=0,1,n (6.2),称y=(x)为被插值函数; 称(x)为插值函数; 称x0 , x1 ,xn为插值节点; 称式(6.2)为插值条件; 寻求插值函数(x)的方法称为插值方法.,在构造插值函数时, 函数类P的不同选取, 对应不同的,插值方法,这里主要讨论函数类P是代数多项式,即所谓的多项式插值.,o,x0,y,x,y=(x),多项式插值
2、,从几何上看就是要求过n+1个点(xk ,yk) (k=0,1,n)的n次代数曲线y=pn(x)作为(x)的近似.,用Pn表示所有次数不超过n的多项式函数类,若pn(x) Pn ,则pn(x)=a0+a1x+anxn是由n+1个系数唯一确定的.若pn(x)满足插值条件(6.2),则有,x1,xn,y=pn(x),其系数行列式为,定理6.1 给定n+1个互异节点x0,x1,xn上的函数值y0,y1,yn ,则满足插值条件(6.2)的n次插值多项式pn(x)是存在且唯一的.,2 Lagrange插值多项式,对n+1个节点x0,x1,xn ,构造n+1个n次多项式l0(x), l1(x),ln(x)
3、,使满足,li(xj)=ij ,i,j=0,1,n (6.3),就是函数(x)满足插值条件(6.2)的n次插值多项式.,那么,Ln(x)=l0(x)y0+l1(x)y1+ln(x)yn,称lk(x)(k=0,1,n)是关于节点xk (k=0,1,n)的n次Lagrange插值基函数,(6.4)式确定的n次多项式Ln(x)称为n次Lagrange插值多项式.,由于lk(x)满足:lk(xj)=0,(j=0,1,k-1,k+1,n), 所以可设,lk(x)=c(x-x0)(x-x1)(x-xk-1)(x-xk+1)(x-xn),再由lk(xk)=1确定c,从而有,若记n+1(x)=(x-x0)(x
4、-x1)(x-xn),则lk(x)可写成,若取(x)=xk (k=0,1,n),由插值多项式的唯一性有,特别当k=0时,有,例1,求(x)关于节点x0,x1的线性Lagrange插值多项式,解 对节点x0,x1,Lagrange插值基函数为,于是有,易见,L1(x)就是过点(x0,(x0)和点(x1,(x1)的直线.,例2,求(x)关于节点x0,x1,x2的二次Lagrange插值多项式.,解 对节点x0,x1,x2的Lagrange插值基函数为,于是有,L2(x)是过点(x0,(x0),(x1,(x1)和(x2,(x2)的抛物线.,为了研究插值多项式的近似程度,记 Rn(x)=(x)-Ln(
5、x) 称为n次Lagrange插值余项.,Lagrange插值多项式简单而优雅, 只要取定节点就可写出基函数,进而得到插值多项式.易于计算机上实现.,设(n)(x)在a,b连续, (n+1)(x)在(a,b)内存在,在节点ax0x1xnb上, 满足插值条件(6.2)的插值多项式Ln(x),对任一xa,b,插值余项为,定理6.2,其中x(a,b)且与x有关.,证 由于Rn(xi)=(xi)-Ln(xi)=0(i=0,1,n),所以,Rn(x)=C(x)n+1(x),对于任一xa,b,xxi(i=0,1,2,n),构造函数 (t)=(t)-Ln(t)-C(x)n+1(t),则有,(xi)=0 (i
6、=0,1,2,n), (x)=0,即,(t)在a,b至少有n+2个零点.,0=(n+1)(x)=(n+1)(x),由Rolle定理可知(t)在a,b至少有n+1个零点,反复应用Rolle定理知(n+1)(t)在a,b至少有1个零点x, 于是,-C(x),(n+1)!,因而有,所以,若|(n+1)(x)|在a,b有上界Mn+1,则Lagrange插值余项也可写成,用二次插值计算ln11.25的近似值,并估计误差.,例3 给定函数表,解 取节点x0=10,x1=11,x2=12,作二次插值有,ln11.25L2(11.25),在区间10,12上lnx的三阶导数的上限M3=0.002,可得误差估计式
7、,实际上,ln11.25=2.420368,|R2(11.25)|=0.000058.,在被插值函数未知或无法估计其高阶导数界时,上述插值余项不能用来估计误差,下面介绍事后误差估计法.,记Ln(x)是(x)以x0,x1,xn为节点的n次插值多项式而Ln(1)(x)为(x)以x1,x2,xn,xn+1 为节点的n次插值多项式,由于,如在例3中,再以节点x1=11,x2=12,x3=13作二次插值多项式L2(1)(x),则L2(1)(11.25)=2.420301,由(6.7)式得,则有,从而得,若,也有,由(6.6)式也可得到ln11.25的新的近似值,称(xj)-(xi)与xj-xi(ij)的
8、比值为(x)关于点xi,xj的一阶差商,并记为xi,xj,即,3 Newton插值多项式,实际上,(6.6)式右侧恰是(x)以x0,x1,xn,xn+1为节点的n+1次插值多项式.,3.1 差商及其性质,而称,为(x)关于点xi,xj,xk的二阶差商. 一般地,称,为(x)关于点x0,x1,xk的k阶差商.以上定义中,点x0,x1, xk为互不相同的点.,差商具有以下性质:,(1)k阶差商x0,x1,xk可以表示成 (x0), (x1), ,(xk)的线性组合,(2)差商对节点具有对称性,即,其中,i0,i1,ik是0,1,k的任一排列.,(3)n次多项式(x)的k阶差商,当kn时是一个n-k
9、次多,项式;当kn时恒等于0.,其中在k+1个节点之间.,给出节点x0,x1,xn和函数值(x0),(x1),(xn),可按如下的差商表顺序逐次计算各阶差商值.,(4)若(x)具有k阶连续导数,则,例4 给出函数y=(x)的函数表,解 差商表如下,写出函数y=(x)的差商表.,(x)=(x0)+(x-x0)x0,x,由差商的定义可得,所以有,3.2 Newton插值多项式及其余项,x0,x=x0,x1+(x-x1)x0,x1,x,x0,x1,x=x0,x1,x2+(x-x2)x0,x1,x2,x,x0,x1,xn-1,x=x0,x1,xn +(x-xn)x0,x1,xn,x,(x)=(x0)+
10、(x-x0)x0,x1 +(x-x0)(x-x1)x0,x1,x2+ +(x-x0)(x-x1)(x-xn-1)x0,x1,xn +(x-x0)(x-x1)(x-xn)x0,x1,xn,x,则有,而且Nn(x)是n次多项式,且满足Nn(xi)=(xi)(i=0,1,n),Rn(x)=(x-x0)(x-x1)(x-xn)x0,x1,xn,x,记,称Nn(x)为n次Newton插值多项式,称Rn(x)为n次Newton插值余项.,Nn(x)=(x0)+(x-x0)x0,x1 +(x-x0)(x-x1)x0,x1,x2+ +(x-x0)(x-x1)(x-xn-1)x0,x1,xn (6.8),(x)
11、=Nn(x)+Rn(x),由插值多项式的唯一性有,Nk+1(x)=Nk(x)+k+1(x)x0,x1,xk+1 k=1,2,n-1,由(6.8)式易见,解 由例4的差商表知x0,x1=-2,x0,x1,x2=3, x0,x1,x2,x3=-1,于是有,N1(x)=5-2(x+2)=1-2x N2(x)=1-2x+3(x+2)(x+1)=3x2+7x+7 N3(x)=3x2+7x+7-(x+2)(x+1)(x-1)=-x3+x2+8x+9,例5,对例4中的(x),求节点为x0,x1的一次插值x0,x1, x2的二次插值和x0,x1,x2,x3的三次插值多项式.,对(x)=(1+25x2)-1,在
12、区间-1,1上取等距节点xi=-1+ih, i=0,1,10,h=0.2,作(x)关于节点xi(i=0,1,10)的10次插值多项式L10(x), 如图所示,看下面的例子,4 分段插值多项式,x,y,o,1,-1,0.5,1,1.5,y=L10(x),这个现象被称为Runge现象. 表明高次插值的不稳定性. 实际上, 很少采用高于7次的插值多项式.,4.1 分段Lagrange插值,取节点ax0x1xnb,hi=xi-xi-1(i=1,2,n),插值条件yk=(xk),k=0,1,n.,1. 分段线性插值,设S1(x)是满足插值条件的分段一次多项式,则有,S1(x)是平面上以点(xi,yi)(
13、i=0,1,n)为节点的折线.,若(x)C2a,b,则当xxi-1,xi时,有,若记,对任一xa,b都有,可见,当h0时,分段线性插值S1(x)收敛于(x).,2. 分段二次插值,在每个小区间xi-1，xi内,取半节点,若记,补充插值条件,(i=1,2,n),设(x)满足插值条件的分段二次插值多项式为S2(x),则有,若(x)C3a,b,则当xxi-1,xi时,有,则有,可见,S2(x)是收敛的,而且S2(x)在a,b是连续的,但不可导.,此时,在小区间xi-1,xi上有四个插值条件,故能构造一个三次多项式,只要令,4.2 分段Hermite插值,设在节点ax0x1xnb,hi=xi-xi-1
14、(i=1,2,n)上给出插值条件yk=(xk),yk=(xk),k=0,1,n.,其中,i-1(x),i(x),i-1(x),i(x)都是三次多项式,而且满足,则,H3(i)(x)就是满足条件,的三次多项式.,下面来求基函数.,i-1(xi-1)=1,i-1(xi)=0,i-1(xi-1)=0,i-1(xi)=0,i(xi-1)=0,i(xi)=1,i(xi-1)=0,i(xi)=0,i-1(xi-1)=0,i-1(xi)=0,i-1(xi-1)=1,i-1(xi)=0,i(xi-1)=0,i(xi)=0,i(xi-1)=0,i(xi)=1,H3(i)(xi-1)=yi-1, H3(i)(xi
15、)=yi, H3(i)(xi-1)=yi-1, H3(i)(xi)=yi,i-1(x),i(x),i-1(x),i(x)称为三次Hermite插值基函数.,因为i-1(xi)=0,i-1(xi)=0,所以可将i-1(x)写成 i-1(x)=(ax+b)(x-xi)2,解得 a=2hi-3, b=(xi-3xi-1)hi-3,由对称性可得,将i-1(xi-1)=1,i-1(xi-1)=0带入可得 (axi-1+b)hi2=1 , ahi2-2hi(axi-1+b)=0,故得,因为i-1(xi-1)=0,i-1(xi)=0,i-1(xi)=0，所以有,因此,故有,i-1(x)=C(x-xi-1)(x-xi)2,将i-1(xi-1)=1
