數(shù)值分析ppt第2章_插值法

1、 在工程技術(shù)與科學(xué)研究中，常會(huì)遇到函數(shù)表達(dá)在工程技術(shù)與科學(xué)研究中，常會(huì)遇到函數(shù)表達(dá)式過于復(fù)雜而不便于計(jì)算，且又需要計(jì)算眾多點(diǎn)處式過于復(fù)雜而不便于計(jì)算，且又需要計(jì)算眾多點(diǎn)處的函數(shù)值；或已知由實(shí)驗(yàn)（測(cè)量）得到的某一函數(shù)的函數(shù)值；或已知由實(shí)驗(yàn)（測(cè)量）得到的某一函數(shù) y=f(x)在區(qū)間在區(qū)間a,b中互異的中互異的n+1個(gè)個(gè)xi ( i=0, 1, . ,n)處處的值的值yi=f(xi) (i=0,1,.,n), 需要構(gòu)造一個(gè)需要構(gòu)造一個(gè)簡(jiǎn)單易算的簡(jiǎn)單易算的函數(shù)函數(shù)P(x)作為作為y=f(x)的近似表達(dá)式的近似表達(dá)式 y=f(x)P(x) , 使得使得 P(xi)= f(xi) = yi (i=0,1,

2、 ., n) 這類問題就稱為這類問題就稱為插值問題插值問題， P(x)稱為稱為插值函數(shù)插值函數(shù)， P(x)一般取最簡(jiǎn)單又便于計(jì)算得函數(shù)。一般取最簡(jiǎn)單又便于計(jì)算得函數(shù)。第第2章章 插插 值值 法法x0 x1x2x3x4xP(x) f(x)f(x) y=f(x)P(x) , 使得使得 P(xi)= f(xi) = yi (i=0,1, ., n) 其它點(diǎn)其它點(diǎn) P(x) f(x) = y2.1.1 插值問題插值問題 設(shè)設(shè) y= f(x) 是區(qū)間是區(qū)間a , b 上的一個(gè)實(shí)函數(shù)上的一個(gè)實(shí)函數(shù), xi ( i=0, 1, . ,n)是是a,b上上n+1個(gè)互異實(shí)數(shù)個(gè)互異實(shí)數(shù),已知已知 y=f(x) 在在

3、 xi 的的值值 yi=f(xi) (i=0,1,.,n), 求一個(gè)求一個(gè)次數(shù)不超過次數(shù)不超過n的多項(xiàng)式的多項(xiàng)式Pn(x)使其滿足使其滿足Pn(xi)=yi (i=0,1, ., n)這就是這就是多項(xiàng)式插值問題多項(xiàng)式插值問題.2.1 引言引言其中其中Pn(x) 稱為稱為 f(x) 的的n次插值多項(xiàng)式次插值多項(xiàng)式, f(x) 稱為稱為被插函被插函數(shù)數(shù), xi(i=0,1, .,n)稱為稱為插值節(jié)點(diǎn)插值節(jié)點(diǎn), (xi, yi) (i=0,1, ,n) 稱為稱為插值點(diǎn)插值點(diǎn), a,b 稱為稱為插值區(qū)間插值區(qū)間, 式式(5-1)稱為稱為插值條件插值條件。 從幾何意義來看從幾何意義來看,上上述問題就是要

4、求一條多述問題就是要求一條多項(xiàng)式曲線項(xiàng)式曲線 y=Pn(x), 使它使它通過已知的通過已知的n+1個(gè)點(diǎn)個(gè)點(diǎn)(xi,yi) (i=0,1, ,n),并用并用Pn(x)近似表示近似表示f(x).即即 P(x)=a0+a1x+a2x2+.+anxn其中其中ai為實(shí)數(shù)，就稱為實(shí)數(shù)，就稱P(x) 為為 插值多項(xiàng)式插值多項(xiàng)式，相應(yīng)的插，相應(yīng)的插值法稱為值法稱為多項(xiàng)式插值多項(xiàng)式插值，若，若P(x)為分段的多項(xiàng)式，就為分段的多項(xiàng)式，就稱為稱為分段插值分段插值，若，若P(x)為三角多項(xiàng)式為三角多項(xiàng)式,就稱為就稱為三角插三角插值值，本章只討論插值多項(xiàng)式與分段插值。，本章只討論插值多項(xiàng)式與分段插值。 本章主要研究如

5、何求出本章主要研究如何求出插值多項(xiàng)式插值多項(xiàng)式，分段插值分段插值函數(shù)，樣條插值函數(shù)；討論插值多項(xiàng)式函數(shù)，樣條插值函數(shù)；討論插值多項(xiàng)式P(x)的存在的存在唯一性、收斂些及誤差估計(jì)等。唯一性、收斂些及誤差估計(jì)等。定理定理1 設(shè)節(jié)點(diǎn)設(shè)節(jié)點(diǎn) xi (i=0,1, ,n)互異互異, 則則滿足插值條件滿足插值條件 Pn(xi)=yi (i=0,1, ., n)的次數(shù)不超過的次數(shù)不超過n的多項(xiàng)的多項(xiàng) 式存在且唯一式存在且唯一.證證 設(shè)所求的插值多項(xiàng)式為設(shè)所求的插值多項(xiàng)式為 Pn(x)=a0+a1x+a2x2+.+anxn則由插值條件式則由插值條件式Pn(xi)=yi (i=0,1, ., n) 可得可得關(guān)于

6、系數(shù)關(guān)于系數(shù)a0 ,a1 , ,an的線性代數(shù)方程組的線性代數(shù)方程組2.1.2 插值多項(xiàng)式的存在性和唯一性插值多項(xiàng)式的存在性和唯一性 nnnnnnnnnyxaxaayxaxaayxaxaa101111000010此方程組有此方程組有n+1個(gè)方程個(gè)方程, n+1個(gè)未知數(shù)個(gè)未知數(shù), 其系數(shù)行列式是其系數(shù)行列式是范德蒙范德蒙(Vandermonde)行列式：行列式：20002111211()01nnjij innnnxxxxxxxxxxx 由克萊姆法則知方程組由克萊姆法則知方程組 的解存在唯一的解存在唯一. 證畢。證畢。 上頁上頁上頁上頁上頁上頁下頁下頁下頁下頁下頁下頁 考慮最簡(jiǎn)單、最基本的插值問題

7、考慮最簡(jiǎn)單、最基本的插值問題.求求n次插值多項(xiàng)式次插值多項(xiàng)式 l i(x) (i=0,1, ,n),使其滿足使其滿足插值條件插值條件0,()(0,1, )1,ijjil xjnji 2.2.1 基函數(shù)基函數(shù)可知可知, 除除 xi點(diǎn)外點(diǎn)外, 其余都是其余都是 li(x)的零點(diǎn)的零點(diǎn), 故可設(shè)故可設(shè)Lagrange法法1736- -1813 0( )()()inl xA xxxx 11()()iixxxx 2.2 拉格朗日插值拉格朗日插值其中其中A為常數(shù)為常數(shù), 由由li(xi)=1可得可得)()()(1110niiiiiixxxxxxxxA 稱之為稱之為拉格朗日基函數(shù)拉格朗日基函數(shù), 都是都是n

8、次多項(xiàng)式次多項(xiàng)式 。00()()( )()()(0,1, )niiinxxxxl xxxxxin 11()()iixxxx 11()()iiiixxxx 0( )()()inl xA xxxx 11()()iixxxx nijjjijxxxx0 n=1時(shí)的時(shí)的一次基函數(shù)一次基函數(shù)為為: 0 x1xy1 O x)(0 xl y 10 x1x)(1xlO x.)(,)(01011010 xxxxxlxxxxxl 即已知函數(shù)即已知函數(shù) f(x)在點(diǎn)在點(diǎn)x0和和x1點(diǎn)的函數(shù)值點(diǎn)的函數(shù)值 y0=f(x0)，y1=f(x1).求線性函數(shù)求線性函數(shù) L(x)=a0+ a1x使?jié)M足條件：使?jié)M足條件：L(x0)

9、=y0 , L(x1)=y1. .)()(001010 xxxxyyyxL 此為兩點(diǎn)線性插值問題此為兩點(diǎn)線性插值問題或用或用直線的兩點(diǎn)式表示為：直線的兩點(diǎn)式表示為：0011() () xxxxll則則 稱稱 ： 叫叫 做做 點(diǎn)點(diǎn) 的的 一一 次次 插插 值值 基基 函函 數(shù)數(shù) 為為 點(diǎn)點(diǎn) 的的 一一 次次 插插 值值 基基 函函 數(shù)數(shù)插值基函數(shù)的特點(diǎn)插值基函數(shù)的特點(diǎn)： x0 0 x1 1l0 01 10 0l1 10 01 11x0 x1l0 0l1 1.)(,)(01011010 xxxxxlxxxxxl 記記.)(010110101xxxxyxxxxyxL 1200102()()( ),(

10、)()xxxxlxxxxx n=2時(shí)的時(shí)的二次基函數(shù)二次基函數(shù)為為 : 0211012()()( ),()()xxxxlxxxxx 0122021()()( ).()()xxxxlxxxxx 0 01 10( )( )( )( )( )nnn ni iiL xy lxy l xy lxy l x 可知其滿足可知其滿足2.2.2 拉格朗日插值多項(xiàng)式拉格朗日插值多項(xiàng)式利用拉格朗日基函數(shù)利用拉格朗日基函數(shù)l i(x), 構(gòu)造次數(shù)構(gòu)造次數(shù)不超過不超過n的多項(xiàng)式的多項(xiàng)式njyxLjjn, 1 , 0)( )()(xLxPnn 稱為稱為拉格朗日插值多項(xiàng)式拉格朗日插值多項(xiàng)式,再再由插值多項(xiàng)式的唯一性由插值多

11、項(xiàng)式的唯一性,得得 特別地特別地, 當(dāng)當(dāng) n =1時(shí)又叫時(shí)又叫線性插值線性插值,其幾何意義為其幾何意義為過兩點(diǎn)的直線過兩點(diǎn)的直線. 當(dāng)當(dāng) n =2時(shí)又叫時(shí)又叫拋物（線）插值拋物（線）插值, 其幾其幾何意義為過三點(diǎn)的拋物線何意義為過三點(diǎn)的拋物線.1)(0 niixl注意注意 :(1) 對(duì)于插值節(jié)點(diǎn)對(duì)于插值節(jié)點(diǎn),只要求它們互異只要求它們互異,與大小次序無關(guān)與大小次序無關(guān); 以以 xi (i=0,1,n)為插值節(jié)點(diǎn)為插值節(jié)點(diǎn), 函數(shù)函數(shù) f(x) 1作插值多作插值多項(xiàng)式項(xiàng)式, 由插值多項(xiàng)式的唯一性即得由插值多項(xiàng)式的唯一性即得基函數(shù)的一個(gè)性質(zhì)基函數(shù)的一個(gè)性質(zhì)(2) 插值基函數(shù)插值基函數(shù)l i(x) 僅

12、由插值節(jié)點(diǎn)僅由插值節(jié)點(diǎn)xi (i=0,1, ,n)確定確定, 與被插函數(shù)與被插函數(shù) f(x)無關(guān)無關(guān);(3) 插值基函數(shù)插值基函數(shù)l i(x) 的順序與的順序與插值節(jié)點(diǎn)插值節(jié)點(diǎn)xi (i=0,1, ,n) 的順序一致的順序一致.1)(0 niixl這是因?yàn)槿暨@是因?yàn)槿羧∪?(x)=xk (k=0,1,n),由插值多項(xiàng)式的唯由插值多項(xiàng)式的唯一性有一性有0( ),0,1,nkkiiil x xxkn 特別當(dāng)特別當(dāng)k=0k=0時(shí)時(shí), ,就得到就得到所以所以019141( )(9), ( )(4)495945xxlxxlxx 10 01 111( )( )( )2(9)3(4)55L xy lxy l

13、xxx 1137(7)2.65L01,4,9,yx xx7例例1 已知已知 用線性插值用線性插值(即一次插即一次插值多項(xiàng)式值多項(xiàng)式)求求 的近似值。的近似值。012,3,yy 基函數(shù)分別為基函數(shù)分別為:解解插值多項(xiàng)式為插值多項(xiàng)式為23(9)(4)55xx 1(6)5x( )4, 3, 1, 13210 xxxx)4)(3)(1(401)41)(31)(11()4)(3)(1()(0 xxxxxxxl)4)(3)(1(121)41)(31)(11()4)(3)(1()(1 xxxxxxxl)4)(1)(1(81)43)(13)(13()4)(1)(1()(2 xxxxxxxl)3)(1)(1(1

14、51)34)(14)(14()3)(1)(1()(3 xxxxxxxl例例2 求過點(diǎn)求過點(diǎn)(- -1,- -2), (1,0), (3,- -6), (4,3)的拋物線插值的拋物線插值(即即三次插值多項(xiàng)式三次插值多項(xiàng)式).解解 以以以為節(jié)點(diǎn)的基函數(shù)以為節(jié)點(diǎn)的基函數(shù)分別為分別為:)()()()()(332211003xlyxlyxlyxlyxL ) 3)(1)(1(1513)4)(1)(1(81)6()4)(3)(1(1210)4)(3)(1(401) 2( xxxxxxxxxxxx)3)(1)(1(51)4)(1)(1(43)4)(3)(1(201 xxxxxxxxx3423 xx()則拉格朗

15、日則拉格朗日的三次插值多項(xiàng)式為的三次插值多項(xiàng)式為 截?cái)嗾`差截?cái)嗾`差Rn(x)=f (x) - -Ln(x)也稱為也稱為n n次次LagrangeLagrange插插值多項(xiàng)式的余項(xiàng)值多項(xiàng)式的余項(xiàng)。以下為。以下為拉格朗日余項(xiàng)定理拉格朗日余項(xiàng)定理。 定理定理2 設(shè)設(shè) f (x) 在區(qū)間在區(qū)間 a ,b上存在上存在 n+1 階導(dǎo)數(shù)階導(dǎo)數(shù), xi a, b (i=0,1, , n) 為為 n+1個(gè)互異節(jié)點(diǎn)個(gè)互異節(jié)點(diǎn), 則對(duì)任何則對(duì)任何x a ,b, 有有(1)1( )( )( )( )( )(1)!nnnnfR xf xL xxn 2.2.3 插值余項(xiàng)插值余項(xiàng)( , )a b 且與且與x有關(guān)有關(guān))10(

16、 )()nniixxx 其其中中證證 由插值條件和由插值條件和 n+1(x) 的定義的定義, 當(dāng)當(dāng)x=xk 時(shí)時(shí) , 式子顯式子顯然成立然成立, 并且有并且有 n+1(xk)=0 ( k=0,1,n ), 這表明這表明x0 , x1, , xn 都是函數(shù)都是函數(shù) n+1(x) 的零點(diǎn)的零點(diǎn), 從而從而 n+1(x) 可表示為可表示為 1( )( )( )( )( )nntf tL tK xt (1)1( )( )( )( )( )(1)!nnnnfR xf xL xxn 1( )( )( )( )( )nnnRxf xLxK xx 其中其中K(x)是是待定函數(shù)待定函數(shù)。 對(duì)于對(duì)于任意固定的任意

17、固定的x a,b, x xk ,構(gòu)造自變量構(gòu)造自變量 t 的輔的輔助函數(shù)助函數(shù)1( )( )( )( )( )nntf tL tK xt 由式由式 n+1(xk)=0 和式和式 Ln(xk)=yk ( k=0,1,n ),以及以及1( )( )( )( )( )nnnRxf xLxK xx 可知：可知：x0 , x1, , xn 和和 x 是是 (t) 在區(qū)間在區(qū)間a,b上的上的 n+2個(gè)個(gè)互異零點(diǎn)互異零點(diǎn), 因此根據(jù)羅爾因此根據(jù)羅爾 (Rolle) 定理定理, 至少存在一點(diǎn)至少存在一點(diǎn) = (x) (a,b),使使 (1)( )0n (1)( )( )(1)!nfK xn 即即(1)1( )

18、( )( )( )( )(1)!nnnnfR xf xL xxn 所以所以 一般來說一般來說,外推比內(nèi)插效果差外推比內(nèi)插效果差,在估計(jì)誤差時(shí)下列在估計(jì)誤差時(shí)下列不等式很有用。不等式很有用。),(, )()!1()(01baxxxnMxRniinn 或或),(, )(max)!1()(01baxxxnMxRniibxann 。其中：其中：)(max)1(1xfMnbxan niinnnxxnfxLxfxR0) 1()()!1()()()()( 25. 0)4(, 4 . 0)5 . 2(, 5 . 0)2(210 fyfyfy)45 . 2)(25 . 2()4)(2(4 . 0)42)(5 .

19、 22()4)(5 . 2(5 . 0)(2 xxxxxL)5 . 24)(24()5 . 2)(2(25. 0 xx15. 1425. 005. 02 xx,1)(xxf ，節(jié)點(diǎn)節(jié)點(diǎn)4, 5 . 2, 2210 xxx)(xf求求的拋物插值多項(xiàng)式的拋物插值多項(xiàng)式,且計(jì)算且計(jì)算f (3)的近似值并估計(jì)誤差。的近似值并估計(jì)誤差。例例3 設(shè)設(shè)解解 插值多項(xiàng)式為插值多項(xiàng)式為,6)(4xxf 83| )2(| )(|max4, 23 fxfMx21 3|(3)| |(3)(3)|(32)(32.5)(34)|6 80.03125RfL 因?yàn)橐驗(yàn)楣使蕓 )4)(5 . 2)(2( |8361| )4)(

20、5 . 2)(2( |!3| )(|33 xxxxxxMxR325. 0)3()3(2 Lf于是于是用二次插值計(jì)算用二次插值計(jì)算ln11.25ln11.25的近似值的近似值, ,并估計(jì)誤差并估計(jì)誤差. .例例4 給定函數(shù)表給定函數(shù)表x10111213lnx 2.302585 2.3978952.484907 2.564949解解 取節(jié)點(diǎn)取節(jié)點(diǎn)x x0 0=10,x=10,x1 1=11,x=11,x2 2=12,=12,作二次插值有作二次插值有302585. 2)1210)(1110()1225.11)(1125.11( 397895. 2)1211)(1011()1225.11)(1025.

21、11( 484907. 2)1112)(1012()1125.11)(1025.11( 420426. 2 ln11.25ln11.25 L L2 2(11.25)(11.25)在區(qū)間在區(qū)間10,1210,12上上lnx lnx 的三階導(dǎo)數(shù)的上限的三階導(dǎo)數(shù)的上限M M3 3=0.002,=0.002,可得誤差估計(jì)式可得誤差估計(jì)式00007. 0| )1225.11)(1125.11)(1025.11( |! 3)25.11(32 MR實(shí)際上實(shí)際上,ln11.25=2.420368,ln11.25=2.420368, |R |R2 2(11.25)|=0.000058.(11.25)|=0.00

22、0058.2.3.1 均差及其基本性質(zhì)均差及其基本性質(zhì)定義定義1 稱稱101010)()(,xxxfxfxxf 為為 f (x)在在x0、x1點(diǎn)的點(diǎn)的一階均差一階均差.一階均差的均差一階均差的均差(差商差商)202110210,xxxxfxxfxxxf 稱為函數(shù)稱為函數(shù)f (x)在在x0、x1 、x2 點(diǎn)的點(diǎn)的二階均差二階均差.英英1642-1727 2.3 均差與牛頓插值公式均差與牛頓插值公式一般地，一般地，n-1階均差的均差階均差的均差nnnnnnxxxxxfxxxfxxxf 01112010, 稱為稱為f (x)在在x0 , x1 , , xn點(diǎn)的點(diǎn)的 n 階均差階均差。差商的計(jì)算步驟與

23、結(jié)果可列成差商的計(jì)算步驟與結(jié)果可列成均差表均差表，如下，如下 一般一般f(xi) 稱為稱為f(x) 在在xi點(diǎn)的點(diǎn)的零階均差零階均差，記作，記作fxi。xk函數(shù)值函數(shù)值一階均差一階均差二階均差二階均差三階均差三階均差. x0 x1 x2 x3 . f (x0) f (x1) f (x2) f (x3) . f x0 , x1 f x1 , x2 f x2 , x3 . f x0, x1, x2 f x1, x2, x3 . f x0, x1, x2 , x3 .表表2-1（均差表）（均差表）給出節(jié)點(diǎn)給出節(jié)點(diǎn)x x0 0,x,x1 1, ,x,xn n和函數(shù)值和函數(shù)值 (x(x0 0),), (

24、x(x1 1),), , (x(xn n),),可按如下的差商表順序逐次計(jì)算各階差商值可按如下的差商表順序逐次計(jì)算各階差商值. .(xi)一階一階差商差商二階差商二階差商三階差商三階差商n階差商階差商(x0)(x1)(x2)(x3) (xn)x0,x1x1,x2x2,x3 xn-1,xnx0,x1,x2x1,x2,x3 xn-2,xn-1,xnx0,x1,x2,x3 xn-3,xn-2,x2,x3 x0,x1,xn nknkkkkkkknxxxxxxxxxfxxxf011010)()()()(,這一性質(zhì)可以用數(shù)學(xué)歸納法證明這一性質(zhì)可以用數(shù)學(xué)歸納法證明，它表明均差與節(jié)它表明均差與節(jié)點(diǎn)的排列次序無

25、關(guān)點(diǎn)的排列次序無關(guān)，即，即 fx0 , x1 , x2 , ., xn= fx1 , x0 , x2 , ., xn= = fx1 , x2 , ., xn , x0 性質(zhì)性質(zhì)1 均差可以表示為函數(shù)值的線性組合，即均差可以表示為函數(shù)值的線性組合，即稱之為稱之為均差的對(duì)稱性（也稱為對(duì)稱性質(zhì)）均差的對(duì)稱性（也稱為對(duì)稱性質(zhì)）。性質(zhì)性質(zhì)2 由性質(zhì)由性質(zhì)1立刻得到立刻得到或或11202010, nnnnnnnxxxxxfxxxfxxxf01021102110,xxxxxfxxxfxxxxfxxxfnnnnn 性質(zhì)性質(zhì)3 n次多項(xiàng)式次多項(xiàng)式f(x)的的k階階差商差商, ,當(dāng)當(dāng)k n時(shí)是一個(gè)時(shí)是一個(gè)n- -

26、k次多次多項(xiàng)式項(xiàng)式; ;當(dāng)當(dāng)kn時(shí)恒等于時(shí)恒等于0.性質(zhì)性質(zhì)4 若若f(x)在在a,b上存在上存在n階導(dǎo)數(shù)階導(dǎo)數(shù), 且節(jié)點(diǎn)且節(jié)點(diǎn)x0 , x1 , xna,b ,則至少存在一點(diǎn)則至少存在一點(diǎn) a, b 滿足下式滿足下式!)(,)(10nfxxxfnn 例例1 f (x)=6x8+7x510, 求求f 1,2, ,9及及f 1,2, ,10. 解解 f (8)(x)=68 !, f 1,2, ,9=-6, f (9)(x)=0, f 1,2, ,10=0.2.3.2 牛頓插值多項(xiàng)式牛頓插值多項(xiàng)式設(shè)設(shè)x是是a，b上一點(diǎn)，由一階均差定義得上一點(diǎn)，由一階均差定義得)(,)()(000 xxxxfxfx

27、f 同理，由二階均差定義同理，由二階均差定義)(,110100 xxxxxfxxfxxf 如此繼續(xù)下去，可得一系列等式如此繼續(xù)下去，可得一系列等式000)()(,xxxfxfxxf 110010,xxxxfxxfxxxf 得得得得01010 , ,()nnnnf x xxf xxxf x xxxx )(,)()(000 xxxxfxfxf )(,110100 xxxxxfxxfxxf )(,221021010 xxxxxxfxxxfxxxf 依次把后式代入前式，最后得依次把后式代入前式，最后得00000100101001001201012012( )() ,()(),() ,()()(),()

28、,()() ,()()()f xf xf x xxxf xf xxxxf x xxxxxxf xf xxxxf xxxxxxxf x xxxxxxxxx00100101001001201012012( )(),() ,()()(),(),()() ,()()()( )( )nnf xf xf x xxxf x x xxxxxf xf x xxxf x x xxxxxf x x x xxxxxxxN xR x 00100120101010011( )( ) , () , ,()() , ,()()( ) , , ( )nnnnkkkN xf xf x x x xf x x xx xx xf x

29、xxx xx xf xf x xxx 其中其中00101( ) ,()()() ,( )nnnnnR xf x xxxxxxxxf x xxx ( )( )( )nnf xN xR x 可見可見, Nn(x)為次數(shù)不超過為次數(shù)不超過n 的多項(xiàng)式的多項(xiàng)式,且易知且易知 Rn(xi)= 0 即即 Nn(xi)= yi , (i=0,1, ,n) 滿足插值條件滿足插值條件, 故其為插值問題的解故其為插值問題的解, Nn(x)稱為稱為牛頓牛頓插值多項(xiàng)式插值多項(xiàng)式。001001201001( )( ) ,() ,()() ,()()nnnN xf xf x xx xf x x xx xx xf xxx

30、xx x 001( ) ,()()()nnnRxf x xxxxxxxx Rn(x)稱為稱為牛頓型插值余項(xiàng)牛頓型插值余項(xiàng)。由插值多項(xiàng)式的唯一性知，它與拉格朗日插值多項(xiàng)式由插值多項(xiàng)式的唯一性知，它與拉格朗日插值多項(xiàng)式是等價(jià)的是等價(jià)的,即即 Ln(x) Nn(x)且有如下且有如下遞推形式遞推形式)()(,)()(1001 nnnnxxxxxxfxNxN和和余項(xiàng)公式余項(xiàng)公式)()(,)(010nnnxxxxxxxxfxR )()()!1()(0)1(nnxxxxnf 由此即得性質(zhì)由此即得性質(zhì)4。且。且)()(,)()(,)(01100101nnnnnnnxxxxxxxxfxxxxxxxxfxR xk

31、 f(xk)一階均差一階均差二階均差二階均差三階均差三階均差四階均差四階均差0.400.550.650.800.900.410750.578150.696750.888111.026521.11601.18601.27571.38410.28000.35880.43360.19700.21370.0344例例1 已知已知f(x)=shx的數(shù)表的數(shù)表,求二次牛頓插值多項(xiàng)式求二次牛頓插值多項(xiàng)式,并由并由 此計(jì)算此計(jì)算f(0.596)的近似值。的近似值。 )55. 0)(40. 0(2800. 0)40. 0(1160. 141075. 0)(2 xxxxN解解 由上表可得過前三點(diǎn)的二次牛頓插值多項(xiàng)

32、式為由上表可得過前三點(diǎn)的二次牛頓插值多項(xiàng)式為632010. 0)596. 0()596. 0(2 Nf又又1970. 0,3210 xxxxf可得過前四點(diǎn)的三次牛頓插值多項(xiàng)式可得過前四點(diǎn)的三次牛頓插值多項(xiàng)式)65. 0)(55. 0)(40. 0(1970. 0)()(23 xxxxNxN故故6319145. 0)596. 0()596. 0(3 Nf故故)55. 0)(40. 0(2800. 0)40. 0(1160. 141075. 0)(2 xxxxN)80. 0)(65. 0)(55. 0)(40. 0(0344. 0)(3 xxxxxR可得可得N3(x)的截?cái)嗾`差的截?cái)嗾`差63103

33、4. 0)596. 0( R0344. 0,40 xxf 設(shè)函數(shù)設(shè)函數(shù)y=f(x)在在等距節(jié)點(diǎn)等距節(jié)點(diǎn)xi=x0+ih (i=0,1, ,n)上上的函數(shù)值為的函數(shù)值為fi=f(xi)(h為為步長(zhǎng)步長(zhǎng))定義定義2 fi=fi+1-fi 和和 fi=fi-fi-1分別稱為函數(shù)分別稱為函數(shù)f(x)在點(diǎn)在點(diǎn)xi處的處的一階向前差分一階向前差分和和一階向一階向后差分后差分。 一般地一般地, f(x) 在點(diǎn)在點(diǎn) xi 處的處的 m 階向前差分階向前差分和和 m 階向階向后差分后差分分別為分別為 mfi= m-1fi+1- m-1fi 和和 mfi= m-1fi - m-1fi-12.4 差分與等距節(jié)點(diǎn)插值

34、差分與等距節(jié)點(diǎn)插值2.4.1 差分及其性質(zhì)差分及其性質(zhì)函數(shù)值函數(shù)值一階差分一階差分二階差分二階差分三階差分三階差分四階差分四階差分. f (x0) f (x1) f (x2) f (x3)f (x4) . f0 ( f1) f1 ( f2) f2 ( f3) f3 ( f4) . 2f0 ( 2f2) 2f1 ( 2f3) 2f2 ( 2f4) . 3f0 ( 3f3) 3f1 ( 3f4). 4f0 ( 4f4) .構(gòu)造構(gòu)造差分表差分表5-2容易證明，差分有如下容易證明，差分有如下基本性質(zhì)基本性質(zhì)性質(zhì)性質(zhì)1 各階差分均可用函數(shù)值表示各階差分均可用函數(shù)值表示. 即即jinjnnjjinnnin

35、nininfcfcfcff 011) 1() 1(jijnnjjninnniniinfcfcfcff 011) 1() 1(且有等式且有等式 nfi= nfi+n .性質(zhì)性質(zhì)3 均差與差分的關(guān)系式為均差與差分的關(guān)系式為111,!1,!miii mimmi mi miimf x xxfm hf xxxfm h性質(zhì)性質(zhì)2 函數(shù)值均可用各階差分表示函數(shù)值均可用各階差分表示. 即即injjjninnniniinfcfcfcff 01且有差分與微商的關(guān)系式為且有差分與微商的關(guān)系式為),()()(nkknnnnxxfhf 差分的其它性質(zhì)參看本章差分的其它性質(zhì)參看本章p59習(xí)題習(xí)題8，9，10，11.代入牛

36、頓插值公式代入牛頓插值公式 ,可得可得)1()1(!)1(! 2)()(002000 ntttnfttftffthxNxNnnn稱為稱為牛頓向前插值公式牛頓向前插值公式，其，其余項(xiàng)余項(xiàng)為為),()()!1()()1()()(0)1(10nnnnnxxfhnntttthxRxR 插值節(jié)點(diǎn)為插值節(jié)點(diǎn)為 xi=x0+ih (i=0,1, ,n), 如果要計(jì)算如果要計(jì)算 x0附近附近點(diǎn)點(diǎn) x 處的函數(shù)值處的函數(shù)值f(x), 可令可令 x=x0+th (0 t n)2.4.2 等距節(jié)點(diǎn)差值公式等距節(jié)點(diǎn)差值公式 類似地類似地, 若計(jì)算若計(jì)算 xn 附近的函數(shù)值附近的函數(shù)值 f(x), 可令可令 x=xn+

37、th (- n t 0) ，可得，可得牛頓向后插值公式牛頓向后插值公式)1()1(!)1(! 2)()(2 ntttnfttftffthxNxNnnnnnnnn),(, )()!1()()1()()(0)1(1nnnnnnxxfhnntttthxRxR 及其及其余項(xiàng)余項(xiàng)例例2 設(shè)設(shè) y=f(x)=ex, xi=1, 1.5, 2, 2.5, 3, 用三次插值多項(xiàng)用三次插值多項(xiàng) 式求式求f(1.2) 及及f(2.8)的近似值的近似值.解解 相應(yīng)的函數(shù)值及差分表如下相應(yīng)的函數(shù)值及差分表如下:xif (xi)一階差分一階差分二階差分二階差分三階差分三階差分 四階差分四階差分11.522.532.71

38、828 4.481697.2890612.1824920.08554 1.76341 2.90347 4.793437.90305 1.14396 1.886063.10962 0.74210 1.223560.48146求求f(1.2)用用牛頓前插公式牛頓前插公式, 且由且由 1.2=1+0.5t, 得得t=0.431.14396(1.2)(1.2)2.71828 1.76341 0.40.4 (0.4 1)2!0.742100.4 (0.4 1)(0.4 2)3.33386323!fN xif (xi)一階差分一階差分二階差分二階差分三階差分三階差分 四階差分四階差分11.522.532.

39、71828 4.481697.2890612.1824920.08554 1.76341 2.90347 4.793437.90305 1.14396 1.886063.10962 0.74210 1.223560.48146求求f(2.8)用用牛頓后插公式牛頓后插公式,且由且由 2.8=3+0.5t, 得得t= -0.43(2.8)(2.8)fN xif (xi)一階差分一階差分二階差分二階差分三階差分三階差分四階差分四階差分11.522.532.71828 4.481697.2890612.1824920.08554 1.76341 2.90347 4.793437.90305 1.143

40、96 1.886063.10962 0.74210 1.223560.481463.1096220.08554 7.90305 ( 0.4)( 0.4) ( 0.4 1)2! 1.22356( 0.4) ( 0.4 1)( 0.4 2)15.76808723! 求求f(1.8)呢呢?2.5.1 三次埃爾米特插值多項(xiàng)式三次埃爾米特插值多項(xiàng)式 設(shè)設(shè) y=f(x)是區(qū)間是區(qū)間a, b上的實(shí)函數(shù)上的實(shí)函數(shù), x0, x1 是是a, b上相異兩點(diǎn)上相異兩點(diǎn), 且且 x0 x1, y=f (x) 在在xi上的函數(shù)值和一階導(dǎo)數(shù)值分別為上的函數(shù)值和一階導(dǎo)數(shù)值分別為 yi=f (xi) (i=0,1)和和mi

41、= f (xi) (i=0,1), 求三次多項(xiàng)式求三次多項(xiàng)式 H3(x), 使其使其滿足：滿足：33()(0,1)()iiiiHxyiHxm H3(x)稱為稱為三次埃爾米特插值多項(xiàng)式三次埃爾米特插值多項(xiàng)式。法法1822 -1901 2.5 埃爾米特埃爾米特(Hermite)插值插值構(gòu)造三次埃爾米特插值多項(xiàng)式如下構(gòu)造三次埃爾米特插值多項(xiàng)式如下:定理定理3 滿足條件式滿足條件式 的三次埃爾米特插值多項(xiàng)式存在且唯一。的三次埃爾米特插值多項(xiàng)式存在且唯一。33(),()(0,1)iiiiHxy Hxm i 300110011( )( )( )( )( )Hxyxyxmxmx 條條 件件函函 數(shù)數(shù)函數(shù)值函

42、數(shù)值導(dǎo)數(shù)值導(dǎo)數(shù)值x0 x1x0 x1 0(x)1000 1(x)0100 0(x)0010 1(x)0001由由0)()(1010 xx 可將它寫成可將它寫成2100)()(xxxxbax 21000)(11)(xxax ，得，得由由 ，所以，所以）（，得，得再由再由3100020)(xxbx 21010100)(21)(xxxxxxxxx 20101011)(21)(xxxxxxxxx ）（將將同同理理10 xx ，可可令令同同樣樣由由0)()()(101000 xxx 2100)()(xxxxcx ，再再由由1)(00 x 210)(1xxc 得得,)()(210100 xxxxxxx 2

43、01011)()(xxxxxxx 210100)()(xxxxxxx 201011)()(xxxxxxx 2201000022101111( )12 ( ) ( )( )() ( )( )12 ( ) ( )( )() ( )xlx lxxxx lxxlx lxxxx lx,)(21 )(21010100 xxxxxxxxx ,)(21 )(20101011xxxxxxxxx 即即)(),(10 xlxl插值點(diǎn)的插值點(diǎn)的Lagrange),(),(1100yxyx為為以以一次基函數(shù)一次基函數(shù). 可得滿足條件的可得滿足條件的三次埃爾米特插值多項(xiàng)式三次埃爾米特插值多項(xiàng)式為為300110011( )

44、( )( )( )( )Hxyxyxmxmx220011011001011022010011011012()12()()()()()xxxxxxxxyyxxxxxxxxxxxxm xxm xxxxxx 定理定理4 設(shè)設(shè)f(x)在包含在包含x0、x1的區(qū)間的區(qū)間a,b內(nèi)存在四階內(nèi)存在四階導(dǎo)數(shù)，則當(dāng)導(dǎo)數(shù)，則當(dāng)xa,b時(shí)有時(shí)有余項(xiàng)余項(xiàng)(4)2233011( )( )( )( )() ()4!R xf xH xfx xx x 設(shè)設(shè))(max)4(410 xfMxxx 則當(dāng)則當(dāng)x(x0 , x1)時(shí)時(shí),余項(xiàng)有如下估計(jì)式（余項(xiàng)有如下估計(jì)式（誤差限誤差限）443384)(hMxR 2.5.2 誤差估計(jì)誤差估

45、計(jì)( , )a b 且與且與x有關(guān)有關(guān))例例2 已知已知f(x)=x1/2及其一階導(dǎo)數(shù)的數(shù)據(jù)見下表及其一階導(dǎo)數(shù)的數(shù)據(jù)見下表,用埃爾用埃爾米特插值公式計(jì)算米特插值公式計(jì)算1251/2的近似值的近似值,并估計(jì)其截?cái)嗾`差并估計(jì)其截?cái)嗾`差. x121144 f(x)1112 f (x)1/221/24解解23121144( )1112144121121144xxHx21441211212121144144121xx2112114422144121121144xx2114412124121144144121xx得得3125(125)11.18035H由由2/7)4(1615)(xxf 可求得可求得223

46、323151(125)419384 1615190.000012384 12111R 2233322221112( )2219144265212123231112114414412122 2324 23H xxxxxxxxx 2.6 分段低次插值分段低次插值先看下面的例子先看下面的例子 對(duì)對(duì)(x)=(1+25x2)-1,在區(qū)間在區(qū)間-1,1上取等距節(jié)點(diǎn)上取等距節(jié)點(diǎn) xi=- -1+ih, i=0,1,10,h=0.2,作作(x)關(guān)于節(jié)點(diǎn)關(guān)于節(jié)點(diǎn) xi(i=0,1,10)的的10次插值多項(xiàng)式次插值多項(xiàng)式 L10(x), 如圖所示如圖所示xyo1-10.511.522511yy=L10(x)這個(gè)現(xiàn)

47、象被稱為這個(gè)現(xiàn)象被稱為Runge現(xiàn)象現(xiàn)象. 表明高次插值的不穩(wěn)定性表明高次插值的不穩(wěn)定性. 實(shí)際上實(shí)際上, 很少采用高于很少采用高于7次的插值多項(xiàng)式次的插值多項(xiàng)式.2.6.1 分段線性插值分段線性插值01()(0,1,., ),iinyf xin axxxb 已已知知求一個(gè)分段函數(shù)求一個(gè)分段函數(shù)P(x), 使其滿足使其滿足:(1) P(xi)=yi (i=0,1, ., n);(2) 在每個(gè)子區(qū)間在每個(gè)子區(qū)間xi，xi+1 上是線性函數(shù)上是線性函數(shù).稱滿足上述條件的函數(shù)稱滿足上述條件的函數(shù)P(x)為為分段線性插值函數(shù)分段線性插值函數(shù).),.,1 , 0)(nixfyii分別作線性插值得分別作線

48、性插值得,在每個(gè)子區(qū)間在每個(gè)子區(qū)間xi，xi+1已知已知11111( ),(0,1,1)iiiiiiiiiixxxxP xyyxx xxxxxin 1111( ),(0,1,1)iiiiiiiiiiixxxxP xyyxx xhhhxxin 或或由線性插值的誤差即得分段線性插值在區(qū)間由線性插值的誤差即得分段線性插值在區(qū)間xi, xi+1上的上的余項(xiàng)估計(jì)式余項(xiàng)估計(jì)式為為1122( )()()()()2!max()max()88iiiiixxxaxbff xP xxxxxhhfxfx 201max,max()iinaxbhhMfx 因此因此,在插值區(qū)間在插值區(qū)間a,b上有余項(xiàng)上有余項(xiàng)22()(),

49、 ,8hfxP xMxa b 2.6.2 分段拋物線插值分段拋物線插值(2) 在每個(gè)子區(qū)間在每個(gè)子區(qū)間xi-1, xi+1 上，上，L(x)是次數(shù)不超過是次數(shù)不超過2的的 多項(xiàng)式多項(xiàng)式.稱滿足上述條件的函數(shù)稱滿足上述條件的函數(shù)L(x)為為分段拋物線插值函數(shù)分段拋物線插值函數(shù).(1) L(xi)=yi (i=0,1, ., n);對(duì)對(duì)01naxxxb 求一個(gè)分段函數(shù)求一個(gè)分段函數(shù)L(x), 使其滿足使其滿足:即將區(qū)間即將區(qū)間a, b分為小區(qū)間分為小區(qū)間xi-1, xi+1 (i=1,2, ,n)2.6.3 分段三次分段三次Hermite插值插值(),()(0,1, ),iiiiyf xmfxin

50、 已知已知01naxxxb 求一個(gè)分段函數(shù)求一個(gè)分段函數(shù)H(x), 使其滿足使其滿足:(2) 在每個(gè)子區(qū)間在每個(gè)子區(qū)間xi, xi+1 上，上，H(x)是次數(shù)不超過是次數(shù)不超過3的的 多項(xiàng)式多項(xiàng)式.稱滿足上述條件的函數(shù)稱滿足上述條件的函數(shù)H(x)為為分段三次分段三次Hermite插值插值函數(shù)函數(shù).(1)(),()(0,1, ),iiiiH xyHxmin 2211122111( )1 2()1 2()()()()()iiiiiiiiiiiiiiiiiixxxxxxxxH xyyhhhhxxxxm xxmxxhh 22111332211122( )1 2()()1 2()()()()()()ii

51、iiiiiiiiiiiiiiyyH xxxxxxxxxhhmmxxxxxxxxhh 1(0,1,1)iiihxxin 或或xi，xi+1上上(),()(0,1, ),iiiiyf xmfxin 得在每個(gè)子區(qū)間得在每個(gè)子區(qū)間由由分段三次埃爾米特插值在區(qū)間分段三次埃爾米特插值在區(qū)間xi, xi+1上的上的余項(xiàng)估計(jì)式余項(xiàng)估計(jì)式為為1(4)2214(4)1( )( )( )() ()4!max( ) ,384iiiiiiixxxff xH xxxxxhfxxxx 因此，因此，在插值區(qū)間在插值區(qū)間a, b上有余項(xiàng)上有余項(xiàng)44()(), , 384hfxH xMxa b (4)401max,max()ii

52、naxbhhMfx 例例3 構(gòu)造函數(shù)構(gòu)造函數(shù)f(x)=lnx在在1x10上的數(shù)表上的數(shù)表, 應(yīng)如何應(yīng)如何選取步長(zhǎng)選取步長(zhǎng)h,才能使利用數(shù)表進(jìn)行分段插值時(shí)誤差不才能使利用數(shù)表進(jìn)行分段插值時(shí)誤差不超過超過0.510-4 。解解221101( ),max( )1.xfxMfxx 欲使欲使2241101( )( )max( )10882xhhf xP xfx 即進(jìn)行分段線性插值時(shí)，應(yīng)取即進(jìn)行分段線性插值時(shí)，應(yīng)取h210-2，誤差不，誤差不超過超過0.510-4。22 10h 得得(4)(4)441106( ),max( )6.xfxMfxx 欲使欲使44(4)41101( )( )max( )1038

53、4642xhhf xH xfx 142 210h 得得即進(jìn)行分段三次埃爾米特插值時(shí)即進(jìn)行分段三次埃爾米特插值時(shí),應(yīng)取應(yīng)取誤差不超過誤差不超過0.510-4 。142 210h 2.7.1 問題的提出問題的提出定義定義 給定區(qū)間給定區(qū)間a,b的一個(gè)劃分的一個(gè)劃分 a=x0 x1xn=b， yi=f (xi) (i=0,1,n),如果函數(shù)如果函數(shù)S(x)滿足：滿足：(1) S(xi )=yi (i=0,1,n);(2) 在每個(gè)小區(qū)間在每個(gè)小區(qū)間xi, xi+1 (i=0,1,.,n-1)上是次數(shù)不超上是次數(shù)不超過過3的多項(xiàng)式的多項(xiàng)式;(3) 在每個(gè)內(nèi)節(jié)點(diǎn)在每個(gè)內(nèi)節(jié)點(diǎn)xi (i=1,2,.,n-1)

54、上具有上具有二階連續(xù)導(dǎo)數(shù)二階連續(xù)導(dǎo)數(shù), 則稱則稱 S(x) 為關(guān)于上述劃分的一個(gè)為關(guān)于上述劃分的一個(gè)三次多項(xiàng)式樣條三次多項(xiàng)式樣條 函數(shù)函數(shù)，簡(jiǎn)稱，簡(jiǎn)稱三次樣條三次樣條。2.7 三次樣條插值三次樣條插值 S(x)在每個(gè)小區(qū)間在每個(gè)小區(qū)間xi , xi+1上是一個(gè)次數(shù)不超過上是一個(gè)次數(shù)不超過3的多項(xiàng)式的多項(xiàng)式, 因此需確定因此需確定四個(gè)待定常數(shù)四個(gè)待定常數(shù), 一共有一共有n個(gè)小個(gè)小區(qū)間區(qū)間,故應(yīng)故應(yīng)確定確定4n個(gè)系數(shù)個(gè)系數(shù), S(x)在在n-1個(gè)內(nèi)節(jié)點(diǎn)上個(gè)內(nèi)節(jié)點(diǎn)上具有具有二階連續(xù)導(dǎo)數(shù)，應(yīng)滿足條件二階連續(xù)導(dǎo)數(shù)，應(yīng)滿足條件)1, 2 , 1()0()0()0()0()0()0( nixSxSxSxSx

55、SxSiiiiii即有即有3n-3個(gè)連續(xù)條件，再加上個(gè)連續(xù)條件，再加上S(x) 滿足的插值條件滿足的插值條件n+1個(gè)，共計(jì)個(gè)，共計(jì)4n-2個(gè)，因此還需要個(gè)，因此還需要2個(gè)條件才能確定個(gè)條件才能確定S(x)，通常補(bǔ)充兩個(gè)，通常補(bǔ)充兩個(gè)邊界條件邊界條件。2.7.2 三彎矩方程三彎矩方程Mi來求來求S(x)的方法稱為的方法稱為三彎矩法三彎矩法。),.,1 , 0()(niMxSii 為參數(shù)為參數(shù),這種通過這種通過確定確定設(shè)設(shè)iiiiiihxxMhxxMxS 11) )( ( 在在xi , xi+1上是一次多項(xiàng)式上是一次多項(xiàng)式, 且可表示為且可表示為 )(xS 對(duì)對(duì) 積分兩次并利用積分兩次并利用S(x

56、i)=yi和和S(xi+1)=yi+1定出積定出積分常數(shù)得分常數(shù)得)(xS 321112111()()( )()666() , (0,1,1)6iiiiiiiiiiiiiiiixxxxM hxxS xMMyhhhM hyxx xin hxxi 321112111()()( )()666() , (0,1,1)6iii iiiiiiiiiiiiixxx xMhxxS xMMyhhhM hyxx xin 對(duì)對(duì)S(x)求導(dǎo)得求導(dǎo)得iiiiiiiiiiiihMMhyyhxxMhxxMxS62)(2)()(112121 1,(0,1,1)iixx xin hxxi 所以所以11111(0)36(0)63

57、iiiiiiiiiiiiiiiihhyyS xMMhhhyyS xMMh (i=1,2,.,n-1) )( () )( (00iixSxS由由iiiiiiiiiiiihMMhyyhxxMhxxMxS62)(2)()(112121 11111116336iiiiiiiiiiiiiihhyyhhyyMMMMhh 111111111166 ,iiiiiiiiiiiiiiiiiiiiihhhhhhyyyydf xx xhhhh 112(1,2,1)iiiiiiMMMdin得得其中其中11111116336iiiiiiiiiiiiiihhyyhhyyMMMMhh 由公式由公式nnmxSmxS) )( (, ,) )( (001. 邊界條件邊界條件為為11111(0)36(0)63iiiiiiiiiiiiiiiihhyyS xMMhhhyyS xMMh 00100001011111()36()63nnnnnnnnnhhyymS x