《拉格朗日插值法与牛顿插值法的比较.pdf》由会员分享，可在线阅读，更多相关《拉格朗日插值法与牛顿插值法的比较.pdf（12页珍藏版）》请在三一文库上搜索。
1、莆 膇拉格朗日插值法与牛顿插值法的比较 薄 聿 摘要 在生产和科研中出现的函数是多样的。对于一些函数很难找出其解析表达式。即使在某些情况下，可以写出 函数的解析表达式，但由于解析表达式的结构相当复杂，使用起来很不方便。插值法即是解决此类问题的一种古老的、 然而却是目前常用的方法，它不仅直接广泛地应用于生产实际和科学研究中，而且也是进一步学习数值计算方法的基础。 拉格朗日插值法和牛顿插值法则是二种常用的简便的插值法。本文即是讨论拉格朗日插值法和牛顿插值法的理论及二者 的比较。 蝿 关键词 拉格朗日插值牛顿插值插值多项式比较 薆 芄一、背景 膁在工程和科学研究中出现的函数是多种多样的。常常会遇到这
2、样的情况：在某个实际 问题中，虽然可以断定所考虑的函数)(xf在区间,ba上存在且连续，但却难以找到它的 解析表达式，只能通过实验和观测得到在有限个点上的函数值（即一张函数表）。显然， 要利用这张函数表来分析函数)(xf的性态，甚至直接求出其他一些点上的函数值可能是非 常困难的。面对这些情况，总希望根据所得函数表（或结构复杂的解析表达式），构造某 个简单函数)(xP作为)(xf的近似。这样就有了插值法， 插值法是解决此类问题目前常用的 方法。 袇如设函数 )(xfy在区间,ba上连续，且在1n个不同的点bxxxa n , 10 上分别 取值 n yyy, 10 。 羆插值的目的就是要在一个性质
3、优良、便于计算的函数类 中，求一简单函数)(xP，使 螁 ),1,0()(niyxP ii 膂而在其他点 i xx上，作为)(xf的近似。 艿通常，称区间,ba 为插值区间，称点 n xxx, 10 为插值节点，称式 ii yxP)(为插值条 件，称函数类为插值函数类，称)(xP为函数)(xf在节点 n xxx, 10 处的插值函数。求 插值函数)(xP的方法称为插值法。 蒅插值函数类 的取法不同，所求得的插值函数)(xP逼近)(xf的效果就不同。它的选择 取决于使用上的需要，常用的有代数多项式、三角多项式和有理函数等。当选用代数多项 式作为插值函数时，相应的插值问题就称为多项式插值。本文讨论
4、的拉格朗日插值法与牛 顿插值法就是这类插值问题。 蒁在多项式插值中，最常见、最基本的问题是：求一次数不超过 n的代数多项式 罿 n nx axaaxP 10 )( 莈使 ), 1 ,0()(niyxP iin ，其中， n aaa, 10 为实数。 袅拉格朗日插值法即是寻求函数 )(xLn（拉格朗日插值多项式）近似的代替函数)(xf。相 似的，牛顿插值法则是通过)(xNn（牛顿插值多项式）近似的求得函数的值。 节 肁二、 理论基础 蒆（一）拉格朗日插值法 芄在求满足插值条件n 次插值多项式 )(xPn之前，先考虑一个简单的插值问题：对节点 ), 1,0(nixi中任一点)0(nkxk，作一 n
5、 次多项式)(xl k ，使它在该点上取值为1， 而在其余点), 1, 1,1,0(nkkixi上取值为零，即 羂 ki ki xl ik 0 1 )( 肂上式表明 n个点 nkk xxxxx, 1110 都是 n次多项式)(xl k 的零点，故可设 衿 1 1110 )()()()( nkkkk xxxxxxxxxxAxl 螃其中， k A 为待定系数。由条件1)( kk xl立即可得 蚂 )()()( 1 110nkkkkkk k xxxxxxxx A 衿故 )()()( )()()( )( 110 110 nkkkkkk nkk k xxxxxxxx xxxxxxxx xl 羇由上式可以
6、写出1n个 n次插值多项式)(,),(),( 10 xlxlxl n 。我们称它们为在1n个节 点 n xxx, 10 上的 n次基本插值多项式或n次插值基函数。 莇利用插值基函数立即可以写出满足插值条件的n次插值多项式 蒃)()()( 1100 xlyxlyxly nn 羁根据条件 ki ki xl ik 0 1 )(，容易验证上面多项式在节点 i x 处的值为),1 ,0(niyi， 因此，它就是待求的 n次插值多项式 )(xP n 。 艿形如 )()()( 1100 xlyxlyxly nn 的插值多项式就是拉格朗日插值多项式，记为)(xLn， 即 袆 )()()( )()()( )()
7、()()( 110 110 2211 nkkkkkk nkk nnn xxxxxxxx xxxxxxxx xlyxlyxlyxL 膃作为常用的特例，令1n ，由上式即得两点插值公式 螈 )()( 0 01 01 01 xx xx yy yxL，这是一个线性函数，故又名线性插值。 蒈若令1n，则又可得到常用的三点插值公式 芅 )( )( )( )( )( )( )( 1202 10 2 2101 20 1 2010 21 02 xxxx xxxx y xxxx xxxx y xxxx xxxx yxL 羃这是一个二次函数，故又名二次插值或抛物插值。 袀（二）牛顿插值法 薆由 线 性 代 数 知
8、， 任 何 一 个 不 高 于 n 次 多 项 式 ， 都 可 以 表 示 成 函 数 )()( ,),)( , 1 110100n xxxxxxxxxxxx的线性组合。既可以吧满足插值条件 ), 1,0()(niyxP ii 的n 次插值多项式写成如下形式 蚅 )()()()( 110102010nn xxxxxxaxxxxaxxaa 蚄其中， k a 为待定系数。这种形式的插值多项式称为牛顿插值多项式，记为)(xNn，即 1 110102010 )()()()()( nnn xxxxxxaxxxxaxxaaxN 袁因此，牛顿插值多项式)(xN n 是插值多项式)(xPn的另一种表示形式。
9、袈设函数)(xf在等距节点), 1 , 0( 0 nkkhxxk处的函数值 kk yxf)(为已知，其中h 是正常数，称步长。我们称两个相邻点 k x 和 1k x处函数之差 kk yy 1 为函数)(xf在点 k x 处 以h为步长的一阶向前差分，记作 k y ，即 kkk yyy 1 膄于是，函数)(xf在各节点处的一阶差分依次为 11121010 , nnn yyyyyyyyy 蒄又称一阶差分的差分 kkkk yyyy 1 2 )(为二阶差分。一般的，定义函数)(xf在 点 k x 处的 m阶差分为 k m k m k m yyy 1 1 1 。 蚈在等距节点 ), 1 ,0( 0 nk
10、khxxk情况下，可以利用差分表示牛顿插值多项式的系数。 事 实 上 ， 由 插 值 条 件 00) (yxNn可 得 00 ya； 再 由 插 值 条 件 11) (yxNn可 得 h y xx yy a 0 01 01 1 ；一般的，由插值条件 kkn yxN)(可得),2, 1( ! 0 nk hk y a k k k 。 羇于是，满足插值条件 iin yxN)(的插值多项式为 薄)()( ! )( ! 2 )()( 110 0 10 2 0 2 0 0 0n n n n xxxxxx hn y xxxx h y xx h y yxN 膅三、 二者的比较 螀拉格朗日插值法与牛顿插值法都是
11、二种常用的简便的插值法。但牛顿法插值法则更为 简便，与拉格朗日插值多项式相比较，它不仅克服了“增加一个节点时整个计算工作必须 重新开始”（见下面例题）的缺点，而且可以节省乘、除法运算次数。同时，在牛顿插值 多项式中用到的差分与差商等概念，又与数值计算的其他方面有着密切的关系。 荿现用一实例比较拉格朗日插值法与牛顿插值法 芇例 已知函数表如下： 蚁x 肅0.1 螂0.2 羁0.3 蚅0.4 袃0.5 袀0.6 莀sinx 莆0.09983 袄0.19867 芃0.29552 蝿0.38942 膆0.47943 羆0.56464 莁计算 sin(0.12) 的值。 腿利用拉格朗日插值法计算过程如下
12、： （计算程序代码见附件） 袇 因为 0.12 位于 0.1 与 0.2 之间，故取节点2. 0, 1 .0 10 xx 螃利用线性插值所求的近似值为 螃 119598.0 1.02.0 1.012.0 19867.0 2.01.0 2.012.0 09983.0 )12.0(12.0sin 1 L 蚈计算结果如下图 蚇 袄利用抛物插值所求的近似值为 袂 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 .
13、01.0( )3 .012.0)(2 .012.0( 09983. 0 )12. 0(12.0sin 1 L 莁计算结果如下图 莇 袆利用牛顿插值法计算过程如下： 羀构造差分表如下： 螁x 膈sinx 蚃y 莂y 2 膀y 3 袈0.1 螄 蒁0.2 薀 蕿0.3 螆 袃0.4 聿0.09983 荿 薃0.19867 羂 蒈0.29552 袅 蚄0.38942 肀 袈0.09884 薆 蚆0.09685 蒂 薁0.09390 莆 蒃 薁-0.00199 羀 肆-0.00295 薅 袃 蒀 螇-0.00096 蚆利用线性插值所求的近似值为 肁 11960. 0 09884.02. 09983.0
14、 )12.0()12.0sin( 1 N 衿利用抛物插值所求的近似值为 薇 11976. 0 00016. 0)12. 0( )00199.0( 2 ) 12.0(2 .0 09884.02. 09983.0 )12.0()12.0sin( 1 2 N N 蒃从上面的计算过程可以看出，拉格朗日插值法的线性插值与抛物插值的计算过程没有 继承性，即增加一个节点时整个计算工作必须重新开始。而牛顿插值则避免了这一问题， 这样大量的节省了乘、除法运算次数，减少了计算的时间。因此，对于一些结构相当复杂 的函数)(xf，牛顿插值法比拉格朗日插值法要占优势。 莄 艿 芈 参考文献 蒅1 易大义，沈云宝，李有法
15、编.计算方法 . 杭州：浙江大学出版社，2002 蒂2 冯康等编 . 数值计算方法 . 北京：国防工业出版社，1987 螈3 李庆阳，王能超，易大义编.数值分析（第四版）. 北京：清华大学出版社，施普林格出版社，2001 肈4Burden R L，Faires J D，Reynolds A C. Numerical Analysis. Alpine Press,1981 薆5 易大义，陈道琦编. 数值分析引论 . 杭州：浙江大学出版社，1998 蚁 蒁 螈Comparison between Lagrange interpolation method and Newton interpolat
16、ion method 莃Abstract In the production and scientific researches, there appears a variety of functions. For some function, it is difficult to find out its analytical expression. Though in some cases, the analytical expressions of the structure can be worked out, it is inconvenient to use them becaus
17、e of the complexity of structure. Interpolation method is a kind of old way to solve such problems, which is now commonly used. It is not only applied in the actual production or scientific researches directly and widely, but also become the foundation of further study of numerical calculation metho
18、d. Lagrange interpolation method and Newton interpolation law are two commonly used simple interpolation methods. This paper is a discussion of theory and the comparison between Lagrange interpolation method and Newton interpolation method. 羃Key Words Lagrange interpolation ，Newton interpolation ，In
19、terpolation polynomials ，comparison 袁 蕿 莅 肁 芀 羅 蒆 蒄 虿 螅 芄 薂 附件： #include void main() float x6=0.1,0.2,0.3,0.4,0.5,0.6;int n,k,j; float f6=0.09983,0.19867,0.29552,0.38942,0.47943,0.56464; float p,a,sum=0; printf(“ 输入插值次数 n 和所要求 sina的 a的值 :“); scanf(“%d %f“, for(k=0;k=n;k+) p=1; for(j=0;j=n;j+) if(k!=
20、j)p=p*(a-xj)/(xk-xj); sum=sum+p*fk; printf(“x=%f,y=%f“,a,sum); 仅供个人用于学习、研究；不得用于商业用途。 For personal use only in study and research; not for commercial use. Nur f r den pers?nlichen fr Studien, Forschung, zu kommerziellen Zwecken verwendet werden. Pour l tude et la recherche uniquement des fins personn
21、elles; pas des fins commerciales. , , . 以下无正文 仅供个人用于学习、研究；不得用于商业用途。 For personal use only in study and research; not for commercial use. Nur f r den pers?nlichen fr Studien, Forschung, zu kommerziellen Zwecken verwendet werden. Pour l tude et la recherche uniquement des fins personnelles; pas des fins commerciales. , , . 以下无正文