數(shù)值計(jì)算方法拉格朗日與牛頓插值法

1、拉格朗日插值法問(wèn)題的提出01( ), ,( ),(0,1, )( ) niyf xa ba bx xxyf xinf x 在實(shí)際問(wèn)題中常遇到這樣的函數(shù)，其在某個(gè)區(qū)間上是存在的。但是，通過(guò)觀察或測(cè)量或?qū)嶒?yàn)只能得到在區(qū)間上有限個(gè)離散點(diǎn)上的函數(shù)值或者的函數(shù)表達(dá)式是已知的，但卻很復(fù)雜而不便于計(jì)算，希望用一個(gè)簡(jiǎn)單的函數(shù)來(lái)描述。問(wèn)題的提出 010011( )1,( ),(0,1, ),( )( ),(0,1, ).( )1,( )( )( )niiiinnyf xnx xxyf xinyP xP xyinyf xnxyx yxyxa bR xf xP x插值問(wèn)題的數(shù)學(xué)提法：已知函數(shù)在個(gè)點(diǎn)上的函數(shù)值求一個(gè)多

2、項(xiàng)式，使其滿足即要求該多項(xiàng)式的函數(shù)曲線要經(jīng)過(guò)上已知的個(gè)點(diǎn)同時(shí)在其他上要估計(jì)誤差插值問(wèn)題n 1 ,0011nnxyx yxy( )( )( )Rxf xP x n 1 個(gè)點(diǎn)個(gè)點(diǎn)同時(shí)在其它同時(shí)在其它上要估計(jì)誤差上要估計(jì)誤差。當(dāng)當(dāng)時(shí)時(shí),求一次多項(xiàng)式求一次多項(xiàng)式一次插值 100111( ),nP xxyx y當(dāng)時(shí)，求一次多項(xiàng)式要求通過(guò)兩點(diǎn)二次插值 20011222( ),nP xxyx yxy當(dāng)時(shí)，求二次多項(xiàng)式要求通過(guò)三點(diǎn)拉格朗日插值公式n線性插值（一次插值） 1111111111 ( ),(),()( )(),(),kkkkkkkkkkkkkkf xxxyf xyf xyP xyP xyP xxyx

3、y已知函數(shù)在區(qū)間的端點(diǎn)上的函數(shù)值，求一個(gè)一次函數(shù)使得。其幾何意義是已知平面上兩點(diǎn)，求一條直線過(guò)該已知兩點(diǎn)。線性插值n插值函數(shù)和插值基函數(shù)1111111111111( )()( )( ),( )kkkkkkkkkkkkkkkkkkkkkkkkyyPxyxxxxxxxxyyPxyyxxxxxxxxlxlxxxxx由直線的點(diǎn)斜式公式可知：，把此式按照和寫(xiě)成兩項(xiàng):，記，稱它們?yōu)橐淮尾逯祷瘮?shù)。線性插值n基函數(shù)的特點(diǎn)：( )klxkx1kx( )klx1( )kxl10011( )klxkx1kx11111( )( )( ),k kkkkkkkP xy lxylxyyxx拉格朗日型插從而，此形式稱之為。

4、其中，插值基函數(shù)與、無(wú)關(guān)，而由插值結(jié)點(diǎn) 、值多項(xiàng)式?jīng)Q定例子0101011lg101 , lg201.3010lg12( )lg( )lg(10)1(20)1.3010102011.3010201101( )(20)( )(10)10201020 1010f xxf xxffxxyyxxlxxl xx 例：已知，利用插值一次多項(xiàng)式求的近似值。解：，設(shè)，則插值基本多項(xiàng)式為：，例子10 01 1111.3010( )( )( )(20)(10)101011.3010(12)(1220)(12 10)1.06021010lg12lg10 lg20 lg121.0792).P xy lxy l xxxP

5、 于是，拉格朗日型一次插值多項(xiàng)式為：故即由和兩個(gè)值的線性插值得到，且具有兩位有效數(shù)字（精確解二次插值多項(xiàng)式 111111221122111111 ( ),() , ()()( )()()(),kkkkkkkkkkkkkkkkkkkkkyf xxxxyf xyf xyf xP xP xyP xyP xyxyxyxy已知函數(shù)在點(diǎn)上的函數(shù)值，。求一個(gè)次數(shù)不超過(guò)二次的多項(xiàng)式，使其滿足，。其幾何意義為：已知平面上的三個(gè)點(diǎn)：，求一個(gè)二次拋物線，使得該拋物線經(jīng)過(guò)這三點(diǎn)。二次插值基本多項(xiàng)式11 ,kkkxxx有三個(gè)插值結(jié)點(diǎn)，構(gòu)造三個(gè)插值基本多項(xiàng)式，要求滿足：（1）基本多項(xiàng)式為二次多項(xiàng)式；（2）它們的函數(shù)值滿足

6、下表：1kxkx1kxkx1kx 1( )klx( )klx1( )klx1000100011kx1( )klx( )klx1( )klx二次插值基本多項(xiàng)式1kxkx1kx 1( )klx( )klx1( )klx111111111111111111()0,()0( )()()( )()()()1()()1()()1( )()()()kkkkkkkkkkkkkkkkkkkkkkkkklxlxlxxxxxlxa xxxxlxa xxxxxxxxalxxxxxxx因?yàn)?，故有因子，而其已?jīng)是一個(gè)二次多項(xiàng)式，僅相差一個(gè)常數(shù)倍，可設(shè)，又因?yàn)椋?，得：，從?1111111111()()()()()( )

7、( )()()()()kkkkkkkkkkkkkkkkxxxxxxxxxxlxlxxxxxxxxx，拉格朗日型二次插值多項(xiàng)式拉格朗日型二次插值多項(xiàng)式 2111122 ( )( )( )( )( )( ) , 1, ,1kkk kkkiiP xylxy lxylxP xP xyikk k由前述，拉格朗日型二次插值多項(xiàng)式：，是三個(gè)二次插值多項(xiàng)式的線性組合，因?yàn)樗谴螖?shù)不超過(guò)二次的多項(xiàng)式，且滿足：例子2例 ：已知ixlgiiyxixlgiiyx10152011.17611.3010lg12利用此三值的二次插值多項(xiàng)式求的近似值012012101520(15)(20)1( )1520(10 15)(10

8、20)50(10)(20)1( )1020(15 10)(1520)25(10)(15)1( )1015(20 10)(20 15)50 xxxxxlxxxxxl xxxxxlxxx 解：設(shè)，則例2（續(xù)）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故所以：利用三個(gè)點(diǎn)進(jìn)行拋物線插值得到的的值，與精確值相比，具有 位有效數(shù)字。

9、拉格朗日型拉格朗日型n次插值多項(xiàng)式次插值多項(xiàng)式 0101 ( ),( )( )0,1,1nnnniiyf xx xxyyyP xP xyinnn已知函數(shù)在n+1個(gè)不同的點(diǎn)上的函數(shù)值分別為，求一個(gè)次數(shù)不超過(guò)n次的多項(xiàng)式，使其滿足，即個(gè)不同的點(diǎn)可以唯一決定一個(gè) 次多項(xiàng)式。插值基函數(shù)01 11( ), ( ), ( )( )1( )2( )1,()0,niiiiiknnnlx l xlxl xl xnl xnl xki過(guò)個(gè)不同的點(diǎn)分別決定個(gè) 次插值函數(shù)。每個(gè)插值基本多項(xiàng)式滿足：（）是 次多項(xiàng)式；（ ）而在其它 個(gè)。插值基函數(shù)01101101101 ()0,( )()()()()( )()()()()

10、( )1()()()()( )()()(ikiiiniiiniiiiniiiiil xkil xxxxxxxxxnl xa xxxxxxxxl xaxxxxxxxxl xxxxxx由于，故有因子：，因其已經(jīng)是次多項(xiàng)式，故而僅相差一個(gè)常數(shù)因子。令：由，可以定出 ，進(jìn)而得到：1)()iinxxxn次拉格朗日型插值多項(xiàng)式Pn(x)01010 01 10( )1( ), ( ), ( ),( )( )( )( )( )( )( )0,1,nnnnnn nk kknniiP xnnlx l xlxyyyP xy lxy l xy lxy lxP xnP xyin是個(gè) 次插值基本多項(xiàng)式的線性組合，相應(yīng)的組

11、合系數(shù)是。即從而是一個(gè)次數(shù)不超過(guò) 的多項(xiàng)式，且滿足，例子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：求過(guò)點(diǎn)的拉格朗日型插值多項(xiàng)式。解：用4次插值多項(xiàng)式對(duì)5個(gè)點(diǎn)插值：，；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 lxy l xy lxy l xy lxxxxxxxxxxxxxxxxx 所以拉格朗日插值多項(xiàng)式的截?cái)嗾`差 ,( )( ),( )( )( )( )( )( )( )0nnnniniinia bP xf xR xR xf xP xxxR xf xP x我們?cè)谏嫌枚囗?xiàng)式來(lái)近似替代函數(shù)其截?cái)嗾`差記作，。當(dāng) 在插值結(jié)點(diǎn) 上時(shí)，估計(jì)截?cái)嗾`差。拉格朗日插值多項(xiàng)式的截?cái)嗾`差( )(1)01(1)011( )( ) , ( )( , )( ) , 1( )( )( )(1)!( , ),( )()()()nnnnnnnnny

14、f xnyfxa byfxa baxxxbP xnxa bR xfxna bxxxxxxx 定理 ：設(shè)函數(shù)的 階導(dǎo)數(shù)在上連續(xù)，在上存在；插值結(jié)點(diǎn)為，是次拉格朗日插值多項(xiàng)式；則對(duì)任意有：其中例子12212lg121lg10lg20lg12P 121.0602,lg121.0792e1.0792 1.06020.0190( )lg1( ),10,20ln101|( )|0.043ln10 101|( )(12 10)(1220)| 8 0.0430.3442f xxfxxxff 分析例，例 中計(jì)算的截?cái)嗾`差在例中，用和計(jì)算，估計(jì)誤差：當(dāng)時(shí)例子243242lg10 lg15lg20lg12.P 12

15、1.0766,e1.0792 1.07660.00262( )8.686 10ln101|(12)| |( )(12 10)(12 15)(1220)|3!18.686 102 3 80.006956fxxRf 在例 中，用，和計(jì)算估計(jì)誤差：故牛頓插值均差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設(shè)函數(shù)在個(gè)相異的點(diǎn)上的函數(shù)值分別為，或者記為一階均差：稱為關(guān)于結(jié)點(diǎn)的一階均差

16、，記為。二階均差：一階均差，的均差稱為關(guān)于結(jié)點(diǎn)的二階均差，0120111201001,3.1, ,( )1,nnnnnf x x xnnnf x xxf x xxf x xxxxf xnx xx記為。階均差：遞歸地用階均差來(lái)定義 階均差，稱為關(guān)于個(gè)結(jié)點(diǎn)的均差。均差的性質(zhì)010100110101010101100112012020102011001.11,()()()()()(), ,11()nnknkkkkkkknnnyyyyf x xxxxxxxxxxf xf xyyf x xxxxxxxf x xf x xf x x xxxyyxxxxxxx性質(zhì) ： 階均差可以表示成個(gè)函數(shù)值的線性組合，即

17、例：122122101201020210122021012010210122021()11()()()()()()()()()()()yyxxxxxyyyxxxxxxxxxxxxxxyyyxxxxxxxxxxxx均差的性質(zhì)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：均差與結(jié)點(diǎn)的順序無(wú)關(guān)，即：若是 的 次多項(xiàng)式，則一階均差是 的次多項(xiàng)式，二階均差是 的次多項(xiàng)式；一般地，函數(shù)性的 階均差是質(zhì)（對(duì)稱性）的次多項(xiàng)式，而

18、時(shí)性，質(zhì)階均差為零。利用均差表計(jì)算均差 n利用均差的遞推定義利用均差的遞推定義,可以用遞推來(lái)計(jì)算均差?？梢杂眠f推來(lái)計(jì)算均差。n如下表：如下表：n如要計(jì)算四階均差如要計(jì)算四階均差,應(yīng)再增加一個(gè)節(jié)點(diǎn)應(yīng)再增加一個(gè)節(jié)點(diǎ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計(jì)算三階均差f1,3,4,7例子解：列表計(jì)

19、算ixix ( )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牛頓插值公式的構(gòu)造因?yàn)椋允揭?，有?式因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最后一項(xiàng)中，均差部分含有 是余項(xiàng)部分，記作。前面項(xiàng)中，均差部分不含有 ，因而前

21、面項(xiàng)是關(guān)于 的 次多項(xiàng)式，記作，這就是牛頓公式。于是上式成為：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例如：當(dāng)時(shí)，其中，這就是牛頓一次插值多項(xiàng)式，也就是點(diǎn)斜式直線方程。當(dāng)時(shí)，0122001001201)()()( )(),(),()()xxxxxxNxf xf x xxxf x x xxxxx這就是牛頓二次插值多項(xiàng)式。20001210

22、101010122020010112202102011222()()()()()()()()()()()()()()()()()1()()()( )Nxf xf xf xNxf xxxf xxxf xf xNxf xxxxxf xf xf xf xxxxxxxxxxxf xNx顯然，即滿足二次插值條件。例2例2：已知ixix ( )if x1347021512( )if x求滿足以上插值條件的牛頓型插值多項(xiàng)式。例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、，我們已經(jīng)計(jì)算出，；則牛頓三次插值多項(xiàng)式為例3ix ( )if x3( )(0.596)f xf例 ：已知在六個(gè)點(diǎn)的函數(shù)值如下表，運(yùn)用牛頓型插值多項(xiàng)式求的近似值。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 欲求，只需在之后再加一項(xiàng)：故拉格朗日插值與牛頓插值的比較(1)01( )( )()()(), 0,1,( )( )( ) ,( )(

26、 )(1)!1nnnknkknnnnnnP xNxnP xNxf xknP xNxff x x xxxxnnn（1）和均是 次多項(xiàng)式，且均滿足插值條件：由多項(xiàng)式的唯一性，因而，兩個(gè)公式的余項(xiàng)是相等的，即：（2）當(dāng)插值多項(xiàng)式從次增加到 次時(shí)，拉格朗日型插值必須重新計(jì)算所有的基本插值多項(xiàng)式；而對(duì)于牛頓插值，只需要表格再計(jì)算一個(gè)n階均差，然后加上一項(xiàng)即可。等距牛頓插值公式n插值節(jié)點(diǎn)為等距節(jié)點(diǎn)：0,0,1, ,kxxkh kn如下圖：hhhhx1x0 x2x3Xn-1Xn( )().kkkhyf xxyf x其中， 稱為步長(zhǎng)，函數(shù)在 的函數(shù)值為差分的概念（向前差分）12121111112()()1,k

27、kkkkkkkkkmmmkkkkkkyyyyyyyyyymmyyyxxx ：；一般地， 階差分用階一階差分二階差差分來(lái)定義：以上定義的是：從 起向前的函數(shù)值的差， 稱為分前差向前差分算子。差分的概念（向后差分）121112111()()kkkkkkkkkkmmmkkkyyyyyyyyyymyyym 表示一階向后差分：二階向后差分：，階向后差分：分別稱為一階，二階， ， 階向向后差分算子后差分。差分的性質(zhì)（性質(zhì)1）1212111012121111( 1)( 1)( 1)( 1)1 2 ()()nkk nnk nnk niinnnnnk n inknkniink n iikkkkkkkkkknny

28、yC yC yC yCyC yC ynyyynyyyyyyy 性質(zhì) ： 階差分是個(gè)函數(shù)值的線性組合。驗(yàn)證：時(shí)，；時(shí)，21(2)kkkyyy差分的性質(zhì)（性質(zhì)1續(xù)）32213212132131233(2)(2)33;33kkkkkkkkkkkkkkkkkknyyyyyyyyyyyyyyyyyy 時(shí)，一般地，可用數(shù)學(xué)歸納法證明此公式。對(duì)于后差也有類似的公式，例如：差分的性質(zhì)（性質(zhì)2）112211121112221221,!,2 ,2 ,1,111122mkkk mkmkkkkkkkkkkkkkkkkkkkkkkkkkf xxxym hxxh xxh xxhyyf xxyxxhf xxf xxf xxxxxyyyh hhh性質(zhì) ：在等距插值的情況下，差分和均差有如下關(guān)系：驗(yàn)證：因?yàn)樗?差分的性質(zhì)（性質(zhì)2續(xù)）1233212132231223,11113226kkkkkkkkkkkkkkkf xxxxf xxxf xxxxxyyyhhhh等距節(jié)點(diǎn)的牛頓插值公式000(),0,1,0.kkknxxkhyf xknxx