多項式插值與樣條插值

1、1汪遠征汪遠征 實踐中常有這樣的問題：實踐中常有這樣的問題： (1) 由實驗得到某一函數(shù)由實驗得到某一函數(shù)f(x)在一系列點在一系列點x0, x1, , xn處的值處的值y0, y1, , yn, 其函數(shù)的解析表達式是未知的其函數(shù)的解析表達式是未知的 (2) 或者或者f(x)雖有解析式雖有解析式, 但計算復雜但計算復雜, 不便于使用不便于使用 需要構(gòu)造一個簡單函數(shù)需要構(gòu)造一個簡單函數(shù)p(x)近似地代替近似地代替f(x) 這就是函這就是函數(shù)逼近問題數(shù)逼近問題汪遠征汪遠征 設已知被逼近函數(shù)設已知被逼近函數(shù)f (x)在離散點在離散點xi a, b上的值上的值 f (xi) = yi, i = 0,

2、1, 2, , n (1) 要求要求p(x)滿足滿足 （甚至（甚至 ）的問題稱為函數(shù)插值。）的問題稱為函數(shù)插值。 (2) 要求要求p(x)滿足滿足 為最小的問題稱為數(shù)據(jù)擬為最小的問題稱為數(shù)據(jù)擬合（曲線擬合）合（曲線擬合）0| )()(|max0 iinixpxf0| )()(|max0 iinixpxf niiixpxf02| )()(|汪遠征汪遠征 設設 0, 1, , n線性無關(guān)線性無關(guān), 令令 = span 0, 1, , n為簡單函數(shù)類為簡單函數(shù)類, 其中其中 0, 1, , n稱為稱為 的基函數(shù)。的基函數(shù)。 逼近問題即用逼近問題即用p(x) = a0 0(x) + a1 1(x) +

3、 an n(x)來做逼近來做逼近, 問題歸結(jié)為求其中的待定系數(shù)問題歸結(jié)為求其中的待定系數(shù)a0, a1, , an。汪遠征汪遠征 【定義定義1】設區(qū)間設區(qū)間a, b上定義的函數(shù)上定義的函數(shù)f(x)在在n+1個互異點個互異點a x0 x1 . xn b的函數(shù)值為的函數(shù)值為y0, y1, ., yn, 若存在一個次若存在一個次數(shù)不超過數(shù)不超過n的多項式的多項式pn(x)滿足條件：滿足條件：pn(xi) = yii = 0, 1, 2, , n(3.1)則稱則稱pn(x)為函數(shù)為函數(shù)f(x)的的n次插值多項式次插值多項式 按條件按條件(3.1)求函數(shù)求函數(shù)f(x)近似表達式近似表達式pn(x)的方法稱

4、為插值法的方法稱為插值法, 條件條件(3.1)稱為插值條件稱為插值條件 點點xi (i = 0, 1, 2, , n)稱為插值節(jié)點稱為插值節(jié)點 區(qū)間區(qū)間a, b稱為插值區(qū)間稱為插值區(qū)間汪遠征汪遠征 【定義定義1】設區(qū)間設區(qū)間a, b上定義的函數(shù)上定義的函數(shù)f(x)在在n+1個互異點個互異點a x0 x1 . xn b的函數(shù)值為的函數(shù)值為y0, y1, ., yn, 若存在一個次若存在一個次數(shù)不超過數(shù)不超過n的多項式的多項式pn(x)滿足條件：滿足條件：pn(xi) = yii = 0, 1, 2, , n(3.1)則稱則稱pn(x)為函數(shù)為函數(shù)f(x)的的n次插值多項式次插值多項式 幾何意義：

5、曲線幾何意義：曲線y = pn(x)與曲線與曲線y = f(x)在平面上相交于在平面上相交于n+1個互異的點個互異的點(xi, yi) (i = 0, 1, 2, , n).汪遠征汪遠征 【定理定理1】存在唯一存在唯一pn(x) Pnx滿足插值條件滿足插值條件(3.1)證明：設證明：設pn(x) = a0 + a1x + anxn 滿足插值條件滿足插值條件pn(xi) = yii = 0, 1, 2, , n 從而只需求解線性方程組從而只需求解線性方程組pn(xi) = a0 + a1xi + anxin = yi (i = 0, 1, 2, , n) (3.2)(3.2)的系數(shù)行列式為范德蒙

6、行列式：的系數(shù)行列式為范德蒙行列式：nnnnnnnxxxxxxxxxV111),.,(110010 niijjixx110)(汪遠征汪遠征 【定理定理1】存在唯一存在唯一pn(x) Pnx滿足插值條件滿足插值條件(3.1)證明：證明：只需求解線性方程組只需求解線性方程組pn(xi) = a0 + a1xi + anxin = yi (i = 0, 1, 2, , n) (3.2)(3.2)的系數(shù)行列式為范德蒙行列式：的系數(shù)行列式為范德蒙行列式：因為因為x0, x1, , xn互異互異, 所以所以Vn 0。即。即(3.2)存在唯一解存在唯一解, 從而從而存在唯一的存在唯一的pn(x) Pnx 滿

7、足插值條件滿足插值條件(3.1)。 niijjinnnnnnnxxxxxxxxxxxV110110010)(111),.,(汪遠征汪遠征 【例例1 】給定數(shù)據(jù)給定數(shù)據(jù)求次數(shù)不大于求次數(shù)不大于3的插值多項式的插值多項式p3(x)解：設解：設p3(x) = a0 + a1x + a2x2 + a3x3依題意有依題意有解之得：解之得：a0 = 10, a1 = 5, a2 = 5, a3 = 2即有即有 p3(x) = 10 + 5x 5x2 +2x3 35)5()5()5(4)2()2()2(7)1()1()1(7)1()1()1(332210332210332210332210aaaaaaaaa

8、aaaaaaa汪遠征汪遠征 【例例1 】給定數(shù)據(jù)給定數(shù)據(jù)求次數(shù)不大于求次數(shù)不大于3的插值多項式的插值多項式p3(x)注：注：(1) 范德蒙矩陣的條件數(shù)很大范德蒙矩陣的條件數(shù)很大 誤差大計算量大誤差大計算量大(2) 選擇適當基函數(shù)使插值多項式具特殊形式選擇適當基函數(shù)使插值多項式具特殊形式汪遠征汪遠征 所求的插值多項式所求的插值多項式pn(x)是線性空間是線性空間Pnx中的一個點中的一個點, 而而Pnx的基是不唯一的。因此的基是不唯一的。因此, n次代數(shù)插值多項式次代數(shù)插值多項式pn(x)可以寫可以寫成多種形式成多種形式. 由線性空間的不同基底出發(fā)由線性空間的不同基底出發(fā), 構(gòu)造滿足插值條件的多項

9、式構(gòu)造滿足插值條件的多項式的方法稱為基函數(shù)法。的方法稱為基函數(shù)法。汪遠征汪遠征 由線性空間的不同基底出發(fā)由線性空間的不同基底出發(fā), 構(gòu)造滿足插值條件的多項式構(gòu)造滿足插值條件的多項式的方法稱為基函數(shù)法。的方法稱為基函數(shù)法。 基函數(shù)法求插值多項式的步驟：基函數(shù)法求插值多項式的步驟： 1) 定義定義n+1個線性無關(guān)的特殊多項式個線性無關(guān)的特殊多項式插值基函數(shù)：插值基函數(shù)： 2) 根據(jù)插值條件確定插值多項式的系數(shù)根據(jù)插值條件確定插值多項式的系數(shù)a0, ., an)(,),(),(10 xxxn )()()()(1100 xaxaxaxpnnn 汪遠征汪遠征 (1) n = 1時時. 設設yi = f(

10、xi) i = 0, 1.作直線方程：作直線方程： 令：令：稱稱L1為兩點式插值或線性插值。為兩點式插值或線性插值。)(001010 xxxxyyyy )()()(1000101001xxyxxyxxyxx )()(1011001xxyxxyxx .)(101001011yxxxxyxxxxxL 汪遠征汪遠征 (1) n = 1時時. 設設yi = f(xi) i = 0, 1.令：令：稱稱L1為兩點式插值或線性插值。為兩點式插值或線性插值。 【例例1】設設 的函數(shù)表的函數(shù)表求求f(175)的近似值。的近似值。解：解：x0 = 169, x1 = 225, y0 = 13, y1 = 15。.

11、)(101001011yxxxxyxxxxxL xxf )(151312225169144xx1516922516913225169225)(1 xxxL汪遠征汪遠征 (1) n = 1時時. 設設yi = f(xi) i = 0, 1.令：令：稱稱L1為兩點式插值或線性插值。為兩點式插值或線性插值。 【例例1】設設 的函數(shù)表的函數(shù)表求求f(175)的近似值。的近似值。解：解：.)(101001011yxxxxyxxxxxL .214285.131751751 Lxxf )(151312225169144xx1516922516913225169225)(1 xxxL汪遠征汪遠征 (2) n

12、= 2時時. 設設yi = f(xi) i = 0, 1, 2. 令：令：稱稱L2為三點式插值或拋物插值。為三點式插值或拋物插值。 【例例1】計算計算 。解解：x0 = 144, x1 = 169, x2 = 225, y0 = 12, y1 = 13, y2 = 15 13.23158 2120210121012002010212)()()()()()(yxxxxxxxxyxxxxxxxxyxxxxxxxxxL 175 15)169225)(144225()169175)(144175(13)225169)(144169()225175)(144175(12)225144)(169144()

13、225175)(169175(1751752 L汪遠征汪遠征 【定義定義2】滿足滿足 (3.3)次數(shù)不大于次數(shù)不大于n的多項式的多項式li(x)稱為以稱為以x0, ., xi-1, xi+1, ., xn為節(jié)點為節(jié)點的的Lagrange插值基函數(shù)。插值基函數(shù)。注：因為注：因為n個節(jié)點個節(jié)點x0, ., xi-1, xi+1, ., xn是是li(x)的零點的零點所以可設所以可設 li(x) = bi(xx0).(xxi-1)(xxi+1).(xxn)又由又由li(xi) = 1, 得得即即 ijijxlijji01)( ).()().(1110niiiiiiixxxxxxxxb nijjjij

14、niiiiiiniiixxxxxxxxxxxxxxxxxxxxxl0110110).()().().()().()(汪遠征汪遠征 【定義定義2】滿足滿足 (3.3)次數(shù)不大于次數(shù)不大于n的多項式的多項式li(x)稱為以稱為以x0, ., xi-1, xi+1, ., xn為節(jié)點為節(jié)點的的Lagrange插值基函數(shù)。插值基函數(shù)。注：即注：即(j = 0, 1, ., n) nijjjijniiiiiiniiixxxxxxxxxxxxxxxxxxxxxl0110110).()().().()().()( ijijxlijji01)( 汪遠征汪遠征 【定義定義3】令令 (3.4)則易知則易知(3.4

15、)所示的所示的pn(x)為次數(shù)不大于為次數(shù)不大于n的多項式的多項式, 且滿足插值且滿足插值條件條件(3.1): (j = 0, 1, ., n)稱稱Ln(x)為為Lagrange插值多項式。插值多項式。注：注：n = 1時稱為線性插值：時稱為線性插值：L1(x) = l0(x)y0 + l1(x)y1 ninijjjijiniiinxxxxyxlyxL000)()(jnijiijnyxlyxL 0)()(1010)(xxxxxl 0101)(xxxxxl 汪遠征汪遠征 【定義定義3】令令 (3.4)則易知則易知(3.4)所示的所示的pn(x)為次數(shù)不大于為次數(shù)不大于n的多項式的多項式, 且滿足

16、插值且滿足插值條件條件(3.1): (j = 0, 1, ., n)稱稱Ln(x)為為Lagrange插值多項式。插值多項式。注：注：n = 2時稱為拋物插值：時稱為拋物插值：L2(x) = l0(x)y0 + l1(x)y1 + l2(x)y2)()()(2010210 xxxxxxxxxl )()()(2101201xxxxxxxxxl )()()(1202102xxxxxxxxxl ninijjjijiniiinxxxxyxlyxL000)()(jnijiijnyxlyxL 0)()(汪遠征汪遠征 【例例3】已知離散數(shù)據(jù)如下：已知離散數(shù)據(jù)如下： (1) 求以求以x2 =0, x3 =1為

17、節(jié)點的線性插值多項式為節(jié)點的線性插值多項式, 并預測并預測x =0.3時時f 的近似值。的近似值。 (2) 求以求以x1 = -1, x2 = 0, x3 = 1為節(jié)點的二次插值多項式為節(jié)點的二次插值多項式, 并預并預測測x = 0.3時時f 的近似值。的近似值。汪遠征汪遠征 【例例3】已知離散數(shù)據(jù)如下：已知離散數(shù)據(jù)如下： (1) 求以求以x2 =0, x3 =1為節(jié)點的線性插值多項式為節(jié)點的線性插值多項式, 并預測并預測x =0.3時時f 的近似值。的近似值。解解:(1) 線性插值多項式是：線性插值多項式是：由于由于L1(0.3) = 0.3+1 = 1.3, 所以當所以當x=0.3時時f

18、的近似值為的近似值為1.3。232332321)(xxxxyxxxxyxL 01021011 xx汪遠征汪遠征 【例例3】已知離散數(shù)據(jù)如下：已知離散數(shù)據(jù)如下： (2) 求以求以x1 = -1, x2 = 0, x3 = 1為節(jié)點的二次插值多項式為節(jié)點的二次插值多項式, 并預并預測測x = 0.3時時f 的近似值。的近似值。由于由于L2(0.3)=1.2475, 所以當所以當x = 0.3時時f 的近似值為的近似值為1.2475。)01)(1(1()0)(1(2)10)(1(0()1)(1(1)11)(01()1)(0(5 . 0)(2 xxxxxxxL)1()1()1(25. 02 xxxxx

19、175. 025. 02 xx汪遠征汪遠征 Matlab代碼代碼function s=lagrange1(x0, y0)syms xn = length(x0); s = 0;for k = 1:n xp = x0(1:k-1 k+1:n); yp = prod(x-xp)./(x0(k)-xp); s = s + yp*y0(k);ends = vpa(s, 2)s = sym(s)s = simple(s);汪遠征汪遠征 Matlab代碼代碼function yh=lagrange2(x0, y0, xh)n = length(x0); m = length(xh);yh=zeros(1,

20、 m);for k = 1:m for i = 1:n xp = x0(1:i-1 i+1:n); yp = prod(xh(k)-xp)./(x0(i)-xp); yh(k) = yh(k) + yp*y0(i); endend汪遠征汪遠征 設設pn(x)為函數(shù)為函數(shù)f(x)關(guān)于給定節(jié)點關(guān)于給定節(jié)點x0, x1, ., xn上的上的n次插值多次插值多項式。項式。 稱稱Rn(x) = f(x) pn(x)為插值余項為插值余項 【定理定理2】設設f(x)在插值區(qū)間在插值區(qū)間a, b上存在上存在n + 1階導數(shù)階導數(shù), 則對則對于任意于任意x a, b, 存在存在 = (x) (a, b), 使使

21、 (3.5)()!1()()()()(1)1(xnfxpxfxRnnnn 汪遠征汪遠征 【定理定理2】設設f(x)在插值區(qū)間在插值區(qū)間a, b上存在上存在n + 1階導數(shù)階導數(shù), 則對則對于任意于任意x a, b, 存在存在 = (x) (a, b), 使使 (3.5)證明：顯然證明：顯然Rn(xi) = 0, (i = 0, 1, 2, , n), 所以所以Rn(xi)至少有至少有n + 1個零點個零點, 故可設故可設作輔助函數(shù)作輔助函數(shù))()!1()()()()(1)1(xnfxpxfxRnnnn )()()()()(10 xxKxxxKxRnniin niinxtxKtptft0)()(

22、)()()( 汪遠征汪遠征 【定理定理2】設設f(x)在插值區(qū)間在插值區(qū)間a, b上存在上存在n + 1階導數(shù)階導數(shù), 則對則對于任意于任意x a, b, 存在存在 = (x) (a, b), 使使 (3.5)證明：設證明：設作輔助函數(shù)作輔助函數(shù)則則 (t)在在a, b上具有上具有n+1階導數(shù)階導數(shù), 且有且有n+2個互異的零點：個互異的零點：x0, x1, ., xn, x)()!1()()()()(1)1(xnfxpxfxRnnnn )()()()()(10 xxKxxxKxRnniin niinxtxKtptft0)()()()()( )()()()()(10 xxKxxxKxRnnii

23、n 汪遠征汪遠征 【定理定理2】設設f(x)在插值區(qū)間在插值區(qū)間a, b上存在上存在n + 1階導數(shù)階導數(shù), 則對則對于任意于任意x a, b, 存在存在 = (x) (a, b), 使使 (3.5)證明：作輔助函數(shù)證明：作輔助函數(shù)則則 (t)在在a, b上具有上具有n+1階導數(shù)階導數(shù), 且有且有n+2個互異的零點：個互異的零點：x0, x1, ., xn, x由羅爾定理由羅爾定理, 存在存在 (a, b)使使)()!1()()()()(1)1(xnfxpxfxRnnnn niinxtxKtptft0)()()()()( )()()()()1(1)1()1( nnnnnxKpf)(0)1( n

24、)()()()()(10 xxKxxxKxRnniin 汪遠征汪遠征 【定理定理2】設設f(x)在插值區(qū)間在插值區(qū)間a, b上存在上存在n + 1階導數(shù)階導數(shù), 則對則對于任意于任意x a, b, 存在存在 = (x) (a, b), 使使 (3.5)證明：由證明：由羅爾定理羅爾定理, 存在存在 (a, b)使使 f (n+1)( ) K(x)(n + 1)! = 0 )()!1()()()()(1)1(xnfxpxfxRnnnn )()()()()1(1)1()1( nnnnnxKpf)(0)1( n)!1()()()1( nfxKn )()()()()(10 xxKxxxKxRnniin

25、汪遠征汪遠征 【定理定理2】設設f(x)在插值區(qū)間在插值區(qū)間a, b上存在上存在n + 1階導數(shù)階導數(shù), 則對則對于任意于任意x a, b, 存在存在 = (x) (a, b), 使使 (3.5)注：注：(1) 通常余項估計：通常余項估計：(3.6)其中其中 (3.7)| )(|)!1(| )(|11xnMxRnnn | )(|max)1(,1xfMnbaxn | )(|max)!1(| )(|max1,1xnMxRnbaxnn )()!1()()()()(1)1(xnfxpxfxRnnnn 汪遠征汪遠征 【定理定理2】設設f(x)在插值區(qū)間在插值區(qū)間a, b上存在上存在n + 1階導數(shù)階導數(shù)

26、, 則對則對于任意于任意x a, b, 存在存在 = (x) (a, b), 使使 (3.5)注：注：(2) 對于指定對于指定x, 應取靠近應取靠近x的的n+1個節(jié)點作插值個節(jié)點作插值, 以使以使| n+1(x)|較小較小)()!1()()()()(1)1(xnfxpxfxRnnnn 汪遠征汪遠征 【例例4】利用余項公式估計例利用余項公式估計例1中的中的L1(175)和例和例2中的中的L2(175)的誤差的誤差, 并做比較。并做比較。解解 因為因為 所以所以于是于是,83)(,41)()(2523 xxfxxxf422516921014. 1| )169(| )(|max fxfMx62251

27、4431051. 1| )144(| )(|max fxfMx2211071. 1)225175)(169175(! 2)( MxR3321034. 2)225175)(169175)(144175(! 3)( MxR. )()!1()(11xnMxRnnn 13.21428513.230158汪遠征汪遠征 L插值的缺點：每增加一個新節(jié)點插值的缺點：每增加一個新節(jié)點, 其插值基函數(shù)其插值基函數(shù)li(x)要重要重新計算新計算, 能否充分利用已有結(jié)果呢？能否充分利用已有結(jié)果呢？ 為此作基函數(shù)：為此作基函數(shù)：即將即將pn(x)表示為：表示為： (3.8)這樣這樣, 當增加一個新節(jié)點時當增加一個新節(jié)點

28、時, 只需增加一個新項只需增加一個新項 1,.,2 , 1 , 0)()()(1)(10nixxxxxiii 10102010)(.)()(1)(-niinnxxcxxxxcxxccxp 10)(-niinxxc汪遠征汪遠征作基函數(shù)：作基函數(shù)：即將即將pn(x)表示為：表示為： (3.8) 例如例如N1(x) = c0 + c1(x x0)N2(x) = c0 + c1(x x0) + c2(x x0)(x x1) 1,.,2 , 1 , 0)()()(1)(10nixxxxxiii 10102010)(.)()(1)(-niinnxxcxxxxcxxccxp汪遠征汪遠征即將即將pn(x)表示

29、為：表示為： (3.8) 利用插值條件利用插值條件(5.1-1)可得可得 c0 = f0 稱為一階差商稱為一階差商稱為二階差商稱為二階差商 10102010)(.)()(1)(-niinnxxcxxxxcxxccxppn(xi) = f(xi) = fi,10010101011xxfxxffxxcfc 121020121002021202021022,)()(xxxxfxxfxxxxfxxffxxxxxxccfc ,210 xxxf 汪遠征汪遠征即將即將pn(x)表示為：表示為： (3.8) c0 = f0稱為一階差商稱為一階差商稱為二階差商稱為二階差商稱為稱為i階差商階差商 (i = 1,

30、2, , n),.,.,.,1011210210iiiiiiiixxxfxxxxxxfxxxxfc ,2101210202xxxfxxxxfxxfc ,10010101011xxfxxffxxcfc 10102010)(.)()(1)(-niinnxxcxxxxcxxccxp汪遠征汪遠征 注：差商的基本性質(zhì)如下：注：差商的基本性質(zhì)如下： (1) i階差商階差商f x0, x1, , xi可表為可表為f(x0), f(x1), , f(xi)的線性的線性組合組合 (2) 差商具有對稱性差商具有對稱性, 即差商與它所含節(jié)點的排列順序無關(guān)即差商與它所含節(jié)點的排列順序無關(guān) iknkkkkkkkixxx

31、xxxxxxfxxxf011010).()().()(,.,.,.,.,.,.,.,00kijkjixxxxfxxxxf ,.,.,.,1011210210iiiiiiiixxxfxxxxxxfxxxxfc 汪遠征汪遠征 注：差商的基本性質(zhì)如下：注：差商的基本性質(zhì)如下： (2) 差商具有對稱性差商具有對稱性, 即差商與它所含節(jié)點的排列順序無關(guān)即差商與它所含節(jié)點的排列順序無關(guān)從而從而,.,.,.,.,.,.,00kijkjixxxxfxxxxf 1121021010,.,.,., iiiiiiixxxxxxfxxxxfxxxf,.,0211iiixxxxxf 00211211,.,.,xxxxx

32、xfxxxxfiiiiii 011011,.,.,xxxxxfxxxfiiii ,.,.,.,1011210210iiiiiiiixxxfxxxxxxfxxxxfc 汪遠征汪遠征 注：差商的基本性質(zhì)如下：注：差商的基本性質(zhì)如下： (2) 差商具有對稱性差商具有對稱性, 即差商與它所含節(jié)點的排列順序無關(guān)即差商與它所含節(jié)點的排列順序無關(guān)從而從而差商表差商表01101110,.,.,.,xxxxxfxxxfxxxfiiiii ,.,.,.,.,.,.,00kijkjixxxxfxxxxf 汪遠征汪遠征 注：差商的基本性質(zhì)如下：注：差商的基本性質(zhì)如下： (2) 差商具有對稱性差商具有對稱性, 即差商與

33、它所含節(jié)點的排列順序無關(guān)即差商與它所含節(jié)點的排列順序無關(guān)差商表差商表例例汪遠征汪遠征 有了差商的定義有了差商的定義, 可以證明可以證明表為表為 pn(x) = f0 +f x0, x1(x x0) + +f x0, x1, , xn(xx0)(xx1)(xxn-1) (3.9)稱稱(3.9)為為Newton插值多項式插值多項式, 記為記為 Nn(x) = f0 +f x0, x1(x x0) + +f x0, x1, , xn(xx0)(xx1)(xxn-1) 10102010)(.)()(1)(niinnxxcxxxxcxxccxp汪遠征汪遠征 【例例5】已知函數(shù)已知函數(shù)y = f(x)的數(shù)

34、據(jù)表如下的數(shù)據(jù)表如下求求(1) 次數(shù)不大于次數(shù)不大于3的插值多項式的插值多項式p3(x)通過前通過前4個數(shù)據(jù)點個數(shù)據(jù)點 (2) 次數(shù)不大于次數(shù)不大于4的插值多項式的插值多項式p4(x)通過所給通過所給5個數(shù)據(jù)點個數(shù)據(jù)點, 并并計算計算f (4.0)的近似值。的近似值。解：計算差商表如下：解：計算差商表如下：xif i一階差商一階差商二階差商二階差商三階差商三階差商四階差商四階差商1.014.22.717.82.1183.222.08.4002.8554.838.210.1250.821-0.5355.651.716.8752.8130.6870.266汪遠征汪遠征 【例例5】已知函數(shù)已知函數(shù)y

35、 = f(x)的數(shù)據(jù)表如下的數(shù)據(jù)表如下求求(1) 次數(shù)不大于次數(shù)不大于3的插值多項式的插值多項式p3(x)通過前通過前4個數(shù)據(jù)點個數(shù)據(jù)點 (2) 次數(shù)不大于次數(shù)不大于4的插值多項式的插值多項式p4(x)通過所給通過所給5個數(shù)據(jù)點個數(shù)據(jù)點, 并并計算計算f (4.0)的近似值。的近似值。解：解：(1) N3(x)=14.2+2.118(x1.0)+2.855(x1.0)(x2.7) 0.535(x 1.0)(x 2.7)(x 3.2)汪遠征汪遠征 【例例5】已知函數(shù)已知函數(shù)y = f(x)的數(shù)據(jù)表如下的數(shù)據(jù)表如下求求(1) 次數(shù)不大于次數(shù)不大于3的插值多項式的插值多項式p3(x)通過前通過前4個

36、數(shù)據(jù)點個數(shù)據(jù)點 (2) 次數(shù)不大于次數(shù)不大于4的插值多項式的插值多項式p4(x)通過所給通過所給5個數(shù)據(jù)點個數(shù)據(jù)點, 并并計算計算f (4.0)的近似值。的近似值。解：解：(2) N4(x)=14.2+2.118(x1.0)+2.855(x1.0)(x2.7) 0.535(x 1.0)(x 2.7)(x 3.2) + 0.266(x1.0)(x2.7)(x3.2)(x4.8)汪遠征汪遠征 將將x看成與看成與x0, x1, ., xn互異的節(jié)點互異的節(jié)點, 則按則按Newton插值公式得插值公式得上式令上式令t = x, 則因為則因為f(x) = Nn+1(x) (插值條件插值條件) niinn

37、iinnxtxxxxfxtxxxfxtxxfftN010101001001)(,.,)(,.,.)(,)( niinniinxxxxxxfxxxxxfxxxxffxf01010100100)(,.,)(,.,.)(,)(汪遠征汪遠征 由余項公式由余項公式(3.5)知知 niinniinxxxxxxfxxxxxfxxxxffxf01010100100)(,.,)(,.,.)(,)( niinnxxxxxxfxN010)(,.,)()(,.,)(,.,)()()(110010 xxxxxfxxxxxxfxNxfxRnnniinnn )!1()(,.,)1(10 nfxxxxfnn 汪遠征汪遠征(3

38、.10)!)(,.,)(10kfxxxfkk )!1()(,.,)1(10 nfxxxxfnn 汪遠征汪遠征 【例例6】設設f(x)=ex, 給出給出f(x)在在0, 1上上n+1個等距節(jié)點處的函個等距節(jié)點處的函數(shù)值數(shù)值 (1) 若按所給的函數(shù)值表用線性插值求若按所給的函數(shù)值表用線性插值求f (x) = ex, （0 x 1）的近似值的近似值, 使其絕對誤差限不大于使其絕對誤差限不大于 , 問問n應取多大應取多大 (2) 每個表值每個表值f(xi)應取幾位有效數(shù)字應取幾位有效數(shù)字),.,2 , 1 , 0(ninixi 61021 汪遠征汪遠征 【例例6】設設f(x)=ex, 給出給出f(x)

39、在在0, 1上上n+1個等距節(jié)點處的函個等距節(jié)點處的函數(shù)值數(shù)值 (1) 若按所給的函數(shù)值表用線性插值求若按所給的函數(shù)值表用線性插值求f (x) = ex, （0 x 1）的近似值的近似值, 使其絕對誤差限不大于使其絕對誤差限不大于 , 問問n應取多大應取多大解：解：(1) 由于由于x 0, 1, 故必有一個故必有一個i, 使得使得xi-1 x xi若若p1(x)是是f(x)在在xi-1, xi上的線性插值多項式上的線性插值多項式, 且用且用p1(x)的值的值作為作為f(x) = ex的近似值的近似值, 則由則由(3.7)及及| )(|max)!1(| )(|max1,1xnMxRnbaxnn

40、eexfxxx 1010max| )(|max211)(41| )( |max1 iiiixxxxxxxxxii),.,2 , 1 , 0(ninixi 61021 汪遠征汪遠征 【例例6】設設f(x)=ex, 給出給出f(x)在在0, 1上上n+1個等距節(jié)點處的函個等距節(jié)點處的函數(shù)值數(shù)值 (1) 若按所給的函數(shù)值表用線性插值求若按所給的函數(shù)值表用線性插值求f (x) = ex, （0 x 1）的近似值的近似值, 使其絕對誤差限不大于使其絕對誤差限不大于 , 問問n應取多大應取多大解：解：(1) 由由(3.7)及及有有由此解得由此解得n 824。| )(|max)!1(| )(|max1,1x

41、nMxRnbaxnn eexfxxx 1010max| )(|max6221110218)(41! 21| )(| neexxxRii211)(41| )( |max1 iiiixxxxxxxxxii),.,2 , 1 , 0(ninixi 61021 汪遠征汪遠征 【例例6】設設f(x)=ex, 給出給出f(x)在在0, 1上上n+1個等距節(jié)點處的函個等距節(jié)點處的函數(shù)值數(shù)值 (1) 若按所給的函數(shù)值表用線性插值求若按所給的函數(shù)值表用線性插值求f (x) = ex, （0 x 1）的近似值的近似值, 使其絕對誤差限不大于使其絕對誤差限不大于 , 問問n應取多大應取多大解：解：(1) 由此解得由

42、此解得n 824。造表時一個合適的選取是造表時一個合適的選取是n = 1000。此時步長為。此時步長為0.001。6221110218)(41! 21| )(| neexxxRii),.,2 , 1 , 0(ninixi 61021 汪遠征汪遠征 【例例6】設設f(x)=ex, 給出給出f(x)在在0, 1上上n+1個等距節(jié)點處的函個等距節(jié)點處的函數(shù)數(shù)值值 (2) 每個表值每個表值f(xi)應取幾位有效數(shù)字應取幾位有效數(shù)字解：解：(2) 因因0 x 1, 有有1 ex e, 即個位數(shù)非零即個位數(shù)非零, 由有效數(shù)位由有效數(shù)位的概念知的概念知, 每個表值至少應有每個表值至少應有7位有效數(shù)字。位有效

43、數(shù)字。61021 ),.,2 , 1 , 0(ninixi 汪遠征汪遠征 當節(jié)點等距時當節(jié)點等距時, 稱為等距插值節(jié)點。稱為等距插值節(jié)點。 此時差商此時差商 的分母為一個常數(shù)的分母為一個常數(shù) 可以期望可以期望Newton插值公式可以簡單一些插值公式可以簡單一些 設有設有n+1個等距插值節(jié)點個等距插值節(jié)點, 為步長。為步長。ikikkixxffxxf ,),.,2 , 1 , 0( ,0nkkhxxk nxxhn0 汪遠征汪遠征 設有設有n+1個等距插值節(jié)點個等距插值節(jié)點, 為步長。為步長。 【定義定義4】設設fk = f(xk), 則則 稱稱 為為f在在x=xk處的一階向前差分處的一階向前差分

44、, 稱為向前差稱為向前差分算子。分算子。 稱稱 為為f在在x=xk處的一階向后差分處的一階向后差分, 稱為向后差稱為向后差分算子。分算子。),.,2 , 1 , 0( ,0nkkhxxk nxxhn0 kkkfff 1 1 kkkfff汪遠征汪遠征 【定義定義4】設設fk = f(xk), 則則 稱稱 為為f 在在x=xk處的一階處的一階向前差分向前差分 稱稱 為為f 在在x=xk處的一階處的一階向后差分向后差分 稱稱 為為f在在x=xk處的處的m階向前差分階向前差分 稱稱 為為f在在x=xk處的處的m階階向后差分向后差分注：注： 由歸納法由歸納法, 可證：可證：kmkmkmfff111 11

45、1 kmkmkmfffmkmkmff kkkfff 122212 kkkfff)()(112kkkkffff kkkfff 1 1 kkkfff汪遠征汪遠征注：注： 差商與差分有如下關(guān)系：差商與差分有如下關(guān)系： (3.11)事實上：事實上： k = 1成立成立, 設設 （k時成立）時成立）, 則當則當k + 1時時kmkmkmfff111 kkkhkfxxxf!,010 kkkkkhkfxxxf!,01 ,0010110hfxxffxxf kkkhkfxxxf!,010 011011110,.,.,.,xxxxxfxxxfxxxxfkkkkkk hkhkfhkfkkkk)1(!01 101)!

46、1( kkkhkff 101)!1( kkhkf 汪遠征汪遠征注：注： 差商與差分有如下關(guān)系：差商與差分有如下關(guān)系： (3.11)事實上：事實上： k = 1成立成立, 設設 （k時成立）時成立）, 則當則當k + 1時時由歸納法原理由歸納法原理, 對所有自然數(shù)對所有自然數(shù)k成立。成立。kmkmkmfff111 101)!1( kkhkf ,.,110 kkxxxxfkkkhkfxxxf!,010 kkkhkfxxxf!,010 kkkkkhkfxxxf!,01 ,0010110hfxxffxxf kkkhkfxxxf!,010 汪遠征汪遠征注：注： 差分與導數(shù)的關(guān)系：差分與導數(shù)的關(guān)系：事實上

47、：事實上：).()(0 kkkfhf .,0kxx ,!100kkkxxxfhkf kkkhkfxxxf!,010 ).(!)(!)()( kkkkfhkfhk 汪遠征汪遠征注：注： 差分表差分表44332214433422232243133212211440433032202100432 iiiiiiiiiffffffffffffffffffffffffffffffffff 汪遠征汪遠征 設設 插值點插值點( ).則則 牛頓插值公式中的一般項化為：牛頓插值公式中的一般項化為：).,.,2 , 1 , 0( ,0nkkhxxk ).0( ,0 tthxx0,00 hxxtnxxhn).,.,2

48、 , 1 , 0( ,)(nkhktxxk kkjkkkjjkhjthkfxxxxxf 1001010)(!)(, 100)(!kjkjtkf 20nxxx 汪遠征汪遠征 設設 插值點插值點( ).則則 牛頓插值公式中的一般項化為：牛頓插值公式中的一般項化為：從而從而(3.9)表示為表示為 (3.12)20nxxx 1001010)(!)(,kjkkjjkjtkfxxxxxf 101000)(!)()(kjnkknnjtkffthxNxN 101100)(,)()(kjjnkknxxxxxfxfxN).,.,2 , 1 , 0( ,0nkkhxxk ).0( ,0 tthxx0,00 hxxt

49、nxxhn).,.,2 , 1 , 0( ,)(nkhktxxk 汪遠征汪遠征從而從而(3.9)表示為表示為 (3.12)稱稱(3.12)為牛頓前插公式。其余項：為牛頓前插公式。其余項：以差分近似表示導數(shù)。以差分近似表示導數(shù)。 101000)(!)()(kjnkknnjtkffthxNxN njnnjjnnjtnfxxnfthxR0010)1(0)()!1()()!1()()( 汪遠征汪遠征 設設 記記( )則則 (3.12)稱稱(3.12)為牛頓后插公式。為牛頓后插公式。).,.,2 , 1 , 0( ,nkkhxxnkn ).0( , tthxxn0,0 hxxtnxxhnn.)(hktx

50、xkn ).,.,2 , 1 , 0(nk . )(!)(101 kjnknknnnjtkffthxNnnxxx 2汪遠征汪遠征 僅滿足條件僅滿足條件(3.1)的插值多項式還不能全面反映被插值函數(shù)的插值多項式還不能全面反映被插值函數(shù)f(x)的性態(tài)的性態(tài), 許多實際問題不但要求插值函數(shù)在某些節(jié)點或全許多實際問題不但要求插值函數(shù)在某些節(jié)點或全部節(jié)點上與部節(jié)點上與f(x)的導函數(shù)值也相等的導函數(shù)值也相等, 甚至要求高階導數(shù)也相等甚至要求高階導數(shù)也相等. 這種插值問題就是厄米特插值問題這種插值問題就是厄米特插值問題 只討論較為簡單的情形只討論較為簡單的情形汪遠征汪遠征 【定義定義5】已知已知 i =

51、0, 1, , n, 求插值多項式求插值多項式H(x)滿足：滿足： i = 0, 1, , n (3.13)則稱則稱H(x)為厄米特為厄米特(Hermite)插值多項式。插值多項式。注：注： 1) H(x)與與f(x)的圖形在的圖形在n+1個節(jié)點處相切個節(jié)點處相切.2) 插值條件有插值條件有2(n+1)個。故個。故H(x)的次數(shù)的次數(shù)2n+1.特別特別: n=1時有時有2個節(jié)點個節(jié)點, 3次多項式次多項式 )()(iiiixfyxfy iiiiyxHyxH)()(兩點三次兩點三次Hermite插值插值汪遠征汪遠征 設設令令其中其中 為三次多項式為三次多項式, 滿足：滿足： 101010)()(

52、yyxfyyxfxxx ).()()()()(11110000 xyxyxyxyxH )(),(xxii jijixji01)( 0)()( iijixx jijixji01)( . 0)()( jiiixx x0 x1汪遠征汪遠征令令其中其中 為三次多項式為三次多項式, 滿足：滿足：則易知則易知H(x)滿足厄米特插值條件。滿足厄米特插值條件。 101010)()(yyxfyyxfxxx ).()()()()(11110000 xyxyxyxyxH )(),(xxii 0)(0)(0)(1)(10001000 xxxx 0)(0)(1)(0)(11011101xxxx 0)(1)(0)(0)(

53、10001000 xxxx 1)(0)(0)(0)(11011101xxxx 汪遠征汪遠征 由由 , 考慮考慮li(x) 二重零點二重零點, 考慮考慮li2(x) .又又 三次多項式三次多項式, 考慮考慮其中其中a, b待定。待定。 jijixji01)( 22)()()()( jijiixxxxbaxxlbaxx 0)(0)(0)(1)(10001000 xxxx 0)(0)(1)(0)(11011101xxxx 汪遠征汪遠征考慮考慮其中其中a, b待定。待定。因為因為1= i(xi) = axi+b, 22)()()()( jijiixxxxbaxxlbaxx jijijjijixxxxx

54、xbaxxxxxax 1)(2)(2 jiiixxax 2)(0 ijxxa 2 0)(0)(0)(1)(10001000 xxxx 0)(0)(1)(0)(11011101xxxx 汪遠征汪遠征考慮考慮其中其中a, b待定。待定。因為因為1= i(xi) = axi+b, 22)()()()( jijiixxxxbaxxlbaxx ijxxa 2ijiixxxaxb 211jiixxx 21 0)(0)(0)(1)(10001000 xxxx 0)(0)(1)(0)(11011101xxxx 汪遠征汪遠征考慮考慮其中其中a, b待定。待定。22)()()()( jijiixxxxbaxxlb

55、axx ijxxa 2jiixxxb 21)1 , 0()21()(2 ixxxxxxxxxjijjiii 0)(0)(0)(1)(10001000 xxxx 0)(0)(1)(0)(11011101xxxx 汪遠征汪遠征同理可得同理可得)1 , 0()21()(2 ixxxxxxxxxjijjiii ).1 , 0()(2 ixxxxxxxjijii .2121)(20101121010020100111210110003 xxxxxxyxxxxxxyxxxxxxxxyxxxxxxxxyxH).()()()()(11110000 xyxyxyxyxH 汪遠征汪遠征注：注： 一般地一般地, n

56、+1個節(jié)點個節(jié)點2n+1次厄米特插值公式：次厄米特插值公式： .2121)(20101121010020100111210110003 xxxxxxyxxxxxxyxxxxxxxxyxxxxxxxxyxH).()()()()(11110000 xyxyxyxyxH 103)()(iiiiixyxyH niiiiinxyxyxH012)()()( 汪遠征汪遠征注：注： 一般地一般地, n+1個節(jié)點個節(jié)點2n+1次厄米特插值公式：次厄米特插值公式：其中其中 （i=0, 1, , n）. niiiiinxyxyxH012)()()( nikkkikiiiinijjijiiixxxxxlxlxxxxl

57、xxxxx0202)()()()()(1)(21()( 103)()(iiiiixyxyH 汪遠征汪遠征 【例例1】設設 , 求求H3(x).解：解：x0=1, x1=2, y0=2, y1=3, y0 = 0, y1 = -1, 103221iiffx221011000)2)(12()21()( xxxxxxxxxxx 220100111)1)(25()21()( xxxxxxxxxxx 2210100)2)(1()()( xxxxxxxxx 2201011)1)(2()()( xxxxxxxxx ).()()()()(11110000 xyxyxyxyxH 汪遠征汪遠征 【例例1】設設 ,

58、 求求H3(x).解：解：x0=1, x1=2, y0=2, y1=3, y0 = 0, y1 = -1, H(x)=2 0(x)+3 1(x) - 1(x)= -3x3+13x2-17x+920)2)(12()( xxx 21)1)(25()( xxx 20)2)(1()( xxx 21)1)(2()( xxx ).()()()()(11110000 xyxyxyxyxH 103221iiffx汪遠征汪遠征 設設R3(x) = f(x) - H3(x) 【定理定理5.1】設設f(4)在在x0, x1上連續(xù)上連續(xù), 則則 x x0, x1有有 (x0, x1)證明：證明：R3(xi) = R3

59、(xi) = 0 (i = 0, 1)可設可設R3(x) = K(x)(x x0)2(x x1)2令令 (t) = f(t) H3(t) K(x)(t x0)2(t x1)2 五個零點五個零點由羅爾定理由羅爾定理, (x0, x1) 使使 (4)( ) = 0即即 f(4)( ) K(x)4! = 0 2120)4(3)()(! 4)()(xxxxfxR ! 4)()()4( fxK 汪遠征汪遠征 n+1個節(jié)點個節(jié)點2n+1次厄米特插值公式：次厄米特插值公式：其中其中 （i = 0, 1, , n） n+1個節(jié)點個節(jié)點2n+1次厄米特插值公式的余項表達式為：次厄米特插值公式的余項表達式為： (

60、a, b) niiiiniiiiiinyxlxxyxlxxxlxH020212)()()()(21()( nikkkikixxxxxl0)( njjnnnxxnfxHxfxR02)22(1212)()!22()()()()( 汪遠征汪遠征 為使插值更準確為使插值更準確, 插值節(jié)點之間間距應較小插值節(jié)點之間間距應較小, 即增加節(jié)點即增加節(jié)點, 此時插值多項式的次數(shù)增高此時插值多項式的次數(shù)增高高次插值。高次插值。function f=runge(n)p=10.0/nx=-5:p:5;y=1./(1+x.2);xh=-5:0.25:5;yh=lagrange2(x, y, xh);x1=-5:0.2