第2章_插值法.

第2章插值法§2.1引言§2.2拉格朗日插值§2.3均差与牛顿插值多项式§2.4埃尔米特插值§2.5分段低次插值§2.6三次样条插值插值法是一种古老的数学方法，早在一千多年前的隋唐时期定制历法时就广泛应用了二次插值。刘焯将等距节点的二次插值应用于天文计算。插值理论却是在17世纪微积分产生后才逐步发展起来的，Newton插值公式理论是当时的重要成果。由于计算机的使用以及航空、造船、精密仪器的加工，插值法在理论和实践上都得到进一步发展，获得了广泛的应用。当精确函数y=f(x)非常复杂或未知时，在一系列节点x0…xn处测得函数值y0=f(x0),…yn=f(xn)，由此构造一个简单易算的近似函数P(x)f(x)，满足条件P(xi)=f(xi)(i=0,…n)。这里的P(x)称为f(x)的插值函数。最常用的插值函数是…?多项式x0x1x2x3x4xP(x)f(x)插值问题上的代数插值多项式为在区间设函数],[)(baxfynnnxaxaxaaxP2210)(且满足niyxPiin,,2,1,0)(满足这种条件的n次插值多项式是否唯一？唯一的！满足线性方程组的系数即多项式nnaaaaxP,,,,)(21000202010yxaxaxaann11212110yxaxaxaannnnnnnnyxaxaxaa2210上述方程组的系数行列式为n+1阶范德蒙行列式nnnnnnxxxxxxxxxV212110200111101)(ninijijxxjixx0由Cramer法则,线性方程组(2)有唯一解唯一解定理1.nnnxaxaxaaxP2210)(niyxPiin,,2,1,0)(),(jixxji若插值节点则满足插值条件的插值多项式存在且唯一.反证：若不唯一，则除了Pn(x)外还有另一n阶多项式Ln(x)满足Ln(xi)=yi。考察则Qn的阶数,)()()(xLxPxQnnnn而Qn有个不同的根n+1x0…xn注：若不将多项式次数限制为n，则插值多项式不唯一。例如也是一个插值多项式，其中可以是任意多项式。niinxxxpxLxP0)()()()()(xp为了求得便于使用的简单的插值多项式P(x),我们先讨论n=1的情形111,(),()kkkkkxxyfxyfxk假定已知区间端点处的函数值要求线性插值多项式L1(x),使它满足：1111(),()kkkkLxyLxyL1(x)的几何意义就是通过这两点的直线；11111111()()(()(kkkkkkkkkkkkkkyyLxyxxxxxxxxLxyyxxxx点斜式）两点式）yx由两点式可以看出，L1(x)是由两个线性函数1111kkkkkkkxxxxyxxxxk和线性组合得到，其系数分别为y及11()()()kkkkxylxylx1即L也是线性插值多项式1()1()0kkkklxlx111()0()1kkkklxlx1()()kklxlx和线性无关称为线性插值基函数11111()(kkkkkkkkxxxxLxyyxxxx两点式）n=2的情况，假定插值节点为112,,,()()(1,,1)kkkjjxxxxLxyjkkk2要求一个二次插值多项式L，使它满足211(),),,),,)kkkyLxyyyk-1kk+1在几何上就是通过三点(x(x(x的抛物线为了求出L2(x)的表达式，可采用基函数方法11kkklll此时基函数，，是二次函数，且在节点上满足条件111111()1()0()1()0()1()0kkkjkkkjkkkjlxlxlxlxlxlx，　(j=k,k+1)，　(j=k-1,k+1)，　(j=k-1,k)1111(),()()0kkkkklxlxlx如求：因为11()()()kkklxAxxxx可以表示为111111()1()()kkkkkklxAxxxx11111()()()()()kkkkkkkxxxxlxxxxx同理111111111()()()()(),()()()()()kkkkkkkkkkkkkkxxxxxxxxlxlxxxxxxxxx线性无关，作为二次插值基函数得到二次插值多项式211112()()()()()(1,,1)kkkkkkjjLxylxylxylxLxyjkkk显然它满足例1:15)225(,13)169(,12)144()(fffxf满足已知.)175(,)(的近似值并求插值多项式的二次作fLagrangexf解:225,169,144210xxx设)(0xl插值基函数为的二次则Lagrangexf)())(())((201021xxxxxxxx2025)225)(169(xx)(1xl))(())((210120xxxxxxxx1400)225)(144(xx)(2xl))(())((120210xxxxxxxx4536)169)(144(xx15,13,12210yyy插值多项式为的二次因此Lagrangexf)()()()()(2211002xlyxlyxlyxL且)175(f)175(2L)175(15)175(13)175(12210lll73158230.13在例1中,如果只给出两个节点169和225,也可以作插值多项式,即1次Lagrange插值多项式,有两个插值基函数,这种插值方法称为Lagrange线性插值,也可以在n+1个节点中取相邻的两个节点作线性插值17513.228756555322952...例2.).175(1fLagrange中的线性插值多项式求例用之间与在由于插值点22516917521xxx解:为插值节点与因此取22516921xx)(1xl212xxxx56225x)(2xl121xxxx56169xLagrange插值基函数为Lagrange线性插值多项式为)()()(22111xlyxlyxL5622513x5616915x)175(f5622517513561691751571285214.13所以17513.228756555322952...考虑通过n+1个节点01()()(0,1)njjxxxnxxyjnnn……的次插值多项式L，要满足条件L?………()xn如何构造Ln1希望找到li(x)，i=0,…,n使得li(xj)=ij；然后令niiinyxlxP0)()(，则显然有Pn(xi)=yi。li(x)每个li有n个根x0…xi…xnnjjijiniiixxCxxxxxxCxl00)())...()...(()(jijiiiixxCxl)(11)(njijjijixxxxxl0)()()(niiinyxlxL0)()(LagrangePolynomial与有关，而与无关节点f插值余项Remainder插值的从上节可知Lagrangexfy)(,满足nixfxLiin,,1,0)()(],[bax但)()(xfxLn不会完全成立因此,插值多项式存在着截断误差,那么我们怎样估计这个截断误差呢？niiinxlyL0)()()(],[xPxfban的插值多项式为上假设在区间)()()(xPxfxRnn令上显然在插值节点为),,1,0(nixi)()()(iniinxPxfxRni,,1,0,0个零点上至少有在因此1],[)(nbaxRn)()()(1xxKxRnn设)())(()(101nnxxxxxxx为待定函数)(xK其中)()()()()(1xxKxPxfxRnnn)()()()(1xxKxPxfnn0)()()()()(1txKtPtftnn若引入辅助函数)(x则有0的区分与注意xt)(ix且)()()(1ininxxKxR0即个零点上至少有在区间若令因此,2],[)(,,nbatxxi,0)(xni,,1,0nixi,,2,1,0,0)(也可微则可微因此若为多项式和由于)(,)(,)()(1txfxxPnn)()()()(1xxKxPxfnn)()()()(1ininixxKxPxf近似函数误差根据Rolle定理,个零点上有至少在区间1),()(nbat再由Rolle定理,个零点上有至少在区间nbat),()(依此类推阶导数为零的使得内至少有一个点在区间1)(,),(ntba0)()1(n)()1(tn)()()()()(1txKtPtftnn)()()()()1(1)1()1(txKtPtfnnnnn由于)()()()()()1(1)1()1()1(nnnnnnxKPf因此)!1()()()1(nxKfn0'()()tt在的两个零点间至少有一个零点)!1()()()1(nfxKn)()()(1xxKxRnn)()!1()(1)1(xnfnn所以)()()(截断误差的余项为插值多项式称xPxRnn定理2.有则插值节点为次插值多项式上的在为阶可微上在区间设],,[],,[}{,],[)()(,1],[)(0baxbaxnbaxfxPnbaxfniin)(xRn)()!1()(1)1(xnfnn,)()(01niinxxx其中.,),(xba且依赖于Lagrange型余项1n时线性插值余项为''''12010111()()()()()(),,22Rxfxfxxxxxx'''2012021()()()()(),,6Rxfxxxxxxxx2n时线性插值余项为注：通常不能确定x,而是估计,x(a,b)将作为误差估计上限。1)1()(nnMxfniinxxnM01||)!1(当f(x)为任一个次数n的多项式时，,可知，即插值多项式对于次数n的多项式是精确的。0)()1(xfn0)(xRn|)(|max)1(1xfMnbxan|)(||)(|011niinnxxxN设|)(|xRn则)()!1()(1)1(xnfnn11)!1(1nnNMn例：已知233sin,214sin,216sin分别利用sinx的1次、2次Lagrange插值计算sin50并估计误差。解：0x1x2x185500n=1分别利用x0,x1以及x1,x2计算4,610xx利用216/4/6/214/6/4/)(1xxxL这里)3,6(,sin)(,sin)()2(xxxfxxf而)4)(6(!2)()(,23sin21)2(1xxfxRxx00762.0)185(01319.01Rsin50=0.7660444…)185(50sin10L0.77614外推/*extrapolation*/的实际误差0.010013,421xx利用sin500.76008,00660.0185~00538.01R内插/*interpolation*/的实际误差0.00596内插通常优于外