第五章 插值與擬合 (1)

1、第第 五五 章章 插值與擬合插值與擬合5.1 插值的基本概念插值的基本概念5.2 Lagrange插值插值5.3 Newton插值插值5.4 差分與等距節(jié)點插值差分與等距節(jié)點插值5.5 Hermite插值插值5.6 分段低次插值分段低次插值5.7 三次樣條插值三次樣條插值5.8 曲線擬合的最小二乘法曲線擬合的最小二乘法思考問題思考問題1、有哪些問題涉及到插值、有哪些問題涉及到插值2、插值條件、插值條件3、兩點如何插值，如何構造插值函數(shù)、兩點如何插值，如何構造插值函數(shù)4、各種插值方法及插值條件、各種插值方法及插值條件5、插值本質(zhì)、插值本質(zhì)6、如何構造、如何構造Sinx函數(shù)的近似函數(shù)函數(shù)的近似函數(shù)

2、5.1 插值的基本概念插值的基本概念插值問題的背景插值問題的背景 在生產(chǎn)和實驗中，在生產(chǎn)和實驗中，函數(shù)函數(shù) f(x)或者其表達式不便或者其表達式不便于計算于計算, 或者或者無表達式而只有函數(shù)在給定點的函數(shù)無表達式而只有函數(shù)在給定點的函數(shù)值值(或其或其導數(shù)值導數(shù)值) ，此時我們希望建立一個簡單的而，此時我們希望建立一個簡單的而便于計算的近似函數(shù)便于計算的近似函數(shù) ( (x) )，來逼近函數(shù)來逼近函數(shù) f( (x) )。 常用的函數(shù)逼近方法有：常用的函數(shù)逼近方法有： 插值法；插值法； 最小二乘法（或稱均方逼近）；最小二乘法（或稱均方逼近）； 一致逼近等。一致逼近等。5.1 插值的基本概念插值的基本

3、概念已經(jīng)測得在某處海洋不同深度處的水溫如下：深度（M） 466 741 950 1422 1634水溫（oC）7.04 4.28 3.40 2.54 2.13根據(jù)這些數(shù)據(jù)，希望合理地估計出其它深度（如500米，600米，1000米）處的水溫舉例這就是本章要討論的“插值問題”插值法插值法 插值法是函數(shù)逼近的重要方法之一，有著廣泛的應用。簡單地說，插值法就是用給定的(未知)函數(shù) f(x)的若干點上的函數(shù)值(或其導數(shù)值) 來構造 f (x)的近似函數(shù)(x)，要求(x)與 f(x)在給定點的函數(shù)值相等。 有很多種插值法，其中以拉格朗日(Lagrange)插值和牛頓(Newton)插值為代表的多項式插值

4、最有特點，常用的插值還有Hermite插值，分段插值和樣條插值。函數(shù)可以未知，函數(shù)可以未知，只需已知若干點只需已知若干點上的值。上的值。設設 f(x)為為a，b上的上的函數(shù)，函數(shù)，在互異點在互異點x0 , x1, . , xn 處處的函數(shù)值分別為的函數(shù)值分別為 f(x0) , f (x1) , , f (xn) ,構造一個簡單函構造一個簡單函數(shù)數(shù) (x) 作為函數(shù)作為函數(shù) f(x) 的近似表達式的近似表達式y(tǒng)= f(x) (x),使使 (xi)f(xi) , i0, 1, 2, ,n (5.0)則稱則稱 (x) 為關于節(jié)點為關于節(jié)點x0 , x1, . , xn的的插值函數(shù)插值函數(shù)；稱；稱 x

5、0 , x1, . , xn 為為插值節(jié)點插值節(jié)點；稱；稱(xi, f (xi), i=1,2, , n 為為插值點插值點；f(x) 稱為稱為被插值函數(shù)被插值函數(shù)。 (5.0)式稱為式稱為插值條件插值條件。這類問題稱為這類問題稱為插值問題插值問題。 構造出構造出 ( (x) )，對，對 f( (x) )在在 a, ,b 上函數(shù)值的計算，就轉(zhuǎn)化為上函數(shù)值的計算，就轉(zhuǎn)化為 ( (x) )在在對應點上的計算。對應點上的計算。插值法的定義插值法的定義5.2 Lagrange插值插值 選用代數(shù)多項式作為插值函數(shù)。Lagrange插值就是選用節(jié)點上的函數(shù)值作為插值條件。5.2.1 線性插值線性插值 給定兩

6、個點(x0，y0)，(x1，y1），x0 x1，確定一個一次多項式插值函數(shù)，簡稱線性插值線性插值。待定系數(shù)法待定系數(shù)法 設 L1(x)=a0+a1x, 代入插值點當x0 x1時，方程組的解存在唯一。01000111aa xyaa xy即插值條件：L1(xi)= f(xi)=yi,i=0,1解之得解之得， 因此，因此， （5.1）式稱為一次Lagrange插值插值。 由求解過程知，用待定系數(shù)法，需要求解線性方程組，當已知節(jié)點較多時，即方程的未知數(shù)多，計算量較大，不便向高階插值推廣。011001010101,.x yx yyyaaxxxx0110011010101010110( )(5.1)x y

7、x yyyL xxxxxxxxxxyyxxxx插值基函數(shù)法插值基函數(shù)法 分別構造兩個節(jié)點上的一次函數(shù)，使其在本節(jié)點上的函數(shù)值為1，而在其他節(jié)點上的函數(shù)值為0。設l0(x), l1(x)分別為滿足上述條件的一次函數(shù)，即 或簡單地記為 對于過兩個節(jié)點x0 , x1的線性插值（5.1），令00100111()1,()0()0,()1lxl xlxl x1,()0,.ijijijlxij01010110( ), ( ),xxxxlxl xxxxx顯然， l0(x), l1(x) 滿足：線性插值函數(shù)可以寫成節(jié)點上函數(shù)值的線性組合，即 L1(x) = l0(x) y0 + l1(x) y1 稱l0(x),

8、 l1(x) 分別為x0, x1的插值基函數(shù)。線性插值誤差線性插值誤差定理定理 1 設L1(x)為一次Lagrange插值函數(shù), 若 f (x) 一階連續(xù)可 導，f “(x)在(a, b)上存在，則對任意給定的x(a ,b), 至少存在一點(a,b),使得證明證明 因為L(xi)= f(xi),i=0,1,所以，R1(x0)=R1(x1)=0, 即 x0,x1為R1(x)的兩個根。因此，可設R1(x)為(), ,0,1.ijijl xi j易知滿足插值條件：L1(xi) = yi , i=0,11101( )( )( )( )()()(5.3)2!fR xf xL xxxxx可設 R1(x)

9、= k(x)(x-x0)(x-x1). 固定任一 x，作輔助函數(shù)，令 則 (xi )=0, i =1,2, (x)=0, 即 (t)有3個零點x0, x1, x。 假定，x0 x x1 , 分別在x0，x和x，x1上應用洛爾（Rolle）定理，可知， (t)在每個區(qū)間上至少存在一個零點，1，2，使(1)=0，(2)=0(此即(t)有2個零點)。再利用洛爾定理知， (t)在1,2上至少有一個零點，使 ()=0。 對 (t)求2階導數(shù)得， (t) = f (t) - -2!k(x), 因為 ()=0，所以，有 k(x) = f () / /2!。 證畢。101( )( )( )( )()(),tf

10、 tL tk x txtx5.2.2 二次插值二次插值 給定3個互異插值點(xi, f (xi), i = 0,1,2，確定一個二次插值多項式函數(shù)，即拋物線插值（如圖）。待定系數(shù)法 設L2(x)=a0+a1x+a2x2, 代入3個插值條件： L2(xi)= f(xi), i = 0,1,2，解線形方程組可得a0, a1, a2。 插值基函數(shù)法插值基函數(shù)法 構造3個節(jié)點上2次插值基函數(shù) l0(x), l1(x), l2(x), 使?jié)M足 li(xj)=ij ， i, j = 0,1,2。 因為l0(x) 為2次插值基函數(shù), 且l0(x1) = l0(x2) = 0, 所以可設 l0(x) = A

11、(x - x1)(x - x2)。 由條件：l0(x0) = 1，得同理可得，二次Lagrange插值多項式為01021,()()Axxxx1200102()()( ).()()xxxxlxxxxx02011210122021()()()()( ),( ).()()()()x xx xx xx xl xl xxxxxxxxx220011220( )( ) ()( ) ()( ) ()( ) ()(5.4)iiiLxlx f xl x f xlx f xl x f x 容易驗證滿足插值條件二次插值的誤差二次插值的誤差22012( )( )( )( )()()()(5.5)3!fRxf xLxxx

12、xxxx 定理定理 設設L2(x)為二次Lagrange插值函數(shù), 若 f (x) C3a，b ， 則任給x(a ,b),至少存在一點=(x) (a,b),使 提示提示：因為R2(x0)=R2(x1)=R2(x2)=0,可設 作輔助函數(shù) 易知，x0, x1, x2, x為(t)的4個零點，在4個點兩兩組成的區(qū) 間上，應用Rolle定理，然后再反復應用Rolle定理即得證。 2012( )( )()()().Rxk x xxxxxx2012( )( )( )( )()()(),tf tL tk x txtxtx例例5.1 給定sin11=0.190809,sin12=0.207912,求線性插

13、值，并計算sin1130和sin1030 。解解 x0= 11, x1= 12, y0= 0.190809, y1= 0.207912， sin1130L1(11.5)=0.199361, sin1030L1(10.5)=0.182258.由定理1知，誤差為10101(12)(11)( )(12)(11).11 1212 11xxL xyyx yxy準確值為：sin1130=0.199368sin1030=0.182236101( )sin( )( )()()(11)(12).2!2fR xxxxxxx11( )(11)(12)21(11.5 11)(11.5 12)0.125.2R xxx0

14、111 1211.522xxx例例5.2 給定sin11=0.190809,sin12=0.207912, sin13=0.224951,構造二次插值，并計算 sin1130。 解解 x0= 11, x1= 12, x2= 13, y0= 0.190809, y1= 0.207912,y2= 0.224951， sin1130L2(11.5) = 0.199369, sin1130= 0.199368. sin1130L1(11.5)=0.199361,2(12)(13)(11)(13)( )0.1908090.207912(11 12)(11 13)(12 11)(12 13)(11)(12

15、)0.224951(13 12)(13 12)xxxxLxxx 例例5.3 要制作三角函數(shù)sin x的值表，已知表值有四位小數(shù)，要求用線性插值引起的截斷誤差不超過表值的舍入誤差，試確定其最大允許的步長。解解 f(x)=sin x, 設xi, xi為任意兩個插值節(jié)點，最大允許步長記為 h = hi = xi xi，111111121124( )sin( )()()()()2!211()()()()22221()(),88110 ,0.02.82iiiiiiiiiiiiiiiifR xxxxxxxxxxxxxxxxxxxhxxxxhh5.2.3 n次次Lagrange插值多項式插值多項式 已知 n

16、+1個互異插值節(jié)點 (xi, f(xi), i=0, 1, 2, , n , 研究n次插值多項式的存在性及其表示形式。 存在性存在性 設 n 次多項式為 代入插值點，即插值條件：Pn (xi) = f (xi), i = 0, 1,2, , n , 得 其范德蒙德(Vandermonde)行列式為：20121( ),(5.6)nnnP xaa xa xa x20102000201121112012()()(5.6)()nnnnnnnnnnaa xa xa xf xaa xa xa xf xaa xa xa xf x 所以，(5.6)的解存在唯一。 解出(5.6)的解a0 , a1, , an

17、，代入(5.6)1即得 n 次插值多項式Pn(x)。 n 次插值多項式的構造次插值多項式的構造 有上面的討論知，用待定系數(shù)法要求解一個線性方程組，計算量大，實際中不可取。20002111012011(,)1()0,nnnnnnnijj i nxxxxxxV xxxxxxxx 插值基函數(shù)法插值基函數(shù)法 分別構造x0 , x1, , xn 上的 n 次插值基函數(shù) l0(x), l1(x), , ln(x),滿足性質(zhì)： 即1,0,1,2,()0ijijijnl xij， 節(jié)點基函數(shù)x0 x1x2xnl0(x)1000l1(x)0100l2(x)0010ln(x)0001先構造 l0(x)。有上表知，

18、 x1 , x2, , xn 為 l0(x) 的零點，設由l0(x0)=1，得同理可設由li (xi)=1，得0012( )()()(),nlxaxxxxxx001020120010201,()()()()()()( ).()()()nnnaxxxxxxxxxxxxlxxxxxxx011( )()()()(),iiiinl xa xxxxxxxx1111,()()()()iiiiiinaxxxxxxxx于是，所以我們得到 n 次Lagrange插值多項式： 容易驗證， Ln(xi) = f (xi), i = 0, 1, 2, n.0110111()()()()( )()()()(),1,2,

19、(5.7)iiniiiiiinnjijjj ixxxxxxxxl xxxxxxxxxxxinxx00110( )( ) ()( ) ()( ) ()( ) ()(5.8)nnnniiiLxlx f xl x f xlx f xl x f x例例5.4 已知插值點 (-2.00,17.00), (0.00,1.00), (1.00,2.00), (2.00,17.00), 求三次插值，并計算 f (0.6)。解解 先計算4個節(jié)點上的基函數(shù)：1230010203()()()( )()()()(0)(1.00)(2.00)( 2.000)( 2.00 1.00)( 2.002.00)1(1)(2),

20、24xxxxxxlxxxxxxxxxxx xx 0231101213()()()1( )(2)(1)(2),()()()4xxxxxxl xxxxxxxxxx0132202123()()()1( )(2) (2),()()()3xxxxxxlxxx xxxxxxx 三次Lagrange插值多項式為： f (0.6) L3(0.6) = -0.472.0123303132()()()1( )(2) (1).()()()8xxxxxxlxxx xxxxxxx3171( )(1)(2)(2)(1)(2)244217(2) (2)(2) (1).38L xx xxxxxxx xxx x n 次插值多項

21、式的誤差次插值多項式的誤差 定理定理 2 2 設Ln(x)是a,b上過插值點(xi, f(xi)的 n 次 Lagrange插值多項式，節(jié)點xi兩兩互異，若 f(x)Cn+1a,b, 則 x a,b,存在=(x) a,b,使得 證明提示：因為Rn(xi)=0, i =0, 1, 2, , n, 令 作輔助函數(shù) 顯然， (t)有 n+2 個零點x0，x1，xn，x，反復應用Rolle 定理，由(n+1)()=0,定理得證。(1)01( )( )()()()(5.9)(1)!nnnfRxxxxxxxn01( )( )()()().nnRxk x xxxxxx01( )( )( )( )()()()

22、,nntf tL tk x txtxtx n 次插值多項式的幾點說明次插值多項式的幾點說明 若| f (n+1)(x)|M,xa,b,則由(5.9)得 當 f(x)為不高于n次的多項式時，因為Rn(x)=0,則 Ln(x) = f (x). 特別地，取 f(x) = xk, k = 0,1,2,n, 則 令 k =0，可知 n 次Lagrange基函數(shù)li(x)滿足0( )(5.12)(1)!nniiMRxxxn 即 f(x)為不超過n次的多項式時，插值多項式就是被插函數(shù)本身00( )( ) ()( )( ),0,1,2, .nnkkniiiiiiLxl x f xl x xf xxkn0(

23、)1.niil x 實際計算中，如果 f (x)的形式未知，也就無法求出 f (n+1)(x)或估計出其較精確的上界。所以也就無法估計|Rn(x)|。 我們采用事后估計，即給定 n+2個節(jié)點，x0, x1, xn, xn+1,構造兩個n次插值多項式Ln(x)和 ，用它們來估計|Rn(x)|。 由定理 2，得( )nLx( )0121nLxnnxxxxx ( )nLx (1)101()( )( )()()()(5.13)(1)!nnnff xLxxxxxxxn(1)211()( )( )()()()(5.14)(1)!nnnnff xLxxxxxxxn假定 f (n+1)(x) 在 a, b內(nèi)連

24、續(xù), 且變化不大, 即 f (n+1)(1) f (n+1)(2).(5.13)和(5.14)兩式相除，得解之得，于是，得誤差01( )( ),( )( )nnnf xLxxxxxf xLx100110( )( )( ).nnnnnxxxxf xLxLxxxxx001( )( )( )( )( )(5.16)nnnnnxxRxf xLxLxLxxx事后估計：即用求出的插值多項式來估計誤差。所以我們得到 n 次Lagrange插值多項式： 0110111()()()()( )()()()(),1,2,(5.7)iiniiiiiinnjijjj ixxxxxxxxl xxxxxxxxxxxinxx

25、00110( )( ) ()( ) ()( ) ()( ) ( )(5.8)nnnniiiL xlx f xl x f xlx f xl x f x n 次插值多項式的算法描述次插值多項式的算法描述 輸入節(jié)點數(shù) n、插值點(xi, yi) (i=0,1,2, ,n)和要計算的函數(shù)點 x。 實現(xiàn)基函數(shù) li(x)和插值 Ln(x): FOR i=0,1, , n tmp=1; FOR j=0, 1, , i1, i+1, , n tmp=tmp*(xxj)/(xixj); (實現(xiàn) li(x) ) fx=fx+tmp*yi; (實現(xiàn)Ln(x) ) 輸出 fx。5.3 Newton插值插值 Lagr

26、ange插值的優(yōu)缺點：插值的優(yōu)缺點： 優(yōu)點：優(yōu)點：形式整齊、規(guī)范，理論上保證插值存在唯一性。 缺點：缺點：計算量大、不具有承襲性。 函數(shù)未知時，無法計算其精度5.3.1 差商及其性質(zhì)差商及其性質(zhì)一階差商一階差商：f (x)關于點x0，x1的一階差商記為 f x0, x1，二階差商：二階差商： f (x)關于點x0，x1， x2的二階差商記為 f x0, x1, x2,010101()(),.f xf xf xxxx011201202,.f xxf x xf xx xxx 一般地，k 階差商 f x0, x1, xn 定義為： 差商的性質(zhì)差商的性質(zhì) 性質(zhì)性質(zhì)1 k 階差商 f x0, x1, x

27、k可表成節(jié)點上函數(shù)值 f(x0), f(x1), , f(xk) 的線性組合，即 例如例如，k = 2時， (5.17)011120110,.kkkkkf xxxf x xxf xxxxxx0101101,().()()()()kkiiiiiiikif xxxf xxxxxxxxx011201202012010210122021,()()().()()()()()()f xxf x xf xx xxxf xf xf xxxxxxxxxxxxx性質(zhì)性質(zhì) 2 各階差商具有對稱性, 即改變差商中節(jié)點的次序不會 改變差商的值。設i0, i1, , ik為0, 1, , k的任一排列, 則 由性質(zhì)1知，

28、任意改變節(jié)點的次序，只改變(5.17)式右端求和的次序，故其值不變。例如,由定義知，性質(zhì)性質(zhì) 3 若 f (x)為 n 次多項式，則一階差商 f x, xi為n 1次 多項式。 由定義令x = xi, 則分子為0, 說明分子中含有因子x xi, 與分母約去。0101,.kkiiif xxxf xxx01011001()(),.f xf xf xxf x xxx( )() ,.iiif xf xf x xxx性質(zhì)性質(zhì) 4 若 f (x)在 a, b 存在 n +1階導數(shù)，xi a, b , i = 0,1,n, 固定 xa, b, 則 n+1 階差商與導數(shù) 存在如下關系：(1)01( ) ,(

29、, ).(1)!nnff x xxxa bn 差商的計算差商的計算 由差商的定義由差商的定義 一階差商是由節(jié)點上函數(shù)值定義的，二階差商是由一階差商定義的，依此構造差商表：i xi f (xi) 一階差商一階差商 二階差商二階差商 三階差商三階差商 n 階差商階差商0 x0 f (x0)1 x1 f (x1) f x0, x12 x2 f (x2) f x1, x2 f x0, x1, x23 x3 f (x3) f x2, x3 f x1, x2, x3 f x0, x1, x2, x3 n xn f (xn) f xn 1, xn f xn 2, xn 1, xn f xn 3, xn f

30、x0, x1, , xn例例5.5 計算 (2, 17), (0, 1), (1, 2), (2, 19)的一至三階差商。i xi f (xi) f xi 1, xi f xi 2, xi 1, xi f xi 3, xi 2, xi 1, xi0 2 171 0 1 2 1 2 3 2 19 例例5.5 計算 (2, 17), (0, 1), (1, 2), (2, 19)的一至三階差商。解解 由表易知， f x0, x1 = f 2, 0 = 8 f x0, x1, x2 = f 2, 0, 1 =(8 1)/(2 1) = 3 f x0, x1, x2, x3 = f 2, 0, 1,

31、2 =(3 8)/(2 2) = 5/4i xi f (xi) f xi 1, xi f xi 2, xi 1, xi f xi 3, xi 2, xi 1, xi0 2 171 0 1 82 1 2 1 33 2 19 17 8 5/4 由差商與導數(shù)的關系（性質(zhì)由差商與導數(shù)的關系（性質(zhì)4）例例 5.6 對 f (x) = x7x4+3x+1， 求 f 20,21， f x,20,21,26 和 f x,20,21,27。解解 顯然， f (7) (x) = 7!, f (8) (x) = 0, 由性質(zhì)4得(7)016( ) ,2 ,2 ,2 1,7!ff x(8)017( ) ,2 ,2 ,

32、2 0.8!ff x01(1)(2)4 1192 ,2 115,1 21fff5.3.2 Newton插值插值 線性插值線性插值 給定兩個插值點(x0, f(x0), (x1, f(x1), x0 x1, 設 N1(x) = a0 + a1(x x0) 直線的點斜式直線的點斜式 代入插值點得， 于是得線性Newton插值公式010010101()()(),.f xf xaf xaf xxxx10010( )(),()(5.18)N xf xf xxxx由插值的唯一性知，L1(x)與 N1(x)為同一多項式，只是表達形式不同而已。 二次二次Newton插值插值 給定三個互異插值點(xi, f (

33、xi), 設代入插值條件： N2(xi) = f (xi), i =0,1,2, 得二次Newton插值公式為2010201( )()()().Nxaa xxaxxxx0010120012022021020101221(),()(),()()(),.af xaf xxf xf xf xxxxaxxxxf xxf xxf xx xxx2001001201( )(),(),()()(5.19)Nxf xf xxxxf xx xxxxx n 次次Newton插值公式插值公式 給定n+1個插值點(xi, f(xi), i = 0, 1, 2, n, xi互異， 類似地，有二階至 n 階差商的定義得(x

34、x0)(xx0)(xx1) (xx0)(xxn1) 上述所有n +1個等式相加，得000( )()() ,f xf xxxf x x000( )() ,f xf xf x xxx00110101012201201010 ,() , ,() , ,() ,nnnnf x xf xxxxf x xxf x xxf xx xxxf x xx xf x xxf xxxxxf x xx其中，插值誤差為：000101012011010101( )()() ,()() ,()()() ,()()() ,( )( ).nnnnnnf xf xxxf xxxxxxf xx xxxxxxxf xxxxxxxxxf

35、 x xxxNxRx00010101201101( )()() ,()() ,()()() ,nnnNxf xxxf xxxxxxf xx xxxxxxxf xxx0101010( )()()() , ,().nnnnniiRxxxxxxxf x xxxf x xxxxxn次Newton插值公式容易驗證，Newton插值滿足插值條件： Nn(xi) = f (xi), i = 0, 1, 2, n. 關于關于Lagrange插值和插值和Newton插值的幾點說明插值的幾點說明1.由插值的唯一性質(zhì)，Ln(x) = Nn(x)。因此，他們的誤差也相同，即當 f(x)Cn+1a, b時，有 故得差商

36、的性質(zhì)4 此外，比較Nn(x) 和Ln(x) 中xn的系數(shù)，即得性質(zhì)1。(1)0100( ) ,()()(1)!nnnniiiiff x xxxxxxxn(1)01( ) , , ,( , )(1)!nnff x xxxxa ba bn 差商的性質(zhì)差商的性質(zhì) 性質(zhì)性質(zhì)1 k 階差商 f x0, x1, xk可表成節(jié)點上函數(shù)值 f(x0), f(x1), , f(xk) 的線性組合，即 例如例如，k = 2時， (5.17)0101101,().()()()()kkiiiiiiikif xxxf xxxxxxxxx011201202012010210122021,()()().()()()()(

37、)()f xxf x xf xx xxxf xf xf xxxxxxxxxxxxx 2. 牛頓插值的誤差不要求函數(shù)的高階導數(shù)存在，所以更具有一般性。它對 f(x)是由離散點給出的函數(shù)情形或 f(x)的導數(shù)不存在的情形均適用。3. 引入記號: f x0 = f (x0) , t0(x) = 1, t1(x) = x x0, t2(x) = (x x0)(x x1), , tn(x) = (x x0)(x x1) (x xn1)， 于是 n 次Newton插值公式可表為稱 t0(x), t1(x), t2(x), , tn(x) 為Newton插值的基函數(shù)，而且滿001010100( )( ) (

38、 ) ,( ) ,( ) ,nnnniiiNxtx f xt x f xxtx f xxxt x f xx 足如下關系： ti(x) = ti1(x)(x xi1), i =1,2, n； ti(xj) = 0， j i， ti(xj) 0，j i。4. Newton插值具有承襲性質(zhì)，即5. Newton插值公式的計算量 乘：1+2+ (n1)+ n = n(n+1)/2 除：n + (n1)+ 2+1 = n(n+1)/2第 i 個節(jié)點以后非零101( )( )( ) ,.kkkkNxNxtx f xxx(1)n n例例 5.7 給定四個插值點(2,17), (0,1), (1,2), (2

39、,19), 計算 N2(0.9), N3(0.9)。解解 x0= 2，x1=0，x2=1，x3=2，由例5.5知， f x0, x1 = 8， f x0, x1, x2 = 3，f x0, x1, x2, x3 = 5/4，所以， N2(0.9) = 17 8(0.9+2)+3(0.9+2)0.9 = 1.63; N3(0.9) = N2(0.9)+1.250.9(0.9+2)(0.9 1)= 1.30375.2000101012( )()() ,()() ,178(2)3(2) .Nxf xxxf xxxxxxf xx xxxx320120123( )( )()()() ,5178(2)3(

40、2)(2) (1).4NxNxxxxxxxf xx xxxxxxx x Newton插值的算法插值的算法 用牛頓插值公式，首先要計算各階差商值，然后再計算插值。牛頓插值由承襲性質(zhì)容易實現(xiàn)，關鍵是實現(xiàn)差商。 1. 輸入初始數(shù)據(jù):節(jié)點數(shù) n, 插值點序列xi，f(xi), i =0,1,2, n, 及要計算的函數(shù)點u； 2. 形成差商表 g k, k =1,2, , n ;（ g k = f x0,xk） 3. 形成插值基函數(shù)及插值 t =1, newton = f(x0) 對 i =1,2, , n t = (uxi1) t ; (由tk = (uxk1)tk 1 形成(ux0) (uxi1)

41、) newton = newton + tgi 4. 輸出牛頓插值 Nn(u)=newton。 牛頓插值公式中只用到差商表中對角線上的差商，即 f x0, f x0, x1, f x0, x1, x2, , f x0, x1, xn.可以分別用一維數(shù)組 gi 來存放這些差商，i = 0, 1, 2, , n.形成差商具體步驟：形成差商具體步驟：(1) 對gi初始化，即 gi = f (i), i = 0, 1, 2, , n.(2) 除了g0(即 f (x0) 以外，其余函數(shù)值在計算一階差商后 不再使用，因此可用來存放一階差商，即 g j = f xj 1, xj, j = n, n 1, 2

42、, 1(3) 類似地，計算二階差商后，除g 1 = f x0, x1外, 其余一 階差商也不再使用, 可用g j存放二階差商 f xj 2, xj 1, xj, 即 g j = f xj 2, xj 1, xj, j = n, n 1, 2，(4) 最后， gn = f x0, x1, , xn. 差商表差商表程序 1 計算差商算法：計算差商算法： for i = 0 to n gi = f (xi) for k = 1 to n for j = n to k g j = (g j g j 1)/(xj xj k) 5.4 差分與等距節(jié)點插值差分與等距節(jié)點插值 設插值節(jié)點為等距節(jié)點：設插值節(jié)點

43、為等距節(jié)點： 其中，其中，h稱為步長，函數(shù)稱為步長，函數(shù) 在在 的函數(shù)值為的函數(shù)值為 。 5.4.1 差分及性質(zhì)差分及性質(zhì) 一階差分一階差分: ； 二階差分二階差分: 一般地，一般地，m階差分用階差分用m-1階差分來定義：階差分來定義： k0 xxkh ( )yf x kx()kkyf x kk 1kyyy ()()2kk 1kk 2k 1k 1kyyyyyyy mm 1m 1kk 1kyyy 以上定義的是前差以上定義的是前差,稱為向前差分算子。稱為向前差分算子。 下面定義向后差分下面定義向后差分,表示向后差分算子：表示向后差分算子： 一般地一般地， 分別稱為一階，二階，分別稱為一階，二階，.

44、 . . ，m階向后差分。階向后差分。kkk 1yyy ()()2kkk 1kk 1k 1k 2yyyyyyy mm 1m 1kkk 1yyy 差分的性質(zhì)差分的性質(zhì) 性質(zhì)性質(zhì)1. (差分與函數(shù)值的關系差分與函數(shù)值的關系)n階差分是階差分是n+1個函個函數(shù)值的線性組合。數(shù)值的線性組合。 證明證明: 用數(shù)學歸納法立即可得。用數(shù)學歸納法立即可得。 性質(zhì)性質(zhì)2. (前差與后差的關系前差與后差的關系) ： 證明：在性質(zhì)證明：在性質(zhì)1的前差中的前差中, 用用k-n取代取代k即得。即得。 ()nniiknk ii 0y1 C y (),nniiknk n ii 0y1 C y nnk nkyy 性質(zhì)性質(zhì)3.

45、 (差分與差商的關系差分與差商的關系) 證明：利用差商性質(zhì)及性質(zhì)證明：利用差商性質(zhì)及性質(zhì)1,得得 性質(zhì)性質(zhì)4. (差分與導數(shù)的關系差分與導數(shù)的關系): 證明：證明：nnk nkyy ,!mkk 1kmkm1f xxxym h ,()()()()()()!()!()()! !()!mk ikk 1k mi 0ikii 1ii 1immmlk ik m lm immi 0l 0mllmmk m lkmml 0yf x xxxxxxxxxxyyiml1i mi1hml l h111 C yym hm h 令令( )( )(,)nnniinyh fx x ( )( )( )!,!( )!nnnnnni

46、ii nfyn h f xxn hh fn 差分的計算差分的計算-由差分的定義由差分的定義一階差分是由節(jié)點上函數(shù)值定義的，二階差分是由一階差分定義的，依此構造差分表：i xi f (xi) 一階差一階差分分 二階差二階差分分 三階差三階差分分 n 階差階差分分0 x0 f (x0) 1 x1 f (x1) f0 2 x2 f (x2) f1 2f03 x3 f (x3) f2 2f1 3f0 n xn f (xn) fn-1 2fn-2 3fn-3 nf0 5.4.2 等距節(jié)點的牛頓插值公式等距節(jié)點的牛頓插值公式 將牛頓插值公式中的差商用差分代替將牛頓插值公式中的差商用差分代替 從而從而,牛頓

47、插值公式在等距插值節(jié)點下的形式為：牛頓插值公式在等距插值節(jié)點下的形式為： -稱牛頓前插公式。稱牛頓前插公式。 余項為：余項為： 下面來推導等距牛頓向后插值公式：下面來推導等距牛頓向后插值公式：()()() ,k00 xxxthxkhtk h ( )()()()!2nn000011Nxyt yt t1yt t1tn1y2n ()()( )( )( )( )()()()!()!n 1n 1n 1nn 1ffR xxht t1tnn 1n 1 令 則 ,于是 -稱牛頓后插公式。稱牛頓后插公式。 余項為：余項為：()nxxthnt0 ()n knn kxxkhxxtk h ( )()()()!2nnn

48、nnn11Nxyt yt t1yt t1tn1y2n ()( )()()()()!n1n1nfRxht t1tnn1 例例: 設設 插值節(jié)點為插值節(jié)點為 相應的函數(shù)值如下表相應的函數(shù)值如下表,求求f(2.2)。 ( )xyf xe ,. ,. ,x1 1 5 2 2 5 3 xiyiyi2 2yi3 3yi4 4yi12.718281.54.481691.7634127.289062.907371.143962.512.182494.793431.886060.74210320.085547.903053.109621.223560.48146 解：精確值解：精確值f(2.2)=e2.2=9.

49、025011, 此時此時 .( . )()!2200018 87232N2 2yt yt t1y2 ( . )( . )()()( . ).!332021N 22N 22t t1 t2yN 220166239038553 ( . )( . )()()().!44301N 22N 22t t1 t2 t3y9022374 . , . , .234R015269R001354R000264 .0 xxth22105tt24 5.5 埃爾米特埃爾米特(Hermite) 插值插值 Hermite插值描述：插值描述： 設 f (x)具有一階連續(xù)導數(shù)，已知節(jié)點上的函數(shù)值和導數(shù)值，即 (xi, f (xi)

50、, (xi, f (xi), i = 0, 1, 2, , n, 若存在 2n+1次多項式 H2n+1(x) 滿足 則稱 H2n+1(x) 為 f (x) 關于節(jié)點xi (i = 0,1,2,n)的Hermite插值多項式。 記 f (xi) = yi, f (xi) = mi, i = 0,1,2,n .2121( )( ),( )( ),0,1,2, .niiniiHxf xHxf xin 三次三次Hermite插值的構造插值的構造 存在性存在性 給定 f (xi) = yi, f (xi) = mi, i = 0, 1. 設 代入插值條件: H3(xi) = f(xi), H3(xi)

51、= f (xi), i =0,1,得2330123( ),Hxaa xa xa x23010203002301121311212030021213112323aa xa xa xyaa xa xa xyaa xa xmaa xa xm230002341110120021111()0.01230123xxxxxxxxxxxx 其解存在唯一其解存在唯一, 解解 出出 a0, a1, a2, a3, 代代入即得入即得 H3(x). 基函數(shù)法基函數(shù)法 每個節(jié)點上對應兩套基函數(shù)：x0: h0(x), g0(x); x1: h1(x), g1(x),滿足 或簡記為 函數(shù)值導數(shù)值x0 x1x0 x1 h0(

52、x) h1(x)g0(x)g1(x)1000010000100001(),()0,0,1()0,(),0,1.ijijijijijijh xh xi jg xg xi j 三次Hermite插值多項式為300110011( )( )( )( )( )(5.22)Hxh x yh x ygx mg x m 先構造 h0(x), 設 h0(x) = (a + bx)(x x1)2 ,為方便計算，可設由h0(x0) = 1, 得 a =1；由 所以，同理設h0(x1)=h0(x1)=0210001( )().xxh xab xxxx00012()0,h xbxx 20100101( )1 2.xxx

53、xh xxxxx20111010( )1 2.xxxxh xxxxx210001( )(),xxgxa xxxxg0(x0)=g0(x1)=0, g0(x1)=0由 g0(x0) =1, 得 a =1。所以注：注：我們知道，過 x0, x1 兩點的Lagrange插值基函數(shù)為 顯然， 于是，三次Hermite插值的基函數(shù)可表為220100110110( )(),( )().xxxxgxxxg xxxxxxx01010110( ),( ).xxxxlxl xxxxx0011011011(),().lxl xxxxx20000021111122000111( )12 ()()( ),( )12 (

54、)()( ),( )()( ),( )()( ).h xlxxxlxh xl xxxlxgxxx lxg xxx lx 三次Hermite插值多項式為 容易驗證，當 f(x)C4a, b時, 三次Hermite插值的誤差為 提示：設 作輔助函數(shù) 固定x a, b，則(t) 有三個零點 x0, x1, x, 且 x0, x1為二重零 點。反復應用Rolle定理可證。300110011( )( )( )( )( )(5.22)Hxh x yh x ygx mg x m3(4)2201( )( )( )( )() () ,( , )(5.23)4!R xf xHxfxxxxa b 2201( )(

55、)() () .R xk x xxxx22301( )( )( )( )() () ,xf tHtk x txtx 高次高次Hermite插值的構造插值的構造插值基函數(shù)法插值基函數(shù)法 給定 n+1個節(jié)點 x0, x1,xn 上的函數(shù)值 f (xi)和導數(shù)值 f(xi) ，可以構造 2n+1 次Hermite插值多項式 滿足 其中，hi(x), gi(x)分別為對應于函數(shù)值和導數(shù)值的不高于 2n+1 次插值基函數(shù)，它們滿足210( ) ( ) ()( )()nniiiiiHxh x f xg x fx2121()(),()(),0,1,2, .niiniiHxf xHxfxin(),()0,0,

56、1, ,()0,(),0,1, .ijijijijijijh xh xi jng xg xi jn完全仿照三次Hermite插值基函數(shù)的求法，可得 容易驗證， Hermite插值的誤差(定理定理)： 當 f(x)C2n+2a, b時, 則存在(a, b), 使 22( )(1 2 ()()( ),(5.24)( )()( ),0,1,2,iiiiiiiih xl xxxlxg xxx lxin01().niiijjj il xxx提示：對li(x)取對數(shù)ln，并注意li(xi)=121(22)22201( )( )( )( )() ()()(5.25)(22)!nnnR xf xHxfxxxx

57、xxn例例5.8 給定 f ( 1)=0, f (1)=4, f ( 1)=2, f (1)=0, 求H3(x), 并計算 f (0.5).解解 x0 = 1, x1 = 1, f(0.5)H3(0.5) = 3.5625.3010110( )( ) 0( ) 4( ) 2( ) 04( )2( ).Hxh xh xgxg xh xgx 221220( 1)11( )12(2)(1) ,1 11 ( 1)411( )( 1)(1)(1) ,1 14xxh xx xxgxxxx 2231( )(2)(1)(1)(1) ,2Hxx xxx例例5.9 給定 f(0) = 1, f(1) = 2, f

58、 (0) = 2, 構造二次插值函數(shù)。解解 (1) 公式法公式法 設 f (1) = m1，由三次Hermite插值公式得， 令 m1 = 0，得到二次Hermite插值函數(shù) P2(x) = x2 + 2x + 1.3010112222122221311( )( )2( )2( )( )0110122 121 00 10 11 0102(0)(1)0 11 0(12 )(1)2(32 )2 (1)(1)(1)Hxh xh xgxm g xxxxxxxxm xx xx xx xm xxm xm221.xx (2) 插值基函數(shù)法插值基函數(shù)法 設節(jié)點 x0上的二次基函數(shù)為t0(x), g0(x),節(jié)

59、點 x1上的二次基函數(shù)為t1(x), 它們滿足 設 由t0(x0) =1,即 b(0 1)=1, 得 b = 1。 由t0(x0) =0,即 a(0 1) + a0 +b=0, 得 a = 1 。所以 同理可設， 分別由條件 001000011101001000()1()0()0()0()1()0()0()0()1txt xgxtxt xgxtxt xgx01( )()(),txaxb xx01( )()(),txa xxaxb20( )(1)(1)1,txxxx 210001( )() ,( )()(),t xa xxgxb xxxx22110010()1, ()1( ), ( ).t xg

60、xt xxgxxx 22010( )( )2 ( )2( )21.P xtxt xgxxx (3) 擴展牛頓法擴展牛頓法 寫成差商表的形式，將帶導數(shù)的節(jié)點X0及其上的函數(shù)值重復一遍，無導數(shù)的節(jié)點X1不重復，即 x f(x) f (x) x0 0 1 x1 0 1 2 X1 x2 1 2 1 1 20010012012( )(),(),()()12( 1)(0)(0)21.P xf xf xxxxf xx xxxxxxxxxx 121212()()1 2,10 1f xf xf x xxx011201202,2 1,10 1f xxf x xf xx xxx 0X 擴展牛頓法擴展牛頓法用牛頓差商