计算方法课件-第4章-多项式插值方法

1第四章多项式插值方法4.1引言4.2Lagrange插值多项式4.3Newton插值多项式4.4分段低次插值2则称P(x)为f(x)的插值函数。这时，我们称[a,b]为插值区间，称为插值节（结）点，称（4-1）为插值条件，f(x)为被插函数。求插值函数P(x)的方法称为插值法。4.1引言定义4.1设y=f(x)在区间[a,b]上连续，在[a,b]内n+1个互不相同的点上取值。如果存在一性态较好的简单函数P(x)，使得010,,()nnxxxaxxb01,,nyyy()(0,1,)(41)iiPxyin01,,nxxx3从几何上看，插值法就是确定一个简单曲线为y=P(x)，使其通过给定的n+1个点，并用它近似已知曲线y=f(x).(,),0,1,,iixyin图2-14特别地，当P(x)为次数不超过n次的代数多项式时，相应的插值法称为多项式插值；当P(x)为三角多项式时，相应的插值法称为三角插值；当P(x)为分段解析函数时，相应的插值法称为分段插值。其中三角插值主要用于处理周期函数。本章仅介绍最基本的多项式插值。定理4.1在n+1个互异点上满足插值条件(4-1)的次数不超过n次的插值多项式Pn(x)存在且惟一。01,,,nxxx5记实系数多项式0()(42)nknkkPxax即有0000111111(42)1nnnnnnnayxxayxxayxx10110(,,)()0ninnijijAVxxxxx因所以，解存在且惟一，这说明由式(4-2)表示的Pn(x)存在且惟一，证毕。证明：64.2Lagrange插值多项式4.2.1线性插值与二次插值设给定函数两点，经过这两点的多项式插值就是直线()yfx0011(,),(,)xyxy011010110()xxxxLxyyxxxx称给定为线性插值多项式。称为关于点的线性插值基函数，其在节点处满足：1()Lx01,xx01010110(),()xxxxlxlxxxxx1,()0,ijijlxij74.2.1线性插值与二次插值假定插值节点为，，，要求二次插值多项式2x1x0x),(2xL几何上是通过三点的抛物线.)(2xL),(),,(),,(221100yxyxyx).2,1,0()(2jyxLjj可以用基函数的方法求的表达式，)(2xL),(0xl),(1xl)(2xl是二次函数，);2,1(,0)(,1)(000jxlxlj);2,0(,0)(,1)(111jxlxlj).1,0(,0)(,1)(222jxlxlj84.2.2拉格朗日插值多项式1(),{0,1,}(44)0ijijijlxijnij0()naxxb解的零点为)(,,,,110xlxxxxiniinjijjixxxl0)()(中含有因式而此因式已为n次多项式，故应有为待定系数injijjiiAxxAxl0)()(),,1,0()(nixli求的n+1个次数次的插值多项式满足n901()()niiiijjijlxAxx再由01()inijjijAxx得001()()(,,,)()njijiijjxxlxinxx00045()()()nnnjniiiiijiijjxxLxylxyxx称为n次拉格朗日（Lagrange）插值基函数或称为拉格朗日基本插值多项式。(据之，我们可构造多项式10它称为n次拉格朗日插值多项式。引进n+1次与n次多项式函数为10()()(4.2.10)nnjjxxx1()()/()inixxxx0()()()niniiiixLxyxn次拉格朗日插值多项式可表示为11误差估计定理注（1）余项公式主要用于理论分析。实际使用时，代之以误差估计式11()()(1)!nnnMRxxn4.2.2插值余项与误差估计定理4.2设f(x)的n+1阶导数在[a,b]存在，则对任何，插值余项满足(1)1()()()()(),[,](1)!nnnnfRxfxLxxxabn()(,).xab其中(1)()nfx[a,b]x12（2）插值节点的选取应尽量靠近插值点，以使尽可能小，以减小误差。)(1xn(1)()=(),()0,knfxxknfx若那么0()()0,nkkniiiRxxxlx0(),0,1,,.nkkiiixlxxkn0()1.niilx特别地，当k=1时13例4.1：已知函数x-101y1.250.751.252L()x求3001122()()()()Pxlxylxylxy解：1200102()()1()(1)()()2xxxxlxxxxxxx而0211012()()()(1)(1)()()xxxxlxxxxxxx0122021()()1()(1)()()2xxxxlxxxxxxx142001122012()()()()()()()1.25()0.75()1.25()Lxfxlxfxlxfxlxlxlxlx255(1)0.75(1)(1)(1)883142xxxxxxx154.3Newton插值多项式问题：利用插值基函数得到的拉格朗日插值多项式有何优缺点？优点：结构紧凑，便于理论分析，易于编程求解。缺点：当插值节点增减时全部插值基函数均要随之变化，整个公式也将发生变化.问题：如何改进？164.3Newton插值多项式4.3.1均差的定义和性质定义：称为函数关于点的一阶均差.100110()()[,]fxfxfxxxx)(xf01,xx120101220[,][,][,,]fxxfxxfxxxxx称为关于点的二阶均差.)(xf012,,xxx一般地，称11011010[,,,][,,][,,]nnnnnfxxxfxxxfxxxxx为的阶均差n)(xf（均差也称为差商）.174.3Newton插值多项式4.3.1均差的定义和性质利用如下均差表来计算均差：0011012212012332312301234434234123401234()1st2nd3rd4th()()[,]()[,][,,]()[,][,,][,,,]()[,][,,][,,,][,,,,]kkxfxxfxxfxfxxxfxfxxfxxxxfxfxxfxxxfxxxxxfxfxxfxxxfxxxxfxxxxx表21均差均差均差均差（）（）（）（）18解根据给定函数表造出均差表给出的如下函数表，由此计算关于点0,2,4,8的三阶均差.()fx()fx例9-39-3108420kx)(kxf-2.875-18-3940.98437551298-6.5-32100三阶均差二阶均差一阶均差kx)(kxf[0,2,4,8]f19均差的性质：时恒为零。次多项式，当时为当阶均差函数次多项式，则其为若）（nkknnkxxxPknxPknn],,,[)(210的任一排列），，为排列顺序无关，即有由此知，均差与节点的kiiixxxfxxxfxxxfxxxfkiiikkikjijjiikk10,,(],,,[],,,[)124()()(],,,[)1(1010001010这性质又称为均差关于自变量的对称性。20根据均差定义，把看成上一点，x[,]ab000[,()()(),]fxxfxfxxx010001011012212[,,][,,[,](),[,[,,,](),]][,]fxxxxfxxfxxxfxxfxxxxxfxxxxx010101[,,,][,,,][,,,,]().nnnnfxxxfxxxfxxxxxx可得4.3Newton插值多项式4.3.2Newton均差插值多项式21只要把后一式代入前一式，就得到0010()()[,]()fxfxfxxxx01201[,,]()()fxxxxxxx()(),nnNxRx0010()()[,]()nNxfxfxxxx01201[,,]()()fxxxxxxx其中0101[,,,]()()nnfxxxxxxx01[,,,]()nnfxxxx0101[,,,]()(),nnfxxxxxxx4.3.2Newton均差插值多项式2201()()()[,,,](),nnnnRxfxNxfxxxx（*）是同Lagrange余项定义的.)(1xn显然，由确定的多项式满足插值条件，()nNx且次数不超过n的多项式，其所给出形式的系数为001[,,],(,,,).kkafxxkn称为牛顿（Newton）均差插值多项式.()nNx系数就是均差表4-1中主对角线上的各阶均差，它比拉格朗日插值计算量省，且便于程序设计.ka4.3.2Newton均差插值多项式23但（3.7）更有一般性，它在是由离散点给出的情形或导数不存在时也是适用的.ff（*）为插值余项，由插值多项式惟一性知，它与拉格朗日插值多项式的余项应该是等价的.事实上，利用均差与导数关系式就可以证明这一点.牛顿插值多项式的优点还在于它的递进性，当增加插值节点时，只要在原来插值多项式的基础上增加一项即可.),(],,,[)()()(10xxxxfxNxfxRnnnn（3.7）4.3.2Newton均差插值多项式24解由于是3次函数,所以取靠近0.45的4个点产生均差表.例4.6根据给定数据(见p51的表)，用3次牛顿插值多项式计算f(0.25)的近似值,并估计近似误差.4.3.2Newton均差插值多项式一阶二阶三阶0.20.5877850.40.9510571.8163600.60.9510570.00000-4.5409000.80.587785-1.816360-4.5409000.00000()iixfx253(0.4())[0.5(0.540900)(0.6)(0.000001.8871)]785(0.2){}6360Nxxxx于是4(0.45)(0.45)0.985114fN按牛顿插值公式，将数据代入得26为了估计误差，增加一个靠近0.45的插值点0.0，在均差表后加一行（均差与节点排列无关）.一阶二阶三阶四阶0.20.5877850.40.9510571.8163600.60.9510570.00000-4.5409000.80.587785-1.816360-4.5409000.000000.00.0000000.734733-4.251817-0.7227083.613540()iixfx27因此，截断误差3044(0.45)[,,](0.4596)0.0024.Rfxx事实上，给定的函数是因此可计算实际误差3sin0.45(0.45)0.002574N由此可见，误差估计是相当有效的。sinx284.4分段低次插值4.4.1Runge现象问题：根据区间上给出的节点做出的插值多项式),(xLn],[ba在次数增加时逼近的精度是否也增加?n)(xf事实上，对于有些函数，插值多项式次数很高时会在某些区间内产生较大的误差。例如著名的Runge现象。29考虑函数，它在上的各阶导数均存在.]5,5[)1/(1)(2xxfnknkxk,,1,0,105所构造的10次（n=10）拉格朗日插值多项式与原函数的图像：取上的个等距节点]5,5[1n4.4.1Runge现象304.4分段低次插值4.4.2分段低次插值问题：如何克服龙格现象呢？解决办法：不用高次插值，改用分段低次插值.由于升高插值多项式的阶数有时并不能达到提高精度的效果,所以实际中往往采用分段插值的思想.分段