《《插值与逼近》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《插值与逼近》PPT课件.ppt（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),多项式插值,从几何上看就是要求过n
2、+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),使满足,li(xj)=ij,i,j=
3、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-x1)(x-xn),则lk(x)可写成,若取
4、(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(x)称为n次Lagrange插值余项.,Lagr
5、ange插值多项式简单而优雅,只要取定节点就可写出基函数,进而得到插值多项式.易于计算机上实现.,设(n)(x)在a,b连续,(n+1)(x)在(a,b)内存在,在节点ax0 x1xnb上,满足插值条件(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=0,1,2,n),(x)=0,即,(t)在a,b至少有n
6、+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,可得误差估计式,实际上,ln11.25=2.420368,|R2(11.25
7、)|=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)的比值为(x)关于点xi,xj的一阶差商,并记为xi,xj,即,
8、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次多,项式;当kn时恒等于0.,其中在k+1个节点之间.,给出节点x0,x
9、1,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)+(x-x0)x0,x1+(x-x0)(x-x1)x0,x1,x2+(x-x0
10、)(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)=Nn(x)+Rn(x),由插值多项式的唯一性有,Nk+1(x)=Nk(x)+k+1(x)x
11、0,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,在区间-1,1上取等距节点xi=-1+ih,i=0,1,10,h=0.2,作(x)关于节点xi(i
12、=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插值,取节点ax0 x1xnb,hi=xi-xi-1(i=1,2,n),插值条件yk=(xk),k=0,1,n.,1.分段线性插值,设S1(x)是满足插值条件的分段一次多项式,则有,S1(x)是平面上以点(xi,yi)(i=0,1,n)为节点的折线.,若(x)C2a,b,则当xxi-1,xi时,有,若记,对任一xa,b都有,
13、可见,当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插值,设在节点ax0 x1xnb,hi=xi-xi-1(i=1,2,n)上给出插值条件yk=(xk),yk=(xk),k=0,1,n.,其中,i-1(x),i(
14、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)=yi,H3(i)(xi-1)=yi-1,H3(i)(xi)=yi,i-1(x),i(x),i-1(x),
15、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带入得,Chi2=1,即 C=hi-2,由对称性可得,满足插值条件H3(xi)=y
16、i,H3(xi)=yi(i=0,1,n)的分段三次多项式H3(x)为,H3(x)=H3(i)(x),xxi-1,xi,i=1,2,n,若(x)C4a,b,则当xxi-1,xi时,有,而且,若(x)C4a,b,记,则有,可见,H3(x)是收敛的.而且由于H3(xi+0)=H3(xi-0)=yi,知H3(x)在a,b具有一阶连续导数.,例6,设(x)C40，2，且(0)=1,(1)=0，(2)=3,(1)=0,试求(x)的三次插值多项式H3(x),并给出余项.,解 法1(基函数法):设,H3(x)=0(x)y0+1(x)y1+2(x)y2+1(x)y1,=0(x)+32(x),所以,则0(x)=c
17、(x-1)2(x-2),=-1/2(x-1)2(x-2),=1/2x(x-1)2,2(x)=cx(x-1)2,H3(x)=-1/2(x-1)2(x-2)+3/2x(x-1)2,=1/2(x-1)2(2-x)+3x,=(x-1)2(x+1),法2(待定系数法):设,由H3(0)=1得:b=1,所以,解得:a=1,b=1.,由H3(2)=3得:2a+b=3,H3(x)=(x-1)2(x+1),H3(x)=(x-1)2(ax+b),于是,R3(x)=C(x)x(x-1)2(x-2),R3(x)=(x)-H3(x),记R3(x)=(x)-H3(x),则R3(0)=R3(1)=R3(2)=R3(1)=0
18、,对于任一x0,2,x0,1,2,构造函数:,(t)=(t)-H3(t)-C(x)t(t-1)2(t-2),由于(0)=(1)=(2)=(1)=(x)=0,可得:,5 三次样条插值,给定节点a=x0 x1xn=b,及其上的函数值yk=(xk),k=0,1,n.就是给出平面上n+1个点(xi,yi),i=0,1,n.,x,y,o,定义6.1 给定节点a=x0 x1xn=b,及其上的函数值yk=(xk),k=0,1,n.如果函数S(x)满足,(1)S(x)是一个分段的三次多项式且S(xk)=yk;,(2)S(x)C2a,b.,则称S(x)是区间a,b上的三次样条插值函数.,S(x)在区间xi-1,
19、xi上是三次多项式,S(x)=aix3+bix2+cix+di,有4个待定系数,要确定S(x)共有4n个待定系数.,由S(xi)=yi,i=0,1,n,有2n个条件.,再由S(xi-0)=S(xi+0),i=1,2,n-1,有n-1个条件,及S(xi-0)=S(xi+0),i=1,2,n-1,有n-1个条件,共有4n-2个条件.,为了得到唯一的三次样条函数,通常可在区间a,b的端点x0=a,xn=b上各加一个条件,称为边界条件.常用的边界条件有,(1)S(x0)=y0,S(xn)=yn;,(2)S(x0)=y0,S(xn)=yn;,(3)假设(x)是以b-a为周期的周期函数,这时要求,S(x0
20、+0)=S(xn-0),S(x0+0)=S(xn-0),S(x0+0)=S(xn-0),这样确定的S(x)为周期样条函数.,若假设S(xi)=mi,i=0,1,n,利用分段Hermite插值多项式,当xxi-1,xi时,有,其中hi=xi-xi-1.为了确定S(x),只需确定mi,i=0,1,n.可利用S(xi-0)=S(xi+0)来求出mi.,当xxi-1,xi时,由于,所以,于是有,由连续性条件S(xi-0)=S(xi+0)可得,两侧同除以,3(ixi-1,xi+ixi,xi+1)=gi,则有,imi-1+2mi+imi+1=gi,i=1,2,n-1.(6.9),再结合不同的边界条件,可得
21、关于mi的方程.,若边界条件为:m0=y0,mn=yn,带入(6.9)式可得,若边界条件为:S(x0)=y0,S(xn)=yn,则有,连同(6.9)式一起,可得,若边界条件为周期性边界条件，由S(x0+0)=S(xn-0),和S(x0+0)=S(xn-0),有,m0=mn,nmn-1+2mn+nm1=gn,和,其中,于是有,对应不同的边界条件，只要求出相应的线性方程组的解，便得到三次样条函数在各区间xi-1,xi上的表达式.,由于三个方程组的系数矩阵都是严格对角占优矩阵,所以都有唯一解,前两个方程组均可用追赶法求解,第三个方程组可用LU分解法或Gauss消元法求解.,例7,设(0)=1,(1)
22、=0,(2)=-1,(3)=0,(0)=1,(3)=0,试求(x)在区间0,3的三次样条插值函数S(x).,解 这里h1=h2=h3=1,y0=1,y3=0,计算参数有,1=2=1=2=1/2,g1=-3,g2=0,于是有,解得,故有,三次样条函数S(x)也可以利用在节点处的二阶导数为参数来表示,设S(xi)=Mi,i=0,1,n,则对xxi-1,xi有,连续积分两次,并利用S(xi-1)=yi-1,S(xi)=yi,确定积分常数,可得,其中hi=xi-xi-1.为了确定S(x),只需确定Mi,i=0,1,n.可利用S(xi-0)=S(xi+0)来求出Mi.,对上式求导易得:,于是有,因此,若
23、记,则有,再结合不同的边界条件,可得关于Mi的方程.,若边界条件为:M0=y0,Mn=yn,可得,若边界条件为:S(x0)=y0,S(xn)=yn,则有,可得,若边界条件为周期性边界条件，由S(x0+0)=S(xn-0),和S(x0+0)=S(xn-0),有,M0=Mn,nM1+nMn-1+2Mn=dn,和,其中,于是有,而且M0=Mn.,例8,设(0)=0,(1)=1,(2)=0,(3)=1,(0)=1,(3)=0,试求(x)在区间0,3的三次样条插值函数S(x).,解 这里h1=h2=h3=1,y0=1,y3=0,计算参数有,1=2=1=2=1/2,d1=-6,d2=6,于是有,解得,故有
24、,利用内积可以定义函数的平方模,6 正交多项式,记区间a,b上所有连续函数的全体为Ca,b,可以证明Ca,b是一个线性空间,把所有次数不超过n的多项式全体记为Pn,则Pn是Ca,b的子空间.若(x),g(x)Ca,b,则称,为(x)与g(x)的内积,记为(,g),满足,(1)(,g)=(g,);,(2)(c,g)=c(,g);,(3)(1+2,g)=(1,g)+(2,g);,若(,g)=0,称(x)与g(x)正交,记为g.,函数的平方模满足,(1)20,而且2=0(x)=0;,(2)c2=|c|2;,(3)+g22+g2,(4)(,g)2 g2,考虑到(x)在区间a,b上各点的函数值比重不同,
25、常引进加权形式的定义,这里函数(x)是非负连续函数,称为a,b上的权函数.它的物理意义可以解释为密度函数.,若0(x),1(x),n(x)为Ca,b上的一组线性无关函数,则可得到Ca,b上一组两两正交的函数组g0(x),g1(x),gn(x)满足,定理6.3,(1)gk(x)为0(x),1(x),k(x)的线性组合;,(2)k(x)为g0(x),g1(x),gk(x)的线性组合.,证 只要按Schemite正交化过程构造,g0(x)=0(x),再令,g0(x),g1(x),gn(x)两两正交且满足(1),(2).,称函数组e0(x),e1(x),en(x)为规范正交组.,Pn上由线性无关函数1
26、,x,x2,xn 经过Schemite正交化过程得到的多项式p0(x),p1(x),pn(x)称为a,b上的正交多项式.,例9,求区间-1,1上,权函数(x)=1的正交多项式.,解 按Schemite正交化过程有,p0(x)=1,若p0(x),p1(x),pn(x)是a,b上权函数为(x)的正交多项式,则有下列性质:,(1)pk(x)是首项系数不为零的k次多项式;,(2)p0(x),p1(x),pn(x)构成Pn上的一组正交基;,(3)pn(x)与任一不高于n-1次的多项式正交,pn(x)Pn-1;,(4)方程pn(x)=0在a,b上有n个单根;,(5)方程pn-1(x)=0的根x1(n-1)
27、,x2(n-1),xn-1(n-1),与方程pn(x)=0的根x1(n),x2(n),xn(n)在a,b上交错分布.,下面介绍几个常用的正交多项式,1.Legendre多项式,的正交多项式,且满足:,是区间-1,1上权函数(x)=1的正交多项式,且满足:,(1)(Lm,Ln)=,(2)有三项递推关系,(n+1)Ln+1(x)=(2n+1)xLn(x)-nLn-1(x),n1,L0(x)=1,L1(x)=x,2.Chebyshev多项式,Tn(x)=cos(narccosx)x-1,1,n=0,1,2,是区间-1,1上权函数(x)=,(1)(Tm,Tn)=,(2)有三项递推关系,Tn+1(x)=
28、2xTn(x)-Tn-1(x)n=1,2,3,T0(x)=1,T1(x)=x,(3)Tn(x)在-1,1上的n个零点为,3.Laguere多项式,是区间0,+)上权函数(x)=e-x 的正交多项式,且满足:,(1)(Lm,Ln)=,Ln+1(x)=(2n+1-x)Ln(x)-n2Ln-1(x),n1,L0(x)=1,L1(x)=1-x,4.Hermite多项式,是区间(-,+)上权函数(x)=,的正交多项式,且满足:,(1)(Hm,Hn)=,Hn+1(x)=2xHn(x)-2nHn-1(x),n1,H0(x)=1,H1(x)=2x,7 数据拟合的最小二乘法,7.1 数据拟合问题,经常由观察或测
29、试可得到y(x)的一组离散数据:,需要在给定的函数类上根据这组离散数据作出逼近曲线.要求逼近曲线在xi处与离散数据尽可能接近.,对函数(x),要求以(x)在离散点的误差,0=(x0)-y0,1=(x1)-y1,m=(xm)-ym,为分量的误差向量=(0,1,m)T,按某一向量范数达到最小.对不同的范数,构造出不同意义下的拟合函数.,函数类通常取为:=Span0(x),1(x),n(x),其中函数系0(x),1(x),n(x)在包含节点xi的区间a,b上线性无关.,(x)=a00(x)+a11(x)+ann(x),中任一函数(x)可以表示为,常用的函数系有幂函数系xj,三角函数系sinjx,co
30、sjx,指数函数系,正交函数系等.最常用的是幂函数系xj,即取=Pn=Span1,x,x2,xn,这时求得的拟合曲线称为多项式拟合曲线.,7.2 数据拟合的最小二乘法,为了便于计算,在求误差向量的范数时,宜采用向量的2-范数,这时对应的曲线拟合方法称为最小二乘法.,就是在函数类=Span0(x),1(x),n(x)中找一个函数y=*(x),使误差向量*的2-范数达到最小值,即,在实际问题中,考虑到数据的比重不同,常采用误差向量的加权范数形式,其中(x)0,是在a,b上的权函数.,由于,G(a0,a1,an),寻求拟合曲线问题就转换为求多元函数G(a0,a1,an)的最小值问题.,令,得到关于a
31、0,a1,an的线性方程组:,引进向量,j=(j(x0),j(x1),j(xm)T,j=0,1,2,n,=(y0,y1,ym)T,且记向量内积,于是有,其矩阵形式为,称为(由最小二乘法导出的)正则方程组或法方程组.,如果向量组0,1,n线性无关,则正则方程组的系数矩阵是对称正定矩阵,可由平方根法或SOR法求得唯一解a0*,a1*,an*,于是得到拟合函数:,*(x)=pn*(x)=a0*0(x)+a1*1(x)+an*n(x),若取函数类=Pn=Span1,x,x2,xn,正则方程组为,其中i=(xi),.此时拟合曲线为,*(x)=pn*(x)=a0*+a1*x+an*xn,若取0(x),1(
32、x),n(x)为正交函数系,即(i,j)=0,(ij),则正则方程组的系数矩阵为对角矩阵,易得,ak*=(,k)/(k,k),k=0,1,2,n,x,y,o,4,-3,1,4,例10 给出如下离散数据,试求y(x)的拟合曲线.,-3,解 绘草图,故求线性拟合曲线,0(x)=1,1(x)=x.权函数(x)=1,记,0=(1,1,1,1,1,1,1,1)T,1=(-3,-2,-1,0,1,2,3,4)T,=(-3.2,-2.1,-1.2,0.1,0.9,2.1,3.3,4)T.正则方程组为,8a0+4a1=3.9,4a0+44a1=46,解得,所求拟合曲线为,此时,拟合曲线的均方误差为|*20.3
33、29666,例11 对下列数据求形如y=aebx的拟合曲线,解 设z=lny,则 z=A+bx,其中A=lna,由zi=lnyi 得,对z(x)作线性拟合曲线,取 0(x)=1,1(x)=x.权函数(x)=1,则 0=(1,1,1,1,1,1,1,1)T,1=(1,2,3,4,5,6,7,8)T,z=(2.72785,3.02042,3.31054,3.60005,3.89386,4.18358,4.47506,4.76729)T,得正则方程组,8A+36b=29.97865,36A+204b=147.13503,解得 A*=2.43686,b*=0.29122,于是有a*=eA*=11.43
34、707,拟合曲线为:(x)=11.43707e0.29122x,例12 用最小二乘法求方程组,3x-2y=1,2x+y=2,x-4y=-1,3x+2y=-3,的近似解.,解 记 G(x,y)=(3x-2y-1)2+(2x+y-2)2+(x-4y+1)2+(3x+2y+3)2,令,则有 6(3x-2y-1)+4(2x+y-2)+2(x-4y+1)+6(3x+2y+3)=0-4(3x-2y-1)+2(2x+y-2)-8(x-4y+1)+4(3x+2y+3)=0,即 23x-2y=-3-2x+25y=-2,解得:x=-0.138354,y=-0.091068,练习题,第180页 习题66-1,6-2,6-3,6-4,6-5,练习题,第180页 习题66-8,6-9,6-10,6-12,6-13,练习题,第180页 习题66-15,6-19,6-20,6-22,课间休息,
