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

拉格朗日插值法与牛顿插值法的比较一、背景在工程和科学研究中出现的函数是多种多样的。常常会遇到这样的情况：在某个实际问题中，虽然可以断定所考虑的函数f3)在区间",b］上存在且连续，但却难以找到它的解析表达式，只能通过实验和观测得到在有限个点上的函数值(即一张函数表)。显然，要利用这张函数表来分析函数f3)的性态，甚至直接求出其他一些点上的函数值可能是非常困难的。面对这些情况，总希望根据所得函数表(或结构复杂的解析表达式)，构造某个简单函数P(x)作为f⑴的近似。这样就有了插值法，插值法是解决此类问题目前常用的方法。如设函数y=f(x)在区间",b］上连续，且在n+1个不同的点a<%,气,…,七<b上分别取值y,y，…,y。TOC\o"1-5"\h\z01n插值的目的就是要在一个性质优良、便于计算的函数类①中，求一简单函数P(x)，使P(Xj)=y(i=0,1,…,n)而在其他点x丰工,上，作为f(x)的近似。通常，称区间［a,b］为插值区间，称点x,x，…,x为插值节点，称式P(x)=y为插值01nii条件，称函数类①为插值函数类，称P(x)为函数f(x)在节点x,x，…,x处的插值函数。01n求插值函数P(x)的方法称为插值法。插值函数类①的取法不同，所求得的插值函数P(x)逼近f(x)的效果就不同。它的选择取决于使用上的需要，常用的有代数多项式、三角多项式和有理函数等。当选用代数多项式作为插值函数时，相应的插值问题就称为多项式插值。本文讨论的拉格朗日插值法与牛顿插值法就是这类插值问题。在多项式插值中，最常见、最基本的问题是：求一次数不超过n的代数多项式P(x)=a+ax++axn使P(x)=y(i=0,1,…,n)，其中，a,a，…,a为实数。nii01n拉格朗日插值法即是寻求函数、(x)(拉格朗日插值多项式)近似的代替函数f(x)。相似的，牛顿插值法则是通过Nn(x)(牛顿插值多项式)近似的求得函数的值。二、理论基础(一)拉格朗日插值法在求满足插值条件n次插值多项式P(X之前，先考虑一个简单的插值问题：对节点x,(i=0,1,...,n)中任一点七(0<k<n)，作一n次多项式匕(x)，使它在该点上取值为1，而在其余点x,(i=0,1,k-1,k+1,...,n)上取值为零，即[1i=klk(X，)=[0i。k上式表明n个点x,x，…,x,x，…,x都是n次多项式l(x)的零点，故可设01k-1k+1nkl(x)=A(x—x)(x—x)…(x—x)(x—x)・・・(x—x)[1]kk01k—1k+1n其中，Ak为待定系数。由条件lk(x「=1立即可得k(x-x)(x-x)(x-x)(x-x)k0kk—1kk+1kn玖(x-x)•••(x-x)(x-x)•••(x-x)故l(x)=0k-1k+1nk(x-x).・・(x-x)(x-x)・・・(x-x)k0kk—1kk+1kn由上式可以写出n+1个n次插值多项式l(x),l(x),・,l(x)。我们称它们为在n+1个节01n点x,x,・,x上的n次基本插值多项式或n次插值基函数。01n利用插值基函数立即可以写出满足插值条件的n次插值多项式yl(x)+yl(x)+…+yl(x)0011nn1i=k根据条件l(x)=J,，容易验证上面多项式在节点x处的值为y(i=0,1,・,n)，ki10i。kii因此，它就是待求的n次插值多项式P(x)。形如yl(x)+yl(x)+…+yl(x)的插值多项式就是拉格朗日插值多项式，记为0011nnL(x)，即L(x)=yl(x)+yl(x)+…+yl(x)n1122nn(x-x)(x-x)(x-x)(x-x)=0k-1k+1n(x-x)(x-x)(x-x)(x-x)k0kk—1kk+1kn作为常用的特例，令n=1，由上式即得两点插值公式L(x)=y+(x-x)，这是一个线性函数，故又名线性插值。10x1-x00若令n=1，则又可得到常用的三点插值公式/、(x-x)(x-x)(x-x)(x-x)(x-x)(x-x)L(x)=y12—+yo2—+yo1—20(x-x)(x-x)1(x-x)(x-x)2(x-x)(x-x)010210122021这是一个二次函数，故又名二次插值或抛物插值。(二)牛顿插值法由线性代数知，任何一个不高于n次多项式，都可以表示成函数1,x-x,(x-x)(x-x),—,(x-x)(x-x)…(x-x)的线性组合。既可以吧满足插值条件TOC\o"1-5"\h\z00101n-1P(x‘)=y,(i=0,1,...,n)的n次插值多项式写成如下形式a+a(x-x)+a(x-x)(x-x)+—Fa(x-x)(x-x)…(x-x)

010201n01n-1其中，a*为待定系数。这种形式的插值多项式称为牛顿插值多项式，记为Nn(x)，即N(x)=a+a(x-x)+a(x-x)(x-x)+—Fa(x-x)(x-x)—(x-x)[1]n010201n01n-1因此，牛顿插值多项式N.(x)是插值多项式P(x)的另一种表示形式。设函数f(x)在等距节点x^=x°+kh(k=0,1,—,n)处的函数值f(x^)=y^为已知，其中h是正常数，称步长。我们称两个相邻点x和x处函数之差y-y为函数f(x)在点x处kk+1k+1kk以h为步长的一阶向前差分，记作Ayk，即Zk=ykx-yk于是，函数f(x)在各节点处的一阶差分依次为Ay=y-y,Ay=y-y,Ay=y-y010121n-1nn-1又称一阶差分的差分A2yk=A(Ayk)=Ay^-Ay*为二阶差分。一般的，定义函数f(x)在点x处的m阶差分为Amy=Am-1y-Am-1y。kkk+1k在等距节点xk=x0+kh(k=0,1,—,n)情况下，可以利用差分表示牛顿插值多项式的系数。事实上，由插值条件N(x0)=y0可得a0=y0；再由插值条件N(x1)=y1可得a=^=^0；一般的，由插值条件N(x)=y可得a=^ky0(k=1,2,—,n)。1x-xhnkkkk'.hk于是，满足插值条件七(x,)=y,的插值多项式为N(x)=y+竺0(x-x)+△'0(x-x)(x-x)++^_乙(x-x)(x-x)—(x-x)n0h02!・h201n'h01n-1三、二者的比较拉格朗日插值法与牛顿插值法都是二种常用的简便的插值法。但牛顿法插值法则更为

简便，与拉格朗日插值多项式相比较，它不仅克服了“增加一个节点时整个计算工作必须重新开始”（见下面例题）的缺点，而且可以节省乘、除法运算次数。同时，在牛顿插值多项式中用到的差分与差商等概念，又与数值计算的其他方面有着密切的关系。现用一实例比较拉格朗日插值法与牛顿插值法例已知函数表如下：x0.10.20.30.40.50.6sinx0.099830.198670.295520.389420.479430.56464计算sin（0.12）的值。利用拉格朗日插值法计算过程如下：（计算程序代码见附件）因为0.12位于0.1与0.2之间，故取节点％=0.1,气=0.2利用线性插值所求的近似值为0.12-0.10.2-0.1sin0.12r'(0.12)0.12-0.2=0.09983x+0.19867x0.1-0.2r0.119598计算结果如下图利用抛物插值所求的近似值为sin0.12rL(0.12)=0.09983x(口12-0.2)(0.12*+0.19867x(°」2一0.1)。12一的(0.1-0.2)(0.1-0.3)(0.2-0.1)(0.2-0.3)+0.29552x(0.12一0.1)。12项2)(0.3-0.1)(0.3-0.2)0.12-0.10.2-0.1计算结果如下图r0.119757计算结果如下图利用牛顿插值法计算过程如下:构造差分表如下：xsinxE△2j△3>0.10.099830.098840.20.198670.09685-0.00199-0.000960.30.295520.09390-0.002950.40.38942利用线性插值所求的近似值为sin(0.12)nN1(0.12)=0.9983+0.2x0.09884=0.11960利用抛物插值所求的近似值为sin(0.12)nN2(0.12)=0.9983+0.2x0.09884+。^X