數(shù)字分析 (4)

1、第二章第二章 插值法插值法n2.1 引言 n2.2 拉格朗日插值n2.3 均差與牛頓插值公式n2.4 差分與等距節(jié)點插值n2.5 埃爾米特插值n2.6 分段低次插值n2.7 三次樣條插值2.1 引言引言n在實際問題中，我們會遇到兩種情況n變量間存在函數(shù)關(guān)系，但只能給出一離散點列上的值n變量間的函數(shù)關(guān)系可以表示，但計算復(fù)雜，只能計算特殊點的函數(shù)值n為了研究自變量與因變量間的變化關(guān)系，我們需要建立變量間的函數(shù)關(guān)系，從而可以計算原始數(shù)據(jù)以外需要處的值，這就是我們研究插值的目的。2.1 引言引言n設(shè)函數(shù) 在區(qū)間 上有定義，且 已知在點 上的值 ， ， ， ，若存在一簡單函數(shù) ，使： ， 成立，就稱 為

2、 的插值函數(shù)，點n為了研究自變量與因變量間的變化關(guān)系，我們需要建立變量間的函數(shù)關(guān)系，從而可以計算原始數(shù)據(jù)以外需要處的值，這就是我們研究插值的目的。( )yf x , a b01naxxxb0y1yny( )P x( )iiP xy(0,1, )in( )P x( )f x插值的定義插值的定義n設(shè)函數(shù) 在區(qū)間 上有定義，且 已知在點 上的值 ， ， ， ，若存在一簡單函數(shù) ，使： ， 成立，就稱 為 的插值函數(shù)，點 稱為插值節(jié)點，包含插值節(jié)點的區(qū)間 稱為插值區(qū)間，求插值函數(shù) 的方法稱為插值法。若 是次數(shù)不超過 代數(shù)多項式，即( )yf x , a b01naxxxb0y1yny( )P x( )

3、iiP xy(0,1, )in( )P x( )f x01,nxxx , a b( )P x( )P xn01( )nnP xaa xa x插值的定義插值的定義n其中 為實數(shù)，就稱 為插值多項式，相應(yīng)的插值法稱為多項式插值。若 為分段多項式，就稱為分段插值。若 為三角多項式，就稱為三角插值。n 稱為插值節(jié)點，包含插值節(jié)點的 區(qū)間 稱為插值區(qū)間，求插值函數(shù) 的方法稱為插值法。若 是次數(shù)不超過 代數(shù)多項式，即01,nxxx , a b( )P x( )P xn01( )nnP xaa xa xia( )P x( )P x( )P xn其中 為實數(shù)，就稱 為插值多項式，相應(yīng)的插值法稱為多項式插值。若

4、 為分段多項式，就稱為分段插值。若 為三角多項式，就稱為三角插值。ia( )P x( )P x( )P x插值的幾何意義插值的幾何意義n從幾何上看，插值就是求一條曲線 使其通過給定的 個點 ， 并且與已知曲線有一定的近似度。( )yP x1n( ,)iix y(0,1, )in0 xnxxy0yny( )yf x( )yP x本章的主要內(nèi)容本章的主要內(nèi)容n插值多項式n分段插值函數(shù)n樣條插值函數(shù)n插值多項式的存在唯一性n插值多項式的收斂性n插值的誤差估計2.2 拉格朗日插值拉格朗日插值n2.2.1 線性插值與拋物線插值n2.2.2 拉格朗日插值多項式n2.2.3 插值余項與誤差估計2.2.1 線

5、性插值與拋物線插值線性插值與拋物線插值n線性插值：對兩點 ， ，通過這兩點的插值多項式是一條直線，其方程為：這里的 就是我們所求的線性插值函數(shù)。若記 ， ，則 稱 ， 為關(guān)于 ， 的線性插值基函數(shù) 。 00(,)xy11( ,)x y011010110( )xxxxL xyyxxxx1( )L x1001( )xxlxxx0110( )xxl xxx10 01 1( )( )( )L xy lxy l x0( )lx1( )l x0 x1x2.2.1 線性插值與拋物線插值線性插值與拋物線插值n線性插值與其基函數(shù)示意圖若記 ， ，則 稱 ， 為關(guān)于 ， 的線性插值基函數(shù) 。 1001( )xxl

6、xxx0110( )xxl xxx0( )lx1( )l x0 x1x10 01 1( )( )( )L xy lxy l x2.2.1 線性插值與拋物線插值線性插值與拋物線插值n線性插值與其基函數(shù)示意圖0 x1xxy0y1y( )yf x1( )yL xOxy10( )ylx1( )yl x0 x1xO2.2.1 線性插值與拋物線插值線性插值與拋物線插值n線性插值與其基函數(shù)示意圖xy0 0( )yy lx1 1( )yy l x0 x1xO10 01 1( )( )( )L xy lxy l x0 x1xxy0y1y( )yf x1( )yL xO2.2.1 線性插值與拋物線插值線性插值與拋

7、物線插值n拋物線插值：當(dāng) 時，對于給定的三點：我們可以求出一條通過這三個點的拋物線：其中：稱為關(guān)于點 ， ， 的2次插值基函數(shù)。2n 001122(,),( ,),(,)xyx yxy0201122012010210122021()()()()()()( )()()()()()()xxxxxxxxxxxxL xyyyxxxxxxxxxxxx020112012010210122021()()()()()()( ), ( ), ( )()()()()()()x xx xx xx xx x x xl xl xl xxx xxxxxxxxxx0 x1x2x2.2.1 線性插值與拋物線插值線性插值與拋物

8、線插值n二次插值基函數(shù)示意圖其中：稱為關(guān)于點 ， ， 的2次插值基函數(shù)。020112012010210122021()()()()()()( ), ( ), ( )()()()()()()x xx xx xx xx x x xl xl xl xxx xxxxxxxxxx0 x1x2xn二次插值基函數(shù)示意圖0 x2x1x0( )lx1( )l x2( )lx1Oxy20 01 12 2( )( )( )( )L xy lxy l xy lx拉格朗日插值多項式拉格朗日插值多項式n定義：若 次多項式 在 個節(jié)點 上滿足條件：n就稱這 個 次多項式 為節(jié)點 上的 次插值基函數(shù)。 可以推出： n( )

9、(0,1, )jlxjn1n01nxxx1 ,()0 ,jkkjlxkj( ,0,1, )j kn1nn( ) (0,1, )jlxjn01,nxxxn(0,1, )kn011011()()()()( )()()()()kknkkkkkkknxxxxxxxxlxxxxxxxxx拉格朗日插值多項式拉格朗日插值多項式n從而，插值多項式可表示為：n由基函數(shù)的定義，我們可以算得：n就稱這 個 次多項式 為節(jié)點 上的 次插值基函數(shù)。 可以推出： 1nn( ) (0,1, )jlxjn01,nxxxn(0,1, )kn011011()()()()( )()()()()kknkkkkkkknxxxxxxxx

10、lxxxxxxxxx0( )( )nnk kkL xy lx0()()nnjk kjjkL xy lxy(0,1, )jn拉格朗日插值多項式拉格朗日插值多項式n從而，插值多項式可表示為：n由基函數(shù)的定義，我們可以算得：n多項式 稱為拉格朗日多項式。n引入記號n可以求得n于是得到0( )( )nnk kkL xy lx0()()nnjk kjjkL xy lxy(0,1, )jn( )nL x101( )()()()nnxxxxxxx1011( ) ()()()()nkkkkkkknxxxxxxxxx101( )( )()()nnnkkknkxL xyxxx拉格朗日插值多項式拉格朗日插值多項式n

11、定理：在次數(shù)不超過 的多項式集合 中，滿足插值條件的插值多項式 是存在唯一的。n多項式 稱為拉格朗日多項式。n引入記號n可以求得n于是得到( )nL x101( )()()()nnxxxxxxx1011( ) ()()()()nkkkkkkknxxxxxxxxx101( )( )()()nnnkkknkxL xyxxxnnH( )nnL xH插值多項式的存在唯一定理插值多項式的存在唯一定理n定理：在次數(shù)不超過 的多項式集合 中，滿足插值條件的插值多項式 是存在唯一的。n定理的證明：僅需證明唯一性。反證: 假設(shè)不唯一，即有 和 均滿足插值條件。于是有 對 ， 成立，這表明多項式 有 個零點 ，這

12、與 次多項式只有 個零點矛盾，故只能 。nnH( )nnL xH( )nL x( )nP x( )( )nnnL xP xH1n01,nxxx( )( )0niniL xP x0i 1,nnn( )( )nnL xP x插值多項式的存在唯一定理插值多項式的存在唯一定理n根據(jù)存在唯一性定理，若令 ， ，可得： 若取 ，則 假設(shè)不唯一，即有 和 均滿足插 值條件。于是有 對 ， 成立，這表明多項式 有 個零點 ，這與 次多項式只有 個零點矛盾，故只能 。( )nL x( )nP x( )( )nnnL xP xH1n01,nxxx( )( )0niniL xP x0i 1,nnn( )( )nnL

13、 xP x( )mf xx0,1,mn0( )nmmkkkx lxx0,1,mn0m n根據(jù)存在唯一性定理，若令 ， ，可得： 若取 ，則 ( )mf xx0,1,mn0( )nmmkkkx lxx0,1,mn0m 0( )1nkklx2.2.3 插值余項與誤差估計插值余項與誤差估計n 稱為插值多項式的余項n定理2：設(shè) 在 上連續(xù)， 在 內(nèi)存在，節(jié)點為 是滿足插值條件的插值多項式，則對任何 ，插值余項 這里 且依賴于 ， 如以前定義( )( )( )nnR xf xL x( )( )nfx , a b(1)( )nfx( , )a b01naxxxb( )nL x , xa b(1)1( )(

14、 )( )( )( )(1)!nnnnfR xf xL xxn( , )a bx1( )nx2.2.3 插值余項與誤差估計插值余項與誤差估計n證明：由已知條件得到： 于是有： 是滿足插值條件的插值多項式，則對任何 ，插值余項 這里 且依賴于 ， 如以前定義( )nL x , xa b(1)1( )( )( )( )( )(1)!nnnnfR xf xL xxn( , )a bx1( )nx()0nkR x011( )( )()()()( )( )nnnR xK x xxxxxxK xx(0,1, )knn證明：由已知條件得到： 于是有： 其中 是與 有關(guān)的待定函數(shù)。 現(xiàn)在把 看成一個固定點，作

15、函數(shù) 根據(jù)插值條件及余項定義，可知 在 點 及 處均為零，故 在 ()0nkR x(0,1, )kn011( )( )()()()( )( )nnnR xK x xxxxxxK xx( )K xxx01( )( )( )( )()()()nntf tL tK x txtxtx( ) t01,nxxxx( ) t , a b 上有 個零點，根據(jù)Roll定理， 在 的每兩個零點間至少有一個零點，故 在 內(nèi)至少有 個零點，對 再用 其中 是與 有關(guān)的待定函數(shù)。 現(xiàn)在把 看成一個固定點，作函數(shù) 根據(jù)插值條件及余項定義，可知 在 點 及 處均為零，故 在 ( )K xxx01( )( )( )( )()

16、()()nntf tL tK x txtxtx( ) t01,nxxxx( ) t , a b2n( ) t( ) t( ) t , a b1n( ) t 上有 個零點，根據(jù)Roll定理， 在 的每兩個零點間至少有一個零點，故 在 內(nèi)至少有 個零點，對 再用Roll定理，可知 在 內(nèi)至少有 個零點，依此類推， 在 內(nèi)至少有一個零點，記為 ，使得 且依賴于 于是結(jié)論成立。2n( ) t( ) t( ) t , a b1n( ) t( ) t , a bn(1)( )nt , a b( , )a b(1)(1)( )( )(1)!( )0nnfnK x(1)( )( ),( , )(1)!nfK

17、xa bnxn由于 是不能確定，因此我們并不能確定誤差的大小，但如能求出 ，那么用 逼近 的截斷誤差限是： Roll定理，可知 在 內(nèi)至少有 個零點，依此類推， 在 內(nèi)至少有一個零點，記為 ，使得 且依賴于 于是結(jié)論成立。( ) t , a bn(1)( )nt , a b( , )a b(1)(1)( )( )(1)!( )0nnfnK x(1)( )( ),( , )(1)!nfK xa bnx(1)1max( )nna x bfxM ( )nL x( )f xn由于 是不能確定，因此我們并不能確定誤差的大小，但如能求出 ，那么用 逼近 的截斷誤差限是：n當(dāng) 時，n當(dāng) 時(1)1max(

18、)nna x bfxM ( )nL x( )f x11( )( )(1)!nnnMR xxn1n 12010111( )( )( )( )()(),22R xfxfxxxxx x 2n 230120211( )( )( )( )()()(),66,R xfxfxxxxxxx x n已知 ， ，用線性插值及拋物線插值計算 的值并估計截斷誤差。n當(dāng) 時，n當(dāng) 時11( )( )(1)!nnnMR xxn1n 12010111( )( )( )( )()(),22R xfxfxxxxx x 2n 230120211( )( )( )( )()()(),66,R xfxfxxxxxxx x sin0.

19、320.314567sin0.340.333487sin0.360.352274sin0.3367例例1n已知 ， ，用線性插值及拋物線插值計算 的值并估計截斷誤差。 解：由題意令線性插值時取 ，得插值公式：sin0.320.314567sin0.340.333487sin0.360.352274sin0.33670120.32,0.34,0.36xxx0120.314567,0.333487,0.352274yyy010.32,0.34xx10.33670.32sin0.3367(0.3367)0.3145670.340.320.33670.340.3334870.3303650.320.3

20、4L例例1n其截斷誤差為：其中 ，因為 解：由題意令線性插值時取 ，得插值公式：0120.32,0.34,0.36xxx0120.314567,0.333487,0.352274yyy010.32,0.34xx10.33670.32sin0.3367(0.3367)0.3145670.340.320.33670.340.3334870.3303650.320.34L2101( )()() ,2MR xxxxx012max( )xx xMf ( )sin ,( )sinf xx fxxn其截斷誤差為：其中 ，因為可取 ，于是： 2101( )()() ,2MR xxxxx012max( )xx

21、xMf ( )sin ,( )sinf xx fxx0121max sinsin0.3335xx xMxx 115(0.3367)sin0.3367(0.3367)10.3335 0.0167 0.00330.92 10 ,2RLn用拋物線插值時，所有節(jié)點全取，得到可取 ，于是： 0121max sinsin0.3335xx xMxx 115(0.3367)sin0.3367(0.3367)10.3335 0.0167 0.00330.92 10 ,2RLn用拋物線插值時，所有節(jié)點全取，得到2(0.33670.34)(0.33670.36)sin0.3367(0.3367)0.314567(0

22、.320.34)(0.320.36)(0.33670.32)(0.33670.36)0.333487(0.340.32)(0.340.36)(0.33670.32)(0.33670.34)0.352274(0.360.32)(0.360.34)0.314567L4440.7689 103.89 100.3334870.00080.00040.5511 100.3522740.3303740.0008n用拋物線插值時，所有節(jié)點全取，得到2(0.33670.34)(0.33670.36)sin0.3367(0.3367)0.314567(0.320.34)(0.320.36)(0.33670.32

23、)(0.33670.36)0.333487(0.340.32)(0.340.36)(0.33670.32)(0.33670.34)0.352274(0.360.32)(0.360.34)0.314567L4440.7689 103.89 100.3334870.00080.00040.5511 100.3522740.3303740.0008n余項討論：其中：于是：我們注意到，這時精度已與6位函數(shù)表一致32012( )()()() ,6MR xxxxxxx0120max( )cos0.828xx xMfxx 226(0.3367)sin0.3367(0.3367)10.828 0.0167 0

24、.033 0.023360.178 10 ,RL2.3 均差與牛頓插值公式均差與牛頓插值公式nLagrange插值的優(yōu)缺點： 公式結(jié)構(gòu)緊湊，在理論分析中方便，但如遇節(jié)點增減，所有數(shù)據(jù)需全部重算。n為改變這種狀態(tài)，我們尋求如下形式的插值多項式：n其中的 為待定系數(shù)，由插值條件確定01020101( )()()()()()nnnP xaa xxaxxxxaxxxxia2.3 均差與牛頓插值公式均差與牛頓插值公式n記函數(shù) 在 的值 ，稱為 關(guān)于 的零階均差。n從零階均差出發(fā)，歸納地定義各階均差n為改變這種狀態(tài)，我們尋求如下形式的插值多項式：n其中的 為待定系數(shù)，由插值條件確定01020101( )(

25、)()()()()nnnP xaa xxaxxxxaxxxxia( )f xix ( )iif xf x if x( )f xix均差的定義均差的定義n記函數(shù) 在 的值 ，稱為 關(guān)于 的零階均差。n從零階均差出發(fā)，歸納地定義各階均差n稱 為函數(shù) 關(guān)于點 的一階均差n一般地， 關(guān)于 的k階均差為( )f xix ( )iif xf x if x( )f xix111 ,iiiiiif xf xf x xxx( )f x1,iix x( )f x1,iii kx xx12111, , ,iii kiii kiii ki kif xxxf x xxf x xxxx 均差的定義均差的定義性質(zhì)1：均差可

26、表示為函數(shù)值的線性組合，即：n 稱 為函數(shù) 關(guān)于點 的一階均差n 一般地， 關(guān)于 的k階均差為111 ,iiiiiif xf xf x xxx( )f x1,iix x( )f x1,iii kx xx12111, , ,iii kiii kiii ki kif xxxf x xxf x xxxx 010011(),()()()()njnjjjjjjjnf xf x xxxxxxxxxx均差的基本性質(zhì)均差的基本性質(zhì)性質(zhì)1：均差可表示為函數(shù)值的線性組合，即：性質(zhì)2：均差關(guān)于所含節(jié)點是對稱的，即：性質(zhì)3：性質(zhì)4：設(shè) 在 存在n階導(dǎo)數(shù)，且則 ，使得010011(),()()()()njnjjjjjj

27、jnf xf x xxxxxxxxxx011010, ,nnnnf x xxf x xxf xxx12011011 ,kmkkmmkf xxxf x xxf xxxxx( )01( ),!nnff x xxn( , )a b ( )f x , a b , jxa b均差性質(zhì)的證明均差性質(zhì)的證明n性質(zhì)1可用歸納法證明；n性質(zhì)2是性質(zhì)1的直接推論；n性質(zhì)3可由下式得到性質(zhì)2：均差關(guān)于所含節(jié)點是對稱的，即：性質(zhì)3：性質(zhì)4：設(shè) 在 存在n階導(dǎo)數(shù)，且則 ，使得011010, ,nnnnf x xxf x xxf xxx12011011 ,kmkkmmkf xxxf x xxf xxxxx( )01( )

28、,!nnff x xxn( , )a b ( )f x , a b , jxa b均差性質(zhì)的證明均差性質(zhì)的證明n性質(zhì)1可用歸納法證明；n性質(zhì)2是性質(zhì)1的直接推論；n性質(zhì)3可由下式得到n性質(zhì)4的證明在下面的討論中給出。011102021021020111,kmkkmkmkkmkkmkmkf x xxxf xxxxf xxxf xxxxxf xxxf x xxxx均差性質(zhì)的證明均差性質(zhì)的證明n均差的計算一般用列均差表的方法，即n性質(zhì)4的證明在下面的討論中給出。011102021021020111,kmkkmkmkkmkkmkmkf x xxxf xxxxf xxxf xxxxxf xxxf x x

29、xxx均差的計算均差的計算n均差的計算一般用列均差表的方法，即一階均差 二階均差三階均差四階均差ix0 x1x2x3x4x( )if x1()f x2()f x3()f x4()f x0()f x01,f x x12 ,f x x23,f x x34,f x x012,f x x x123 ,f x x x234,f x x x0123,f x x x x1234 ,f x x x x01234 , , ,f x x x x x牛頓插值公式牛頓插值公式n根據(jù)均差的定義，把 看成 上的一點，可得：n只要把后一式代入前一式，就得到：x , a b000( )() ,()f xf xf x xxx0

30、01011 , ,()f x xf x xf x x xxx010101 , ,()nnnnf x xxf x xxf x x xxxx0010( )(),()f xf xf x xxx01201,()()f x x xxxxx0101,()()nnf x xxxxxx011 ,( )( )( )nnnnf x x xxxNxR x牛頓插值公式牛頓插值公式n其中n只要把后一式代入前一式，就得到：0010( )(),()f xf xf x xxx01201,()()f x x xxxxx0101,()()nnf x xxxxxx011 ,( )( )( )nnnnf x x xxxNxR x00

31、10( )(),()nNxf xf x xxx01201,()()f x x xxxxx0101,()()nnf x xxxxxx011( )( )( ) ,( )nnnnR xf xNxf x x xxxn其中n 顯然滿足插值條件，且次數(shù)不超過它就是插值多項式，其系數(shù)為：n我們稱 為牛頓均差插值多項式0010( )(),()nNxf xf x xxx01201,()()f x x xxxxx0101,()()nnf x xxxxxx011( )( )( ) ,( )nnnnR xf xNxf x x xxx( )nNxn01,kkaf x xx0,1,kn( )nNx例例2n已知 的函數(shù)表，

32、求4次牛頓插值多項式n從表中可以看到4階均差幾乎為常數(shù)，故取4次插值多項式即可，于是：( )f x0.400.410750.550.578151.116000.650.696751.186000.280000.800.888111.275730.358930.197330.901.026521.384100.433480.213000.031341.051.253821.515330.524930.228630.03126-0.00012n于是：n截斷誤差為：n這說明截斷誤差很小。4( )0.41075 1.166(0.4)0.28(0.4)(0.55)0.19733(0.4)(0.55)(0

33、.65)0.03134(0.4)(0.55)(0.65)(0.8)Nxxxxxxxxxxx4(0.596)(0.596)0.63192fN94012355( ),(0.596)3.63 10R xf x x x x x截斷誤差的估計截斷誤差的估計n這里的截斷誤差估計時，5階均差 是用 來近似的，另一種方法是 ，用 來近似，從而求得 的近似值n截斷誤差為：n這說明截斷誤差很小。01234 ,f x x x x x x01234 , , ,f x x x x x0.596x(0.596)0.63192f4( )R x94012355( ),(0.596)3.63 10R xf x x x x x差

34、分和等距節(jié)點插值差分和等距節(jié)點插值n在前面的討論中，節(jié)點是任意分布的，但實際上經(jīng)常遇到等距節(jié)點的情況，這時插值公式可以得到簡化，為此，我們先介紹差分的概念。n設(shè)函數(shù) 在等距節(jié)點上的值 為已知，這里 為常數(shù)，稱為步長。我們來討論差分的定義。( )f x0(0,1, )kxxkh kn()kkff xh差分和等距節(jié)點插值差分和等距節(jié)點插值n記號n設(shè)函數(shù) 在等距節(jié)點上的值 為已知，這里 為常數(shù)，稱為步長。我們來討論差分的定義。( )f x0(0,1, )kxxkh kn()kkff xh1kkkfff1kkkfff1122()()22kkkkkhhff xf xff差分的定義差分的定義n記號n分別稱

35、為 在 處以 為步長的 向前差分、向后差分、中心差分n符號 、 、 分別稱為向前差分算子、向后差分算子、中心差分算子1kkkfff1kkkfff1122()()22kkkkkhhff xf xff( )f xkxh差分的定義差分的定義n用一階差分可以定義二階差分n一般地可定義m階差分為：n分別稱為 在 處以 為步長的 向前差分、向后差分、中心差分n符號 、 、 分別稱為向前差分算子、向后差分算子、中心差分算子( )f xkxh21212kkkkkkffffff 111mmmkkkfff 111mmmkkkfff 高階差分高階差分n用一階差分可以定義二階差分n一般地可定義m階差分為：n對于中心差

36、分，因為 用到的 、不在函數(shù)表上，因此，一階中心差分應(yīng)寫成 、 從而定義 、以此類推。21212kkkkkkffffff 111mmmkkkfff 111mmmkkkfff kf12kf12kf121kkkfff121kkkfff11222kkkfff不變算子不變算子I、移位算子移位算子En定義n從而可得：于是得到：同理，由于：n對于中心差分，因為 用到的 、不在函數(shù)表上，因此，一階中心差分應(yīng)寫成 、 從而定義 、以此類推。kkIff1kkEff1()kkkkkkfffEfIfEI fEI 111()kkkkkkfffIfEfIEfkf12kf12kf121kkkfff121kkkfff112

37、22kkkfff不變算子不變算子I、移位算子移位算子En定義n從而可得：于是得到：同理，由于：得到：由于：得到：n由差分的定義及不變算子和移位算子有 kkIff1kkEff1()kkkkkkfffEfIfEI fEI 1IE 1122EE111()kkkkkkfffIfEfIEf111122221122()kkkkkkfffE fEfEEf不變算子不變算子I、移位算子移位算子E性質(zhì)1：各階差分均可用函數(shù)值表示，如：得到：由于：得到：n由差分的定義及不變算子和移位算子有 1IE 1122EE111122221122()kkkkkkfffE fEfEEf00()( 1)( 1)nnnnjnjjkk

38、kk njjjnnfEIfEffjj 100()( 1)( 1)nnnnn jj nn jkkkkj njjnnfIEfEffjj 差分的性質(zhì)差分的性質(zhì)性質(zhì)1：各階差分均可用函數(shù)值表示，如：性質(zhì)2：某點的函數(shù)可用各階差分來表示：00()( 1)( 1)nnnnjnjjkkkk njjjnnfEIfEffjj 100()( 1)( 1)nnnnn jj nn jkkkkj njjnnfIEfEffjj 00()nnnnjjn kkkkkjjnnfE fIfffjj 差分的性質(zhì)差分的性質(zhì)n性質(zhì)3：均差與差分有如下關(guān)系：性質(zhì)2：某點的函數(shù)可用各階差分來表示：00()nnnnjjn kkkkkjjnn

39、fE fIfffjj 111,(1,2, )!mkkk mkmf xxxfmnm h111,(1,2, )!mkkk mkmf xxxfmnm hn性質(zhì)3：均差與差分有如下關(guān)系：n性質(zhì)4：差分與導(dǎo)數(shù)有如下關(guān)系：111,(1,2, )!mkkk mkmf xxxfmnm h111,(1,2, )!mkkk mkmf xxxfmnm h( )( ),(,)nnnkkk nfh fxx差分的計算差分的計算n計算差分可用差分表的方式：kf( ) 22() 33() 44() 0f1f2f3f4f23()ff34()ff01()ff12()ff2224()ff2202()ff2213()ff3314()

40、ff3303()ff4404()ff等距節(jié)點插值公式等距節(jié)點插值公式n將牛頓插值公式中的各階均差用相應(yīng)的差分代替，即得各種形式的等距節(jié)點插值公式n牛頓前插公式 令 ， 有從而可得插值多項式和余項分別為：0(0,1, )kxxkh kn0,01xxtht 110( )()(1)()kkkjjxxxt ttk h200000(1)(1)(1)()2!nnt tt tt nN xthft fffn 1(1)0(1)()( )( ),( ,)(1)!nnnnt tt nR xhfx xn等距節(jié)點插值公式等距節(jié)點插值公式n牛頓后插公式 令 ， 有從而可得插值多項式和余項分別為：從而可得插值多項式和余項分

41、別為：110( )()(1)()kkkjjxxxt ttk h200000(1)(1)(1)()2!nnt tt tt nN xthft fffn 1(1)0(1)()( )( ),( ,)(1)!nnnnt tt nR xhfx xn0(0,1, )kxxkh kn0, 10 xxtht 110( )()(1)()kkkjjxxxt ttk hn牛頓后插公式 令 ， 有從而可得插值多項式和余項分別為：0(0,1, )kxxkh kn0, 10 xxtht 110( )()(1)()kkkjjxxxt ttk h20(1)(1)(1)()2!nnnnnnt tt ttnN xthft fffn

42、 1(1)0(1)()( )( )()( ),( ,)(1)!nnnnnnt ttnR xf xN xthhfx xnn已知 在處的函數(shù)值，試用4次等距節(jié)點插值公式計算 及 的近似值并估計誤差。n解：先構(gòu)造差分表如下頁。用牛頓向前20(1)(1)(1)()2!nnnnnnt tt ttnN xthft fffn 1(1)0(1)()( )( )()( ),( ,)(1)!nnnnnnt ttnR xf xN xthhfx xn( )cosf xx,0,1,6,0.1kxkh kh(0.566)f(0.048)f例例3n已知 在處的函數(shù)值，試用4次等距節(jié)點插值公式計算 及 的近似值并估計誤差。n

43、解：先構(gòu)造差分表如下頁。用牛頓向前插值公式計算 的近似值，取 ， ，用差分表的上半部差分，得 ( )cosf xx,0,1,6,0.1kxkh kh(0.048)f(0.566)f(0.048)f0.048x 0.1h 00.48xthn 1.000000.995000.980070.955340.921060.877580.82534-0.00500-0.01493-0.02473-0.03428-0.04348-0.05224-0.00993-0.00980-0.00955-0.00920-0.008760.000130.000250.000350.000440.000120.000100

44、.00009-0.00002-0.00001kf( ) 22() 33() 44() 55() n 4(0.048)1.000000.48 ( 0.00500)N (0.48)(0.48 1)( 0.00993)21(0.48)(0.48 1)(0.482)(0.00013)3!5754(0.048)(1)(2)(3)(4)1.5845 105!MRt tttth5sin0.60.565M 1(0.48)(0.48 1)(0.482)(0.483)(0.00012)4!0.99885cos(0.048)n 4(0.048)1.000000.48 ( 0.00500)N (0.48)(0.48

45、1)( 0.00993)21(0.48)(0.48 1)(0.482)(0.00013)3!5754(0.048)(1)(2)(3)(4)1.5845 105!MRt tttth5sin0.60.565M 1(0.48)(0.48 1)(0.482)(0.483)(0.00012)4!0.99885cos(0.048)n 4(0.048)1.000000.48 ( 0.00500)N (0.48)(0.48 1)( 0.00993)21(0.48)(0.48 1)(0.482)(0.00013)3!40.00876(0.566)0.825340.350.05224(0.66)20.000440

46、.00009(1.66)2.660.84405cos0.566624N5754(0.566)(1)(2)(3)(4)1.7064 105!MRt tttth50.565M n用牛頓向后插值公式計算 的近似值，取 ， ， ，用差分表的下半部差分，得 (0.566)f0.566x 60.6x 60.34xxth 40.00876(0.566)0.825340.350.05224(0.66)20.000440.00009(1.66)2.660.84405cos0.566624N5754(0.566)(1)(2)(3)(4)1.7064 105!MRt tttth50.565M 2.5 埃爾米特插值埃

47、爾米特插值n拉格朗日和牛頓均只保證函數(shù)插值；n實際問題有時需要導(dǎo)數(shù)也插值；n滿足這種需要的插值稱為埃爾米特插值埃爾米特插值的一般提法埃爾米特插值的一般提法n埃爾米特插值的一般提法為：設(shè)函數(shù) 在節(jié)點 的函數(shù)值與導(dǎo)數(shù)值為：其中 是正整數(shù)，尋求一個次數(shù)盡可能低的多項式 ，使?jié)M足：01,nxxx( ),iif xf( ),iifxf ,(1)(1)( ),iimmiifxf0,1,in01,nm mm( )H x( )( )( ),kkiiHxf0,1,in0,1,1;ikm埃爾米特插值的一般提法埃爾米特插值的一般提法n可以證明，存在唯一的滿足插值條件的次數(shù)不超過 的多項式 ，即所謂的埃爾米特多項式其

48、中 是正整數(shù)，尋求一個次數(shù)盡可能低的多項式 ，使?jié)M足：01,nm mm( )H x( )( )( ),kkiiHxf0,1,in0,1,1;ikm( )H x1niimmn可以證明，存在唯一的滿足插值條件的次數(shù)不超過 的多項式 ，即所謂的埃爾米特多項式其中 是 多項式，且滿足條件：( )H x1niimm1( )00( )( )imnkiikikH xfhx( )ikhxim( )1&()0;likjijlkhxotherwise；n當(dāng) 時有：而多項式的次數(shù)為不超過 ，記為 ，因此： 滿足條件：其中 是 多項式，且滿足條件：1( )00( )( )imnkiikikH xfhx( )ikhxi

49、m( )1&()0;likjijlkhxotherwise；2im ( ),iif xf( ),iifxf 0,1,in2 121nimn 21( )nHx21( )nHx較為實用的簡單情況較為實用的簡單情況n當(dāng) 時有：而多項式的次數(shù)為不超過 ，記為 ，因此： 滿足條件： ， ，從幾何上看，即要求 與 在 個節(jié)點處有相同的切線（即曲線相切），此時 稱為二重節(jié)點。這種帶導(dǎo)數(shù)的插值法稱為密切插值。2im ( ),iif xf( ),iifxf 0,1,in2 121nimn 21( )nHx21( )nHx21( )niiHxf21( )niiHxf0,1,in01,nxxx21( )nHx21(

50、 )nHx1n較為實用的簡單情況較為實用的簡單情況n定理：設(shè) ，則在區(qū)間上滿足插值條件的不超過3次的多項式 是存在唯一的，且可如下構(gòu)造： ， ，從幾何上看，即要求 與 在 個節(jié)點處有相同的切線（即曲線相切），此時 稱為二重節(jié)點。這種帶導(dǎo)數(shù)的插值法稱為密切插值。21( )niiHxf21( )niiHxf0,1,in01,nxxx21( )nHx21( )nHx1n101( ),f xC xx01,xx( )H x00110011( )( )( )( )( )H xfxfxfxfx二點三次埃爾米特插值二點三次埃爾米特插值n定理：設(shè) ，則在區(qū)間上滿足插值條件的不超過3次的多項式 是存在唯一的，且可

51、如下構(gòu)造：其中 稱為插值基函數(shù)。如果 ，那么插值余項為：101( ),f xC xx01,xx( )H x00110011( )( )( )( )( )H xfxfxfxfx0101( ),( ),( ),( )xxxx401( ),f xCxx(4)2201( )( )( )( )() ()4!fR xf xH xxxxx01,xxx 01( )(,)xxxx二點三次埃爾米特插值二點三次埃爾米特插值其中 稱為插值基函數(shù)。如果 ，那么插值余項為：0101( ),( ),( ),( )xxxx401( ),f xCxx(4)2201( )( )( )( )() ()4!fR xf xH xxxx

52、x01,xxx 01( )(,)xxxx20101001( )12xxxxxxxxx210001( )xxxxxxx插值基函數(shù)插值基函數(shù)n 20101001( )12xxxxxxxxx20110110( )12xxxxxxxxx210001( )xxxxxxx201110( )xxxxxxx插值基函數(shù)插值基函數(shù)n先證明 滿足插值條件。易驗證： 20110110( )12xxxxxxxxx201110( )xxxxxxx( )H x010()01kkxk100()11kkxk定理的證明定理的證明n先證明 滿足插值條件。易驗證：( )H x010()01kkxk100()11kkxk2011010

53、0110010121( )2 12xxxxxxxxxxxxxxxxx20011011001101021( )2 12xxxxxxxxxxxxxxxxx00()0 x01()0 x10()0 x11()0 x定理的證明定理的證明n 20110100110010121( )2 12xxxxxxxxxxxxxxxxx20011011001101021( )2 12xxxxxxxxxxxxxxxxx00()0 x01()0 x10()0 x11()0 x211000101011( )2xxxxxxxxxxxxx00()0 x01()0 x10()0 x11()0 xn從而證明 滿足插值條件，這同時也證

54、明了 的存在性。 211000101011( )2xxxxxxxxxxxxx200111010101( )2xxxxxxxxxxxxx00()0 x01()0 x10()0 x11()0 x00()1x01()0 x10()0 x11()1x( )H x( )H xn唯一性證明。設(shè)有兩個不超過3次的多項式 和 同時滿足插值條件，顯然 是次數(shù)不超過3次的多項式n從而證明 滿足插值條件，這同時也證明了 的存在性。 200111010101( )2xxxxxxxxxxxxx00()1x01()0 x10()0 x11()1x( )H x( )H x( )H x( )H x( )( )( )p xH

55、xH xn唯一性證明。設(shè)有兩個不超過3次的多項式 和 同時滿足插值條件，顯然 是次數(shù)不超過3次的多項式且有這表明 和 都是 的二重根，從而這是不可能的，除非 ，即 ，因此( )H x( )H x( )( )( )p xH xH x()()0 (0,1)kkp xp xk0 x1x( )p x2201( )() ()p xc xxxx0c ( )0p x ( )( )H xH xn再證余項公式。 設(shè) ，則有：且有這表明 和 都是 的二重根，從而這是不可能的，除非 ，即 ，因此()()0 (0,1)kkp xp xk0 x1x( )p x2201( )() ()p xc xxxx0c ( )0p

56、x ( )( )H xH x( )( )( )nR xf xH x()00,1nkR xk()00,1nkR xkn再證余項公式。 設(shè) ，則有：所以， ， 都是 的二重根，從而 可表示為： 對于任何固定的 ， ， ，構(gòu)造自變量為 的輔助函數(shù)( )( )( )nR xf xH x()00,1nkR xk()00,1nkR xk0 x1x( )nRx( )nRx2201( )( )( )( )() ()nR xf xH xK x xxxx , xa bkxx0,1k t2201( )( )( )( )() ()tf tH tK x txtxn則 ， ， 是 在 上的三個互異的零點，且 和 為二重零

57、點，因此，存在 及 ，使得：所以， ， 都是 的二重根，從而 可表示為： 對于任何固定的 ， ， ，構(gòu)造自變量為 的輔助函數(shù)0 x1x( )nRx( )nRx2201( )( )( )( )() ()nR xf xH xK x xxxx , xa bkxx0,1k t2201( )( )( )( )() ()tf tH tK x txtx0 x1xx( ) t01,x x0 x1x10(, )xx22( ,)x x12()()0 n則 ， ， 是 在 上的三個互異的零點，且 和 為二重零點，因此，存在 及 ，使得：同時有 ，故 為 在 內(nèi)的四個互異的零點，因此 在 中有一個零點，而而 ，因此由

58、 得到：0 x1xx( ) t01,x x0 x1x10(, )xx22( ,)x x12()()0 01()()0 xx0121,xx ( )x01(,)x x(4)( )x01(,)x x(4)(4)(4)( )( )( )4!( )tftHtK x(4)( )0Ht (4)( )0(4)( )( )4!fK xn現(xiàn)在推導(dǎo) 形式的由來。 對于 個節(jié)點，每個節(jié)點都滿足函數(shù)插值，導(dǎo)數(shù)插值，即同時有 ，故 為 在 內(nèi)的四個互異的零點，因此 在 中有一個零點，而而 ，因此由 得到：01()()0 xx0121,xx ( )x01(,)x x(4)( )x01(,)x x(4)(4)(4)( )(

59、)( )4!( )tftHtK x(4)( )0Ht (4)( )0(4)( )( )4!fK x( ),( )iixx1nn現(xiàn)在推導(dǎo) 形式的由來。 對于 個節(jié)點，每個節(jié)點都滿足函數(shù)插值，導(dǎo)數(shù)插值，即共有 個條件，可唯一確定一個次數(shù)不超過 的多項式 ，其形式為：目標(biāo)：求出所有的 ；方法：基函數(shù)法( ),( )iixx1n( )( ),( )( ),0,1,iiiiH xf xH xfxin22n21n21( )nHx21210121( )nnnHxaa xaxian先求插值基函數(shù)n基函數(shù)都是 次多項式，且滿足：共有 個條件，可唯一確定一個次數(shù)不超過 的多項式 ，其形式為：目標(biāo)：求出所有的 ；方

60、法：基函數(shù)法22n21n21( )nHx21210121( )nnnHxaa xaxia( ),( ),(0,1, )iixxin21n(),()0ikikikxx()0,()ikikikxxn先求插值基函數(shù)n基函數(shù)都是 次多項式，且滿足：n這樣 可表示為：n顯然有：( ),( ),(0,1, )iixxin21n(),()0ikikikxx()0,()ikikikxx21( )nHx210( )( )( )nniiiiiHxfxfx21()nkkHxf21()nkkHxfn現(xiàn)在求 及 ，令其中從而有：n這樣 可表示為：n顯然有：21( )nHx210( )( )( )nniiiiiHxfxf