第六章--插值与逼近课件.ppt

《第六章--插值与逼近课件.ppt》由会员分享，可在线阅读，更多相关《第六章--插值与逼近课件.ppt（69页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第6 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是代数多项式,即所谓的多项式插

2、值.ox0yxy=(x)多项式插值,从几何上看就是要求过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),则有x1xny=pn(x)其系数行列式为 定理定理6.16.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(

3、x),l1(x),ln(x),使满足 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次LagrangeLagrange插值节点基函数插值节点基函数,(6.4)式确定的n次多项式Ln(x)称为n次LagrangeLagrange插值多项式插值多项式.由于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-x

4、n)再由lk(xk)=1确定c,从而有 若记n+1(x)=(x-x0)(x-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)的抛物线

5、.为了研究插值多项式的近似程度,记 Rn(x)=(x)-Ln(x)称为n n次次LagrangeLagrange插值余项插值余项.Lagrange插值多项式简单而优雅,只要取定节点就可写出基函数,进而得到插值多项式.易于计算机上实现.设(n)(x)在a,b连续,(n+1)(x)在(a,b)内存在,在节点ax0 x1n时恒等于0.其中在k+1个节点之间.给出节点x0,x1,xn和函数值(x0),(x1),(xn),可按如下的差商表顺序逐次计算各阶差商值.(4)若(x)具有k阶连续导数,则xi(xi)一阶差商二阶差商三阶差商n阶差商x0 x1x2x3xn(x0)(x1)(x2)(x3)(xn)x0

6、,x1x1,x2x2,x3xn-1,xnx0,x1,x2x1,x2,x3xn-2,xn-1,xnx0,x1,x2,x3xn-3,xn-2,xn-1,xnx0,x1,xn 例例4 4 给出函数y=(x)的函数表 解解 差商表如下i0123xi-2-112(xi)531721写出函数y=(x)的差商表.ixi(xi)一阶差商二阶差商三阶差商0123-2-112531721-2743-1-1 (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

7、-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)(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 n次次NewtonNewton插值多项式插值多项式,称Rn(x)为n n次次NewtonNewton插值余项插值余项.

8、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)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、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=0,1,10)的10次插值多项式L10(x),如图所示 看下面的例子4 分段插值多项式分段插值多项式xyo1-10.511.5y=L10(x)这个现象被称为Runge现象现象.表明高次插值的不稳定性.实际上,很少采用高于7次的插值多项式.4.1 分段分段Lagrange插值插值 取节点ax0 x1xnb,hi=xi-xi-1(i=1,2,n)

10、,插值条件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都有可见,当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是连续的,但不可导.

11、此时,在小区间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(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-

12、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),i(x)称为三次三次HermiteHermite插插值基函数值基函数.因为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,ahi

13、2-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)=yi,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具有一阶连续导数.

14、例例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(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得:

15、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对于任一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.xyo 定义定义6.1 给定节

16、点a=x0 x1xn=b,及其上的函数值yk=(xk),k=0,1,n.如果函数S(x)满足 (1)S(xk)=yk;(2)S(x)是一个分段的三次多项式且S(x)C2a,b.则称S(x)是区间a,b上的三次样条插值函数三次样条插值函数.S(x)在区间xi-1,xi上是三次多项式,S(x)=aix3+bix2 +cix+di,有4个待定系数,要确定S(x)共有4n个待定系数.由S(xi)=yi,i=0,1,n,有n+1个条件,对i=1,2,n-1,由 S(xi-0)=S(xi+0),S(xi-0)=S(xi+0),及S(xi-0)=S(xi+0),有3n-3个条件，共有4n-2个条件.为了得到

17、唯一的三次样条函数,通常可在区间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+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

18、)来求出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)再结合不同的边界条件,可得关于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 和 其中 于是有 对应不同的边界条

19、件，只要求出相应的线性方程组的解，便得到三次样条函数在各区间xi-1,xi上的表达式.由于三个方程组的系数矩阵都是严格对角占优矩阵,所以都有唯一解,前两个方程组均可用追赶法求解,第三个方程组可用LU分解法或Gauss消元法求解.例例7 设(0)=1,(1)=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

20、-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.对上式求导易得:于是有因此若记则有再结合不同的边界条件,可得关于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)=

21、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 于是有 解得 故有 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);若

22、(,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上各点的函数值比重不同,常引进加权形式的定义 这里函数(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(

23、x),gk(x)的线性组合.证证 只要按SchemiteSchemite正交化过程正交化过程构造 g0(x)=0(x),g0(x),g1(x),gn(x)两两正交且满足(1),(2).再令称函数组e0(x),e1(x),en(x)为规范正交组规范正交组.Pn上由线性无关函数1,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)的正交多项式,则有下列性

24、质:(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),x2(n-1),xn-1(n-1),与方程pn(x)=0的根x1(n),x2(n),xn(n)在a,b上交错分布.下面介绍几个常用的正交多项式系 1.Legendre 1.Legendre多项式多项式是区间-1,1上权函数(x)=1的正交多项式,且满足:(1)(Lm,Ln)=(2)有三项递推关系 (n+1)Ln+1(x)

25、=(2n+1)xLn(x)-nLn-1(x),n1 L0(x)=1,L1(x)=x 2.Chebyshev 2.Chebyshev多项式多项式 Tn(x)=cos(narccosx)x-1,1,n=0,1,2,是区间-1,1上权函数(x)=的正交多项式,且满足:(1)(Tm,Tn)=(2)有三项递推关系 Tn+1(x)=2xTn(x)-Tn-1(x)n=1,2,3,T0(x)=1,T1(x)=x (3)Tn(x)在-1,1上的n个零点为 3.Laguere 3.Laguere多项式多项式是区间0,+)上权函数(x)=e-x 的正交多项式,且满足:(1)(Lm,Ln)=Ln+1(x)=(2n+1

26、-x)Ln(x)-n2Ln-1(x),n1 L0(x)=1,L1(x)=1-x 4.Hermite 4.Hermite多项式多项式是区间(-,+)上权函数(x)=的正交多项式,且满足:(1)(Hm,Hn)=Hn+1(x)=2xHn(x)-2nHn-1(x),n1 H0(x)=1,H1(x)=2x7 数据拟合的最小二乘法数据拟合的最小二乘法 7.1 数据拟合问题数据拟合问题 经常由观察或测试可得到y(x)的一组离散数据:xix0 x1x2xmyiy0y1y2ym 需要在给定的函数类上根据这组离散数据作出逼近曲线.要求逼近曲线在xi处与离散数据尽可能接近.对函数(x),要求以(x)在离散点的误差

27、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,cosjx,指数函数系 正交函数系等.最常用的是幂函数系xj,即取=Pn=Span1,x,x2,xn,这时求得的拟合曲线称为多项式拟合曲线多项式拟合曲线.7.2 数据拟合的最小二乘

28、法数据拟合的最小二乘法 为了便于计算,在求误差向量 的范数时,宜采用向量的2-范数,这时对应的曲线拟合方法称为最小二乘法最小二乘法.就是在函数类=Span0(x),1(x),n(x)中找一个函数y=*(x),使误差向量*的2-范数达到最小值,即 在实际问题中,考虑到数据的比重不同,常采用误差向量 的加权范数形式其中(x)0,是在a,b上的权函数权函数.由于 G(a0,a1,an)寻求拟合曲线问题就转换为求多元函数G(a0,a1,an)的最小值问题.令得到关于a0,a1,an的线性方程组:引进向量 j=(j(x0),j(x1),j(xm)T ,j=0,1,2,n =(y0,y1,ym)T 且记向

29、量内积于是有其矩阵形式为称为(由最小二乘法导出的)正则方程组正则方程组或法方程组法方程组.如果向量组 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(x),n(x)为正交函数系,即(i,j)=0,(ij),则正则方程组的系数矩阵为对角矩阵,易得 ak*=(,k)/(k,k),k

30、=0,1,2,nxyo4-314例例10 给出如下离散数据xi-3-2-101234yi -3.2-2.1-1.20.10.92.13.34试求y(x)的拟合曲线.-3 解解 绘草图故求线性拟合曲线,0(x)=1,1(x)=x.权函数(x)=1,记 0 0=(1,1,1,1,1,1,1,1)T,1 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 解得所求拟合曲线为 y=1.048810 x-0.036905此时,拟合曲线的均方误差为|*20.329666例例1

31、1 对下列数据求形如y=aebx的拟合曲线xi12345678yi15.320.527.436.649.165.687.8117.6 解 设z=lny,则 z=A+bx,其中A=lna,由zi=lnyi 得zi2.727853.020423.310543.600053.893864.183584.475064.76729对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 z=(2.72785,3.02042,3.31054,3.60005,3.89386,4.18358,4.47

32、506,4.76729)T,得正则方程组 8A+36b=29.97865 36A+204b=147.13503解得 A*=2.43686,b*=0.29122,于是有a*=eA*=11.43707,拟合曲线为:(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)

33、-8(x-4y+1)+4(3x+2y+3)=0即 23x-2y=-3 -2x+25y=-2解得:x=-0.138354,y=-0.0910681、线性插值、线性插值(n=1)设已知区间设已知区间 xk,xk+1 端点处的函数值端点处的函数值yk=f(xk)，或或L1(x)是两个线性函数是两个线性函数的线性组合的线性组合称为称为线性插值线性插值节点基函数节点基函数 2.1线性插值与抛物线插值线性插值与抛物线插值 yk+1=f(xk+1)，求线性插值多项式，求线性插值多项式L 1(x)，使其满足，使其满足 线性插值线性插值节点节点基函数基函数：满足满足:2、抛物插值法、抛物插值法(n=2 时的二次

34、插值时的二次插值)设插值节点为设插值节点为：xk-1,xk,xk+1,求求二次插值多项式二次插值多项式L2(x)，使得使得 L2(x j)=y j,j=k-1,k,k+1.先求插值基函数先求插值基函数l k-1(x),l k(x),l k+1(x)二次函数二次函数,且在节点且在节点满足：满足：求求 lk-1(x):L2(x j)=y j,j=k-1,k,k+1.L2(x)=yk-1 lk 1(x)+yk lk(x)+yk+1 lk+1(x)再构造插值再构造插值多项式多项式由由练习题练习题第第185页页 习题习题66-1,6-2,6-3,6-4,6-5 练习题练习题第第185页页 习题习题66-8,6-9,6-10,6-12,6-13,练习题练习题第第180页页 习题习题66-15,6-19,6-20,6-22课间休息课间休息