數(shù)值分析第五插值法

1、1第五章第五章 插值法插值法 Lagrange插值插值 Newton插值插值 Hermite插值插值2 為什么需要插值為什么需要插值? 函數(shù)表達(dá)式復(fù)雜函數(shù)表達(dá)式復(fù)雜, 不便于計(jì)算和進(jìn)行理論分析不便于計(jì)算和進(jìn)行理論分析; 沒(méi)有函數(shù)表達(dá)式?jīng)]有函數(shù)表達(dá)式, 只給出離散樣點(diǎn)只給出離散樣點(diǎn). 找簡(jiǎn)單函數(shù)近似找簡(jiǎn)單函數(shù)近似, 即函數(shù)逼近即函數(shù)逼近. 函數(shù)逼近常用方法函數(shù)逼近常用方法: 插值法插值法, 曲線擬合法曲線擬合法. 插值法插值法: 多項(xiàng)式插值多項(xiàng)式插值, 三角多項(xiàng)式插值三角多項(xiàng)式插值.3 已知函數(shù)已知函數(shù) f (x)在區(qū)間在區(qū)間 a, b上上 (n+1) 個(gè)不同點(diǎn)個(gè)不同點(diǎn) x0, x1, x2,

2、, xn 處的函數(shù)值處的函數(shù)值 yi= f (xi) (i=0, 1, 2, n), 求函數(shù)求函數(shù) n(x), 使其滿足使其滿足(1) n(x)為至多為至多n次多項(xiàng)式次多項(xiàng)式, 即即(2) 滿足插值條件滿足插值條件nnnxaxaxaax 2210)( )., 1 , 0()()(niyxfxiiin n(x): 插值多項(xiàng)式插值多項(xiàng)式xi : 插值節(jié)點(diǎn)插值節(jié)點(diǎn) a, b: 插值區(qū)間插值區(qū)間1 Lagrange插值插值4First-order second-order third-order幾何意義幾何意義: n次多項(xiàng)式插值就是過(guò)次多項(xiàng)式插值就是過(guò) (n+1)個(gè)點(diǎn)個(gè)點(diǎn) (xi, f (xi) (i

3、=0, 1, , n), 作一條多項(xiàng)式曲線作一條多項(xiàng)式曲線 y= n(x)近似曲線近似曲線 y=f(x).5 三個(gè)基本問(wèn)題三個(gè)基本問(wèn)題 重點(diǎn)重點(diǎn) 考考 插值多項(xiàng)式插值多項(xiàng)式 n(x)是否存在唯一？是否存在唯一？ 若若 n(x)存在存在, 截?cái)嗾`差截?cái)嗾`差 f (x) n(x)=? 如何求如何求 n(x)？6 插值多項(xiàng)式插值多項(xiàng)式 n(x)的存在唯一性的存在唯一性 nnnnnnnnnnnnnnyxaxaxaaxyxaxaxaaxyxaxaxaax2210112121101002020100)()()( n 次多項(xiàng)式次多項(xiàng)式 n(x)有有(n+1)個(gè)待定系數(shù)個(gè)待定系數(shù)ai (i=0, 1, 2,

4、, n), 插值條件插值條件 n(xi)= f (xi)= yi (i=0, 1, 2, , n)也是也是(n+1)個(gè)個(gè), 恰好給出恰好給出(n+1)個(gè)方程個(gè)方程.7 )()()()(11112102102222212110200nnnnnnnnnxfxfxfxfaaaaxxxxxxxxxxxx即即系數(shù)矩陣系數(shù)矩陣A的行列式是的行列式是Vandermonde行列式行列式, 其值為其值為 njijiijxxA,0,)()det( 當(dāng)插值節(jié)點(diǎn)當(dāng)插值節(jié)點(diǎn)xi (i=0, 1, 2, , n)互不相同時(shí)互不相同時(shí), 此行列此行列式不為式不為0, 即系數(shù)矩陣即系數(shù)矩陣A可逆可逆. 因此因此ai (i=0

5、, 1, 2, , n), 存在唯一存在唯一, 即即 n(x)存在唯一存在唯一.8 插值余項(xiàng)與誤差估計(jì)插值余項(xiàng)與誤差估計(jì))()()(xxfxRnn 截?cái)嗾`差或插值余項(xiàng)截?cái)嗾`差或插值余項(xiàng)定理定理 若若,)()1(baCxfn 則存在則存在 (a, b), 使得使得).()()!1()()(10)1(nnnxxxxxxnfxR 證明證明, 0)()()( iniinxxfxR 故故).()()()(10nnxxxxxxxKxR 其中其中 K (x)是與是與 x有關(guān)的待定函數(shù)有關(guān)的待定函數(shù).如何求如何求 K (x) ?9現(xiàn)把現(xiàn)把x看成是看成是a, b上的固定點(diǎn)上的固定點(diǎn), 作輔助函數(shù)作輔助函數(shù))()

6、()()()()(10nnxtxtxtxKttftF )(0)()()(10 xFxFxFxFn 即即 F(t )在在a, b上有上有 n+2 個(gè)零點(diǎn)個(gè)零點(diǎn). 根據(jù)根據(jù)Rolle定理定理, F (t )在在 F(t )的兩個(gè)零點(diǎn)之間至少有一個(gè)零點(diǎn)的兩個(gè)零點(diǎn)之間至少有一個(gè)零點(diǎn), 故故 F (t )在在(a, b)內(nèi)至少有內(nèi)至少有 (n+1)個(gè)零點(diǎn)個(gè)零點(diǎn). 對(duì)對(duì)F (t )再應(yīng)用再應(yīng)用Rolle 定理，定理， 可知可知F (t )在在(a, b)內(nèi)內(nèi)至少有至少有 n 個(gè)零點(diǎn)個(gè)零點(diǎn). 依此類推依此類推, F(n+1) (t )在在(a, b)內(nèi)至少內(nèi)至少有一個(gè)零點(diǎn)有一個(gè)零點(diǎn), 記之為記之為 (a,

7、b), 使得使得, 0)()!1(0)()()1()1( xKnfFnn 則則10因此因此.),(,)!1()()()1(xbanfxKn且依賴且依賴 )()()()(10nnxxxxxxxKxR ).()()!1()(10)1(nnxxxxxxnf 若若,)(max1)1(, nnbaxMxf則則| )()( |)!1(| )(|101nnnxxxxxxnMxR 11 當(dāng)當(dāng) n =1時(shí)時(shí), 線性插值余項(xiàng)為線性插值余項(xiàng)為).,(),)(2)( )(1010 xxxxxxfxR 當(dāng)當(dāng) n =2時(shí)時(shí), 拋物線插值余項(xiàng)為拋物線插值余項(xiàng)為).,(),)()(6)( )(20210 xxxxxxxxfx

8、R 12求求 L1(x)(1) 至多至多1次多項(xiàng)式次多項(xiàng)式;).1 , 0()()(1 iyxfxLiii(2)已知已知ix1x)(iixfy 1y0 x0y Lagrange方法求插值多項(xiàng)式方法求插值多項(xiàng)式 當(dāng)用當(dāng)用Lagrange方法求插值多項(xiàng)式時(shí)方法求插值多項(xiàng)式時(shí), 其其n次插次插值多項(xiàng)式記為值多項(xiàng)式記為L(zhǎng)n(x). n=1的情形的情形13x0 x1)()(0010101xxxxyyyxL 10100101yxxxxyxxxx 1100)()(yxlyxl )(0 xl1次多項(xiàng)式次多項(xiàng)式ix1x0 x01)(1xl1次多項(xiàng)式次多項(xiàng)式ix1x0 x01n = 1 線性插值多項(xiàng)式線性插值多項(xiàng)

9、式 L1(x)是過(guò)兩點(diǎn)是過(guò)兩點(diǎn) (x0, y0), (x1, y1)的直線方程的直線方程14已知已知ix1x)(iixfy 1y0 x0y求求 L2(x)(1) 至多至多2次多項(xiàng)式次多項(xiàng)式;).2 , 1 , 0()()(2 iyxfxLiii(2)2x2y 二次插值多項(xiàng)式二次插值多項(xiàng)式15n = 2)()()(2101201xxxxxxxxxl )()()(1202102xxxxxxxxxl )()()()()()()(2211002xfxlxfxlxfxlxL )(2010 xxxx )(0 xl)(1xx )(2xx )(0 xl2次多項(xiàng)式次多項(xiàng)式ix1x0 x012x0)(1xl2次多

10、項(xiàng)式次多項(xiàng)式)(2xl2次多項(xiàng)式次多項(xiàng)式ix1x0 x02x01ix1x0 x02x01 二次插值多項(xiàng)式二次插值多項(xiàng)式16l1(x)f (x1)l2(x)f (x2)l0(x)f (x0)x0 x1x2 二次插值多項(xiàng)式二次插值多項(xiàng)式L2(x)17已知已知ix2x1xnx)(iixfy 1y2yny0 x0y求求 Ln(x)(1) 至多至多n次多項(xiàng)式次多項(xiàng)式;)., 1 , 0()()(niyxfxLiiin (2)插值節(jié)點(diǎn)插值節(jié)點(diǎn)插值多項(xiàng)式插值多項(xiàng)式 n次次Lagrange插值多項(xiàng)式插值多項(xiàng)式18)()()()()(1100 xlyxlyxlyxlyxLnniin 其中其中 li (x) 為插

11、值為插值基函數(shù)基函數(shù))(xlin次多項(xiàng)式次多項(xiàng)式)()()(1110niiiiiiixxxxxxxxxx )(xli)(0 xx )(1xx )(1 ixx)(1 ixx)(nxx ,)()()(0 nijjjijixxxxxl)., 1 , 0(ni ixixnx0 x11x1 ix1 ix00000 n次次Lagrange插值多項(xiàng)式插值多項(xiàng)式19例例 已知函數(shù)已知函數(shù) y=lnx 的函數(shù)表如下的函數(shù)表如下xi2.56492.48492.39792.3026f (xi6391分別用分別用Lagrange線性插值和拋物線插值求線性插值和拋物線插值求ln11.5的近的近

12、似值似值, 并估計(jì)誤差并估計(jì)誤差.解解線性插值線性插值. ,111211)12(121112)11()(1 xfxfxL)12()11(21)5 .11(5 .11ln1ffL 取兩個(gè)節(jié)點(diǎn)取兩個(gè)節(jié)點(diǎn) x0=11, x1=12, 插值函數(shù)為插值函數(shù)為計(jì)算器計(jì)算器.4414. 2 20,1111max| )( |max2212,1112,112 xxfMxx| )125 .11)(115 .11( |2| )5 .11(|21 MR.10033. 1811132 拋物線插值拋物線插值. )1213)(1113()12)(11(5649. 2)1312)(1112()13)(11(4849. 2)1

13、311)(1211()13)(12(3979. 2)(2 xxxxxxxL取取x0=11, x1=12, x1=13, 插值多項(xiàng)式為插值多項(xiàng)式為21.442275. 2)5 .11(5 .11ln2 L,1122max| )( |max3313,1113,113 xxfMxx| )135 .11)(125 .11)(115 .11( |6| )5 .11(|32 MR.1039. 9811153 442347. 25 .11ln 22例例 已知函數(shù)已知函數(shù) y=lnx 的函數(shù)表如下的函數(shù)表如下xi2.56492.48492.39792.3026f (xi6391分別用

14、分別用Lagrange線性插值和拋物線插值求線性插值和拋物線插值求ln11.5的近的近似值似值, 并估計(jì)誤差并估計(jì)誤差.解解線性插值線性插值. 取兩個(gè)節(jié)點(diǎn)取兩個(gè)節(jié)點(diǎn) x0=11, x1=12, 插值函數(shù)為插值函數(shù)為計(jì)算器計(jì)算器X=11, 12Y=2.3979, 2.4849pp=polyfit(X,Y,1)ln11dot5=polyval(pp,11.5)23例例 已知函數(shù)已知函數(shù) y=lnx 的函數(shù)表如下的函數(shù)表如下xi2.56492.48492.39792.3026f (xi6391分別用分別用Lagrange線性插值和拋物線插值求線性插值和拋物線插值求ln11.

15、5的近的近似值似值, 并估計(jì)誤差并估計(jì)誤差.解解計(jì)算器計(jì)算器X=11, 12, 13Y=2.3979, 2.4849, 2.5649pp=polyfit(X,Y,2)ln11dot5=polyval(pp,11.5)拋物線插值拋物線插值. 取取x0=11, x1=12, x1=13, 插值多項(xiàng)式為插值多項(xiàng)式為24 由于插值基函數(shù)只與由于插值基函數(shù)只與節(jié)點(diǎn)有關(guān)而與函數(shù)值無(wú)關(guān)節(jié)點(diǎn)有關(guān)而與函數(shù)值無(wú)關(guān), 因此當(dāng)插值節(jié)點(diǎn)相同而函數(shù)值不同時(shí)因此當(dāng)插值節(jié)點(diǎn)相同而函數(shù)值不同時(shí), 所有的所有的Lagrange插值基函數(shù)均不變插值基函數(shù)均不變, 此時(shí)用此時(shí)用Lagrange插值插值多項(xiàng)式比較方便多項(xiàng)式比較方便.

16、11110011001100, , , , :new2, , , :new1, , ,:original nnnnnnnnyxyxyxyxzxzxzxyxyxyx 當(dāng)新增加插值節(jié)點(diǎn)時(shí)當(dāng)新增加插值節(jié)點(diǎn)時(shí), 用用Lagrange插值多項(xiàng)式插值多項(xiàng)式, 則則需要重新計(jì)算所有的插值基函數(shù)需要重新計(jì)算所有的插值基函數(shù), 計(jì)算量大且應(yīng)用計(jì)算量大且應(yīng)用不方便不方便.Lagrange插值插值Newton插值插值25 0010101xxxxxfxfxfxN 線性插值多項(xiàng)式的另一表現(xiàn)形式線性插值多項(xiàng)式的另一表現(xiàn)形式2 Newton插值插值Newton插值公式插值公式26 差商定義差商定義 一階差商一階差商 ( f

17、 (x)關(guān)于點(diǎn)關(guān)于點(diǎn)xi , xj的一階差商的一階差商)jijijixxxfxfxxf )()(, 二階差商二階差商( f (x)關(guān)于點(diǎn)關(guān)于點(diǎn)xi , xj , xk的二階差商的二階差商)kikjjikjixxxxfxxfxxxf , 一階差商的差商一階差商的差商27 k階差商階差商kkkkxxxxxfxxxfxxxf 02111010, 差商定義差商定義28 差商的性質(zhì)差商的性質(zhì) 各階差商具有各階差商具有線性性線性性, 即若即若 f (x)=ag(x)+bh(x), 則有則有,101010kkkxxxbhxxxagxxxf k階差商可表為階差商可表為f (x0), f (x1), , f (

18、xk)的線性組合的線性組合,例例 011100101010,xxxfxxxfxxxfxfxxf 一階差商一階差商29 202110210,xxxxfxxfxxxf 2121101020)()()()(1xxxfxfxxxfxfxx).()()(210 xcfxbfxaf )(12010 xxxxa )(11202xxxxc )(1)(1)(1210120 xxxxxxb)(12101xxxx 二階差商二階差商30 3 階以上的差商可用數(shù)學(xué)歸納法證明階以上的差商可用數(shù)學(xué)歸納法證明. kjkjjjjjjjjxxxxxxxxxxxf01110)()()()(,10kxxxf31 各階差商均具有各階差

19、商均具有對(duì)稱性對(duì)稱性, 即改變節(jié)點(diǎn)的位置即改變節(jié)點(diǎn)的位置, 差差商值不變商值不變.,2134043210 xxxxxfxxxxxf 若若f (x)是是n次多項(xiàng)式次多項(xiàng)式, 則一階差商則一階差商 f x, xi 是是 (n 1)次多項(xiàng)式次多項(xiàng)式.例例32 計(jì)算各階差商可按差商表計(jì)算計(jì)算各階差商可按差商表計(jì)算ix1階差商階差商)(ixf2階差商階差商3階差商階差商 4階差商階差商0 x1x2x3x4x5x)(0 xf)(1xf)(2xf)(3xf)(4xf)(5xf 10,xxf 21,xxf 32,xxf 43,xxf 54,xxf 210,xxxf 321,xxxf 432,xxxf 543,

20、xxxf,3210 xxxxf,4321xxxxf,5432xxxxf,43210 xxxxxf,54321xxxxxf計(jì)算公式？計(jì)算公式？33 01000010101,xxxxfxfxxxxxfxfxfxN 線性插值多項(xiàng)式的另一表現(xiàn)形式線性插值多項(xiàng)式的另一表現(xiàn)形式 Newton線性線性插值多項(xiàng)式插值多項(xiàng)式Newton插值公式插值公式34 1020102xxxxbxxbbxN 221202111020100221202111020100abxbxbabxxbxbabbaxbxbbaxxbxbba 二次二次Newton插值多項(xiàng)式插值多項(xiàng)式 把二次插值多項(xiàng)式改寫(xiě)成下列形式把二次插值多項(xiàng)式改寫(xiě)成下列

21、形式 它與二次函數(shù)的通常形式它與二次函數(shù)的通常形式 是一樣的是一樣的. 兩者的系數(shù)有如下對(duì)應(yīng)關(guān)系兩者的系數(shù)有如下對(duì)應(yīng)關(guān)系.22102)(xaxaaxN 35 利用利用3個(gè)插值條件來(lái)確定個(gè)插值條件來(lái)確定3個(gè)系數(shù)個(gè)系數(shù)b0, b1, b2. 0010002001002xfbxxxxbxxbbxN 令令x=x0確定系數(shù)確定系數(shù)b0 ,1001011111012011012xxfxxxfxfbxfxxxxbxxbxfxN 令令x=x1確定系數(shù)確定系數(shù)b1 1020102xxxxbxxbbxN 二次二次Newton插值多項(xiàng)式插值多項(xiàng)式 把二次插值多項(xiàng)式改寫(xiě)成下列形式把二次插值多項(xiàng)式改寫(xiě)成下列形式36 令

22、令x=x2得到系數(shù)得到系數(shù)b2 ,21012010102022212022020101022xxxfxxxxxfxfxxxfxfbxfxxxxbxxxxxfxfxfxN 二次二次Newton插值多項(xiàng)式插值多項(xiàng)式 1020102xxxxbxxbbxN 把二次插值多項(xiàng)式改寫(xiě)成下列形式把二次插值多項(xiàng)式改寫(xiě)成下列形式37 210210100,xxxfbxxfbxfb 二次二次Newton插值多項(xiàng)式插值多項(xiàng)式 1020102xxxxbxxbbxN 38 .1210102010 nnnxxxxxxxxbxxxxbxxbbxN nnnxxxxfbxxxfbxxfbxfb,.,110210210100 n階階

23、Newton插值多項(xiàng)式插值多項(xiàng)式39)(,)()(000 xxxxfxfxf )(,110100 xxxxxfxxfxxf )(,)()(0100 xxxxfxfxf )(,1010 xxxxxxxf 由一階差商定義得由一階差商定義得 由二階差商定義得由二階差商定義得故故Newton線性線性插值多項(xiàng)式插值多項(xiàng)式余項(xiàng)余項(xiàng)40 )(,221021010 xxxxxxfxxxfxxxf )(,)()(0100 xxxxfxfxf )(,1010 xxxxxxxf )(,)(,)()(102100100 xxxxxxxfxxxxfxfxf )()(,210210 xxxxxxxxxxf 二次二次New

24、ton插值多項(xiàng)式插值多項(xiàng)式余項(xiàng)余項(xiàng)故故41)(,)(,)()(102100100 xxxxxxxfxxxxfxfxf )()(,210210 xxxxxxxxxxf )(,332103210210 xxxxxxxfxxxxfxxxxf )(,)(,)()(102100100 xxxxxxxfxxxxfxfxf )()(,2103210 xxxxxxxxxxf )()()(,32103210 xxxxxxxxxxxxxf 三次三次Newton插值多項(xiàng)式插值多項(xiàng)式余項(xiàng)余項(xiàng)42)(,)(,)()(102100100 xxxxxxxfxxxxfxfxf )()()(,21010nnxxxxxxxxxx

25、xxf )()(,11010 nnxxxxxxxxxf一般地有一般地有n次次Newton均差插值多項(xiàng)式均差插值多項(xiàng)式 Nn(x)余項(xiàng)余項(xiàng) Rn(x)43)()()(xRxNxfnn Nn(x)的特點(diǎn)的特點(diǎn)Nn(x)為至多為至多n次多項(xiàng)式次多項(xiàng)式,., 1 , 0)()()()(nixNxRxNxfininini 因此因此Nn(x)是是 f (x)的的 n 次插值多項(xiàng)式次插值多項(xiàng)式.)()(,)(,)(,)()(11010102100100 nnnxxxxxxxxxfxxxxxxxfxxxxfxfxN)()()(,)(21010nnnxxxxxxxxxxxxfxR 44 .1210102010

26、nnnxxxxxxxxbxxxxbxxbbxN nnnxxxxfbxxxfbxxfbxfb,.,110210210100 n階階Newton插值多項(xiàng)式插值多項(xiàng)式 系數(shù)系數(shù)bi (i=0, 1, 2, , n)就是差商表中對(duì)角線上的元素就是差商表中對(duì)角線上的元素.45 Newton插值多項(xiàng)式的優(yōu)點(diǎn)插值多項(xiàng)式的優(yōu)點(diǎn): 增加一個(gè)節(jié)點(diǎn)增加一個(gè)節(jié)點(diǎn), 插值插值多項(xiàng)式只增加一項(xiàng)多項(xiàng)式只增加一項(xiàng), 即即)()(,)()(01101nnnnnxxxxxxxxfxNxN 便于遞推計(jì)算便于遞推計(jì)算, Newton插值計(jì)算量小于插值計(jì)算量小于Lagrange插值插值.)()(xLxNnn 由插值多項(xiàng)式的唯一性知由插

27、值多項(xiàng)式的唯一性知, n階階Newton插值多項(xiàng)插值多項(xiàng)式和式和n階階Lagrange插值多項(xiàng)式是一樣的插值多項(xiàng)式是一樣的, 只是表現(xiàn)只是表現(xiàn)形式不同而已形式不同而已.46 nnnxxxxxxxxxxfR .,.,1010 )!1()(,.,)1(10 nfxxxxfnn Newton插值多項(xiàng)式的余項(xiàng)插值多項(xiàng)式的余項(xiàng) 由插值多項(xiàng)式的唯一性得由插值多項(xiàng)式的唯一性得 nnnxxxxxxnfR .)!1()(10)1( 故故473 分段線性插值分段線性插值 高次插值多項(xiàng)式的缺陷：高次插值多項(xiàng)式的缺陷：Runge現(xiàn)象現(xiàn)象 用用Lagrange插值多項(xiàng)式插值多項(xiàng)式 Ln(x)近似近似 f (x), 是否

28、是否插值節(jié)點(diǎn)個(gè)數(shù)插值節(jié)點(diǎn)個(gè)數(shù)n越多越多, 其逼近精度越高呢其逼近精度越高呢? 回答是回答是否定否定的！的！ 20世紀(jì)初世紀(jì)初Runge給出了一個(gè)非常著名的例子給出了一個(gè)非常著名的例子1 , 1,2511)(2 xxxf采用等距節(jié)點(diǎn)插值采用等距節(jié)點(diǎn)插值.4822511)(xxf )(4xL4922511)(xxf )(10 xL50 如圖所示如圖所示, Lagrange插值多項(xiàng)式插值多項(xiàng)式L10(x)僅在區(qū)間中僅在區(qū)間中部能較好地逼近部能較好地逼近 f (x), 在其他部位差異較大在其他部位差異較大, 而且越而且越接近區(qū)間端點(diǎn)接近區(qū)間端點(diǎn), 逼近效果越差逼近效果越差. 可以證明當(dāng)節(jié)點(diǎn)個(gè)數(shù)可以證明

29、當(dāng)節(jié)點(diǎn)個(gè)數(shù)n趨于無(wú)窮時(shí)趨于無(wú)窮時(shí), 存在一個(gè)常數(shù)存在一個(gè)常數(shù)c, c 0.726, 使得當(dāng)使得當(dāng)|x| c時(shí)時(shí), Ln(x) f (x) (n), 而當(dāng)而當(dāng)|x|c時(shí)時(shí)Ln(x)發(fā)散發(fā)散. 這一現(xiàn)象稱為這一現(xiàn)象稱為Runge現(xiàn)象現(xiàn)象. 51 它表明用高次插值多項(xiàng)式它表明用高次插值多項(xiàng)式Ln(x)近似近似f (x)效果不見(jiàn)效果不見(jiàn)得好得好, 因而通常因而通常不用高次插值不用高次插值, 而用分段低次插值而用分段低次插值. 常用分段低次插值常用分段低次插值: 分段線性插值分段線性插值, 分段三次分段三次Hermite插值插值, 三次樣條插值三次樣條插值.52 分段線性插值定義分段線性插值定義bxxx

30、an .10.,)(baCx );,., 0(),()(nixfxii 定義定義 已知函數(shù)已知函數(shù) y=f (x)在區(qū)間在區(qū)間a, b上的上的 (n+1)個(gè)節(jié)點(diǎn)個(gè)節(jié)點(diǎn)上的函數(shù)值上的函數(shù)值 yi=f (xi) (i=0,1,n), 求求插值函數(shù)插值函數(shù) (x), 使得使得,1 iixx在每一個(gè)小區(qū)間在每一個(gè)小區(qū)間 上是線性函數(shù)上是線性函數(shù);(1)(2)(3)稱函數(shù)稱函數(shù) (x)為為a, b上關(guān)于數(shù)據(jù)上關(guān)于數(shù)據(jù) (xi, yi) (i=0,1,n)的的分分段線性插值函數(shù)段線性插值函數(shù).53 nnnnnxxIxxIxxIyxyxyxyx, , , , :interval),( ,),(),(),(

31、:points data11-211100221100 x0 x1x2x3 i (x) = ai x+ bi分段線性插值分段線性插值5411 , )(,)( )( iiiiiixxxxxxxfxfx 分段線性插值分段線性插值 nnnnnxxIxxIxxIyxyxyxyx, , , , :interval),( ,),(),(),( :points data11-211100221100 根據(jù)根據(jù)Newton插值公式可寫(xiě)出插值公式可寫(xiě)出 (x)的分段表達(dá)式的分段表達(dá)式55 nnnnnnxxxxxxxfxfxxxxxxxfxfxxxxxxxfxfx1111211211100100 , )(,)(

32、, )(, )( ),(, )( )( 分段線性插值分段線性插值 nnnnnxxIxxIxxIyxyxyxyx, , , , :interval),( ,),(),(),( :points data11-211100221100 56 分段線性插值的誤差估計(jì)分段線性插值的誤差估計(jì)定理定理 如果如果 f (x)在在a, b上二階連續(xù)可微，則分段上二階連續(xù)可微，則分段線性插值函數(shù)線性插值函數(shù) (x)的余項(xiàng)有以下估計(jì)的余項(xiàng)有以下估計(jì)8| )()(| )(|2MhxxfxR 其中其中. | )( |max),(max110 xfMxxhbxaiini 57 在每個(gè)小區(qū)間在每個(gè)小區(qū)間xi, xi+1 (

33、i=0, 1, , n)上上, (x)是是f (x)的線性插值函數(shù)，故對(duì)任意的線性插值函數(shù)，故對(duì)任意 x xi , xi+1有有證明證明)(2)( )()()(1 iixxxxfxxfxR 442)(| )( |222111hhxxxxxxxxxxxxiiiiiii 故故.842| )(|22MhhMxR 而而58分段線性插值分段線性插值 分段線性插值簡(jiǎn)單易行分段線性插值簡(jiǎn)單易行, 收斂性收斂性, 穩(wěn)定性有保證穩(wěn)定性有保證. 沒(méi)有光滑性沒(méi)有光滑性, 一階導(dǎo)數(shù)不連續(xù)一階導(dǎo)數(shù)不連續(xù). 可用更高階的分段插值來(lái)得到連續(xù)導(dǎo)數(shù)，如三次可用更高階的分段插值來(lái)得到連續(xù)導(dǎo)數(shù)，如三次樣條插值樣條插值.59 Her

34、mite插值多項(xiàng)式插值多項(xiàng)式求求 H(x).(1) 至多至多(2n+1)次多項(xiàng)式次多項(xiàng)式;)., 1 , 0(, )( ,)(niyxHyxHiiii (2)4 Hermite插值插值ix2x1xnx)(iixfy 1y2yny0 x0y)( iixfy 1y2yny0y已知已知H(x): Hermite插值多項(xiàng)式插值多項(xiàng)式60jxixnx0 x1)(jixh)( jixh)()()()(1100 xhyxhyxhyxHnn )()()(1100 xHyxHyxHynn )(xHi(2n+1)次多項(xiàng)式次多項(xiàng)式)(xhi(2n+1)次多項(xiàng)式次多項(xiàng)式j(luò)xixnx0 x1)(jixH)( jixHH

35、i (x), hi (x) ( i=0, 1, 2, n): Hermite插值基函數(shù)插值基函數(shù)61 )()( 21)(2xlxxxlxhiiiii 其中其中l(wèi)i (x)是是 Lagrange插值基函數(shù)插值基函數(shù).)(xhijxixnx0 x1(2n+1)次多項(xiàng)式次多項(xiàng)式)()(2xlxhii )(ixxba 1)( iixh 0)( ),( )(2)()()( 2 iiiiiiixhxlxlxxbaxblxh)( 2iixlb )(jixh)( jixh1 a62)()()(2xlxxxHiii 其中其中l(wèi)i (x)是是 Lagrange插值基函數(shù)插值基函數(shù).)(xHijxixnx0 x1(

36、2n+1)次多項(xiàng)式次多項(xiàng)式)()(2xlxHii )(ixxba 0)( iixH 1)( ),( )(2)()()( 2 iiiiiiixHxlxlxxbaxblxH1 b)(jixH)( jixH0 a63)()()()(1100 xhyxhyxhyxHnn )()()(1100 xHyxHyxHynn )()( 21)(2xlxxxlxhiiiii )()()(2xlxxxHiii Hermite插值多項(xiàng)式插值多項(xiàng)式64n=1,)(1010 xxxxxl ,)(0101xxxxxl )()( )(21)(200000 xlxlxxxh 210101021 xxxxxxxx )()( )(

37、21)(211111xlxlxxxh 201010121 xxxxxxxx 210100)( xxxxxxxH 201011)( xxxxxxxH)()()(1100 xhyxhyxH )()(1100 xHyxHy 兩個(gè)節(jié)點(diǎn)的三次兩個(gè)節(jié)點(diǎn)的三次Hermite插值多項(xiàng)式插值多項(xiàng)式65)(0 xh)(1xh)(1xH)(0 xH66 插值余項(xiàng)與誤差估計(jì)插值余項(xiàng)與誤差估計(jì))()()(xHxfxR 截?cái)嗾`差或插值余項(xiàng)截?cái)嗾`差或插值余項(xiàng)定理定理 若若,)()22(baCxfn 則存在則存在 (a, b), 使得使得22120)22()()()()!22()()(nnxxxxxxnfxR 證明證明0)(

38、 , 0)()()( iiiixRxHxfxR故故.)()()()(22120nnxxxxxxxKxR 其中其中 K (x)是與是與 x有關(guān)的待定函數(shù)有關(guān)的待定函數(shù).如何求如何求 K (x) ?67現(xiàn)把現(xiàn)把 x看成是看成是a, b上的固定點(diǎn)上的固定點(diǎn), 作輔助函數(shù)作輔助函數(shù)22120)()()()()()(nxtxtxtxKtHtftF )(0)()()(10 xFxFxFxFn 即即 F(t )在在a, b上有上有 n+2 個(gè)零點(diǎn)個(gè)零點(diǎn). 根據(jù)根據(jù)Rolle定理定理, F (t )在在 F(t )的兩個(gè)零點(diǎn)之間至少有一個(gè)零點(diǎn)的兩個(gè)零點(diǎn)之間至少有一個(gè)零點(diǎn), 故故 F (t )在在(a, b)內(nèi)

39、至少有內(nèi)至少有 (n+1)+(n+1)個(gè)零點(diǎn)個(gè)零點(diǎn). 對(duì)對(duì)F (t )再應(yīng)用再應(yīng)用Rolle 定理定理, 可知可知F (t )在在(a, b)內(nèi)至內(nèi)至少有少有(2 n+1) 個(gè)零點(diǎn)個(gè)零點(diǎn). 依此類推依此類推, F(2n+2) (t )在在(a, b)內(nèi)內(nèi)至少有一個(gè)零點(diǎn)至少有一個(gè)零點(diǎn), 記之為記之為 (a, b), 使得使得, 0)()!22(0)()()22()22( xKnfFnn 0)( )( )( 10 nxFxFxF則則68因此因此.),(,)!22()()()22(xbanfxKn且依賴且依賴 22120)()()()(nxxxxxxxKxR .)()()()!22()(22120)

40、22(nnxxxxxxnf 若若,)(max22)22(, nnbaxMxf則則|)()()( |)!22(| )(|2212022nnxxxxxxnMxR 69)()()(3xHxfxR 2120)4()()(! 4)(xxxxf 兩個(gè)節(jié)點(diǎn)的三次兩個(gè)節(jié)點(diǎn)的三次Hermite插值多項(xiàng)式的截?cái)嗾`差插值多項(xiàng)式的截?cái)嗾`差70定理定理 滿足滿足的的 2n+1 階階Hermite插值多項(xiàng)式是插值多項(xiàng)式是唯一唯一存在的存在的.),., 1, 0()( )( , )()(nixfxHxfxHiiii 22120)22()()()()!22()()()(nnxxxxxxnHxHxH 因?yàn)橐驗(yàn)镠(x)為至多為至

41、多2n+1次多項(xiàng)式，故次多項(xiàng)式，故H(2n+2)(x)=0. 從而從而 Hermite插值多項(xiàng)式的唯一性插值多項(xiàng)式的唯一性證明證明 假設(shè)假設(shè) H(x)與與 H(x) 是滿足相同插值條件的是滿足相同插值條件的 2n+1次次Hermite多項(xiàng)式，多項(xiàng)式， H(x)也是也是 H(x) 的的 (2n+1) 次次Hermite插值多項(xiàng)式插值多項(xiàng)式. 由余項(xiàng)公式由余項(xiàng)公式H(x)= H(x)71 分段三次分段三次Hermite插值定義插值定義 給定函數(shù)表給定函數(shù)表ix2x1xnx)(iixfy 1y2yny0 x0y)( iixfy 1y2yny0y求求分段三次分段三次Hermite插值函數(shù)插值函數(shù)H(x), 使其滿足使其滿足)., 1 , 0(, )( ,)(niyxHyxHiiii (1)(2) 在每個(gè)小區(qū)間在每個(gè)小區(qū)間xi, xi+1 ( i=0, 1, n1)上，上，H(x)是三次多項(xiàng)式是三次多項(xiàng)式.72 分段三次分段三次Hermite插值函數(shù)插值函數(shù)H(x)的分段表