第2講插值法與曲線擬合ppt課件

1、簡(jiǎn)明數(shù)值計(jì)算方法簡(jiǎn)明數(shù)值計(jì)算方法漳州師范學(xué)院計(jì)算機(jī)科學(xué)與工程系漳州師范學(xué)院計(jì)算機(jī)科學(xué)與工程系主要內(nèi)容主要內(nèi)容n插值法插值法n拉格朗日插值拉格朗日插值n差商與差分差商與差分n牛頓插值公式牛頓插值公式n逐次線性插值法逐次線性插值法n三次樣條插值三次樣條插值 n曲線擬合曲線擬合n曲線擬合的最小二乘法曲線擬合的最小二乘法2.1 插值法插值法n在實(shí)踐問(wèn)題中，我們會(huì)遇到兩種情況n變量間存在函數(shù)關(guān)系，但只能給出一離散點(diǎn)列上的值n 例如 : 從實(shí)驗(yàn)中得到一個(gè)數(shù)據(jù)表,或是一組觀測(cè)數(shù)據(jù)n變量間的函數(shù)關(guān)系可以表示,但計(jì)算復(fù)雜,只能計(jì)算特殊點(diǎn)的函數(shù)值n 例如 : 求指數(shù)函數(shù)、對(duì)數(shù)函數(shù)、三角函數(shù)、反三角函數(shù)值等n為了研

2、討自變量與因變量間的變化關(guān)系，我們需求建立變量間的函數(shù)關(guān)系，從而可以計(jì)算原始數(shù)據(jù)以外需求處的值，這就是我們研討插值的目的。xy( )yf xba2.1 插值法插值法設(shè)函數(shù)設(shè)函數(shù) 在區(qū)間在區(qū)間 上有定義上有定義, ,知在點(diǎn)知在點(diǎn) 上的函上的函數(shù)值數(shù)值 , , , , 即即 。nkxfykk,.,2 , 1 , 0),( )yf x , a b01naxxxb0y1yny插值問(wèn)題插值問(wèn)題:求一個(gè)簡(jiǎn)單函數(shù)求一個(gè)簡(jiǎn)單函數(shù) 使得使得ankyxPkk,.,2 , 1 , 0,)( )P x插值條件插值條件插值函數(shù)插值函數(shù)插值節(jié)點(diǎn)插值節(jié)點(diǎn)假設(shè)是多假設(shè)是多項(xiàng)式項(xiàng)式,那么那么稱為插值稱為插值多項(xiàng)式多項(xiàng)式求插值函

3、求插值函數(shù)的方法數(shù)的方法稱為插法稱為插法)(xPy ),(kkyx0 x1xnxkx1nxa,b稱為稱為插值區(qū)間插值區(qū)間如何構(gòu)如何構(gòu)造造P(x)?2.1 插值法插值法設(shè)函數(shù)設(shè)函數(shù) 在區(qū)間在區(qū)間 上有定義上有定義, ,知在點(diǎn)知在點(diǎn) 上的函上的函數(shù)值數(shù)值 , , , , 即即 。nkxfykk,.,2 , 1 , 0),( )yf x , a b01naxxxb0y1yny( )P xnkyxPkk,.,2 , 1 , 0,)(能否存在多項(xiàng)式能否存在多項(xiàng)式 使得使得xyba),(00yx1x當(dāng)當(dāng)n=0時(shí)時(shí),只需一個(gè)插只需一個(gè)插值節(jié)點(diǎn)的情形值節(jié)點(diǎn)的情形當(dāng)當(dāng)n=1時(shí)時(shí), 有兩個(gè)插有兩個(gè)插值節(jié)點(diǎn)的情形值

4、節(jié)點(diǎn)的情形),(22yx0 x0y1y),(11yx2x2y當(dāng)當(dāng)n=2時(shí)時(shí), 有三個(gè)插有三個(gè)插值節(jié)點(diǎn)的情形值節(jié)點(diǎn)的情形*x插值多項(xiàng)式的存在獨(dú)一定理：在次數(shù)不超越插值多項(xiàng)式的存在獨(dú)一定理：在次數(shù)不超越 n n 的多項(xiàng)式集合的多項(xiàng)式集合 中，滿足中，滿足插值條件的插值多項(xiàng)式插值條件的插值多項(xiàng)式 是存在并且獨(dú)一的。是存在并且獨(dú)一的。nH( )nnL xH能否恣意給能否恣意給定定n+1個(gè)不個(gè)不同的插值同的插值 節(jié)節(jié)點(diǎn)都可以構(gòu)點(diǎn)都可以構(gòu)造出滿足插造出滿足插值條件的插值條件的插值多項(xiàng)式值多項(xiàng)式?2.1 插值法插值法n例1: 給定數(shù)據(jù)表如下n n (1) 用一次插值多項(xiàng)式計(jì)算 f(0.7) 的近似值n (2

5、) 用二次插值多項(xiàng)式計(jì)算 f(0.7) 的近似值n (3) 用三次插值多項(xiàng)式計(jì)算 f(0.7) 的近似值x0.2 0.4 0.6 0.8 1.0 1.2f (x)21 25 23 20 21 24求三次插值多求三次插值多項(xiàng)式要解一個(gè)項(xiàng)式要解一個(gè)四階線性方程四階線性方程組組,計(jì)算量大太計(jì)算量大太了了,有沒(méi)有更簡(jiǎn)有沒(méi)有更簡(jiǎn)便的方法便的方法?2.1 插值法插值法n拉格朗日(Lagrange)插值多項(xiàng)式101( )()()()nnxxxxxxx1011()()()()()nkkkkkkknxxxxxxxxx101()()()()nnnkkknkxLxyxxxknknkiiiknkiiinyxxxxxL

6、000)()()(或者寫成例例2: 數(shù)據(jù)如例數(shù)據(jù)如例1,運(yùn)用拉格朗日多項(xiàng)式重新計(jì)算運(yùn)用拉格朗日多項(xiàng)式重新計(jì)算(1)(2)(3)拉格朗日插值的優(yōu)缺陷拉格朗日插值的優(yōu)缺陷: : 公式構(gòu)造緊湊公式構(gòu)造緊湊, ,在實(shí)際分析中方便在實(shí)際分析中方便, ,但如遇節(jié)點(diǎn)增減但如遇節(jié)點(diǎn)增減, ,一切數(shù)據(jù)需全部重算一切數(shù)據(jù)需全部重算2.1 插值法插值法n牛頓牛頓(Newton)插值多項(xiàng)式插值多項(xiàng)式n記函數(shù)記函數(shù) 在在 的值的值 ，稱，稱 為為 關(guān)于關(guān)于 的零階差商。的零階差商。n稱稱 n 為函數(shù)為函數(shù) 關(guān)于點(diǎn)關(guān)于點(diǎn) 的一階差商的一階差商n普通地，普通地， 關(guān)于關(guān)于 的的 k階差商階差商 為為( )f xix ( )

7、iif xf x if x( )f xix000,kkkfxfxfxxxx( )f x0,kx x( )f x01,kx xx02011011,kkkkkkfxxxfxxxfxxxxx0010()(),()nNxfxfxxxx01201,()()fxxxxxxx 0101,()()nnfxxxxxxx2.1 插值法插值法n差商表一階均差一階均差二階均差二階均差三階均差三階均差四階均差四階均差ix0 x1x2x3x4x( )if x1( )f x2( )f x3()f x4()f x0()f x01,f xx12,fxx23,f xx34,f xx012,f xxx123,f x xx234,f

8、 x x x0123,f x x x x1234 ,f x x x x01234,f xx xxx例例3: 數(shù)據(jù)如例數(shù)據(jù)如例1 寫出差商表寫出差商表,運(yùn)用牛頓插值多項(xiàng)式重新計(jì)算運(yùn)用牛頓插值多項(xiàng)式重新計(jì)算(1)(2)(3)2.1 插值法插值法n設(shè)函數(shù)設(shè)函數(shù) 在等距節(jié)點(diǎn)在等距節(jié)點(diǎn) 上的值上的值 n 為知，這里為知，這里 為常數(shù)，稱為步長(zhǎng)。為常數(shù)，稱為步長(zhǎng)。n在前面的討論中，節(jié)點(diǎn)是恣意分布的，但實(shí)踐上經(jīng)常遇到在前面的討論中，節(jié)點(diǎn)是恣意分布的，但實(shí)踐上經(jīng)常遇到等距節(jié)點(diǎn)的情況，這時(shí)插值公式可以得到簡(jiǎn)化。等距節(jié)點(diǎn)的情況，這時(shí)插值公式可以得到簡(jiǎn)化。( )f x0(0,1, )kxxkh kn()kkffxh

9、2.1 插值法插值法n差分的定義差分的定義n 稱為在稱為在 處以處以 為步長(zhǎng)的向前差分為步長(zhǎng)的向前差分n 稱為在稱為在 處以處以 為步長(zhǎng)的向后差分為步長(zhǎng)的向后差分n 稱為在稱為在 處以處以 為步長(zhǎng)的中心差分為步長(zhǎng)的中心差分n下面以向前差分為例下面以向前差分為例,向后差分和中心差分的情形類似向后差分和中心差分的情形類似n用一階差分可以定義二階差分用一階差分可以定義二階差分n普通地可定義普通地可定義 m 階差分為階差分為1kkkfff1kkkfff1122()()22kkkkkhhff xf xffkxhkxhkxh21212kkkkkkffffff 111mmmkkkfff 2.1 插值法插值法

10、n差分表0fkf0f1f2f3f4f41f2f3f2302f12f22f03f13f04f0(0,1, )kxxkh kn0,01xxtht 200000(1)(1)(1)()2!nnt tt ttnNxthftfffn 牛頓向前差分插值公式牛頓向前差分插值公式例例4: 數(shù)據(jù)如例數(shù)據(jù)如例1 寫出差分表寫出差分表,運(yùn)用上式重新計(jì)算運(yùn)用上式重新計(jì)算(1)(2)(3)2.1 插值法插值法n高次插值的病態(tài)性質(zhì)高次插值的病態(tài)性質(zhì)n 對(duì)于一個(gè)確定的區(qū)間對(duì)于一個(gè)確定的區(qū)間,插值節(jié)點(diǎn)越多插值節(jié)點(diǎn)越多, 插值多項(xiàng)式的插值多項(xiàng)式的次數(shù)越高插值次數(shù)越高插值 。20世紀(jì)初，世紀(jì)初，Runge(龍格龍格)就給出了一個(gè)等

11、就給出了一個(gè)等距節(jié)點(diǎn)插值多項(xiàng)式距節(jié)點(diǎn)插值多項(xiàng)式 不收斂到不收斂到 的例子。的例子。n設(shè)設(shè) ，在區(qū)間，在區(qū)間 上取上取 個(gè)等距節(jié)個(gè)等距節(jié)點(diǎn)點(diǎn),構(gòu)造拉格朗日插值多項(xiàng)式為構(gòu)造拉格朗日插值多項(xiàng)式為n n 其中其中( )nL x( )f x2( )1/(1)f xx 5,51n5 10(0,1, )kkxknn 1201( )1( )1()()nnnjjjnjxLxxxxx2.1 插值法插值法n龍格景象龍格景象如何防止高如何防止高次插值的病次插值的病態(tài)問(wèn)題態(tài)問(wèn)題?一種可行的方法是采取分段低次插值一種可行的方法是采取分段低次插值2.1 插值法插值法n分段線性插值分段線性插值: 從幾何上看，就是用折線逼近曲

12、線。從幾何上看，就是用折線逼近曲線。n設(shè)設(shè) 是區(qū)間是區(qū)間 上的函數(shù)，在節(jié)點(diǎn)上的函數(shù)，在節(jié)點(diǎn)n 上的函數(shù)值為上的函數(shù)值為 ，n 記記 那么那么 的分段線性插值函數(shù)的分段線性插值函數(shù)n定義為定義為:n 在區(qū)間在區(qū)間 上上n 顯然有顯然有( )f x , a b01naxxxb01,nfff1,max(),kkkkkhxx hh( )hIx11111( )kkhkkkkkkkkxxxxIxffxxxxxxx1,kkxx(),0,1,hkkIxfkn( )f x2.1 插值法插值法),(kkfxxy分段線性插值表示圖分段線性插值表示圖0 xa2x1nx1xbxnkx1kx),(11kkfx例例5: 數(shù)

13、據(jù)如例數(shù)據(jù)如例1, 運(yùn)用分段線性插值計(jì)算運(yùn)用分段線性插值計(jì)算f (0.5) , f(0.75)的近似值的近似值*x2.1 插值法插值法n分段二次插值分段二次插值:n設(shè)設(shè) 是區(qū)間是區(qū)間 上的函數(shù)，在節(jié)點(diǎn)上的函數(shù)，在節(jié)點(diǎn)n 上的函數(shù)值為上的函數(shù)值為 ，n 記記 那么那么 的二次插值函數(shù)的二次插值函數(shù)n定義為定義為:n 在區(qū)間在區(qū)間 上上n顯然有顯然有( )f x , a b( )f x( )hp x222,kkxx(),0,1,2hkkpxfkm21222221222()()( )()()()kkhkkkkkxxxxpxf xxxxx222212122122()()()()()kkkkkkkxxx

14、xf xxxxx221222222222221()()(),()()kkkkkkkkkxxxxf xxxxxxxx012maxxxb012,mfff1021max ()kkkmhxx2.1 插值法插值法),(22kkfxxy分段二次插值表示圖分段二次插值表示圖),(1212kkfx例例6: 數(shù)據(jù)如例數(shù)據(jù)如例1, 運(yùn)用分段二次插值計(jì)算運(yùn)用分段二次插值計(jì)算f (0.5) , f(0.75)的近似值的近似值*x2x1xbxm20 xakx212 kx22mx22 kx12mx),(2222kkfx2.1 插值法插值法n三次樣條插值函數(shù)n定義：對(duì)于區(qū)間 上給定的一個(gè)分劃n 假設(shè)函數(shù) 在子區(qū)間 上都是不

15、超越3次的多項(xiàng)式，并且 2 階導(dǎo)數(shù) 在內(nèi)節(jié)點(diǎn) 處延續(xù)，那么稱n 為區(qū)間 上以 為節(jié)點(diǎn)的三次樣條函數(shù)。n對(duì)于函數(shù) ，假設(shè) 還滿足插值條件：n 那么稱 為 在區(qū)間 上的 三 次樣條插值函數(shù)。 , a b01naxxxb1,iix x121,nx xx( )s x01,nxxx( )s x , a b)(xs ()()0,1,2,iis xfxin( ) , f xC a b( )s x( )s x , a b( )f x2.1 插值法插值法n三次樣條插值表示圖 : 例7: 數(shù)據(jù)如例1x0.2 0.4 0.6 0.8 1.0 1.2f (x)21 25 23 20 21 24如何求三次樣如何求三次樣

16、條插值函數(shù)條插值函數(shù)?2.1 插值法插值法n三次樣條三次樣條 是節(jié)點(diǎn)是節(jié)點(diǎn) 上的分段三次多項(xiàng)式，故可上的分段三次多項(xiàng)式，故可寫成寫成:n 其中其中 為待定系數(shù)，共有為待定系數(shù)，共有 個(gè)未知數(shù)，個(gè)未知數(shù)，n 而而 應(yīng)滿足的條件為：應(yīng)滿足的條件為：n (1)插值和函數(shù)延續(xù)條件插值和函數(shù)延續(xù)條件 個(gè)；個(gè)；n (2)內(nèi)節(jié)點(diǎn)處一階導(dǎo)數(shù)延續(xù)內(nèi)節(jié)點(diǎn)處一階導(dǎo)數(shù)延續(xù) 個(gè)條件；個(gè)條件；n (3)內(nèi)節(jié)點(diǎn)處二階導(dǎo)數(shù)延續(xù)內(nèi)節(jié)點(diǎn)處二階導(dǎo)數(shù)延續(xù) 個(gè)條件；個(gè)條件；n總共由總共由 個(gè)條件，因此，要確定個(gè)條件，因此，要確定 個(gè)系數(shù)，還需求個(gè)系數(shù)，還需求附加兩個(gè)條件。附加兩個(gè)條件。01,nxxx( )s x321( ) ,0,1,

17、1iiiiiis xa xb xc xdxx xin(1)(1)2nnn1n,iiiia b c d4n( )s x1n42n4n用待定系數(shù)法需用待定系數(shù)法需求解一個(gè)求解一個(gè)4n階的階的線性議程組線性議程組,有沒(méi)有沒(méi)有更簡(jiǎn)便有更簡(jiǎn)便 的方的方法法?2.1 插值法插值法n求三次樣條插值函數(shù)的三彎矩算法n記n經(jīng)過(guò)推導(dǎo)可得n根據(jù) 的一階導(dǎo)數(shù)在內(nèi)節(jié)點(diǎn)的延續(xù)性,可得到)(iixMM 10,1,1iiihxxin( )( )MxsxiiiiiiiiiiihxxhMyhxxMhxxMxs123131)6(6)(6)()(nixxxhxxhMyiiiiiii.,2, 1 ,0,)6(12111.,2 , 1,

18、6,11111nixxxfdhhhhhhiiiiiiiiiiii其中)(xs1.,2, 1,211nidMMMiiiiii2.1 插值法插值法n在實(shí)踐運(yùn)用中，我們普通運(yùn)用如下三種類型的條件。在實(shí)踐運(yùn)用中，我們普通運(yùn)用如下三種類型的條件。n(1) 固支條件固支條件: 即知兩個(gè)端點(diǎn)的一階導(dǎo)數(shù)值即知兩個(gè)端點(diǎn)的一階導(dǎo)數(shù)值n(2) 知兩個(gè)端點(diǎn)的二階導(dǎo)數(shù)值知兩個(gè)端點(diǎn)的二階導(dǎo)數(shù)值:n 特別地，當(dāng)特別地，當(dāng) 時(shí)稱為自然邊境條件時(shí)稱為自然邊境條件n(3) 周期條件周期條件:n 同時(shí)要求同時(shí)要求00()()s xfx()()nns xfx00()()sxfx()()nnsxfx0()()0nfxfx0(0)(0)

19、ns xs x0(0)(0)nsxsx0()()nf xf x2.1 插值法插值法n運(yùn)用第一種邊境條件得到的三彎矩方程0011112222222211112100002000020000200002000012nnnnnnnnnnMdMdMdMdMdMd 2.1 插值法插值法n運(yùn)用第二種邊境條件得到的三彎矩方程111102222333333332222111120000200002000020000200002nnnnnnnnnnnnnMdMMdMdMdMdMdM 2.1 插值法插值法n例例8: 設(shè)設(shè) n 給定邊境條件給定邊境條件 試求三次樣條函數(shù)試求三次樣條函數(shù)n 解：先求出三彎矩方程的參數(shù)

20、解：先求出三彎矩方程的參數(shù):n 于是，三彎矩方程組為于是，三彎矩方程組為:n 求出的解為求出的解為:( )s x(0)0,(1)0.5,(2)2,(3)1.5,ffff(0)0.2,(3)1,ff 121200101012021233323211(0,1, 2),26(,()1.8,6,3,66,6,(),)3,ihidf xxfxdf xxxhdf xxxdfxf xxh 0123211.80.520.530.520.56123MMMM0123,( 0.36,2.52, 3.72,0.36)MMMM 2.1 插值法插值法n代入代入 的分段表示式，得到的分段表示式，得到:3232320.480

21、.180.2,0,1()1.04(1)1.25(1)1.28(1)0.5,1, 20.68(2)1.86(2)0.68(2)2,2, 3xxxxs xxxxxxxxx( )s x邊境條件修正為邊境條件修正為f f (0)=-1, f (0)=-1, f (3)=1(3)=1時(shí)時(shí)得到的三次樣條曲線得到的三次樣條曲線邊境條件為邊境條件為f f (0)=0.2, (0)=0.2, f f (3)=-1(3)=-12.1 插值法插值法n練習(xí)n 給定數(shù)據(jù)表如下(同例1) , 求三次樣條函數(shù) S(x)n (1) 邊境條件為 f (0.2)=0 , f(1.2) =0n (2) 邊境條件為 f (0.2)=

22、 -20, f(1.2) =20n (3) 邊境條件為 f (0.2)=0, f(1.2) =0 x0.2 0.4 0.6 0.8 1.0 1.2f (x)21 25 23 20 21 24474.4 , -348.8, 20.8, 474.4 , -348.8, 20.8, 115.6, 117 , -283.5115.6, 117 , -283.5(1)(1)819.9 , -439.7 , 39 ,819.9 , -439.7 , 39 ,133.7 , 26.1 , 62133.7 , 26.1 , 62(2)(2) 0 , -220.3 , -18.7 , 0 , -220.3 ,

23、-18.7 ,145 , 38.8 , 0145 , 38.8 , 0(3)(3)曲線擬合的最小二乘法曲線擬合的最小二乘法: : 在中在中 找一函數(shù)找一函數(shù) , ,使得誤差平方和使得誤差平方和 最小。最小。這里這里2.2 曲線擬合的最小二乘法曲線擬合的最小二乘法設(shè)函數(shù)設(shè)函數(shù) 在區(qū)間在區(qū)間 上有定義上有定義, ,知在離散點(diǎn)知在離散點(diǎn) 上的實(shí)驗(yàn)數(shù)上的實(shí)驗(yàn)數(shù)據(jù)據(jù) 。 上的線性無(wú)關(guān)函數(shù)族。上的線性無(wú)關(guān)函數(shù)族。( )yf x , a bxyba),(kkyx0 x1xmxkx1mx01( ),( ),( ) , nxxxC a b是01( ),( ),( )nspanxxx( )SxmiiixSmiii

24、miiyxSyxS02)(02*0222)(min)(,0,1,ix im(,),0,1,iixyim0011( )( )( )( ),()nnS xaxaxaxnm )(,)(| )(, 1*1010 xSRaaxaaxSxSxspan )(,)(| )(, 1*21022102xSRaaaxaxaaxSxSxxspan2.2 曲線擬合的最小二乘法曲線擬合的最小二乘法n通常在最小二乘法中 都思索為加權(quán)平方和n 這里 是a,b上的權(quán)函數(shù),它表示不同點(diǎn) 處的數(shù)據(jù)比重不同,例如 可表示在 點(diǎn)處反復(fù)觀測(cè)的次數(shù)。n求解最小二乘擬合問(wèn)題的方法n (1) 計(jì)算向量加權(quán)內(nèi)積n n (2) 列出法方程(正規(guī)方

25、程)n (3) 得到解向量 即 miiiiyxSx0222)()(220)(x),(iiyx)(ix),(iiyx0010000011111101(,)(,)(,)( ,)(,)(,)(,)( ,)(,)(,)(,)( ,)nnnnnnnnayayay 00(,)()(),0,1,( ,)(),0,1,mjkijikiimkiikiixxj knyyxkn *01(,)naaa*0( )( )njjjSxax2.2 曲線擬合的最小二乘法曲線擬合的最小二乘法n例例9 思索下表給出的離散點(diǎn)思索下表給出的離散點(diǎn)( ,)(010)iix yi ixiyixi2xi yiS*(xi)011.311.31

26、.24123.547.02.76234.2912.64.28345.01610.05.79457.02535.07.31568.83652.88.836710.14970.710.347812.564100.011.868913.081117.013.3891015.6100156.014.89101116.1121177.116.416697.1506749.52.2 曲線擬合的最小二乘法曲線擬合的最小二乘法4681046810121416S S* *(x) = -0.276 + 1.517 x(x) = -0.276 + 1.517 x2.2 曲線擬合的最小二乘法曲線擬合的最小二乘法n例10 思索下表給出的離散點(diǎn)xiyi01.00000.251.28400.501.64870.752.11701.002.7183( ,)(04)iix yi 0.20.40.60.811.251.51.7522.252.52.750.20.40.60.811.251.51.7522.252.52.75xiyi - S*(xi)0-0.005