第7章_插值法

计算方法课件其系数矩阵是n+1阶范德蒙(Vandermonde)行列式第7章插值法我们仅介绍多项式插值,即如果已知函数f(x)在n+1个互异点的值yi=f(xi)(i=0,1,2,,n),求一个次数不高于n的多项式Pn(x)=a0+a1x+a2x2++anxn,使Pn(xi)=yi(i=0,1,2,,n)1结束为了确定Pn(x)的n+1个系数,由上述条件得线性方程组nnnnnnnnnnyxaxaxaayxaxaxaayxaxaxaa22101121211000202010计算方法课件结束∵xi≠xj,(i≠j),∴此范德蒙行列式的值不为零,方程组有唯一解a0,a1,a2,,an.nnnnnnnnxxxxxxxxxxxxxxxV2222212110200101111),,,(虽然此法可以求出唯一的插值多项式,但是计算量太大,并不实用。下面介绍拉格朗日和牛顿两种插值法。§7.1拉格朗日插值法。7.1.1线性插值已知两点(x0,y0),(x1,y1),求一次多项式P1(x),使P1(x0)=y0,P1(x1)=y1,即求一条过(x0,y0)和(x1,y1)的直线y=P1(x).2计算方法课件结束由直线的两点式方程得(7.1)称为拉格朗日线性插值公式。010010xxxxyyyy)1.7(10100101yxxxxyxxxxy记01011010)()(xxxxxlxxxxxl则(7.1)可写成)2.7()()()(11001yxlyxlxP其中称为拉格朗日线性插值基函数,其性质如下：)1,0()(ixli3计算方法课件结束可写成拉格朗日线性插值基函数均为x的一次多项式,而拉格朗日线性插值多项式P1(x)插值基函数的线性组合,相当于用直线逼近曲线。例1已知,求1)(,0)(0)(,1)(11011000xlxlxlxl)1,0,(10)(jiijijxlijji)1,0()(ixli解∵∴5.0),(5236.063000yxo弧度7071.0),(7854.044511yxo弧度7071.05236.07854.05236.05.07854.05236.07854.0)(1xxxPo40sin7071.045sin,5.030sinoo4计算方法课件结束7071.05236.07854.05236.06981.05.07854.05236.07854.06981.06380.0∴)6981.0(92)40(40sin111PPPoo7.1.2二次插值已知三点(xi,yi)(i=0,1,2),求一个二次多项式P2(x),使P2(xi)=yi(i=0,1,2)由线性插值的启示和拉格朗日线性插值公式的特点,可令其中均为二次多项式,且满足)2,1,0()(ixli)2,1,0,(10)(jiijijxlijjio40(sin的准确值是0.6428)2211002)()()()(yxlyxlyxlxP5计算方法课件结束用待定系数法可确定。)2,1,0()(ixli例如为确定二次多项式,∵∴可令0)()(2010xlxl)(0xl))(()(210xxxxxl又∵1)(00xl∴1))((2010xxxx))((12010xxxx则2102010210))(())(()(jjjxxxxxxxxxxxxxl类似地有21012101201))(())(()(jjjjxxxxxxxxxxxxxl1021202102))(())(()(jjjxxxxxxxxxxxxxl6计算方法课件结束)2,1,0()(ixli仍叫拉格朗日二次插值基函数,于是拉格朗日二次插值多项式2020202)()(iiijjjijiiiyxxxxyxlxP这相当于用抛物线逼近曲线。例2已知,求o40sin8660.060sin,7071.045sin,5.030sinooo解∵5.0),(5236.063000yxo弧度7071.0),(7854.044511yxo弧度8660.0),(0472.136022yxo弧度7计算方法课件∴结束8660.0)7854.00472.1)(5236.00472.1()7854.0)(5236.0(7071.0)0472.17854.0)(5236.07854.0()0472.1)(5236.0(5.0)0472.15236.0)(7854.05236.0()0472.1)(7854.0()(2xxxxxxxP8660.0)7854.0472.1()5236.00472.1()7854.06981.0()5236.06981.0(7071.0)0472.17854.0()5236.07854.0()0472.16981.0()5236.06981.0(5.0)0472.15236.0()7854.05236.0()0472.16981.0()7854.06981.0(∴)6981.0(92)40(40sin222PPPoo8计算方法课件结束的准确值是0.6428)o40(sin6434.0显然比线性插值P1(40O)=0.6380精确。由二次插值的启示和拉格朗日线性插值公式的特点,可令niiinyxlxP0)()(其中均为n次多项式,且满足),,2,1,0()(nixli),,2,1,0,(10)(njiijijxlijji用待定系数法可确定。),,2,1,0()(nixli7.1.3n次插值已知n+1点(xi,yi)(i=0,1,2,,n),求一个n次多项式Pn(x),使Pn(xi)=yi(i=0,1,2,,n)9计算方法课件结束与二次插值类似可得其中均为拉格朗日n次插值基函数,),,2,1,0()(nixliniinijjjijniiinyxxxxyxlxP000)()(于是拉格朗日n次插值多项式§7.2插值多项式的唯一性及误差估计7.2.1插值多项式的唯一性对于已知数据(xi,yi)(i=0,1,2,,n),设Pn(x)是拉格朗日n次插值多项式,则有Pn(xi)=yi(i=0,1,2,,n)。假如还有另一个次数不超过n的多项式n(x),也使),,2,1,0()(0nixxxxxlnijjjiji10计算方法课件结束n(xi)=yi(i=0,1,2,,n)。令Fn(x)=Pn(x)-n(x),则Fn(x)仍为一次数不超过n的多项式。假设Fn(x)不恒等于零,则方程Fn(x)=0最多有n个根。但是∵),,2,1,0(0)(φ)()(niyyxxPxFiiininin即次数不超过n的方程Fn(x)=0有n+1个根,出现矛盾。∴必有Fn(x)0,即Pn(x)n(x)。于是Pn(x)唯一。这说明,过n个点(xi,yi)(i=0,1,2,,n),次数不超过n的多项式Pn(x)是唯一的。7.2.2插值公式的余项(误差)设已知函数y=f(x)在n+1个点的值yi=f(xi)(i=0,1,2,,n)Pn(x)是满足Pn(xi)=f(xi)的n次插值多项式,则称Rn(x)=f(x)-Pn(x)为插值多项式在点x处的截断误差。11计算方法课件结束可以证明:证明定理7.1设f(x)在插值区间[a,b]上具有n+1阶连续导数,则对任意x[a,b],至少存在一点(a,b),使得)5.7()()!1()()()1(xnfxRnn其中(x)=(x-x0)(x-x1)(x-xn)对于线性插值,其误差为))((!2)()(101xxxxfxR对于二次插值,其误差为))()((!3)()(2102xxxxxxfxR对于n次插值,其误差为(7.5)式。12计算方法课件设函数f(x)在[a,b]上有定义,xi,xj[a,b],且xi≠xj,则称§7.3牛顿插值拉格朗日插值法最大的弱点是,当插值节点增加后,所有的插值基函数都要重新构造,增加节点前的所有计算结果将毫无作用,造成计算的浪费.牛顿插值却克服了此弱点.13结束7.3.1差商1差商概念jijijixxxfxfxxf)()(],[为f(x)在xi,xj的一阶差商。设f(xi,xj)与f(xj,xk)为f(x)在点xi,xj与点xj,xk的一阶差商,则称计算方法课件结束为f(x)在xi,xj,xk的二阶差商。)(],[],[],,[kikikjjikjixxxxxxfxxfxxxf设f(x0,x1,,xk-1)与f(x1,x2,,xk)为f(x)在点x0,x1,,xk-1与点x1,x2,,xk的k-1阶差商,则称为f(x)在点x0,x1,,xk的k阶差商。2差商的基本性质(1)n次多项式的k阶差商,当kn时,为一个n-k次多项式,而当kn时恒为零。)(],,,[],,,[],,,[002111010kkkkkxxxxxxxfxxxfxxxf14计算方法课件结束例如一阶差商(2)差商可以表示为节点处函数值的线性组合：kiiikxfxxxxf010)()(1],,,[其中´(xi)=(xi-x0)(xi-xi-1)(xi-xi+1)(xi-xk)ijjjiijijijixxxfxxxfxxxfxfxxf)()()()(],[15计算方法课件结束kijkkkjjijjjiixxxxxfxxxfxxxfxxxf)()()()())(()(11)())(()(jkikkkjijkijjikiixxxxxfxxxxxxxfxxxxxf))(()())(()())(()(jkikkkjijjjikiixxxxxfxxxxxfxxxxxf二阶差商kikjjikjixxxxfxxfxxxf],[],[],,[16计算方法课件结束类似地],,[],,[],,[],,[],,[],,[ijkjikikjkijjkikjixxxfxxxfxxxfxxxfxxxfxxxf(4)若f(x)在含x0,x1,,xk的区间D上k阶可导。则至少存在一点D,使得!)(],,,[)(10kfxxxfkk3差商表点x0,x1,x2,x3,,的所有差商可以列成如下的一张差商表:(3)差商关于节点对称,与节点的排列次序无关。例如一阶差商],[)()()()(],[ijijijjijijixxfxxxfxfxxxfxfxxf17计算方法课件xif(xi)一阶差商二阶差商三阶差商…x0x1x2x3┇结束],,,[],,[],,[],[],[],[)()()()(32103212103221103210xxxxfxxxfxxxfxxfxxfxxfxfxfxfxf7.3.2牛顿插值公式设x0,x1,,xn为插值节点,x为插值区间内任意一点,以x,x0,x1,,xn为节点,依次作一阶、二阶,,n+1阶差商,可得18计算方法课件结束],[)()()()()(],[000000xxfxxxfxfxxxfxfxxf],,[)(],[],[],[],[],,[101100110010xxxfxxxxfxxfxxxxfxxfxxxf],,,[)(],,[],,[],,[],