第一章 插值法(下)

1、第一章 插值方法李書杰合肥工業(yè)大學 計算機學院 Lagrange插值多項式的缺點插值多項式的缺點)(xljnjiiijixxxx0)()(nj,2 , 1 ,0我們知道我們知道,Lagrange,Lagrange插值多項式的插值基函數(shù)為插值多項式的插值基函數(shù)為理論分析中很方便，理論分析中很方便，但是但是當當插值節(jié)點增減插值節(jié)點增減時時全部插值全部插值基函數(shù)基函數(shù)就要隨之就要隨之變化變化，整個公式也將發(fā)生變化，這在，整個公式也將發(fā)生變化，這在實際計算中是很實際計算中是很不方便不方便的；的；Lagrange 插值雖然易算，但若要增加一個節(jié)點時，插值雖然易算，但若要增加一個節(jié)點時，全部基函數(shù)全部基函

2、數(shù) li(x) 都需重新算過。都需重新算過。提綱埃特金插值牛頓插值埃爾米特插值算法的承襲性在計算方法中有很重要的作用，這樣可以節(jié)省計算量。這里介紹一種具有這種性質的算法：埃特金算法 .一、對于給定的插值點 ，如果除順序排列的 個節(jié)點 外，再增加一個節(jié)點 進行 次插值，則插值結果依賴于所給定的次數(shù) 與節(jié)點 ，記為 。xk110,kxxx)(kixiix)(ikxfkk)(1ixfixx ,001000( )()( )1iiiiixxxxf xf xf xixxxx)()()(1010010111xfxxxxxfxxxxxf)()()(2020020221xfxxxxxfxxxxxf特別地)(2i

3、xfixxx,10)()()()()()()()()()(21202101210120020102122xfxxxxxxxxxfxxxxxxxxxfxxxxxxxxxf212211121221()( )()xxxxfxf xf xxxxx或（改變記號）線性插值一般地有kixfxxxxxfxxxxxfikkikkkikiik),()()(111111)()(0iixfxf約定：例5 利用下表左部所給數(shù)據(jù)求正弦積分在x=0.462的值。dtttxfxsin)(已知線性插值二次插值三次插值將一個高次插值過程歸結為線性插值的多次重復。埃特金插值表中的數(shù)據(jù)均可視為插值結果，而這些數(shù)據(jù)的一致程度即可判斷插

4、值結果的精度。埃特金插值公式是隱性的，即屬于遞推公式。簡單便于程序實現(xiàn)和充分利用計算機資源提綱 埃特金插值 牛頓插值 埃爾米特插值牛頓插值牛頓插值方法的引出牛頓插值方法的推導等距牛頓插值兩點直線公式(xk,yk)(xk+1,yk+1)11111111( )()( )(kkkkkkkkkkkkkkyyL xyxxxxxxxxL xyyxxxx點斜式）兩點式）考慮點斜式，兩點為(x0,y0)(x1,y1):1010010( )()yyP xyxxxx在此基礎上增加一個節(jié)點(x2,y2)，則過這三個點的插值多項式21( )( )( )P xP xc xC(x)應是一個二次多項式。21( )( )(

5、)P xP xc x2010021111()()()()P xP xyP xP xy所以有0101()()0 ,( )()()c xc xc xa xxxx所以C(x)應是一個二次多項式。根據(jù)插值條件根據(jù)插值條件：222()P xy可以求出：221221221202120()()()()()()()pxp xyp xaxxxxxxxx重新寫p2(x)：211021200011020210102010010110201020102122202121( )( )( )()()()()()()()()()()()()()()()()P xP xc xyyyP xyxxxxxxxxxxxxaa xxa

6、xxxxayyyaxxf xf xf xf xxxxxyP xaxxxxxx其中0010111,()(),()()()nxxxxxxxxxxxx010201011( )()()()()()()nnnN x c c x xc x x x xc x x x xx x Newton插值法的思想：插值法的思想：其基函數(shù)為其基函數(shù)為,0,1,kkcn1011( )( )()()()nnnnN xNxc xxxxxx其中待定系數(shù)為其中待定系數(shù)為且且余項校正法余項校正法0,1,2),(, ,)niiiNxf xinx其中 互異插值條件：插值條件：0001101012022021210100()()()()(

7、)()()()()()nnnnjnjcf xccxxf xccxxcxxxxf xccxxcxxf x101202021101001010001001()()0()1()()0)!niijijnnnnjinjxxxxxx xxxxxxxx xcxxx 0010110( )( )( )cf xf xf xcxx2010201021()()( )()f xf xf xf xxxxxxx1020202012010220212021( )()()()()()()()()()()()f xf xf xf xxxf xf xc xxxxcxxxxxxxx010201011( )()()()()()()nn

8、nN x c c x xc x x x xc x x x xx x 0,1,2,( )(, ,)niiiicNxxixfn 其中 互異，求牛頓插值牛頓插值方法的引出牛頓插值方法的推導等距牛頓插值1.()iif xf x()(),ijijijf xf xf xxxx100110( )(),f xf xf x xxx差商差商 定義：定義：-零階差商（兩個節(jié)點定義一階差商：函數(shù)值之差除以相應的節(jié)點之差或零階差商的差商）如： 02 ,f x x , , ,ijkjiikkjxxfff xxxxxxx012,f x x x（一階差商的差商：三個節(jié)點定義二階差商；從這三個節(jié)點中任取兩組兩個節(jié)點組成兩個一階

9、差商，則這兩組節(jié)點中必有一個共同節(jié)點，而另一個節(jié)點不同，則這兩個一階差商的差除以相應的不同節(jié)點之差） 如：- 二階差商-一階差商2020()()f xf xxx2010201021()()( )()f xf xf xf xxxxxxx2c020121 , ,f x xf x xxx1c k-1階差商的差商: k+1個節(jié)點定義 k 階差商從k+1 個節(jié)點中任取兩組k個節(jié)點構成兩個不同的k-1階差商，其中有 k-1個節(jié)點相同，而1個節(jié)點不同，這兩個k-1階差商的差除以相應的不同節(jié)點之差如：11 ,iii ki kf x xxx 階差商 k01,kf x xx201021 , ,kkkkkkf xx

10、xxxxxxf2112,ii kii ki ki ki ki kxxxxfxxxfx 10010012010110( )( ) , () , ,()() , ,()?nnnnjjN xf xf x xxxf x x xxxxxf x xxxxx01, ?kkcf x xx2.Newton 公式的導出公式的導出210010012010110( )( ) , () , ,()() , ,()nnnjjNxf xf x x x xf x x xx xx xf x xxx x110( )( )()nnnniiN xNxcxx1( )( )(,01niiinN xf xinNx ,()()nnnN xf

11、 x111100()()()()()()nnnnnnnnnnniniiiN xNxf xNxcxxxx設設則由則由及及20010011010()(),(),()()nnnnnjjnnniif xf xf x xxxf x xxxxcxx20010111011()(),()()nnnnjjnnniifxfxf xxf xxxxxxxxx20010121011111 , , , ,() , ,()()nnnnnjjnniif x xf x xf x x xxxf x xxxxxx20010120112112,()()nnnnjjnnniif xxf xxf xx xf xxxxxxxxx01201

12、11,nnnnnf x xxxf x xxxx01 , ,nf x xx10010012010110( )( ) , () , ,()() , ,()nnnnjjN xf xf x x x xf x x xx xx xf x xxxx x牛頓插值公式！nkkkxxxxff1100)(,)()()()()()(4433221100 xfxxfxxfxxfxxfxxfxkk四階差商三階差商二階差商一階差商差商的計算方法差商的計算方法( (表格法表格法):):,10 xxf,21xxf,32xxf,43xxf,210 xxxf,321xxxf,432xxxf,3210 xxxxf,4321xxxxf

13、,410 xxxf規(guī)定函數(shù)值為規(guī)定函數(shù)值為零階差商零階差商差商表差商表ix0 x1x2x3xif x0()f x1()f x2()f x3()f x1,iif x x 01,f xx12,f x x23,f xx12,iiif x xx 012,f xx x123,f x xx123 ,iiiif x xxx 0123,f xx xx00100121001110( )()() ,()() ,()()() ,nnnNxf xxxf x xxxxxf xx xxxxxxxf xx x 例：例： 已知已知x=1,4,9的平方根為的平方根為1,2,3，利用牛頓基本差商，利用牛頓基本差商 公式求公式求

14、的近似值。的近似值。ix149ix1231,iif x x 2 10 333334 1. 320 294. 12 ,iiif x xx 0 20 333330 0166791. 7解：解：從而得二階牛頓基本差商公式為從而得二階牛頓基本差商公式為210 3333310 0166714( ).().()()Nxxxx 272 69992( ).N 因此計算得因此計算得 的近似值為的近似值為7NewtonNewton插值公式余項插值公式余項,)()()(000 xxfxxxfxf ,)(,101100 xxxfxxxxfxxf ,.,)(,.,.,0010nnnnxxxfxxxxfxxxf 12 n

15、+1.)(,)(,)()(102100100 xxxxxxxfxxxxfxfxf).(,.,100 nnxxxxxxf)().(,.,100nnnxxxxxxxxxf Nn(x)Rn(x)ai = f x0, , xi NewtonNewton插值公式余項插值公式余項反復的把后一項帶入前一項：NewtonNewton插值公式及其余項插值公式及其余項差商具有如下性質差商具有如下性質: :且的線性組合表示可由函數(shù)值階差商的,)(,),(),(,)()1(10110kkkxfxfxfxxxxfkxf,110kkxxxxfkikiiiiiiixxxxxxxxxf0110)()()()( Warning

16、: my head is explodingWhat is the point of this formula?差商的值與差商的值與 xi 的順序無關！的順序無關！定理定理4 4練習練習74017018312 ,2 ,2 2 ,2 ,2 fxxxff已知 ，求及( )f x分析：本題是一個多項式，可利用差商的性質解：由差商與導數(shù)之間的關系(7)017( )7!2 ,2 ,2 177!ff！(8)018( )02 ,2 ,2 088!ff！牛頓插值牛頓插值方法的引出牛頓插值方法的推導等距牛頓插值上面我們討論了節(jié)點任意分布的插值公式，但實際應上面我們討論了節(jié)點任意分布的插值公式，但實際應用時經常會

17、遇到等距節(jié)點的情形，這時插值公式可以用時經常會遇到等距節(jié)點的情形，這時插值公式可以進一步簡化，計算也簡單多了，為了給出等距節(jié)點的進一步簡化，計算也簡單多了，為了給出等距節(jié)點的插值公式，我們先來看一個新概念；插值公式，我們先來看一個新概念；稱處的函數(shù)值為在等距節(jié)點設, 1 , 0,)(0nkfkhxxxfkkkkkfff1( )kf xx為在處的一階差分1, 1 ,0nkkkkfff12( )kf xx為在處的二階差分利用一階差分可以定義二階差分利用一階差分可以定義二階差分kmkmkmfff111( )kf xxm為在處的 階差分4433221100fxfxfxfxfxfxkk四階差分三階差分二

18、階差分一階差分0f1f2f3f02f12f22f03f13f04f差分表差分表差分與函數(shù)值之間的關系差分與函數(shù)值之間的關系010121232,yyyyyyyyy 201021021213212232432222yyyyyyyyyyyyyyyyyy 2222()abaabb 1()abab 322010321032212143213222325432333333yyyyyyyyyyyyyyyyyyyyy 3223333()abaa babb 433010432104331215432143323265432464464464yyyyyyyyyyyyyyyyyyyyyyyy 4322443464(

19、)a baa ba babb 歸納可知，歸納可知，k階差商可表示為階差商可表示為 01111kii ki kiikkkkkkyyyCCyCCy 在等距節(jié)點的前提下在等距節(jié)點的前提下, ,差商與差分有如下關系差商與差分有如下關系,1iixxfhfi,21iiixxxf212hffii222hfiiiiixxff112211,iiiiiixxxxfxxf,321iiiixxxxf312223hffii33! 3 hfi332121,iiiiiiiixxxxxfxxxf,1miiixxxf依此類推mimhmf!,10kxxxfkkhkf!0即是等距節(jié)點如果節(jié)點,10nxxxnabhnkkhxxk,

20、1 ,0,0,10kxxxfkkhkf!0由差商與差分的關系)(xNnnkkkxxxxff1100)(,Newton插值基本公式為如果假設thxx0Newton差分插值公式差分插值公式10)(kjjxx)(xk1000)(kjjhxthx10)(kjhjtkkhkf!0nkf10)(10kjhjt!0kfknkf10 )(10kjjt)(xNnnkkkxxxxff1100)(,)(0thxNn)(xRn)()!1()(1)1(xnfnn則插值公式化為其余項)(0thxRn)!1()()1(nfnnjnjth01)(化為)(0thxRn)!1()()1(nfnnjnjth01)(!0kfknkf

21、10 )(10kjjt)(0thxNn稱為Newton差分插值公式插值余項為NewtonNewton插值法的優(yōu)點是計算較簡單插值法的優(yōu)點是計算較簡單, ,尤其是增加節(jié)點時尤其是增加節(jié)點時, ,計算只要增加一項計算只要增加一項, ,這點是這點是LagrangeLagrange插值無法比的插值無法比的. .但是但是NewtonNewton插值仍然沒有改變插值仍然沒有改變LagrangeLagrange插值的插值曲線插值的插值曲線在節(jié)點處有尖點，不光滑，插值多項式在節(jié)點處不可導在節(jié)點處有尖點，不光滑，插值多項式在節(jié)點處不可導等缺點等缺點. .例子( )1, 1.5, 2, 2.5, 3(2.2).x

22、yf xexf設插值節(jié)點為相應的函數(shù)值如下表，求xiyiyi2 2yi3 3yi4 4yi12.718281.54.481691.7634127.389062.907371.143962.512.182494.793431.886060.74210320.085547.903053.109621.223560.48146例子（解）2.21220003232(2.2)9.025011,2.212.4 ,2.41(2.2)(1)8.872322!(2.2)(2.2)12.42.4 12.420.742100.166236(2.2)(2.2)0.166213(1)(2)03!kkfexxxhtNyt

23、 yt tyNNNNt tty 解：精確值此時故于是：求時，在后加一項：（） （）所以39.03855例子（解）434043234(2.2)(2.2)1(1)(2)(3)412.4 (2.4 1) (2.42) (2.43) 0.48146240.01618(2.2)(2.2)0.016189.022370.15269,0.01354,0.00264NNt tttyNNRRR 求時，在后再加一項：！所以給出函數(shù)表xx0 x1x2xnyy0y1y2yn( ),0,1,2,iif xy in 其中其中 求求1011( ),( )nnnnnP xaa xaxa xp xn滿足滿足 ( )( )(0,

24、1,2, ),niiiP xf xinx其中 互異插值方法小結插值方法小結由插值條件由插值條件: : , ,可得可得 ( )( ),0,1,niip xf xin 10000111110110110111( )( )( )nnnnnnnnnnnnnn nnaaaaaaaaxxxf xxxxf xxxxf xaaaa待待定定系系數(shù)數(shù)法法拉格朗日（拉格朗日（Lagrange）插值法插值法1 ()( ),(),0()iijjixnxji 0101( )( )( )( )()( )()nnnxxP xf xf xf xx設設用已知的函數(shù)值作為組合系數(shù)去待定相應的基函數(shù)用已知的函數(shù)值作為組合系數(shù)去待定相

25、應的基函數(shù)即即其中其中0( ),0njijijj ixxxi jnxx00( )( )nnjniiijjj ixxP xf xxx基函數(shù)方法基函數(shù)方法0010111,()(),()()()nxxxxxxxxxxxx010201011( )()()()()() ()nnnN x c c x xc x x x xc x x x xx x Newton插值法插值法其基函數(shù)為其基函數(shù)為,0,1,kkcn1011( )( )()()()nnnnN xNxc xxxxxx其中待定系數(shù)為其中待定系數(shù)為余余 項項 校校 正正 法法01,kkcf x xx提綱埃特金插值牛頓插值埃爾米特插值Hermite插值插值）。插值多項式（也稱切觸為種要求的插值多項式稱階導數(shù)值相等，滿足這高值相等，有的甚至要求而且還要求節(jié)點上導數(shù)等在插值節(jié)點上函數(shù)值相在實際應用中不僅要求Hermite, ,He