拉格朗日插值法

1第二章插值法2iiijjijiilxlbx11nnnnnnaaaaaaaaaA212222111211bAx第二章插值法和最小二乘法2.1引言§2.2拉格朗日插值多项式§2.3差商与牛顿插值公式§2.4差分与等距节点插值公式§2.5分段低次插值§2.6三次样条插值§3本章要点用简单的函数(如多项式函数)作为一个复杂函数的近似,最简单实用的方法就是插值本章主要介绍有关插值法的一些基本概念,及多项式插值的基础理论和几个常用的插值方法:Lagrange插值、分段线性插值、Newton插值、Hermite插值和三次样条插值4自然地，希望g(x)通过所有的离散点x0x1x2x3x4xp(x)f(x)实际中，f(x)多样，复杂，通常只能观测到一些离散数据；或者f(x)过于复杂而难以运算。这时我们要用近似函数g(x)来逼近f(x)。52.1引言§且不利于在计算机上其函数形式可能很复杂对函数,),(xf个不同的点上的一组在区间可以获得量假如可以通过实验或测运算1],[)(,,nbaxfbxxxxan210nixfyii,,2,1,0),(上的函数值一、插值问题6niyxPii,,2,1,0)()()(xfxP近似代替并且用--(1)这就是插值问题,(1)式为插值条件,的插值函数为函数称函数)()(xfxP则称之为插值多项式为多项式函数如果,)(xP称为插值节点点,,,2,1,0,nixi称为插值区间区间],[ba满足比如多项式函数),(xP7个等分点上若给定如函数5],0[,sinxy其插值函数的图象如图问题•是否存在唯一•如何构造•误差估计800.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的值可能就会偏离但在节点外必然存在着误差近似代替因此)()(xfxP9二、代数插值多项式的存在唯一性整体误差的大小反映了插值函数的好坏为了使插值函数更方便在计算机上运算,一般插值函数都使用代数多项式和有理函数本章讨论的就是代数插值多项式上的代数插值多项式为在区间设函数],[)(baxfynnnxaxaxaaxP2210)(且满足niyxPiin,,2,1,0)(--------(2)--------(3)10满足线性方程组的系数即多项式nnaaaaxP,,,,)(21000202010yxaxaxaann11212110yxaxaxaannnnnnnnyxaxaxaa2210--------(4)上述方程组的系数行列式为n+1阶Vandermond行列式nnnnnnxxxxxxxxxV212110200111101)(ninijijxxjixx011定理1.由Cramer法则,线性方程组(4)有唯一解nnnxaxaxaaxP2210)(niyxPiin,,2,1,0)(--------(2)--------(3)),(jixxji若插值节点则满足插值条件的插值多项式存在且唯一.虽然线性方程组(4)推出的插值多项式存在且唯一但通过解线性方程组(4)求插值多项式却不是好方法12维的间是的多项式构成的线性空所有次数不超过n1n根据线性空间的理论个多项式组成维线性空间的基底也由这个11nn并且形式不是唯一的表示次多项式可由基底线性而任意一个n且在不同的基底下有不同的形式2.2拉格朗日插值多项式§13所有次数不超过２的多项式的两个不同基底：•1，ｘ，ｘ2•200，ｘ－３，ｘ2－ｘ即所有次数不超过２的多项式可表示成：2210xaxaa或：)()3(2002210xxaxaa14线性表示可由次多项式且任意)(,),(),()(10xxxxPnnn线性无关显然)(,),(),(10xxxn)()()()(1100xaxaxaxPnnn的插值函数为某个函数如果)()(xfxPn为插值基函数则称)(,),(),(10xxxn--------(5)niyxPiin,,2,1,0)(-------(6)且满足(1)式为插值节点其中nixi,,2,1,0,nixfyii,,2,1,0)(维线性空间的一个基底为上述设1)(,),(),(10nxxxn15上的一组节点为区间如果],[210babxxxxannjxlnj,,2,1,0),(次多项式我们作一组)())(())(()())(())(()(11101110njjjjjjjnjjjxxxxxxxxxxxxxxxxxxxxxlnjiiijixxxx0)()(nj,,2,1,0-------(7))())((10nxxxxxx)(1xn令)(1jnx则)())(())((1110njjjjjjjxxxxxxxxxxn+1次多项式16)())(())(()())(())(()(11101110njjjjjjjnjjjxxxxxxxxxxxxxxxxxxxxxlnj,,2,1,0-------(7')且)(ijxljiji01nji,,2,1,0,-------(8)线性无关显然)(,),(),(),(210xlxlxlxln(请同学们思考)))(()(11jjnnxxxx从而17的插值基函数作如果用)()(,),(),(),(210xfyxlxlxlxln则的插值多项式为而,)()(xfxPn)()()()(1100xlaxlaxlaxPnnn为待定参数、、、其中naaa10)(inxPniyxfii,,2,1,0)(令即njijjxla0)(niyi,,2,1,0由(8)式,可得niyaii,,2,1,0-------(9)-------(10)18为记为项式为插值基函数的插值多以上在节点于是))((),,1,0()(,),,1,0()(,xLnixlnixxfynji)()()()(1100xlyxlyxlyxLnnn)(xljnjiiijixxxx0)()(其中-------(7,7')-------(11)插值多项式的为式称LagrangexfyxLn)()()11(插值基函数次为称Lagrangennixlj),,1,0()())(()(11jjnnxxxx19例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yyy20插值多项式为的二次因此Lagrangexf)()()()()(2211002xlyxlyxlyxL且)175(f)175(2L)175(15)175(13)175(12210lll73158230.13在例1中,如果只给出两个节点169和225,也可以作插值多项式,即1次Lagrange插值多项式,有两个插值基函数,这种插值方法称为Lagrange线性插值,也可以在n+1个节点中取相邻的两个节点作线性插值2111,,,kkkkyyxx函数值节点Lagrange线性插值基函数为)(xlk11kkkxxxx)(1xlkkkkxxxx1Lagrange线性插值多项式为)()()(111xlyxlyxLkkkk11kkkkxxxxykkkkxxxxy11参见图22例).175(1fLagrange中的线性插值多项式求例用之间与在由于插值点22516917521xxx解:为插值节点与因此取22516921xx)(1xl212xxxx56225x)(2xl121xxxx56169xLagrange插值基函数为Lagrange线性插值多项式为)()()(22111xlyxlyxL5622513x5616915x23)175(f5622517513561691751571285214.13所以Lagrange插值多项式的缺点：插值基函数计算复杂高次插值的精度不一定高24插值多项式中的误差§一、插值余项插值的从上节可知Lagrangexfy)(,njjjnxlyxL0)()(满足nixfxLiin,,1,0)()(],[bax但)()(xfxLn不会完全成立因此,插值多项式存在着截断误差,那么我们怎样估计这个截断误差呢？25)()(],[xPxfban的插值多项式为上假设在区间)()()(xPxfxRnn令上显然在插值节点为),,1,0(nixi)()()(iniinxPxfxRni,,1,0,0个零点上至少有在因此1],[)(nbaxRn)()()(1xxKxRnn设)())(()(101nnxxxxxxx为待定函数)(xK其中)()()()()(1xxKxPxfxRnnn26)()()()(1xxKxPxfnn0)()()()()(1txKtPtftnn若引入辅助函数)(x则有0的区分与注意xt)(ix且)()()(1ininxxKxR0即个零点上至少有在区间若令因此,2],[)(,,nbatxxi,0)(xni,,1,0nixi,,2,1,0,0)(也可微则可微因此若为多项式和由于)(,)(,)()(1txfxxPnn)()()()()(11xtRtxRtnn也可令)()()()(1xxKxPxfnn)()()()(1ininixxKxPxf27根据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28)!1()()()1(nfxKn)()()(1xxKxRnn)()!1()(1)1(xnfnn所以)()()(截断误差的余项为插值多项式称xPxRnn定理1.有则插值节点为次插值多项式上的在为阶可微上在区间设],,[],,[}{,],[)()(,1],[)(0baxbax