数值分析第六章插值与逼近

第6章插值与逼近§1多项式插值问题设函数y=(x)在区间[a,b]上连续，给定n+1个点ax0x1…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是代数多项式,即所谓的多项式插值.ox0……yxy=(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)nnnnnnnnnnyxaxaxaayxaxaxaayxaxaxaa22101121211000202010其系数行列式为定理6.1给定n+1个互异节点x0,x1,…,xn上的函数值y0,y1,…,yn,则满足插值条件(6.2)的n次插值多项式pn(x)是存在且唯一的.nnnnnxxxxxxD1111100nnnnnxxxxxx10101110)(0njiijxx§2Lagrange插值多项式对n+1个节点x0,x1,…,xn,构造n+1个n次多项式l0(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)4.6()(0nkkkyxl称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,从而有)())(())(()())(())(()(11101110nkkkkkkknkkkxxxxxxxxxxxxxxxxxxxxxlnkjjjkjxxxx0若记n+1(x)=(x-x0)(x-x1)…(x-xn),则lk(x)可写成)()()()(11knknkxxxxxl若取(x)=xk(k=0,1,…,n),由插值多项式的唯一性有nkxxxlnikkii,,1,0,)(0特别当k=0时,有niixl01)(例1求(x)关于节点x0,x1的线性Lagrange插值多项式解对节点x0,x1,Lagrange插值基函数为,)(1010xxxxxl0101)(xxxxxl于是有)()()(101001011xfxxxxxfxxxxxL易见,L1(x)就是过点(x0,(x0))和点(x1,(x1))的直线.例2求(x)关于节点x0,x1,x2的二次Lagrange插值多项式.解对节点x0,x1,x2的Lagrange插值基函数为,))(())(()(2010210xxxxxxxxxl,))(())(()(2101201xxxxxxxxxl))(())(()(1202102xxxxxxxxxl于是有)())(())(()())(())(()())(())(()(2120210121012002010212xfxxxxxxxxxfxxxxxxxxxfxxxxxxxxxLL2(x)是过点(x0,(x0)),(x1,(x1))和(x2,(x2))的抛物线.为了研究插值多项式的近似程度,记Rn(x)=(x)-Ln(x)称为n次Lagrange插值余项.Lagrange插值多项式简单而优雅,只要取定节点就可写出基函数,进而得到插值多项式.易于计算机上实现.设(n)(x)在[a,b]连续,(n+1)(x)在(a,b)内存在,在节点ax0x1…xnb上,满足插值条件(6.2)的插值多项式Ln(x),对任一x[a,b],插值余项为定理6.2)5.6()()!1()()()()(1)1(xnfxLxfxRnxnnn其中x(a,b)且与x有关.证由于Rn(xi)=(xi)-Ln(xi)=0(i=0,1,…,n),所以Rn(x)=C(x)n+1(x)对于任一x[a,b],xxi(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+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)!因而有,)!1()()()1(nfxCxn所以)()!1()()(1)1(xnfxRnxnn若|(n+1)(x)|在[a,b]有上界Mn+1,则Lagrange插值余项也可写成用二次插值计算ln11.25的近似值,并估计误差.)()!1()(11xnMxRnnn例3给定函数表x10111213lnx2.3025852.3978952.4849072.564949解取节点x0=10,x1=11,x2=12,作二次插值有ln11.25L2(11.25)302585.2)1210)(1110()1225.11)(1125.11(397895.2)1211)(1011()1225.11)(1025.11(484907.2)1112)(1012()1125.11)(1025.11(420426.2在区间[10,12]上lnx的三阶导数的上限M3=0.002,可得误差估计式实际上,ln11.25=2.420368,|R2(11.25)|=0.000058.00007.0|)1225.11)(1125.11)(1025.11(|!3)25.11(32MR在被插值函数未知或无法估计其高阶导数界时,上述插值余项不能用来估计误差,下面介绍事后误差估计法.记Ln(x)是(x)以x0,x1,…,xn为节点的n次插值多项式而Ln(1)(x)为(x)以x1,x2,…,xn,xn+1为节点的n次插值多项式,由于)())(()!1()()()(10)1(nxnnxxxxxxnfxLxf))(())(()!1()()()(121)1()1(nnxnnxxxxxxxxnfxLxf如在例3中,再以节点x1=11,x2=12,x3=13作二次插值多项式L2(1)(x),则L2(1)(11.25)=2.420301,由(6.7)式得,则有从而得)()()1()1(xnxnff若10)1()()()()(nnnxxxxxLxfxLxf)6.6()()()()1(010101xLxxxxxLxxxxxfnnnnn也有)7.6())()(()()()1(100xLxLxxxxxLxfnnnn000052.0)420301.2420426.2(13101025.11)(2xR由(6.6)式也可得到ln11.25的新的近似值420374.2420301.210131025.11420426.213101325.1125.11ln称(xj)-(xi)与xj-xi(ij)的比值为(x)关于点xi,xj的一阶差商,并记为[xi,xj],即§3Newton插值多项式实际上,(6.6)式右侧恰是(x)以x0,x1,…,xn,xn+1为节点的n+1次插值多项式.§3.1差商及其性质而称ijijjixxxfxfxxf)()(],[ikjikjkjixxxxfxxfxxxf],[],[],,[为(x)关于点xi,xj,xk的二阶差商.一般地,称为(x)关于点x0,x1,…,xk的k阶差商.以上定义中,点x0,x1,…xk为互不相同的点.01102110],,,[],,,[],,,[xxxxxfxxxfxxxfkkkk差商具有以下性质:(1)k阶差商[x0,x1,…,xk]可以表示成(x0),(x1),…,(xk)的线性组合kjjjkkxfxxxxf0110)()(1],,,[(2)差商对节点具有对称性,即],,,[],,,[1010kiiixxxfxxxfk其中,i0,i1,…,ik是0,1,…,k的任一排列.(3)n次多项式(x)的k阶差商,当kn时是一个n-k次多项式;当kn时恒等于0.其中在k+1个节点之间.给出节点x0,x1,…,xn和函数值(x0),(x1),…,(xn),可按如下的差商表顺序逐次计算各阶差商值.(4)若(x)具有k阶连续导数,则,!)(],,,[)(10kfxxxfkkxiƒ(xi)一阶差商二阶差商三阶差商…n阶差商x0x1x2x3xnƒ(x0)ƒ(x1)ƒ(x2)ƒ(x3)ƒ(xn)ƒ[x0,x1]ƒ[x1,x2]ƒ[x2,x3]ƒ[xn-1,xn]ƒ[x0,x1,x2]ƒ[x1,x2,x3]ƒ[xn-2,xn-1,xn]ƒ[x0,x1,x2,x3]ƒ[xn-3,xn-2,xn-1,xn]………………ƒ[x0,x1,…,xn]例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.2Newton插值多项式及其余项[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)(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)由插值多项式的唯一性有)!1()(],,,,[)1(10nfxxxxfxnnNk+1(x)=Nk(x)+k+1(x)[x0,x1,…,xk+1]k=1,2,…,n-1由(6.8)式易见解由例4的差商表知[x0,x1]=-2,