插值法(拉格朗日插值)

1、 問題的提出問題的提出 拉格朗日插值拉格朗日插值 牛頓插值牛頓插值 埃爾米特插值埃爾米特插值 曲線擬合的最小二乘法曲線擬合的最小二乘法第三章第三章 插值法插值法 /* Interpolation */1問題的提出函數(shù)y = f(x)1）解析式未知；2）雖有解析式但表達(dá)式較復(fù)雜，通過實(shí)驗(yàn)計(jì)算得到的一組數(shù)據(jù)，即在某個(gè)區(qū)間a,b上給出一系列點(diǎn)的函數(shù)值yi=f(xi)，xx0 x1x2 xny=f(x)y0y1y2yn3）列表函數(shù)問題：無法求出不在表中的點(diǎn)的函數(shù)值，也不能進(jìn)一步研究函數(shù)的其他性質(zhì)，如函數(shù)的積分和導(dǎo)數(shù)等。因此需尋找y = f(x)的近似函數(shù)p(x),但要求p(xi) = f(xi) 。插

2、值問題插值問題已知精確函數(shù)已知精確函數(shù) y = f(x) 在一系列節(jié)點(diǎn)在一系列節(jié)點(diǎn) x0 xn 處測得函數(shù)值處測得函數(shù)值 y0 = f(x0), yn = f(xn)，由此構(gòu)，由此構(gòu)造一個(gè)簡單易算的近似函數(shù)造一個(gè)簡單易算的近似函數(shù) p(x) f(x)，滿足，滿足條件條件p(xi) = f(xi) (i = 0, n)。這里的。這里的 p(x) 稱稱為為f(x) 的的插值函數(shù)插值函數(shù)。最常用的插值函數(shù)是。最常用的插值函數(shù)是 ?多項(xiàng)式多項(xiàng)式x0 x1x2x3x4xp(x) f(x)1.1Taylor插值函數(shù)y = f(x)在點(diǎn)x0處展開有Taylor 多項(xiàng)式:200000)(! 2)( )()()

3、(xxxfxxxfxfxpnnnxxnxf)(!)(.00)(可見: Pn(k)(x0)= f (k)(x0) k=0,1,n因此, Pn(x)在點(diǎn)x0鄰近會(huì)很好的逼近f(x). Taylor展開方法就是一種插值方法.泰勒插值要求提供 f(x) 在點(diǎn)x0處的各階導(dǎo)數(shù),這僅僅適用于 f(x) 相當(dāng)簡單的情況. 設(shè)函數(shù)y = f(x)在區(qū)間a,b上有定義，且給出一系列點(diǎn)上的函數(shù)值yi=f(xi) (i=0,1,2,n)，求作n次多項(xiàng)式pn(x) 使得 pn (xi)= yi (i=0,1,2,n) 函數(shù)pn (x)為f(x)的插值函數(shù)；稱x0,x1, xn稱為插值節(jié)點(diǎn)或簡稱節(jié)點(diǎn)。插值節(jié)點(diǎn)所界的區(qū)間

4、a,b稱為插值區(qū)間。pn (xi)= yi 稱為插值條件。 構(gòu)造的n次多項(xiàng)式可表示為: Pn(x)= a0 + a1x + a2x2+ anxn1.2 Lagrange插值定理定理 (插值多項(xiàng)式的插值多項(xiàng)式的存在唯一性存在唯一性) 滿足滿足 的的 n 階插值多項(xiàng)式是唯一存在的。階插值多項(xiàng)式是唯一存在的。niyxPii,., 0,)( 證明：證明： ( 利用利用Vandermonde 行列式行列式論證論證)nnnnnnnnnyxaxaayxaxaayxaxaa.101111000010這是一個(gè)關(guān)于這是一個(gè)關(guān)于a0 , a1 , an 的的n+1元線性方程組元線性方程組,其系其系數(shù)行列式數(shù)行列式:

5、10110)(),.,(ijjininnxxxxxV由于由于i j時(shí)時(shí), xi xj ,因此因此 ,即方程組有即方程組有唯一解唯一解. . 0),.,(10nnxxxV2 拉格朗日插值公式拉格朗日插值公式 niyxPiin,., 0,)( 求求 n 次多項(xiàng)式次多項(xiàng)式 使得使得nnnxaxaaxP 10)(條件：條件：無重合節(jié)點(diǎn)，即無重合節(jié)點(diǎn)，即jixx ji n = 1已知已知 x0 , x1 ; y0 , y1 ，求，求xaaxP101)( 使得使得111001)(,)(yxPyxP 可見可見 P1(x) 是過是過 ( x0 , y0 ) 和和 ( x1, y1 ) 兩點(diǎn)的直線。兩點(diǎn)的直線。

6、)()(0010101xxxxyyyxP 101xxxx 010 xxxx = y0 + y1l0(x)l1(x) 10)(iiiyxl稱為稱為拉氏基函數(shù)拉氏基函數(shù)直線方程的兩點(diǎn)式：線性插值線性插值101001011)(yxxxxyxxxxxLl0(x)l1(x) 10)(iiiyxlL1(x)拋物插值拋物插值2120210121012002010212)()()()()()()(yxxxxxxxxyxxxxxxxxyxxxxxxxxxLl0(x)l1(x)l2(x)n 1li(x)每個(gè)每個(gè) li 有有 n 個(gè)根個(gè)根 x0 xi xn njj i jiniiixxCxxxxxxCxl00)()

7、.().()( j i jiiiixxCxl)(11)( njijjijixxxxxl0)()()( niiinyxlxL0)()(N次拉格朗日次拉格朗日插值多項(xiàng)式插值多項(xiàng)式與與 有關(guān)，而與有關(guān)，而與 無關(guān)無關(guān)節(jié)點(diǎn)節(jié)點(diǎn)f希望找到希望找到li(x)，i = 0, , n 使得使得 li(xj)= ；然后令；然后令 niiinyxlxP0)()(，則顯然有，則顯然有Pn(xi) = yi 。01ji ji n次多項(xiàng)式次多項(xiàng)式 插值余項(xiàng)插值余項(xiàng) /* Remainder */設(shè)節(jié)點(diǎn)設(shè)節(jié)點(diǎn))1( nf在在a , b內(nèi)存在內(nèi)存在, 考察截?cái)嗾`差考察截?cái)嗾`差)()()(xLxfxRnn , baCfn b

8、xxxan 10，且，且 f 滿足條件滿足條件 ,用簡單的插值函數(shù)用簡單的插值函數(shù)L n(x)代替原復(fù)雜函數(shù)代替原復(fù)雜函數(shù)f(x),其其精度取決于截?cái)嗾`差精度取決于截?cái)嗾`差,即插值余項(xiàng)即插值余項(xiàng).)()()()!1()()(210) 1(nnnxxxxxxxxnfxR即niinnxxnfxR0) 1()(! ) 1()()(,ba其中拉格朗日余項(xiàng)定理拉格朗日余項(xiàng)定理注：注： 通常不能確定通常不能確定 , 而是估計(jì)而是估計(jì) , x (a,b) 將將 作為誤差估計(jì)上限。作為誤差估計(jì)上限。1)1()( nnMxf niinxxnM01|)!1(當(dāng)當(dāng) f(x) 為任一個(gè)次數(shù)為任一個(gè)次數(shù) n 的的多項(xiàng)式

9、多項(xiàng)式時(shí)，時(shí)， , 可知可知 ，即插值多項(xiàng)式對于次數(shù)，即插值多項(xiàng)式對于次數(shù) n 的的多項(xiàng)多項(xiàng)式是式是精確精確的。的。0)()1( xfn0)( xRn例：例：已知已知233sin,214sin,216sin 分別利用分別利用 sin x 的的1次、次、2次次 Lagrange 插值計(jì)算插值計(jì)算 sin 50 并估計(jì)誤差。并估計(jì)誤差。 解：解：0 x1x2x185500 n = 1分別利用分別利用x0, x1 以及以及 x1, x2 計(jì)算計(jì)算4,610 xx利用利用216/4/6/214/6/4/)(1 xxxL這里這里)3,6(,sin)(,sin)()2( xxxfxxf而而)4)(6(!2

10、)()(,23sin21)2(1 xxfxRxx00762. 0)185(01319. 01 Rsin 50 = 0.7660444)185(50sin10 L0.77614外推外推 /* extrapolation */ 的實(shí)際誤差的實(shí)際誤差 0.010010.010013,421 xx利用利用sin 50 0.76008, 00660. 018500538. 01 R內(nèi)插內(nèi)插 /* interpolation */ 的實(shí)際誤差的實(shí)際誤差 0.00596 0.00596內(nèi)插通常優(yōu)于外推。選擇內(nèi)插通常優(yōu)于外推。選擇要計(jì)算的要計(jì)算的 x 所在的區(qū)間的所在的區(qū)間的端點(diǎn)，插值效果較好。端點(diǎn)，插值效果

11、較好。n = 223)()(21)()(21)()()(4363463464363646342 xxxxxxxL)185(50sin20 L0.7654323cos21;)3)(4)(6(!3cos)(2 xxxxxxR 00077. 018500044. 02 Rsin 50 = 0.76604442次插值的實(shí)際誤差次插值的實(shí)際誤差 0.00061 0.00061高次插值通常優(yōu)于高次插值通常優(yōu)于低次插值低次插值但絕對不是次數(shù)越但絕對不是次數(shù)越高就越好，嘿高就越好，嘿嘿嘿ininjijjijnyxxxxxL)()()(00 拉格朗日插值多項(xiàng)式編程容易，只需雙重循環(huán)拉格朗日插值多項(xiàng)式編程容易，只

12、需雙重循環(huán) 如果發(fā)現(xiàn)當(dāng)前的插值方法不夠精確，就要增如果發(fā)現(xiàn)當(dāng)前的插值方法不夠精確，就要增加插值點(diǎn)的個(gè)數(shù)，則拉格朗日插值基函數(shù)加插值點(diǎn)的個(gè)數(shù)，則拉格朗日插值基函數(shù) li(x)都將重新計(jì)算。都將重新計(jì)算。 牛頓插值法將討論該問題牛頓插值法將討論該問題。例：已知數(shù)據(jù)表 xk10111213f(xk)2.302 62.397 92.484 92.564 9試用二次插值計(jì)算f(11.75)(計(jì)算過程保留4位小數(shù)) 解：因?yàn)?1.75更接近12，故應(yīng)取11，12，13三點(diǎn)作二次插值先作插值基函數(shù)已知x0=11,y0=2.397 9，x1=12,y0=2.484 9 ，x2=13,y2=2.564 9 2)13)(12()()()(2010210 xxxxxxxxxxxl1)13)(11()()()(2101201xxxxxxxxxxxl2)12)(11()()()(1202102xxxxxxxxxxxl 2(x)=9484. 21)13)(11(9397. 22)13)(12(xxxx9564. 22)12)(11(xx f(11.75)2(11.75)= 9484. 21)135 .11)(1175.11(9397. 22)1375.11)(1275.11(8 2.4639564. 22)1275.11)(1175.11(例 已知x=1,4,9的平方根值，用拉格朗日插值公式求71/2解：x