1、前述插值問題前述插值問題: :要求被插函數與插值多項式在節點取要求被插函數與插值多項式在節點取 相同值相同值() (i0,1,n):niipxy 幾幾何何上上 兩兩曲曲線線有有公公共共點點 lagrange lagrange型插值條件型插值條件 2121()()niiiniyyxhxh ), 1 , 0(ni yx0 x0 xixn4 埃爾米特插值埃爾米特插值 /* hermite interpolation */hermite型插值條件型插值條件然而然而,實際許多問題還常常要求實際許多問題還常常要求求一次數求一次數12 n)(12xhn 的多項式的多項式 ，使之滿足給定的，使之滿足給定的he

2、rmitehermite型插值條件：型插值條件：hermite型插值型插值:兩曲線不僅有共同交點兩曲線不僅有共同交點還要有共同切線還要有共同切線2（n+1）個條件個條件3 hermite interpolation一般地，已知一般地，已知 x0 , , xn 處有處有 y0 , , yn 和和 y0 , , yn ，求，求 h2n+1(x) 滿足滿足 h2n+1(xi) = yi ， h2n+1(xi) = yi。解：解：設設ni)()()(0iixhxhyixh2n+1 n0iyi可驗證可驗證 hi(xj) = ij , hi(xj) = 0, (xj) = 0, (xj) = ij 上式滿

3、足條件上式滿足條件 hi hihi(x)有根有根 x0 , , xi , , xn且都是且都是2重根重根 )()()(2xlbxaxhiiii ijjijixxxxxl)()()(由余下條件由余下條件 hi(xi) = 1 和和 hi(xi) = 0 可解可解ai 和和 bi )()(21 )(2xlxxxlxhiiiii (x) hi有根有根 x0 , , xn, 除了除了xi 外都是外都是2重根重根 hi)()(iili2(x)xxcx hi又又: (xi) = 1 ci = 1 hi)(x)(ili2(x)xx 設設,.210bacfbxxxann 則則20)22()()!22()()(

4、 niixnnxxnfxr 這樣的這樣的hermite 插值唯插值唯一一ni)()()(0iixhxhyixh2n+1 n0iyi)()(21 )(2xlxxxlxhiiiii hi)(x)(ili2(x)xx ijjijixxxxxl)()()(其中其中特別：對兩節點三次埃爾米特插值特別：對兩節點三次埃爾米特插值3( )hx101121xxxxy2010 xxxx00 xxy2101xxxx2010 xxxx11xxy010021xxxxy2101xxxx3 hermite interpolationquiz: 給定給定 xi = i +1, i = 0, 1, 2, 3, 4, 5. 下面

5、哪個是下面哪個是 h2(x)的圖像？的圖像？ x0-10.5123456yxy0-10.5123456斜率斜率=1 求求hermite多項式的基本步驟：多項式的基本步驟： 寫出相應于條件的寫出相應于條件的hi(x)、 hi(x) 的組合形式；的組合形式； 對每一個對每一個hi(x)、 hi(x) 找出盡可能多的條件給出的根；找出盡可能多的條件給出的根； 根據多項式的總階數和根的個數寫出表達式；根據多項式的總階數和根的個數寫出表達式； 根據尚未利用的條件解出表達式中的待定系數；根據尚未利用的條件解出表達式中的待定系數； 最后完整寫出最后完整寫出h(x)。ni)()()(0iixhxhyixh2n

6、+1 n0iyi hi)(x)(ili2(x)xx 例例 給定函數值表如下給定函數值表如下: :123()2412()3iiixf xfx 33333( ),:()() , (2)3( )( )( ).iihxhxf xhr xf xhx 求求一一次次數數不不超超過過 的的多多項項式式使使之之滿滿足足如如下下插插值值條條件件并并寫寫出出截截斷斷誤誤差差的的表表達達式式22323323( )376( )( )(1)(2)(3)(2)3,2.( )29156pxxxhxpxk xxxhkhxxxx 設所求多項式為設所求多項式為由條件得故由條件得故得得的二次多項式的二次多項式先求滿足插值條件先求滿足

7、插值條件方法方法解解,)3 , 2 , 1()()( . 1 :2 iifip(4)2:( )( )(1)(2) (3), (1,3)4!fr xxxx 截截斷斷誤誤差差為為5 分段低次插值分段低次插值 /* piecewise polynomial approximation */提高多項式的次數提高多項式的次數并不一定得到好結果并不一定得到好結果例：例：在在 5, 5上考察上考察 的的ln(x)。取。取211)(xxf),., 0(105niinxi -5 -4 -3 -2 -1 0 1 2 3 4 5 -0.5 0 0.5 1 1.5 2 2.5 n 越大，越大，端點附近抖動端點附近抖動

8、越大，稱為越大，稱為runge 現象現象ln(x) f (x) 分段分段低次低次插值插值折線代替曲線折線代替曲線在每個區間在每個區間 上，用上，用1階多項式階多項式 (直線直線) 逼近逼近 f (x):,1 iixx11111)()( iiiiiiiiyxxxxyxxxxxpxf,for 1 iixxx記記 ，易證：當，易證：當 時，時，|max1iixxh 0h)()(1xfxph一致一致分段插值函數只能保證連續性，分段插值函數只能保證連續性， 不能保證光滑性。不能保證光滑性。 分段分段hermite插值插值 /* hermite piecewise polynomials */給定給定nn

9、nyyyyxx ,.,;,.,;,.,000在在 上利用兩點的上利用兩點的 y 及及 y 構造構造3次次hermite函數函數,1 iixx所要提供的信息太多，導數一般不易得到，所要提供的信息太多，導數一般不易得到，光滑性不太高（只有連續一階導）光滑性不太高（只有連續一階導）整體插值由于節點多次數高而有可能發生龍格現象，整體插值由于節點多次數高而有可能發生龍格現象，分段插值可以得到整體連續函數，但在連接點處一般分段插值可以得到整體連續函數，但在連接點處一般不光滑，而分段不光滑，而分段hermite插值雖然在連接點處一階光插值雖然在連接點處一階光滑，但各節點導數不易給出滑，但各節點導數不易給出既

10、想分段插值，又想在既想分段插值，又想在節節點處保持光滑，甚至點處保持光滑，甚至二階光滑二階光滑三次樣條。三次樣條。 希望：希望： 樣條來源樣條來源6 三次樣條三次樣條 /* cubic spline */問題提出：問題提出：定義定義設設 。三次樣條函數三次樣條函數 , 且在每個且在每個 上為上為 /* cubic polynomial */。若它同。若它同時還滿足時還滿足 ，則稱為，則稱為 f 的的三次樣條插值函三次樣條插值函數數 /* cubic spline interpolant */.bxxxan .10,)(2bacxs ,1 iixx),., 0(),()(nixfxsii 樣條本

11、質上是樣條本質上是一段一段的三次多項式一段一段的三次多項式拼合而成的曲線拼合而成的曲線在拼接處在拼接處, ,不僅函數是連續的不僅函數是連續的, ,且一階和二階導數也是連續的且一階和二階導數也是連續的共共4n個待定系數個待定系數共共3(n-1)個條件個條件()iis xy 0,1,2.,in (0)(0)iis xs x(0)(0)iisxsx (0)(0)iisxsx 1,2.,1in共共n+1個條件個條件共共4n-2個條件個條件 第第1類邊界條件類邊界條件 /* clamped boundary */： s(a) = y0， s(b) = yn 第第2類邊界條件：類邊界條件： s”(a) =

12、 y0” ， s”(b) = yn”特別地，特別地， y0” = yn” = 0 稱為稱為自由邊界自由邊界 /* free boundary */，對應對應的樣條函數稱為的樣條函數稱為自然樣條自然樣條 /* natural spline */。 第第3類邊界條件類邊界條件 /* periodic boundary */ ： 當當 f 為為周期函數周期函數時，時， yn = y0 ， s(a+) = s(b ) 注：注：三次樣條與分段三次樣條與分段 hermite 插值的根本區別在于插值的根本區別在于s(x)自自身光滑身光滑，不需要知道，不需要知道 f 的導數值（除了在的導數值（除了在2個端點可

13、能需個端點可能需要）；而要）；而hermite插值依賴于插值依賴于f 在所有插值點的導數值。在所有插值點的導數值。f(x)h(x)s(x)njmxsjj, 1 ,0,)(設)(,)(1xsxxxfkkk上的三次插值多項式在小區間逐個求插值多項式上的兩點三次表示為將hermitexxxskkk,)(1)(xsk( )( )( )( )( )301 101 1( )( )( )( )( )kkkkkkkkkhxy hxyhxm hxmhx21kkkxxxx11121kkkkxxxxykkxxm211kkkxxxx21kkkxxxx11kkxxmkkkkxxxxy121211kkkxxxx 構造三次

14、樣條插值函數構造三次樣條插值函數并整理后得求二階導數對,)(xsk)()2(6)(131kkkkkkyyhxxxxs kkkkmhxxx21426121246kkkkmhxxxkkkkkkyxxhxxhxs213)()(2)(1231)()(2kkkkkyxxhxxhkkkkmxxhxx212)()(1221)()(kkkkmxxhxx加以整理后可得1, 1 ,01nkxxhkkk，令1(0)(0)kkkksxsx 1,2 , 1nk由條件1(0)kksx )(612kkkyyhkkmh412kkmh(0)kksx )(6121kkkyyh112kkmhkkmh14由于以上兩式相等,得1111

15、1)11(21kkkkkkkmhmhhmh)(321121kkkkkkhyyhyy1, 1nk得并加以整理除上式的兩邊用,111kkhh11kkkkhhh1kkkkhhh)(3111kkkkkkkkkhyyhyyg11,kn-(1)如果問題要求滿足第一類(一階)邊界條件:00()s xy()nns xy基本方程組(1)化為n-1階方程組1121102mmgykkkkkkgmmm1122, 3 ,2nk121112nnnnnnmmgy00 0mynnmy即化為矩陣形式222222122433221nnn12321nnmmmmm11023211nnnngyggggy-(2)這是一個三對角方程組如果

16、問題要求滿足第二類(二階自然)邊界條件:00()sxy()nnsxy0 00nyf自然邊界條件由前式,可知)()2(6)(013001000yyhxxxxs 020100426mhxxx120100246mhxxx)(60120yyh004mh102mh0y)(6)(1211 nnnnnyyhxs112nnmhnnmh14ny011,nnm m mm上式是的方程 整理后得1000100232yyhmmyh1111232nnnnnnnyyhmmyh0gng212222121132211nn與基本方程組(1)聯合,并化為矩陣形式,得nnmmmmm1210nnggggg1210-(3)注：注：三對角

17、方程組三對角方程組, ,可以使用追趕法求解可以使用追趕法求解收斂性：收斂性：若若 ，且，且 ，則，則,bacf chhiiminmax一致一致s(x) f(x)0maxihas即即:提高精度只須提高精度只須增加節點增加節點, 而無須提高樣條階數。而無須提高樣條階數。5 cubic spline小結小結 計算計算 k , k , gk ; 計算計算 mj (追趕法等追趕法等) ; 找到找到 x 所在區間所在區間 ( 即找到相應的即找到相應的 k) ; 由該區間上的由該區間上的 s(x) 算出算出 f(x) 的近似值。的近似值。11kkkkhhh1kkkkhhh)(3111kkkkkkkkkhyy

18、hyyg1, 1nkkkkkkkyxxhxxhxs213)()(2)(kkkkmxxhxx212)()(1221)()(kkkkmxxhxx222222122433221nnn12321nnmmmmm11023211nnnngyggggynnmmmmm1210212222121132211nn1000001211113232nnnnnnnyyhgyhgggyyhgyh第一類邊界條件第一類邊界條件第二類邊界條件第二類邊界條件例. 對于給定的節點及函數值2431)(54213210kkxfxk的近似值并求插值函數的三次樣條求滿足自然邊界條件)3(),(0)()(0fxsxsxsn 3213123113221kkkkhhh11kkkkhhhk 1解:h0=1 h1=2 h2=1291g272g60g63g213/223/13/123/2123210mmmm3210gggg819,45,47,8173210mmmm解方程組得：)(3111kkkkkkkkkhyyhyyg10000032yyhgyh11132nnnnnnyyhgyh211478381)(230 xxxxxs421478381)(231xxxxxs543341