拉格朗日插值法与牛顿插值法的比较

第1页共7页拉格朗日插值法与牛顿插值法的比较[摘要]在生产和科研中出现的函数是多样的。对于一些函数很难找出其解析表达式。即使在某些情况下，可以写出函数的解析表达式，但由于解析表达式的结构相当复杂，使用起来很不方便。插值法即是解决此类问题的一种古老的、然而却是目前常用的方法，它不仅直接广泛地应用于生产实际和科学研究中，而且也是进一步学习数值计算方法的基础。拉格朗日插值法和牛顿插值法则是二种常用的简便的插值法。本文即是讨论拉格朗日插值法和牛顿插值法的理论及二者的比较。[关键词]拉格朗日插值牛顿插值插值多项式比较一、背景在工程和科学研究中出现的函数是多种多样的。常常会遇到这样的情况：在某个实际问题中，虽然可以断定所考虑的函数)(xf在区间],[ba上存在且连续，但却难以找到它的解析表达式，只能通过实验和观测得到在有限个点上的函数值（即一张函数表）。显然，要利用这张函数表来分析函数)(xf的性态，甚至直接求出其他一些点上的函数值可能是非常困难的。面对这些情况，总希望根据所得函数表（或结构复杂的解析表达式），构造某个简单函数)(xP作为)(xf的近似。这样就有了插值法，插值法是解决此类问题目前常用的方法。如设函数)(xfy在区间],[ba上连续，且在1n个不同的点bxxxan,,,10上分别取值nyyy,,,10。插值的目的就是要在一个性质优良、便于计算的函数类中，求一简单函数)(xP，使),,1,0()(niyxPii而在其他点ixx上，作为)(xf的近似。通常，称区间],[ba为插值区间，称点nxxx,,,10为插值节点，称式iiyxP)(为插值条件，称函数类为插值函数类，称)(xP为函数)(xf在节点nxxx,,,10处的插值函数。求插值函数)(xP的方法称为插值法。插值函数类的取法不同，所求得的插值函数)(xP逼近)(xf的效果就不同。它的选择取决于使用上的需要，常用的有代数多项式、三角多项式和有理函数等。当选用代数多项式作为插值函数时，相应的插值问题就称为多项式插值。本文讨论的拉格朗日插值法与牛顿插值法就是这类插值问题。在多项式插值中，最常见、最基本的问题是：求一次数不超过n的代数多项式nnxaxaaxP10)(使),,1,0()(niyxPiin，其中，naaa,,,10为实数。第2页共7页拉格朗日插值法即是寻求函数)(xLn（拉格朗日插值多项式）近似的代替函数)(xf。相似的，牛顿插值法则是通过)(xNn（牛顿插值多项式）近似的求得函数的值。二、理论基础（一）拉格朗日插值法在求满足插值条件n次插值多项式)(xPn之前，先考虑一个简单的插值问题：对节点),,1,0(nixi中任一点)0(nkxk，作一n次多项式)(xlk，使它在该点上取值为1，而在其余点),,1,1,1,0(nkkixi上取值为零，即kikixlik01)(上式表明n个点nkkxxxxx,,,,,,1110都是n次多项式)(xlk的零点，故可设]1[1110)())(())(()(nkkkkxxxxxxxxxxAxl其中，kA为待定系数。由条件1)(kkxl立即可得)())(()(1110nkkkkkkkxxxxxxxxA故)())(()()())(()()(110110nkkkkkknkkkxxxxxxxxxxxxxxxxxl由上式可以写出1n个n次插值多项式)(,),(),(10xlxlxln。我们称它们为在1n个节点nxxx,,,10上的n次基本插值多项式或n次插值基函数。利用插值基函数立即可以写出满足插值条件的n次插值多项式)()()(1100xlyxlyxlynn根据条件kikixlik01)(，容易验证上面多项式在节点ix处的值为),,1,0(niyi，因此，它就是待求的n次插值多项式)(xPn。形如)()()(1100xlyxlyxlynn的插值多项式就是拉格朗日插值多项式，记为)(xLn，即第3页共7页)())(()()())(()()()()()(1101102211nkkkkkknkknnnxxxxxxxxxxxxxxxxxlyxlyxlyxL作为常用的特例，令1n，由上式即得两点插值公式)()(0010101xxxxyyyxL，这是一个线性函数，故又名线性插值。若令1n，则又可得到常用的三点插值公式))(())(())(())(())(())(()(1202102210120120102102xxxxxxxxyxxxxxxxxyxxxxxxxxyxL这是一个二次函数，故又名二次插值或抛物插值。（二）牛顿插值法由线性代数知，任何一个不高于n次多项式，都可以表示成函数)())((,),)((,,1110100nxxxxxxxxxxxx的线性组合。既可以吧满足插值条件),,1,0()(niyxPii的n次插值多项式写成如下形式)())(())(()(110102010nnxxxxxxaxxxxaxxaa其中，ka为待定系数。这种形式的插值多项式称为牛顿插值多项式，记为)(xNn，即]1[110102010)())(())(()()(nnnxxxxxxaxxxxaxxaaxN因此，牛顿插值多项式)(xNn是插值多项式)(xPn的另一种表示形式。设函数)(xf在等距节点),,1,0(0nkkhxxk处的函数值kkyxf)(为已知，其中h是正常数，称步长。我们称两个相邻点kx和1kx处函数之差kkyy1为函数)(xf在点kx处以h为步长的一阶向前差分，记作ky，即kkkyyy1于是，函数)(xf在各节点处的一阶差分依次为11121010,,nnnyyyyyyyyy又称一阶差分的差分kkkkyyyy12)(为二阶差分。一般的，定义函数)(xf在点kx处的m阶差分为kmkmkmyyy111。在等距节点),,1,0(0nkkhxxk情况下，可以利用差分表示牛顿插值多项式的系数。事实上，由插值条件00)(yxNn可得00ya；再由插值条件11)(yxNn可得hyxxyya001011；一般的，由插值条件kknyxN)(可得),,2,1(!0nkhkyakkk。第4页共7页于是，满足插值条件iinyxN)(的插值多项式为)())((!))((!2)()(110010202000nnnnxxxxxxhnyxxxxhyxxhyyxN三、二者的比较拉格朗日插值法与牛顿插值法都是二种常用的简便的插值法。但牛顿法插值法则更为简便，与拉格朗日插值多项式相比较，它不仅克服了“增加一个节点时整个计算工作必须重新开始”（见下面例题）的缺点，而且可以节省乘、除法运算次数。同时，在牛顿插值多项式中用到的差分与差商等概念，又与数值计算的其他方面有着密切的关系。现用一实例比较拉格朗日插值法与牛顿插值法例已知函数表如下：x0.10.20.30.40.50.6sinx0.099830.198670.295520.389420.479430.56464计算sin(0.12)的值。利用拉格朗日插值法计算过程如下：（计算程序代码见附件）因为0.12位于0.1与0.2之间，故取节点2.0,1.010xx利用线性插值所求的近似值为119598.01.02.01.012.019867.02.01.02.012.009983.0)12.0(12.0sin1L计算结果如下图利用抛物插值所求的近似值为第5页共7页119757.0)2.03.0)(1.03.0()2.012.0)(1.012.0(29552.0)3.02.0)(1.02.0()3.012.0)(1.012.0(19867.0)3.01.0)(2.01.0()3.012.0)(2.012.0(09983.0)12.0(12.0sin1L计算结果如下图利用牛顿插值法计算过程如下：构造差分表如下：xsinxyy2y30.10.20.30.40.099830.198670.295520.389420.098840.096850.09390-0.00199-0.00295-0.00096利用线性插值所求的近似值为11960.009884.02.09983.0)12.0()12.0sin(1N利用抛物插值所求的近似值为11976.000016.0)12.0()00199.0(2)12.0(2.009884.02.09983.0)12.0()12.0sin(12NN从上面的计算过程可以看出，拉格朗日插值法的线性插值与抛物插值的计算过程没有继承性，即增加一个节点时整个计算工作必须重新开始。而牛顿插值则避免了这一问题，第6页共7页这样大量的节省了乘、除法运算次数，减少了计算的时间。因此，对于一些结构相当复杂的函数)(xf，牛顿插值法比拉格朗日插值法要占优势。[参考文献][1]易大义，沈云宝，李有法编.计算方法.杭州：浙江大学出版社，2002[2]冯康等编.数值计算方法.北京：国防工业出版社，1987[3]李庆阳，王能超，易大义编.数值分析（第四版）.北京：清华大学出版社，施普林格出版社，2001[4]BurdenRL，FairesJD，ReynoldsAC.NumericalAnalysis.AlpinePress,1981[5]易大义，陈道琦编.数值分析引论.杭州：浙江大学出版社，1998ComparisonbetweenLagrangeinterpolationmethodandNewtoninterpolationmethod[Abstract]Intheproductionandscientificresearches,thereappearsavarietyoffunctions.Forsomefunction,itisdifficulttofindoutitsanalyticalexpression.Thoughinsomecases,theanalyticalexpressionsofthestructurecanbeworkedout,itisinconvenienttousethembecauseofthecomplexityofstructure.Interpolationmethodisakindofoldwaytosolvesuchproblems,whichisnowcommonlyused.Itisnotonlyappliedintheactualproductionorscientificresearchesdirectlyandwidely,butalsobecomethefoundationoffurtherstudyofnumericalcalculationmethod.LagrangeinterpolationmethodandNewtoninterpolationlawaretwocommonlyusedsimpleinterpolationmethods.ThispaperisadiscussionoftheoryandthecomparisonbetweenLagrangeinterpolationmethodandNewtoninterpolationmethod.[KeyWords]Lagrangeinterpolation，Newtoninterpolation，Interpolationpolynomials，comparison第7页共7页附件：#includestdi