数值计算方法拉格朗日与牛顿插值法

1、拉格朗日插值法问题的提出01( ), ,( ),(0,1, )( ) niyf xa ba bx xxyf xinf x 在实际问题中常遇到这样的函数，其在某个区间上是存在的。但是，通过观察或测量或实验只能得到在区间上有限个离散点上的函数值或者的函数表达式是已知的，但却很复杂而不便于计算，希望用一个简单的函数来描述。问题的提出 010011( )1,( ),(0,1, ),( )( ),(0,1, ).( )1,( )( )( )niiiinnyf xnxxxyf xinyP xP xyinyf xnxyx yxyxa bR xf xP x插值问题的数学提法：已知函数在个点上的函数值求一个多项

2、式，使其满足即要求该多项式的函数曲线要经过上已知的个点同时在其他上要估计误差插值问题n 1 ,0011nnxyxyxy( )( )( )Rxf xP x n 1 个点个点同时在其它同时在其它上要估计误差上要估计误差。当当时时,求一次多项式求一次多项式一次插值 100111( ),nP xxyx y当时，求一次多项式要求通过两点二次插值 20011222( ),nP xxyx yxy当时，求二次多项式要求通过三点拉格朗日插值公式n线性插值（一次插值） 1111111111 ( ),(),()( )(),(),kkkkkkkkkkkkkkf xxxyf xyf xyP xyP xyP xxyxy已

3、知函数在区间的端点上的函数值，求一个一次函数使得。其几何意义是已知平面上两点，求一条直线过该已知两点。线性插值n插值函数和插值基函数1111111111111( )()( )( ),( )kkkkkkkkkkkkkkkkkkkkkkkkyyPxyxxxxxxxxyyPxyyxxxxxxxxlxlxxxxx由直线的点斜式公式可知：，把此式按照和写成两项:，记，称它们为一次插值基函数。线性插值n基函数的特点：( )klxkx1kx( )klx1( )kxl10011( )klxkx1kx11111( )( )( ),k kkkkkkkP xy lxylxyyxx拉格朗日型插从而，此形式称之为。其中

4、，插值基函数与、无关，而由插值结点 、值多项式决定例子0101011lg101 , lg201.3010lg12( )lg( )lg(10)1(20)1.3010102011.3010201101( )(20)( )(10)10201020 1010f xxf xxffxxyyxxlxxl xx 例：已知，利用插值一次多项式求的近似值。解：，设，则插值基本多项式为：，例子10 01 1111.3010( )( )( )(20)(10)101011.3010(12)(1220)(12 10)1.06021010lg12lg10 lg20 lg121.0792).P xy lxy l xxxP 于

5、是，拉格朗日型一次插值多项式为：故即由和两个值的线性插值得到，且具有两位有效数字（精确解二次插值多项式 111111221122111111 ( ),() , ()()( )()()(),kkkkkkkkkkkkkkkkkkkkkyf xxxxyf xyf xyf xP xP xyP xyP xyxyxyxy已知函数在点上的函数值，。求一个次数不超过二次的多项式，使其满足，。其几何意义为：已知平面上的三个点：，求一个二次抛物线，使得该抛物线经过这三点。二次插值基本多项式11 ,kkkxxx有三个插值结点，构造三个插值基本多项式，要求满足：（1）基本多项式为二次多项式；（2）它们的函数值满足下表

6、：1kxkx1kxkx1kx 1( )klx( )klx1( )klx1000100011kx1( )klx( )klx1( )klx二次插值基本多项式1kxkx1kx 1( )klx( )klx1( )klx111111111111111111()0,()0( )()()( )()()()1()()1()()1( )()()()kkkkkkkkkkkkkkkkkkkkkkkkklxlxlxxxxxlxa xxxxlxa xxxxxxxxalxxxxxxx因为，故有因子，而其已经是一个二次多项式，仅相差一个常数倍，可设，又因为，故，得：，从而11111111111()()()()()( )(

7、)()()()()kkkkkkkkkkkkkkkkxxxxxxxxxxlxlxxxxxxxxx，拉格朗日型二次插值多项式拉格朗日型二次插值多项式 2111122 ( )( )( )( )( )( ) , 1, ,1kkk kkkiiP xylxy lxylxP xP xyikk k由前述，拉格朗日型二次插值多项式：，是三个二次插值多项式的线性组合，因为它是次数不超过二次的多项式，且满足：例子2例 ：已知ixlgiiyxixlgiiyx10152011.17611.3010lg12利用此三值的二次插值多项式求的近似值012012101520(15)(20)1( )1520(10 15)(1020

8、)50(10)(20)1( )1020(15 10)(1520)25(10)(15)1( )1015(20 10)(20 15)50 xxxxxlxxxxxl xxxxxlxxx 解：设，则例2（续）ixlgiiyx20 01 12 221( )( )( )( )2015501.17611.301010201015255011.1761(12)1220 12 1512 10 122050251.301012 10 12 151.076650lg12lg121.07923P xy lxy l xy lxxxxxxxP故所以：利用三个点进行抛物线插值得到的的值，与精确值相比，具有 位有效数字。拉格

9、朗日型拉格朗日型n次插值多项式次插值多项式 0101 ( ),( )( )0,1,1nnnniiyf xx xxyyyP xP xyinnn已知函数在n+1个不同的点上的函数值分别为，求一个次数不超过n次的多项式，使其满足，即个不同的点可以唯一决定一个 次多项式。插值基函数01 11( ), ( ), ( )( )1( )2( )1,()0,niiiiiknnnlx l xlxl xl xnl xnl xki过个不同的点分别决定个 次插值函数。每个插值基本多项式满足：（）是 次多项式；（ ）而在其它 个。插值基函数01101101101 ()0,( )()()()()( )()()()()(

10、)1()()()()( )()()(ikiiiniiiniiiiniiiiil xkil xxxxxxxxxnl xa xxxxxxxxl xaxxxxxxxxl xxxxxx由于，故有因子：，因其已经是次多项式，故而仅相差一个常数因子。令：由，可以定出 ，进而得到：1)()iinxxxn次拉格朗日型插值多项式Pn(x)01010 01 10( )1( ), ( ), ( ),( )( )( )( )( )( )( )0,1,nnnnnn nk kknniiP xnnl x l xlxyyyP xy l xy l xy lxy lxP xnP xyin是个 次插值基本多项式的线性组合，相应的组

11、合系数是。即从而是一个次数不超过 的多项式，且满足，例子01234012340(2,0)(4,3)(6,5)(8,4)(10,1)24681003541(4)(6)(8)(10)( )(24)(26)(28)(2 10)1(4)(6)(8)(10)384xxxxxyyyyyxxxxlxxxxx例3：求过点的拉格朗日型插值多项式。解：用4次插值多项式对5个点插值：，；123(2 ) (6 ) (8 ) (1 0 )()( 42 ) ( 46 ) ( 48 ) ( 41 0 )1(2 ) (6 ) (8 ) (1 0 )9 6(2 ) (4 ) (8 ) (1 0 )()( 62 ) ( 64 )

12、 ( 68 ) ( 61 0 )1(2 ) (4 ) (8 ) (1 0 )6 4(2 ) (4 ) (6 ) (1 0 )()( 82 ) ( 84 ) ( 86 ) ( 81 0 )1xxxxlxxxxxxxxxlxxxxxxxxxlx，4(2 ) (4 ) (6 ) (1 0 )9 6(2 ) (4 ) (6 ) (8 )()(1 02 ) (1 04 ) (1 06 ) (1 08 )1(2 ) (4 ) (6 ) (8 )3 8 4xxxxxxxxlxxxxx，；40 01 12 23 34 4( )( )( )( )( )( )3(2)(6)(8)(10)965(2)(4)(8)(

13、10)644(2)(4)(6)(10)961(2)(4)(6)(8)384P xy l xy l xy lxy l xy lxxxxxxxxxxxxxxxxx 所以拉格朗日插值多项式的截断误差 ,( )( ),( )( )( )( )( )( )( )0nnnniniinia bP xf xRxRxf xP xxxRxf xP x我们在上用多项式来近似替代函数其截断误差记作，。当 在插值结点 上时，估计截断误差。拉格朗日插值多项式的截断误差( )(1)01(1)011( )( ) , ( )( , )( ) , 1( )( )( )(1)!( , ),( )()()()nnnnnnnnnyf

14、xnyfxa byfxa baxxxbP xnxa bR xfxna bxxxxxxx 定理 ：设函数的 阶导数在上连续，在上存在；插值结点为，是次拉格朗日插值多项式；则对任意有：其中例子12212lg121lg10lg20lg12P 121.0602,lg121.0792e1.0792 1.06020.0190( )lg1( ),10,20ln101|( )|0.043ln10 101|( )(12 10)(1220)| 8 0.0430.3442f xxfxxxff 分析例，例 中计算的截断误差在例中，用和计算，估计误差：当时例子243242lg10 lg15lg20lg12.P 121.

15、0766,e1.0792 1.07660.00262( )8.686 10ln101|(12)| |( )(12 10)(12 15)(1220)|3!18.686 102 3 80.006956fxxRf 在例 中，用，和计算估计误差：故牛顿插值均差010101010101010112011202012( )1,(),(),(),()()1.( ), ,2., ,( ),nnnf xnx xxf xf xf xyyyf xf xf xx xf x xxxf x xf x xf x xf x xxxf xx x x设函数在个相异的点上的函数值分别为，或者记为一阶均差：称为关于结点的一阶均差，记

16、为。二阶均差：一阶均差，的均差称为关于结点的二阶均差，0120111201001,3.1, ,( )1,nnnnnf x x xnnnf x xxf x xxf x xxxxf xnx xx记为。阶均差：递归地用阶均差来定义 阶均差，称为关于个结点的均差。均差的性质010100110101010101100112012020102011001.11,()()()()()(), ,11()nnknkkkkkkknnnyyyyf x xxxxxxxxxxf xf xyyf x xxxxxxxf x xf x xf x x xxxyyxxxxxxx性质 ： 阶均差可以表示成个函数值的线性组合，即例：

17、122122101201020210122021012010210122021()11()()()()()()()()()()()yyxxxxxyyyxxxxxxxxxxxxxxyyyxxxxxxxxxxxx均差的性质0110012102021001012., , ,3.( ),1,2( )2,3,()kf x xf x xf x x xf x x xf x x xf xxnf x xxnf x x xxnf xkf x xxxnkknknk：均差与结点的顺序无关，即：若是 的 次多项式，则一阶均差是 的次多项式，二阶均差是 的次多项式；一般地，函数性的 阶均差是质（对称性）的次多项式，而时性

18、，质阶均差为零。利用均差表计算均差 n利用均差的递推定义利用均差的递推定义,可以用递推来计算均差。可以用递推来计算均差。n如下表：如下表：n如要计算四阶均差如要计算四阶均差,应再增加一个节点应再增加一个节点,表中还要增加表中还要增加一行。一行。xif(xi)一阶均差一阶均差二阶均差二阶均差三阶均差三阶均差x0f(x0)X1f(x1)fx0, X1x2f(x2)fx1, X2fx0, X1, X2x3f(x3)fx2, X3fx1, X2, X3fx0, X1, X2 , X3例子n例1：已知ixix ( )if x1347021512( )if x计算三阶均差f1,3,4,7例子解：列表计算i

19、xix ( )if x一阶均差一阶均差二阶均差二阶均差三阶均差三阶均差10321415134712-1-3.5-1.25( )if x牛顿插值公式0000000010110010110101201220101.( )() ,( )() ,(), (0) , , , ,() (1) , , ,f xf xf x xxxf xf xf x xxxf x xf x xf x x xxxf x xf x xf x x xxxf x x xf x x xf x x x xxxf x x xf x x牛顿插值公式的构造因为，所以式因，有， 式因120122, ,() (2)xf x x x xxx， 式牛

20、顿插值公式01010010100010012010 , , , ,() ()1),( )(),(),()(),2)nnnnnnnnf x xxf x xxf x xxxxf x xxf x xxf x xxxxnf xf xf x xxxnnf x x xxxxxf x一般地， 式将( 式)代入(式式 代入(1式)，(1式)代入(0式)，得：10110101,()()() ,()(),()11( )( )( )( )nnnnnnnnxxxxxxxxf x x xxxxxxxxR xnxnxnNxf xNxR xx最后一项中，均差部分含有 是余项部分，记作。前面项中，均差部分不含有 ，因而前面项

21、是关于 的 次多项式，记作，这就是牛顿公式。于是上式成为：00100101011001000010010012010121( )(),() ,()()( )(),()()2( )(),(),()() ,(nf xf xf x xxxf x x xxxxxyyN xf xf x xxxyxxxxnf xf xf x xxxf x x xxxxxf x x x x例如：当时，其中，这就是牛顿一次插值多项式，也就是点斜式直线方程。当时，0122001001201)()()( )(),(),()()xxxxxxNxf xf x xxxf x x xxxxx这就是牛顿二次插值多项式。2000121010

22、1010122020010112202102011222()()()()()()()()()()()()()()()()()1()()()( )Nxf xf xf xNxf xxxf xxxf xf xNxf xxxxxf xf xf xf xxxxxxxxxxxf xNx显然，即满足二次插值条件。例2例2：已知ixix ( )if x1347021512( )if x求满足以上插值条件的牛顿型插值多项式。例2（解）001012012331()0,1,4,1.25( )0(1)4 (1)(3)1.25 (1)(3)(4)f xf xxf xx xf xx x xNxxxxxxx 解：在例中，我

23、们已经计算出，；则牛顿三次插值多项式为例3ix ( )if x3( )(0.596)f xf例 ：已知在六个点的函数值如下表，运用牛顿型插值多项式求的近似值。kx ()kf xkxx0.400.410750.1960.550.578151.11600.0460.650.696751.18600.28000.0540.800.888111.27570.35880.19700.2040.901.026521.38410.43360.21370.03440.4541.051.253861.51560.52600.23100.03460.0003xkf(xk)一阶均一阶均差差二阶均二阶均差差三阶均三阶

24、均差差四阶均四阶均差差五阶均五阶均差差X-xk0.400.410750.1960.550.57815 1.11600.0460.650.69675 1.18600.2800-0.0540.800.88811 1.27570.35880.1970-0.2040.901.02652 1.38410.43360.21370.0344-0.4541.051.25386 1.51560.52600.23100.03460.0003200100120123201230123( )(),(),()()(0.596)0.41075 1.1160 0.1960.28 0.196 0.0460.632010( )

25、( ),()()()(0.596)0.6320100.1970 0.196 0.046 ( 0.054)0.6Nxf xf x xxxf x x xxxxxNNxNxf x x x xxxxxxxN 4301234012364319145( )( ),()()()()0.0344 0.196 0.046 ( 0.054) ( 0.204)3.4 10( )0.63191450.00000340.6319179NxNxf x x x x xxxxxxxxxNx 欲求，只需在之后再加一项：故拉格朗日插值与牛顿插值的比较(1)01( )( )()()(), 0,1,( )( )( ) ,( )( )

26、(1)!1nnnknkknnnnnnP xNxnP xNxf xknP xNxff x x xxxxnnn（1）和均是 次多项式，且均满足插值条件：由多项式的唯一性，因而，两个公式的余项是相等的，即：（2）当插值多项式从次增加到 次时，拉格朗日型插值必须重新计算所有的基本插值多项式；而对于牛顿插值，只需要表格再计算一个n阶均差，然后加上一项即可。等距牛顿插值公式n插值节点为等距节点：0,0,1, ,kxxkh kn如下图：hhhhx1x0 x2x3Xn-1Xn( )().kkkhyf xxyf x其中， 称为步长，函数在 的函数值为差分的概念（向前差分）12121111112()()1,kkk

27、kkkkkkkmmmkkkkkkyyyyyyyyyymmyyyxxx ：；一般地， 阶差分用阶一阶差分二阶差差分来定义：以上定义的是：从 起向前的函数值的差， 称为分前差向前差分算子。差分的概念（向后差分）121112111()()kkkkkkkkkkmmmkkkyyyyyyyyyymyyym表示一阶向后差分：二阶向后差分：，阶向后差分：分别称为一阶，二阶， ， 阶向向后差分算子后差分。差分的性质（性质1）1212111012121111( 1)( 1)( 1)( 1)1 2 ()()nkk nnk nnk niinnnnnk n inknkniink n iikkkkkkkkkknnyyC

28、yC yC yCyC yC ynyyynyyyyyyy 性质 ： 阶差分是个函数值的线性组合。验证：时，；时，21(2)kkkyyy差分的性质（性质1续）32213212132131233(2)(2)33;33kkkkkkkkkkkkkkkkkknyyyyyyyyyyyyyyyyyy 时，一般地，可用数学归纳法证明此公式。对于后差也有类似的公式，例如：差分的性质（性质2）112211121112221221,!,2 ,2 ,1,111122mkkk mkmkkkkkkkkkkkkkkkkkkkkkkkkkf xxxym hxxh xxh xxhyyf xxyxxhf xxf xxf xxxxxyyyh hhh性质 ：在等距插值的情况下，差分和均差有如下关系：验证：因为所以,差分的性质（性质2续）1233212132231223,11113226kkkkkkkkkkkkkkkf xxxxf xxxf xxxxxyyyhhhh等距节点的牛顿插值公式000(),0,1,0.kkknxxkhyf xknxx