計算方法第三章rr

1、第三章第三章 插值法插值法第一節(jié)第一節(jié) 插值多項式的基本概念插值多項式的基本概念假設(shè)已經(jīng)獲得若干點上的函數(shù)值假設(shè)已經(jīng)獲得若干點上的函數(shù)值即提供了一張數(shù)據(jù)表即提供了一張數(shù)據(jù)表 如何如何利用這張表求某個給定點上的函數(shù)值利用這張表求某個給定點上的函數(shù)值呢呢?插值方插值方法所要研究的就是這個課題。法所要研究的就是這個課題。 ,0,1, ,iif xy inx0 x1x2xnx yf x0y1y2yny 通常用多項式來作為近似函數(shù)，稱為通常用多項式來作為近似函數(shù)，稱為插值多項式插值多項式。2012( )nnnP xaa xa xa x數(shù)據(jù)表中的函數(shù)值為已知的節(jié)點稱為數(shù)據(jù)表中的函數(shù)值為已知的節(jié)點稱為插值節(jié)

2、點插值節(jié)點，插值節(jié)點上所，插值節(jié)點上所給的函數(shù)值稱為給的函數(shù)值稱為樣本值樣本值。函數(shù)值待求的點稱為。函數(shù)值待求的點稱為插值點插值點。插值節(jié)。插值節(jié)點所界定的范圍稱為點所界定的范圍稱為插值區(qū)間插值區(qū)間。如果所給插值點位于插值區(qū)間。如果所給插值點位于插值區(qū)間之內(nèi)，這種插值過程稱為之內(nèi)，這種插值過程稱為內(nèi)插內(nèi)插，否則稱為，否則稱為外插外插。如果插值條件只是給出節(jié)點的函數(shù)值，稱為如果插值條件只是給出節(jié)點的函數(shù)值，稱為拉格朗日插值拉格朗日插值，如，如果既有函數(shù)值也有節(jié)點處函數(shù)的導數(shù)值，稱為果既有函數(shù)值也有節(jié)點處函數(shù)的導數(shù)值，稱為埃爾米特插值埃爾米特插值。因式定理：多項式因式定理：多項式P(x)具有具有r

3、 次因式次因式(x-a)r 的充要條件的充要條件是是P(a)=P (a)=P(a)(r-1)=0最一般的插值條件：最一般的插值條件：是是重根，重根，(1)(1)( ),( ),( )iirriiiiiixyxyxy定理：一旦插值條件給定，則插值多項式是唯一的。定理：一旦插值條件給定，則插值多項式是唯一的。irix011mrrrn設(shè)函數(shù)設(shè)函數(shù)y =f (x)在閉區(qū)間在閉區(qū)間a,b 上有上有n +1階導數(shù)，階導數(shù)，滿足前面的一般插值條件，且插值節(jié)點各不相同，滿足前面的一般插值條件，且插值節(jié)點各不相同，則插值截斷誤差為則插值截斷誤差為01(1)011( )( )( )( )( )(1)!( )()

4、()()mnnnnrrrnmR xf xP xfxnxxxxxxx 01011,mmrrrnx xxx在之間，與 有關(guān)證明思路：構(gòu)造輔助函數(shù)，用羅爾定理。證明思路：構(gòu)造輔助函數(shù)，用羅爾定理。33(4)2012( )( )( )1( )() ()()4!R xf xP xfxxxxxx300300311322(),(),( ),()P xy P xy P xy P xy2301223012( )( )( )() ()() ( )( )/() ()()g tf tP txxxxxxf tP txxxxxx值得注意的是在較大區(qū)間上進行插值時，誤差可能會值得注意的是在較大區(qū)間上進行插值時，誤差可能會很

5、大！另外，一般情況下，外推不如內(nèi)插好！很大！另外，一般情況下，外推不如內(nèi)插好！第二節(jié)第二節(jié)Lagrange插值公式插值公式插值條件是插值條件是0011(,),( ,),(,)nnxyx yxyLagrange插值實質(zhì)上是求通過上面插值實質(zhì)上是求通過上面n+1個點的個點的n次多項式。次多項式。一次插值：一次插值：問題為求一次多項式，即一次函數(shù)，過以下問題為求一次多項式，即一次函數(shù)，過以下兩點：兩點：容易求出，該函數(shù)為：容易求出，該函數(shù)為：0011(,), ( ,)xyx y01010110 xxxxyyyxxxx二次插值：二次插值：問題為求二次多項式，即二次函數(shù)，過以下三點：問題為求二次多項式，

6、即二次函數(shù)，過以下三點：容易求出，該函數(shù)為：容易求出，該函數(shù)為：001122(,), ( ,),(,)xyx yxy120010202110120122021()()()()()()()()()()()()xxxxyyxxxxxxxxyxxxxxxxxyxxxx一般插值問題：求過一般插值問題：求過n+1n+1個點個點的不超過的不超過n n次多項式次多項式 。 稱為稱為LagrangeLagrange插值基函數(shù)，滿足：插值基函數(shù)，滿足：0011(,), ( ,),(,)nnxyx yxy( )nL x0( )( )nniiiL xy l x( )il x1,(),0,ijijijijl xij0

7、11011()()()()( )()()()()iiniiiiiiinxxxxxxxxl xxxxxxxxx問題問題: :過過n+1n+1個點的個點的LagrangeLagrange插值多項插值多項式是否唯一？式是否唯一？滿足n+1個插值條件的n次多項式是唯一的；滿足n+1個插值條件的多項式不是唯一的；插值公式的誤差為：插值公式的誤差為：(1)01( )( )( )()()()()(1)!nnnxnR xf xL xfxxxxxxn(1)1 , 101max( )( )()()()(1)!nnxa bnnnMfxMR xxxxxxxn計算程序計算程序框圖框圖 始 終 輸入數(shù)據(jù)x 及 ,0,1,

8、iix yin 0,0yi 計算權(quán)系數(shù)i存單元 中 ?iniyyy = 1ii Lagrange 公式的計算流程 第三節(jié)第三節(jié) 逐次線性插值逐次線性插值函數(shù)函數(shù) y =f(x)在節(jié)點在節(jié)點上的插值多項上的插值多項式記為式記為，則有，則有,ijkx xx, ,( )i jkNx, , , , , , , , , ,( )( )( )( )( )()i jk p qi jk pi jk qi jk ppqpNxL xNxNxNxxxxxAitken（埃特肯）算法埃特肯）算法Neville（列維爾）算法列維爾）算法0,1, ,0,1,0,1,1,0,1,( )( )( )( )( )()k pkkp

9、kkpkNxL xNxNxNxxxxx,1,1,11,2,1,1( )( )( )( )( )()i iki ikiiki ikikiNxL xNxNxNxxxxxAitken（埃特肯）算法埃特肯）算法0 x0N1x1N0,1( )Nx2x2N0,2( )Nx0,1,2( )Nx3x3N0,3( )Nx0,1,3( )Nx0,1,2,3( )NxNeville（列維爾）算法列維爾）算法0 x0N1x1N0,1( )Nx2x2N1,2( )Nx0,1,2( )Nx3x3N2,3( )Nx1,2,3( )Nx0,1,2,3( )Nx例子：求方程例子：求方程在在(2,3)內(nèi)的根內(nèi)的根思路，用反函數(shù)思

10、路，用反函數(shù)3250 xxyx163-122.058823-0.392.058232.0965892.0956590.0121.51E-52.0956592.0945532.0945292.0945542.094553第四節(jié)第四節(jié) 牛頓插值牛頓插值001122(,),( ,),(,),(,)nnxfxfxfxf010201011( )()()()()()()nnnNxcc xxc xxxxxxxxxxc差商差商設(shè)函數(shù)設(shè)函數(shù) f (x)，定義函數(shù)在兩個不同點的一階差商為定義函數(shù)在兩個不同點的一階差商為三個不同點的二階差商為：三個不同點的二階差商為：在點在點處處K+1 階差商為：階差商為：( )(

11、)( ,),(,)ijijijijf xf xf x xxxijxx( ,)(,)( ,)ijjkijkikf x xf xxf x xxxx011,kkx xxx011101101(,)( ,)(,)kkkkkkf x xxf xxxf x xxxxx給定給定 n +1個點的函數(shù)值，則牛頓插值公式為：個點的函數(shù)值，則牛頓插值公式為：00100120101011101011,( ),0,1,2,( )()(,)()(,)()()(,)()()()( )(,)()()()iiinnnnnnnxff xinNxf xf x xxxf x x xxxxxf x xxxxxxxxNxNf x xxxx

12、xxxx差商的計算簡表：差商的計算簡表：0011012212012332312301234434234123401234()( ) (,)() ( ,) (,)() (,) ( ,) (,)() (,) (,) ( ,) (,)x f xx f xf x xx f xf x xf x x xx f xf x xf x x xf x x x xx f xf x xf x x xf x x x xf x x x x x例子：例子：用用0、30、45、60、90五個點作出五個點作出sinx牛頓插值多項式。牛頓插值多項式。做差商表做差商表00300.50.016667450.70710.013807-

13、0.000063556600.8660.010595-0.00010707-0.00000079010.0044658-0.0001362-0.00000049牛頓插值的截斷誤差：牛頓插值的截斷誤差：101101( )(,)()()()nnnnNxNf x xxxxxxxx111101110111()()()(,)()()()nnnnnnnnnnf xNxNxf x xxxxxxxx101101( )( )( )(,)()()()nnnnf xNxNxf x xxxxxxxx01101( )( )( )(,)()()()nnnnR xf xNxf x xxxxxxxx例子：例子：用用0、30、

14、45、60、90五個點作出五個點作出sinx牛頓插值多項式。牛頓插值多項式。做差商表做差商表009010.011111800-0.01111 -1.235e-4270-1-0.0111104.572e-736000.011111.235e-44.572e-70差商的計算公式：差商的計算公式：差商的對稱性：差商的對稱性：差商的線性差商的線性011000()(,)()( )() ,()()kjkkjkjkkkikjjiiiijf xf x xxxxxxxxxx( )()()( )( ,)ijjiijijjif xf xf xf xf x xxxxx( ,)(,)( ,)ijkjikikjf x x

15、xf xx xf x xx010101( )( )( )(,)(,)(,)nnnf xu xv xf x xxu x xxv x xx由于由于n次插值多項式是唯一的，所以牛頓插值公式與次插值多項式是唯一的，所以牛頓插值公式與LagrangeLagrange插值多項式一樣，這意味著余項也一樣，插值多項式一樣，這意味著余項也一樣，LagrangeLagrange余項為：余項為：所以牛頓余項也一樣，所以牛頓余項也一樣，(1)01()( )()()()(1)!nxnnfR xxxxxxxn01101(1)01( )01()()()() ( ,)()()()()(1)!()(,)!nnnnxnkxkxx

16、xxxxxxf x x xxfxxxxxxnff x xxk差商與導數(shù)的關(guān)系差商與導數(shù)的關(guān)系重節(jié)點差商重節(jié)點差商推論：當推論：當n個節(jié)點全為同一個點，牛頓插值變成個節(jié)點全為同一個點，牛頓插值變成泰勒多項式。泰勒多項式。( )011(,)( )!nnf x xxfn( )00001(,)()!nf x xxfxn差商的導數(shù)差商的導數(shù)n次多項式的的次多項式的的1階差商是階差商是n-1次多項式。次多項式。(1)*011011()(, )(, , )(1)!nnndff x xxxf x xxx xdxn推論：設(shè)推論：設(shè)p(x)是是n次多項式，次多項式，kn時時k階差商是階差商是n-k次次多項式，多項

17、式，kn時時k階差商為零。階差商為零。00000000( )( )()()0( )() ( )( )()() ( )( )()( ,)( )g xp xp xg xg xxx q xp xp xxx q xp xp xp x xq xxx差分差分設(shè)函數(shù)設(shè)函數(shù) ，定義，定義 為該函為該函數(shù)在數(shù)在 i 點的點的一階差分一階差分，記為，記為類似地，定義類似地，定義二階差分為二階差分為：K 階差分為階差分為：此差分稱為此差分稱為向前差分向前差分。( )iif xxf在的函數(shù)值為1iiff, (0,1,2, )ifin21, (0,1,2,)iiifffi 111, (0,1,2,)kkkiiifffi

18、 類似地，類似地，向后差分向后差分定義為：定義為：中心差分中心差分定義為：定義為：1, (0,1,2,)iiifffin111, (0,1,2,)kkkiiifffi 1/21, (0,1,2,)iiifffin1/21/2, (0,1,2,)iiifffin111/21, (0,1,2,)kkkiiifffi差商與差分的關(guān)系：等距節(jié)點時差商與差分的關(guān)系：等距節(jié)點時0/201()()()(,)!nnnnnnnnnf xf xf xf x xxn hn hn h0ixxih第五節(jié)第五節(jié) 帶導數(shù)的插值帶導數(shù)的插值問題的提出：如果在已知節(jié)點處不僅知道函數(shù)值，問題的提出：如果在已知節(jié)點處不僅知道函數(shù)值

19、，同時還知道導數(shù)同時還知道導數(shù)值，這樣，插值多項式就要求在值，這樣，插值多項式就要求在已知節(jié)點處與已知節(jié)點處與函數(shù)值和導數(shù)值都相等函數(shù)值和導數(shù)值都相等。這就是所。這就是所謂謂埃爾米特插值埃爾米特插值，記為，記為H(x)1、牛頓插值、牛頓插值如果已知如果已知某個點某個點i 的的，則，則插值節(jié)點應(yīng)視為插值節(jié)點應(yīng)視為個相同節(jié)點個相同節(jié)點，并注意到，并注意到k+1重節(jié)點的差商重節(jié)點的差商(1),iriiiiy y yyirix( )1( )( ,)!kiiiiikfxf x x xxk 例子：例子：已知關(guān)于函數(shù)已知關(guān)于函數(shù)y =f(x)的函數(shù)值、導數(shù)值的函數(shù)值、導數(shù)值0011112211,00,4,0

20、,61,2,5xyxyyyxyy -100-4-40-4040-403-11-222-101-253121(0,0)(0)0(0,0,0)(0)/2!3(1,1)(1)5fyfyfy已知函數(shù)在已知函數(shù)在n個不同的節(jié)點處的函數(shù)值和導數(shù)值：個不同的節(jié)點處的函數(shù)值和導數(shù)值：求次數(shù)不超過求次數(shù)不超過2n-1次的多項式次的多項式設(shè)想該多項式具有形式設(shè)想該多項式具有形式：,(1,2, )iiixyyin2121( ),( ),(1,2, )niiniiHxyHxyin2111( )( )( )nnnjjjjjjHxy h xy h x( ),( )0,1,2,( )0 ,( ),1,2,jiijjijij

21、iijh xh xj inh xhxj in由條件可得：由條件可得：此外，由此外，由 得：得：2( )()( )jjh xAxB Wx111111()()()()( )()()()()jjnjjjjjjjnxxxxxxxxW xxxxxxxxx()1 ,()0jjjjh xh x12()2()()012()jjjjjjjjjAxBAWxAAxB WxBx Wx 2( )12()()( )jjjjjh xWxxxWx同理：同理：由由 ，可得：，可得：最后，得到埃爾米特插值公式：最后，得到埃爾米特插值公式：2( )()( )jjjh xC xx Wx()1jjh x22()11( )()( )jj

22、jjjCWxCh xxx Wx21112211( )( )( )1 2()()( )()( )nnnjjjjjjnnjjjjjjjjjjHxy h xy h xWxxxWx yxx Wx y特別，當特別，當 n=2 時，三階埃爾米特多項式為：時，三階埃爾米特多項式為：311322311322(),(),(),()HxyHxyHxyHxy21231121222122121222111221221( )(1 2)()(1 2)()()()()()xxxxHxyxxxxxxxxyxxxxxxxxxxyxxyxxxx埃爾米特插值公式唯一。埃爾米特插值公式唯一。誤差估計，設(shè)被插值函數(shù)在插值區(qū)間上誤差估計

23、，設(shè)被插值函數(shù)在插值區(qū)間上2n次連續(xù)可導，次連續(xù)可導，則在則在n個節(jié)點上的個節(jié)點上的2n-1次插值多項式的余項為：次插值多項式的余項為：特別，對于特別，對于2個節(jié)點個節(jié)點3次插值，余項為：次插值，余項為：2121(2 )212( )( )( )()()()()(2 )!nnnxnRxf xHxfxxxxxxn(4)223312()( )( )( )() ()4!xfR xf xHxxxxx例子：例子：3333(0)0,( )0,(0)1 ,( )1HHHH sin x223( )()()()xxHxxx如用距離較小的兩個點插值，效果會好得多如用距離較小的兩個點插值，效果會好得多3333(0)0

24、,(/2)1,(0)1 ,(/2)0HHHH223/2/2( )(12)()()/2/2/2xxxHxx第六節(jié)第六節(jié) 樣條函數(shù)樣條函數(shù)由于被插值函數(shù)高階導數(shù)未知，因此，如果高階導數(shù)隨階數(shù)由于被插值函數(shù)高階導數(shù)未知，因此，如果高階導數(shù)隨階數(shù)增長出現(xiàn)無限增長，則由誤差公式可知，高階插值公式就不增長出現(xiàn)無限增長，則由誤差公式可知，高階插值公式就不一定無限接近被插值函數(shù)。這稱為一定無限接近被插值函數(shù)。這稱為龍格現(xiàn)象龍格現(xiàn)象。所以，在進行多項式插值時，不宜進行高次多項式插值。所以，在進行多項式插值時，不宜進行高次多項式插值。一個解決的途徑是一個解決的途徑是分段低次插值分段低次插值。樣條函數(shù)插值：給定區(qū)間

25、一個樣條函數(shù)插值：給定區(qū)間一個劃分劃分如函數(shù)如函數(shù) S(x)滿足下面條件：滿足下面條件：（1）在每個小區(qū)間）在每個小區(qū)間上為上為m次多項式；次多項式；（2）S(x)及及m1階導數(shù)在整個區(qū)間上連續(xù)。階導數(shù)在整個區(qū)間上連續(xù)。則稱則稱S(x)是關(guān)于該劃分的是關(guān)于該劃分的m次次樣條函數(shù)樣條函數(shù)，劃分點稱，劃分點稱為節(jié)點，為節(jié)點，m3時，就是最常用的時，就是最常用的3次樣條函數(shù)。次樣條函數(shù)。01 , ,:Na baxxxb1,(1,2,)jjxxjN3次樣條函數(shù)的基本思想：次樣條函數(shù)的基本思想：將樣條函數(shù)在每一個子區(qū)間端點的二階導數(shù)值當作參將樣條函數(shù)在每一個子區(qū)間端點的二階導數(shù)值當作參數(shù)，則用這兩個二階

26、導數(shù)值可以將樣條函數(shù)表示出數(shù)，則用這兩個二階導數(shù)值可以將樣條函數(shù)表示出來，再利用銜接條件，即每一段樣條函數(shù)在相鄰兩來，再利用銜接條件，即每一段樣條函數(shù)在相鄰兩個子區(qū)間端點處的二階導數(shù)相等，建立求解二階導個子區(qū)間端點處的二階導數(shù)相等，建立求解二階導數(shù)的方程組。數(shù)的方程組。設(shè)設(shè)S(x)在每個小區(qū)間在每個小區(qū)間端點的二階導端點的二階導數(shù)為：數(shù)為：則：則：記記，將上式積分兩次，并利用端點函數(shù)值已知，將上式積分兩次，并利用端點函數(shù)值已知，有：有：1,(1,2,)jjxxjN11(),()jjjjSxMSxM1111( )jjjjjjjjxxxxSxMMxxxx3311221111()()( )66()(

27、)66,1,2,jjjjjjjjjjjjjjjjjjxxxxS xMMhhMhxxM hxxyyhhxxxjN1jjjhxx我們注意到，在相鄰的兩個子區(qū)間我們注意到，在相鄰的兩個子區(qū)間 和和 的共同端點處，樣條函數(shù)一階導數(shù)相等，的共同端點處，樣條函數(shù)一階導數(shù)相等，經(jīng)過化簡，最后得到：經(jīng)過化簡，最后得到：11jjjxxx1,jjxx1,jjxx111111112,1,1,2,1()/()/6jjjjjjjjjjjjjjjjjjjjjMMMdhjNhhyyhyyhdhh 注意到上面的方程組總共只有注意到上面的方程組總共只有 N1個方程，而未知數(shù)卻共有個方程，而未知數(shù)卻共有 N 個，因此，要求解方程

28、，還需要兩個條件（即兩個方個，因此，要求解方程，還需要兩個條件（即兩個方程），通常有以下幾種方案程），通常有以下幾種方案:1、給出端點一階導數(shù)值、給出端點一階導數(shù)值 ，這相當于增加兩個方程；，這相當于增加兩個方程；2、給定端點二階導數(shù)值，得方程：、給定端點二階導數(shù)值，得方程：特別，令二階導數(shù)在端點為零，得特別，令二階導數(shù)在端點為零，得10010111162()62()NNNNNNNyyMMyhhyyMMyhh0,Nyy00,NNMyMy00 ,0NMM3、樣條件函數(shù)在第一后最后一個區(qū)間上為二次多項樣條件函數(shù)在第一后最后一個區(qū)間上為二次多項式，即樣條函數(shù)在第一和最后一個區(qū)間上的二階式，即樣條函數(shù)

29、在第一和最后一個區(qū)間上的二階導數(shù)為常數(shù)，得兩個方程：導數(shù)為常數(shù)，得兩個方程：總之，可以將方程組統(tǒng)一寫為：總之，可以將方程組統(tǒng)一寫為：011,NNMMMM0001111120202NNNNMdMdMd 4、周期性條件（這只有在給的初值滿足、周期性條件（這只有在給的初值滿足 時才能用），時才能用），此時，由周期性，此時，由周期性， ，就得到兩個，就得到兩個方程；第一個方程為方程；第一個方程為 ，第二個方程為，第二個方程為最后一個方程為：最后一個方程為：最后，方程組為：最后，方程組為：0Nyy1111,NNyyMM1011211121122NMMMdMMMd0NMM111122NNNNNNNNNNNMMMdMMMd111122221222NNNNNMdMdMd 小結(jié)小結(jié)插值法，其目的是利用節(jié)點上的值，構(gòu)造通過這些節(jié)點的多插值法，其目的是利用節(jié)點上的值，構(gòu)造通過這些節(jié)點的多項式，從原則上說，利用項式，從原則上說，利用n+1個節(jié)點的值，可以構(gòu)造個節(jié)點的值，可以構(gòu)造n次多次多項式，而且這種構(gòu)造是項式，而且這種構(gòu)造是唯一的唯一的！利用待定系數(shù)法，將節(jié)點