第2章插值与拟合科学与工程计算(数值分析)

科学和工程计算第2章插值法插值法插值法是一种古老的数学方法，早在一千多年前的隋唐时期定制历法时就广泛应用了二次插值。刘焯将等距节点的二次插值应用于天文计算。插值理论却是在17世纪微积分产生后才逐步发展起来的，Newton插值公式理论是当时的重要成果。由于计算机的使用以及航空、造船、精密仪器的加工，插值法在理论和实践上都得到进一步发展，获得了广泛的应用。1.引言2.拉格朗日插值3.均差与牛顿插值公式4.差分与等距节点插值5.埃尔米特插值6.分段低次插值7.三次样条插值插值法且不利于在计算机上其函数形式可能很复杂对函数,),(xf个不同的点上的一组在区间可以获得量假如可以通过实验或测运算1],[)(,,nbaxfbxxxxan210nixfyii,,2,1,0),(上的函数值能否存在一个性能优良、便于计算的函数)(xP比如多项式函数一、插值问题niyxPii,,2,1,0)()()(xfxP近似代替并且用------(1)这就是插值问题,(1)式为插值条件,个等分点上若给定如函数5],0[,sinxy其插值函数的图象如图为插值区间称区间],[ba为插值节点称点nixi,,2,1,0,则称之为插值多项式为多项式函数如果,)(xP的插值函数为函数称函数)()(xfxP00.511.522.533.500.10.20.30.40.50.60.70.80.91sinx的的的xy00.511.522.533.500.10.20.30.40.50.60.70.80.91sinx的的的xy00.511.522.533.500.10.20.30.40.50.60.70.80.91sinx的的的xy00.511.522.533.500.10.20.30.40.50.60.70.80.91sinx的的的xy)()(xPxf和插值函数对于被插函数处的函数值必然相等在节点ix)()(xfxP的值可能就会偏离但在节点外必然存在着误差近似代替因此)()(xfxP整体误差的大小反映了插值函数的好坏为了使插值函数更方便在计算机上运算,一般插值函数都使用代数多项式和有理函数。x0x1x2x3x4xP(x)f(x)Lagrange插值多项式为了求得便于使用的简单的插值多项式P(x),我们先讨论n=1的情形111,(),()kkkkkxxyfxyfxk假定已知区间端点处的函数值要求线性插值多项式L1(x),使它满足：1111(),()kkkkLxyLxyL1(x)的几何意义就是通过这两点的直线；11111111()()(()(kkkkkkkkkkkkkkyyLxyxxxxxxxxLxyyxxxx点斜式）两点式）由两点式可以看出，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显然它满足考虑通过n+1个节点01()()(0,1)njjxxxnxxyjnnn……的次插值多项式L，要满足条件L?………()xn如何构造L上的一组节点为区间如果],[210babxxxxannjxlnj,,2,1,0),(次多项式我们作一组njiiijixxxx0)()(nj,,2,1,0n+1次多项式)())(())(()())(())(()(11101110njjjjjjjnjjjxxxxxxxxxxxxxxxxxxxxxl)(1jnx则)())(())((1110njjjjjjjxxxxxxxxxx)())((10nxxxxxx)(1xn令)())(())(()())(())(()(11101110njjjjjjjnjjjxxxxxxxxxxxxxxxxxxxxxlnj,,2,1,0且)(ijxljiji01nji,,2,1,0,线性无关显然)(,),(),(),(210xlxlxlxln(请同学们思考)))(()(11jjnnxxxx从而n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例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所以Lagrange插值多项式的缺点：插值基函数计算复杂高次插值的精度不一定高高次插值通常优于低次插值17513.228756555322952...但绝对不是次数越高就越好，嘿嘿……三、插值余项Remainder插值的从上节可知Lagrangexfy)(,njjjnxlyxL0)()(满足nixfxLiin,,1,0)()(],[bax但)()(xfxLn不会完全成立因此,插值多项式存在着截断误差,那么我们怎样估计这个截断误差呢？)()(],[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时线性插值余项为余项表达式只有在f(x)的高阶导数存在时才能应用。(,)ab在内的具体位置通常不可能给出，|)(|max)1(1xfMnbxan|)(||)(|011niinnxxxN设|)(|xRn则)()!1()(1)1(xnfnn11)!1(1nnNMn例3:225,169,144,)(,.1三个节点为