1、1第三章插值法數值分析2在生產和科研實踐中許多實際問題都用函數來表示某種內在規律的數量關系, 雖然可以確定所考慮函數的一些性質，但卻難以找到它的解析表達式，只能通過實驗和觀測得到在有限個點上的函數值。 另外, 有時雖然可以寫出函數的解析表達式，但由于結構相當復雜，使用起來很不方便。 面對這些情況，總希望構造某個簡單函數作為近似。為什么要插值3插值法插值法例：例：已測得在某處海洋不同深度處的水溫如下：已測得在某處海洋不同深度處的水溫如下： 深度（深度（M） 466 741 950 1422 1634 水溫（水溫（oC） 7.04 4.28 3.40 2.54 2.13根據這些數據，希望合理地估計

2、出其它深度（如根據這些數據，希望合理地估計出其它深度（如500、600、800米米）處的水溫。）處的水溫。4插值基本概念插值基本概念已知函數已知函數 y = f(x) 在在 a, b 上有定義，且已經測得在點上有定義，且已經測得在點 a x0 x1 xn b 處的函數值為處的函數值為 y0 = f(x0)， ，yn = f(xn)什么是插值如果存在一個如果存在一個簡單易算簡單易算的函數的函數 P(x)，使得，使得 P(xi) = f(xi)，i = 1, 2, . , n則稱則稱 P(x) 為為 f(x) 的的插值函數插值函數插值區間插值區間插值節點插值節點求插值函數求插值函數 P(x) 的方

3、法就稱為的方法就稱為插值法插值法插值節點插值節點無需遞無需遞增排列增排列，但必須，但必須確保確?；ゲ幌嗤ゲ幌嗤?！插值條件插值條件5常用插值法常用插值法x0 x1x2x3x4xl 多項式插值：多項式插值：P(x) 為多項式函數為多項式函數 - 最常用的插值函數最常用的插值函數l 分段插值：分段插值：P(x) 為分段多項式函數為分段多項式函數l 三角插值：三角插值：P(x) 為三角函數為三角函數 P(x) 常用插值法6多項式插值多項式插值多項式插值已知函數已知函數 y = f(x) 在在 a, b 上上 n + 1 個點個點 a x0 x1 0，稱為步長稱為步長( )()iiif xhxff 此

4、時，可以使用此時，可以使用差分差分來簡化來簡化 Newton插值公式插值公式差分差分f(x) 在在 xi 處步長為處步長為 h 的的 一階差分一階差分35差分差分21( ) iiiiffff 1111()nnnniiiiffff 0()iiff x規定規定 q 高階差分高階差分二階差分二階差分n 階差分階差分1 ()()iiiiiff xhf xff 36差分與函數值差分與函數值q 不變算子不變算子 I 與移位算子與移位算子 E 1 , IEiiiiffff 1 ()E I EI iiiiiiffffff 00 ()( 1)(1)(1) ( 1)!EI Ennnkn kiiiknkn i kk

5、nfffkn nnkfk n 階差分的具體表達式階差分的具體表達式 37差分與函數值差分與函數值q 反之，有反之，有0()EI+ nnkn iiiiknnffffk 38差分與差商差分與差商差分差分與差商之間的關系與差商之間的關系1000110 ,ffff xxxxh kkkhkfxxxf!,010 通過遞推可得通過遞推可得1,!kmmmm kkff xxxk h 差分差分與導數之間的關系與導數之間的關系!)()(0kfx,.,xfkk kkkhff0)()( 39差分的計算差分的計算差分表差分表xi(xi)一階一階差分差分二階二階差分差分三階三階差分差分n 階階差分差分x0 x1 xn-3

6、xn-2 xn-1xn(x0)(x1) (xn-3)(xn-2)(xn-1)(xn) 0 1 n-3 n-2 n-1 20 21 2n-3 2n-2 30 31 3n-3 n040等距牛頓插值等距牛頓插值牛頓牛頓前前插插公式公式10102011()()()( )()nniinaa xxaxxxxaxNxx 設插值點設插值點htxx 0020000( )()(1)(1)(1) 1!2!nnnNxNxthtt tt ttnffffn001,!kkkkfaf x xxk h),(,).(1()!1()()(01)1(nxnxnnxxhntttnfxR 41插值舉例插值舉例例：例：給出給出 f (x)

7、 = cos x 在等距節點在等距節點 0, 0.1, 0.2, 0.3, 0.4, 0.5 處的處的函數值，試用函數值，試用 4 次牛頓前插公式計算次牛頓前插公式計算 f (0.048) 的近似值的近似值xi(xi) 2 3 4 50.00.10.20.30.40.51.000000.995000.980070.955340.921060.87758-0.00500-0.01493 -0.02473-0.03428 -0.04348-0.00993-0.009800.009550.00920-0.00013-0.00025-0.00035-0.00012-0.00010-0.00002解解：

8、插值點插值點 x = 0. 048， t =(x-x0)/h=0. 48 差差分分表表N4(0.048) = 1.00000 + 0.48*(-0.005) + = 0.99884|R4(0.048)| t(t-1) (t-2) (t-3) (t-4)h5M5/5! 1.09212 10-7第三章插值法數值分析 Hermite 插值法插值法Hermite 插值插值在許多實際應用中，不僅要求在許多實際應用中，不僅要求函數值函數值相等，而且要求若干階相等，而且要求若干階導數導數也相等，如機翼設計等。也相等，如機翼設計等。為什么 Hermite 插值( )( )f xx （i = 0, 1, , n

9、）()()iixf x ()()iixfx (2)(2)()()iixfx ()()()()mmiixfx 滿足滿足函數值函數值相等且相等且導數導數也相等的插值方法成為也相等的插值方法成為 Hermite插值插值Hermite 插值多項式插值多項式定義定義 已知已知 f(x) 在節點在節點 x0 , , xn 處處 f (xi) = fi 及一及一階導數值階導數值 f (xi) = fi (i = 0, 1, 2, , n) ，若存在函，若存在函數數 H (x) 滿足：滿足： (1) H (x) 是次數不超過是次數不超過 2n+1 的多項式；的多項式； (2) H (xi)= fi ，H(xi

10、) = fi ； 則稱則稱 H (x) 為為 埃爾米特插值多項式埃爾米特插值多項式；可以證明：滿足以上兩個條件的可以證明：滿足以上兩個條件的埃爾米特插值多項式埃爾米特插值多項式是存在唯一的。是存在唯一的。重節點差商重節點差商定理定理設設 f(x) Cna, b， x0 , , xn 為為 a, b 上的互異上的互異節點，則節點，則 fx0 , , xn 是其變量的連續函數是其變量的連續函數重重節節點點差差商商10100001010()(),lim,()xxf xf xf xxf xxfxxx 102000001201,lim,()2!xxxxf xxxf xx xfx 0( )000101,l

11、im,()!innxxf xxf xxxfxn 一般地，一般地，n 階重節點差商定義為階重節點差商定義為 重節點重節點Newton插值插值在在 Newton 插值公式中，令插值公式中，令 xi x0 , i = 1, , n, 則則0010012011011( )(),(),()() ,()nnniiNxf xf xxxxf xx xxxxxf xxxxx (2)20000000()()()()()2!()()!nnfxf xfxxxxxfxxxnTaylor 插值多項式插值多項式(1)10( )( )()(1)!nnnfRxxxn 余項余項在節點在節點 x0 處的處的 n 次次 Hermit

12、e 插值多項式插值多項式Hermite 插值插值一般來說，給定一般來說，給定 m+1 個插值條件，就可以構造出一個插值條件，就可以構造出一個個 m 次次 Hermite 插值多項式插值多項式 n 兩個典型的兩個典型的 Hermite 插值插值l 三點三次三點三次 Hermite 插值插值l 兩點三次兩點三次 Hermite 插值插值插值節點：插值節點：x0 , x1 , x2 插值條件：插值條件：P(xi) = f(xi)，i = 0, 1, 2，P(x1) = f(x1)插值節點：插值節點：x0 , x1插值條件：插值條件：P(xi) = f(xi)，P(xi) = f(xi) ，i = 0

13、, 1三點三次三點三次Hermite 插值插值插值節點：插值節點：x0 , x1 , x2 插值條件：插值條件：P(xi) = f(xi)，i = 0, 1, 2，P(x1) = f(x1)三點三次 Hermite 插值設設000110010122( )(),() ,()() ()( )()P xf xf xxxxf xx xA xxxxxxxxxx 將將 P(x1) = f(x1) 代入可得代入可得101012101012(),()()()fxf xxf xx xxxAxxxx 三點三次三點三次Hermite 插值插值由于由于 x0 , x1 , x2 是是 R(x) 的零點，且的零點，且

14、x1 是二重零點，故可設是二重零點，故可設余項公式余項公式2012( )()()()( )k xxxxxxxR xf xP x與與 Lagrange 插值余項公式的推導過程類似，可得插值余項公式的推導過程類似，可得42012( )()() ()()( )4!xfR xxxxxxx 其中其中 x 位于位于 由由 x0 , x1 , x2 和和 x 所界定的區間所界定的區間 內內插值舉例插值舉例例：例：函數函數 f(x) = x3/2，插值條件如下，插值條件如下解解：作差商表作差商表試給出三次試給出三次Hermite插值多項式，并寫出余項插值多項式，并寫出余項xi(xi)一階差商一階差商 二階差商

15、二階差商1/419/41/8127/87/619/1011/30將將 P(1) = f(1) = 3/2 代入可得代入可得 A = -14/225f(1/4) = 1/8，f(1) = 1，f(9/4) = 27/8，f(1) = 3/2 171111( )()()(1)86430419 ()(1)()44P xxxxA xxx 插值舉例插值舉例(4)25/22( )( )( )( )19 ()(1) ()4!44919 ()(1) ()4! 1644R xf xP xfxxxxxx 32142632331( )22545045025P xxxx 余項余項兩點三次兩點三次Hermite 插值插

16、值插值節點：插值節點：x0 , x1 插值條件：插值條件：P(xi) = f(xi) = yi，P(xi) = f(xi) = mi，i = 0, 1兩點三次 Hermite 插值模仿模仿 Lagrange 多項式的思想，設多項式的思想，設)()()()()(110011003xbxbxaxaxH 其中其中 均為均為 3 次多項式，且滿足次多項式，且滿足0101( ),( ),( ),( )xxxx(), ()0, ()0, ()jijijijijijixxxxi, j= 0, 1兩點三次兩點三次Hermite 插值插值將將插值條件插值條件代入立即可得代入立即可得300110011( )( )

17、( )( )( )Hxyxyxmxmx 0(x), 1(x), 0(x), 1(x) 的表達式？的表達式？ 0(x)0101()0, ()0 xx21001( )()xxxaxbxx 00000101()1, ()0, ()0, ()0 xxxx 0000()1, ()0 xx010010101322, 1xxxabxxxxxx 兩點三次兩點三次Hermite 插值插值20101001( )12xxxxxxxxx 同理可得同理可得20110110( )12xxxxxxxxx 相類似地，可以推出相類似地，可以推出 210001( )()xxxxxxx 201110( )()xxxxxxx 兩點三

18、次兩點三次Hermite 插值插值滿足插值條件滿足插值條件P(x0) = f(x0) = y0，P(x0) = f(x0) = m0P(x1) = f(x1) = y1，P(x1) = f(x1) = m1的三次的三次 Hermite 插值多項式為插值多項式為 22001130110010110220100110110( )1212 xxxxxxxxHxyyxxxxxxxxxxxxmxxmxxxxxx 余項余項 2243 4)()(!)()(10)(xxxxfxRx01()xx,x 一般公式一般公式 n+1個節點可以唯一確定一個個節點可以唯一確定一個2n+1次次Hermite插值多項式：插值多

19、項式：222100( )(1 2()() ( )() ( )nnnkkkkkkkkkkHxfxx lx lxfxx lx)(! ) 22 ()()()()(2 1 2)2(1212 xnfxHxfxRnxnnn )( b , ax 余項余項（條件：（條件：f(x0) 在插值區間在插值區間 a,b 內的內的 2n+2 階導數存在）階導數存在）第三章插值法數值分析 分段低次插值分段低次插值分段插值分段插值問題問題 拋物線插值的誤差比線性插值要小，拋物線插值的誤差比線性插值要小，是不是是不是插值多項式的次數越高，精度就越好？插值多項式的次數越高，精度就越好？NO!例：例：在在 5, 5 上考察上考察

20、 的的Ln(x)。取取211)(xxf khxk 5),., 0 ,/10(nknh Ln(x) f (x) -5 -4 -3 -2 -1 0 1 2 3 4 5 -0.5 0 0.5 1 1.5 2 2.5 n 越大，端點附近越大，端點附近的抖動越大，稱為的抖動越大，稱為 Runge現象現象。分段插值分段插值高次多項式插值的病態性質：高次多項式插值的病態性質：為什么分段低次插值為什么分段低次插值n 時時 Ln(x) 不一定收斂于不一定收斂于 f(x)例：例：Runge 函數的等距節點插值多項式函數的等距節點插值多項式分段插值分段插值用分段多項式函數來逼近原函數用分段多項式函數來逼近原函數 f

21、(x)分段低次插值分段低次插值n 常見的分段低次插值常見的分段低次插值l 分段線性插值分段線性插值l 分段三次分段三次 Hermite 插值插值每個小區間上用每個小區間上用線性多項式線性多項式來逼近來逼近 f(x) 每個小區間上用每個小區間上用三次三次 Hermite多項式多項式來逼近來逼近 f(x) 分段分段線性插值線性插值分段線性插值分段線性插值設設 a x0 x1 xn b 為為 a, b 上的互異節點上的互異節點f(x) 在這些節點上的函數值為在這些節點上的函數值為 y0 , y1 , , yn記記 ， 求分段函數求分段函數 Ih(x) 滿足滿足 1kkkhxx maxkkhh Ih(

22、x) 在每個小區間在每個小區間 xk, xk+1 上是線性函數上是線性函數() , hIxC a b 0, 1, (), ,hkkknIxy 分段分段線性插值線性插值1111( )kkhkkkkkkxxxxIxyyxxxx 由以上條件直接可得由以上條件直接可得 Ih(x) 在小區間在小區間 xk, xk+1 上的表達式上的表達式x xk, xk+1， k = 0, 1, , n-1誤差估計誤差估計誤差估計誤差估計( )221()( )( )()()2!24kxkhkkfhMf xIxxxxx 在小區間在小區間 xk, xk+1 上有上有2max( )a x bMfx ( )221()( )(

23、)( )max()()2!8kxhkkkfMR xf xIxxxxxh ( )( )( )0hR xf xIx 當當 h 0 時，時，Ih(x) 在在 a, b 上上 一致收斂一致收斂 到到 f(x) 分段線性插值的不足：分段線性插值的不足： Ih(x) 在節點在節點不可導不可導分段分段三次三次Hermite插值插值分段分段三次三次 Hermite 插值插值設設 a x0 x1 xn b 為為 a, b 上的互異節點上的互異節點 yk f(xk) , mk f(xk) ， k = 0, 1, , n 求分段函數求分段函數 Ih(x) 滿足滿足 Ih(x) 在每個小區間在每個小區間 xk, xk

24、+1 上是三次多項式上是三次多項式1() , hIxCa b 0, 1(), , (), , hkkhkkIxyIxmkn 分段分段三次三次Hermite插值插值由以上條件直接可得由以上條件直接可得 Ih(x) 在小區間在小區間 xk, xk+1 上的表達式上的表達式x xk, xk+1， k = 0, 1, , n-1 2211111112211111( )1212 kkkkhkkkkkkkkkkkkkkkkkkkkxxxxxxxxIxyyxxxxxxxxxxxxmxxmxxxxxx 誤差估計誤差估計44( )( )( )384hMR xf xIxh (4)2101max( ) , max

25、()kka x bk nMfxhxx 2243 4)()(!)()(10)(xxxxfxRx01()xx,x 66三次樣條插值三次樣條插值 設插值節點為設插值節點為a = x0 x1 xn-1 xn = b 若函數若函數 S(x) C2a,b，且，且在每個小區間在每個小區間 xj , xj+1上是上是三次多項式，則稱其為三次多項式，則稱其為三次樣條函數三次樣條函數如果同時還滿足如果同時還滿足 S(xi) = f(xi) = yi ， i = 0, 1, 2, , n 則稱則稱 s(x) 為為 f (x) 在在 a , b 上的上的三次樣條插值函數三次樣條插值函數定義定義67三次樣條插值三次樣條

26、插值S(x) 滿足：滿足： S(x) C2a,b； 在在 xj , xj+1 是三次多項式是三次多項式 S(xi) = yi ， i = 0, 1, 2, , n00111211( ), , ( ), , ( ) ( ), ,nnnsxxxxs xxx xs xsxxxx 其中其中 sj(x) 為為 xj, xj+1 上的上的三次多項式，且滿足三次多項式，且滿足sj(xj) = yj，sj(xj+1) = yj+1 j = 0, 1, , n-1怎樣計算三次樣條插值函數怎樣計算三次樣條插值函數68邊界條件邊界條件每個每個 sj(x) 均為三次多項式，有均為三次多項式，有 4 個待定系數，所以共

27、有個待定系數，所以共有 4n 個待定系數，故需個待定系數，故需 4n 個方程才能確定。前面已經得到個方程才能確定。前面已經得到 2n +2(n-1) = 4n-2 個方程，還缺個方程，還缺 2 個方程！個方程！2( ) , S xC a b q 實際問題通常對樣條函數在實際問題通常對樣條函數在兩個端點兩個端點處的狀態有要處的狀態有要求，即所謂的求，即所謂的 邊界條件邊界條件()(), ()()jjjjSxSxSxSx ( j = 1, 2, , n-1)11()(),()()jjjjjjjjsxsxsxsx 69常用的邊界條件常用的邊界條件q 第一類邊界條件：第一類邊界條件：給定函數在端點處的

28、給定函數在端點處的一階導數一階導數，即，即00() ()nnS xf , S xf q 第二類邊界條件：第二類邊界條件：給定函數在端點處的給定函數在端點處的二階導數二階導數，即，即00() ()nnS xf , S xf 當當 S”(x0) = S”(xn) = 0 時，稱為時，稱為自然邊界條件自然邊界條件，此時的樣條函數稱為此時的樣條函數稱為自然樣條函數自然樣條函數q 第三類邊界條件：第三類邊界條件：設設 f (x) 是周期函數，并設是周期函數，并設 xn x0 是是一個周期，于是要求一個周期，于是要求 S(x) 滿足滿足00()()()()nnS xS x, S xS x 70三次樣條函數

29、的計算三次樣條函數的計算設設 S”(xj) = Mj， j = 0, 1, 2, , n由于由于 sj(x) 是三次多項式，故是三次多項式，故 sj”(x) 為線性函數，且為線性函數，且 sj”(xj) = Mj , sj”(xj+1) = Mj+1下面計算下面計算 S(x) 在在 xj, xj+1 的表達式的表達式 sj (x) 由線性插值公式可得由線性插值公式可得11( )jjjjjjjxxxxsxMMhh 1jjjhxx 求積分，可得求積分，可得331112()()( )66jjjjjjjxxxxsxMMc xchh 71三次樣條函數的計算三次樣條函數的計算將插值條件將插值條件 sj(x

30、j) = yj，sj(xj+1) = yj+1 代入，即可確定積代入，即可確定積分常數分常數 c1 和和 c2 。整理后可得。整理后可得 sj(x) 的表達式為的表達式為只需確定只需確定 M0, M1 , , Mn 的值，即可給出的值，即可給出 sj(x)的的表達式，從而可以得到表達式，從而可以得到 S(x) 的表達式。的表達式。331122111()()( )66 +66jjjjjjjjjjjjjjjjjxxxxsxMMhhM hxxMhxxyyhh j = 0, 1, , n-172三次樣條函數的計算三次樣條函數的計算條件：條件：1()()jjjjsxsx 易知易知 221111()()(

31、 )226jjjjjjjjjjjjjxxxxyyhsxMMMMhhh 1111111636jjjjjjjjjjjjjhhhhyyyyMMMhh 111111116,2jjjjjjjjjjjjjjjf xxf xxhhMMMhhhhhh 6 fxj-1, xj, xj+1dj j j73三次樣條函數的計算三次樣條函數的計算或或 1111112() 6,jjjjjjjjjjjhMhh Mh Mf xxf xx j = 1, 2, , n-174三次樣條函數的計算三次樣條函數的計算整理后得關于整理后得關于 Mj-1, Mj 和和 Mj+1 的方程：的方程：jjjjjjdMMM 112 三彎矩方程三彎

32、矩方程共共 n-1 個方程，附加個方程，附加邊界條件邊界條件，補充兩個方程后，即，補充兩個方程后，即可確定可確定 n+1 個未知量個未知量 M0, M1 , , Mn其中其中11111, , 6 ,jjjjjjjjjjjjhhdf xxxhhhh 1 jj j = 1, 2, , n-175第一類邊界條件第一類邊界條件q 第一類邊界條件：第一類邊界條件：00() ()nnS xf , S xf 0110000026 () /MMyyhfhd 直接代入直接代入 sj (x) 的一階導數表達式即得的一階導數表達式即得 111126() /nnnnnnnnMMfyyhhd 與前面的與前面的 n-1 個方程聯立可得個方程聯立可得 n+1 階線性方程組：階線性方程組： nnnnnndddddMMMMM12101210112211 2122212 系數矩陣系數矩陣嚴格對嚴格對角占優角占優，方程組，方程組存在唯一解存在唯一解。76第二類邊界條件第二類邊界條件故前面方程中只含故前面方程中只含 n-1 個未知量，即可得個未知量，即可得 n-1 階線性方程組階線性方程組:1111022222222111122 22nnnnnnnnnMdfMdMdMdf q 第二類邊界條件：第二類邊界條件：00() ()nnS xf , S xf 系數矩陣系數矩陣嚴格對角占優嚴格對角