拉格朗日插值

1、第五章第五章 插值插值 /* Interpolation */ 問(wèn)題提出問(wèn)題提出函數(shù)逼近函數(shù)逼近 / /* *problem formulation-function approximationproblem formulation-function approximation* */ /用用已經(jīng)測(cè)得在某處海洋不同深度處的水溫如下：深度（M） 466 741 950 1422 1634水溫（oC）7.04 4.28 3.40 2.54 2.13根據(jù)這些數(shù)據(jù)，希望合理地估計(jì)出其它深度（如500米，600米，1000米）處的水溫舉例這就是本章要討論的“插值問(wèn)題”函數(shù)逼近的方法有很多，例如函數(shù)逼近的

2、方法有很多，例如Taylor級(jí)數(shù)，級(jí)數(shù)，F(xiàn)ourier級(jí)數(shù)，有限元方法、邊界元方法，小級(jí)數(shù)，有限元方法、邊界元方法，小波分析等，大學(xué)科叫波分析等，大學(xué)科叫逼近論逼近論。插值節(jié)點(diǎn)插值節(jié)點(diǎn)插值條件插值條件-插值問(wèn)題插值問(wèn)題多項(xiàng)式插值是數(shù)值分析的基本工具，常用來(lái)計(jì)算被插函數(shù)多項(xiàng)式插值是數(shù)值分析的基本工具，常用來(lái)計(jì)算被插函數(shù)的近似的近似函數(shù)值函數(shù)值，零、極點(diǎn)零、極點(diǎn)，導(dǎo)數(shù)、積分導(dǎo)數(shù)、積分，解微分方程解微分方程、積積分方程分方程插值插值x0 x1x2x3x4 xf(x)g(x)多項(xiàng)式插值多項(xiàng)式插值-polynomial interpolationProblem I. 給定給定y=f(x)的函數(shù)表的函數(shù)表

3、, xi a,bniyxPiin,., 0,)(= = =求求 次數(shù)不超過(guò)次數(shù)不超過(guò) n 的多項(xiàng)式的多項(xiàng)式 使得使得nnnxaxaaxP = =10)(條件：條件：無(wú)重合節(jié)點(diǎn)無(wú)重合節(jié)點(diǎn)，即，即jixx ji Interpolation intervalInterpolation conditionInterpolation polynomialInterpolation points(2.1)(2.2)當(dāng)精確函數(shù)當(dāng)精確函數(shù) y = f(x) 非常復(fù)雜或未知時(shí)，在一非常復(fù)雜或未知時(shí)，在一系列節(jié)點(diǎn)系列節(jié)點(diǎn) x0 xn 處測(cè)得函數(shù)值處測(cè)得函數(shù)值 y0 = f(x0), yn = f(xn)，由此構(gòu)造

4、一個(gè)簡(jiǎn)單易算的近似函，由此構(gòu)造一個(gè)簡(jiǎn)單易算的近似函數(shù)數(shù) g(x) f(x)，滿足條件，滿足條件g(xi) = f(xi) (i = 0, n)。這里的。這里的 g(x) 稱為稱為f(x) 的的插值函數(shù)插值函數(shù)。最常。最常用的插值函數(shù)是用的插值函數(shù)是 ? 多項(xiàng)式多項(xiàng)式x0 x1x2x3x4xg(x) f(x)最常用的插值函數(shù)是最常用的插值函數(shù)是 ?代數(shù)多項(xiàng)式用代數(shù)多項(xiàng)式作插值函數(shù)的插值稱為代數(shù)插值本章主要討論的內(nèi)容插值函數(shù)的類型有很多種插值問(wèn)題插值法插值函數(shù) 一、插值問(wèn)題解的存在唯一性？ 二、插值多項(xiàng)式的常用構(gòu)造方法？ 三、插值函數(shù)的誤差如何估計(jì)？代數(shù)插值 代數(shù)插值問(wèn)題解的存在惟一性代數(shù)插值問(wèn)題

5、解的存在惟一性 給定區(qū)間給定區(qū)間a,ba,b上互異的上互異的n+1n+1個(gè)點(diǎn)個(gè)點(diǎn)x xj jn nj=0j=0的一的一 組函數(shù)值組函數(shù)值f(xf(xj j) )，j =0j =0，, n, n，求一個(gè)求一個(gè)n n次多項(xiàng)式次多項(xiàng)式p pn n(x)(x)P Pn n，使得使得 p pn n(x(xj j)=f(x)=f(xj j) )，j=0,1,j=0,1,，n. n. . (1) 令令 pn(x)=a0+a1x+anxn, . (2) 只要證明只要證明Pn(x)的系數(shù)的系數(shù)a0 ,a1, an存在唯一即可存在唯一即可為此由插值條件(1)知Pn(x)的系數(shù)滿足下列n+1個(gè)代數(shù)方程構(gòu)成的線性方程

6、組 a0+a1x0+anx0n=f(x0) a0+a1x1+anx1n= f(x1) .a0+a1xn+anxnn= f(xn) (3)200021110121.1.V(,.,).1.nnnnnnnxxxxxxx xxxxx=110()niijijxx=而ai(i=0,1,2,n)的系數(shù)行列式是Vandermonde行列式由于xi互異，所以上式右端不為零，從而方程組(3)的解 a0 ,a1 ,an 存在且唯一。 通過(guò)解上述方程組通過(guò)解上述方程組(3)求得插值多項(xiàng)式求得插值多項(xiàng)式pn(x)的方法并的方法并不可取不可取.這是因?yàn)楫?dāng)這是因?yàn)楫?dāng)n較大時(shí)解方程組的計(jì)算量較大，較大時(shí)解方程組的計(jì)算量較大，

7、而且方程組系數(shù)矩陣的條件數(shù)一般較大（可能而且方程組系數(shù)矩陣的條件數(shù)一般較大（可能是是病態(tài)方程組）病態(tài)方程組）,當(dāng)階數(shù)當(dāng)階數(shù)n越越高時(shí)，病態(tài)越重高時(shí)，病態(tài)越重。為此我們必須從其它途徑來(lái)求Pn(x)：不通過(guò)求解方程組而獲得插值多項(xiàng)式1 拉格朗日多項(xiàng)式拉格朗日多項(xiàng)式 /* Lagrange Polynomial */niyxPiin,., 0,)(= = =求求 n 次多項(xiàng)式次多項(xiàng)式 使得使得nnnxaxaaxP = =10)(條件：條件：無(wú)重合節(jié)點(diǎn)，即無(wú)重合節(jié)點(diǎn)，即jixx ji n = 1已知已知 x0 , x1 ; y0 , y1 ，求，求xaaxP101)( = =使得使得111001)(,

8、)(yxPyxP= = =可見可見 P1(x) 是過(guò)是過(guò) ( x0 , y0 ) 和和 ( x1, y1 ) 兩點(diǎn)的直線。兩點(diǎn)的直線。)()(0010101xxxxyyyxP = =101xxxx 010 xxxx = y0 + y1l0(x)l1(x) = = =10)(iiiyxl稱為稱為拉氏基函數(shù)拉氏基函數(shù) /* Lagrange Basis */，滿足條件滿足條件 li(xj)= ij /* Kronecker Delta */1 Lagrange Polynomialn 1希望找到希望找到li(x)，i = 0, , n 使得使得 li(xj)= ij ；然后令；然后令 = = =n

9、iiinyxlxP0)()(，則顯然有，則顯然有Pn(xi) = yi 。li(x)每個(gè)每個(gè) li 有有 n 個(gè)根個(gè)根 x0 xi xn = = = = = =njj i jiniiixxCxxxxxxCxl00)().().()( = = =j i jiiiixxCxl)(11)(= = = =njijjijixxxxxl0)()()( = = =niiinyxlxL0)()(Lagrange Polynomial與與 有關(guān)，而與有關(guān)，而與 無(wú)關(guān)無(wú)關(guān)節(jié)點(diǎn)節(jié)點(diǎn)f當(dāng)n=1時(shí),為線性插值當(dāng)n=2時(shí),為二次多項(xiàng)式插值(拋物線插值)1線性插值線性插值 (n=1) x0 x1(x0 ,y0)(x1 ,y

10、1)L1(x)f(x)可見可見 L1(x) 是過(guò)是過(guò) ( x0 , y0 ) 和和 ( x1, y1 ) 兩點(diǎn)的直線。兩點(diǎn)的直線。x0 x1x2L2(x) f(x)f(x)2拋物插值（拋物插值（n=2）因過(guò)三點(diǎn)的二次曲線為拋物線，故稱為拋物插值。因過(guò)三點(diǎn)的二次曲線為拋物線，故稱為拋物插值。 1 Lagrange Polynomial定理定理 (唯一性唯一性) 滿足滿足 的的 n 階插值多階插值多項(xiàng)式是唯一存在的。項(xiàng)式是唯一存在的。niyxPii,., 0,)(= = =證明：證明： (利用利用Vandermonde 行列式行列式論證論證)反證：若不唯一，則除了反證：若不唯一，則除了Ln(x)

11、外還有另一外還有另一 n 階多項(xiàng)階多項(xiàng)式式 Pn(x) 滿足滿足 Pn(xi) = yi ?？疾炜疾?則則 Qn 的階數(shù)的階數(shù), )()()(xLxPxQnnn = = n而而 Qn 有有 個(gè)不同的根個(gè)不同的根n + 1x0 xn注：注：若不將多項(xiàng)式次數(shù)限制為若不將多項(xiàng)式次數(shù)限制為 n ，則插值多項(xiàng)式，則插值多項(xiàng)式不唯一不唯一。例如例如 也是一個(gè)插值也是一個(gè)插值多項(xiàng)式，其中多項(xiàng)式，其中 可以是任意多項(xiàng)式?？梢允侨我舛囗?xiàng)式。= = = =niinxxxpxLxP0)()()()()(xp1 Lagrange Polynomial 插值余項(xiàng)插值余項(xiàng) /* Remainder */設(shè)節(jié)點(diǎn)設(shè)節(jié)點(diǎn))1(

12、 nf在在a , b內(nèi)存在內(nèi)存在, 考察截?cái)嗾`差考察截?cái)嗾`差)()()(xLxfxRnn = =, baCfn bxxxan 10，且，且 f 滿足條件滿足條件 ,Rolles Theorem: 若若 充分光滑，充分光滑， ，則，則存在存在 使得使得 。)(x 0)()(10= = =xx ),(10 xx 0)(= = 推廣：推廣：若若0)()()(210= = = =xxx ),(),(211100 xxxx 使得使得0)()(10= = = = ),(10 使得使得0)(= = 0)()(0= = = =nxx 存在存在),(ba 使得使得0)()(= = nRn(x) 至少有至少有 個(gè)

13、根個(gè)根n+1 = = = =niinxxxKxR0)()()(任意固定任意固定 x xi (i = 0, , n), 考察考察 = = = =niixtxKtRnt0)()()()( (x)有有 n+2 個(gè)不同的根個(gè)不同的根 x0 xn x),(, 0)()1(baxxn = = !)1()()()1(nxKRxnn 注意這里是對(duì)注意這里是對(duì) t 求導(dǎo)求導(dǎo)= = !)1)()()()1()1(nxKLfxnnxn !)1()()()1( = = nfxKxn = = = =niixnnxxnfxR0)1()(! ) 1()()( 1 Lagrange Polynomial注：注： 通常不能確定

14、通常不能確定 x , 而是估計(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)式多項(xiàng)式時(shí)，時(shí)， , 可知可知 ，即插值多項(xiàng)式對(duì)于次數(shù)，即插值多項(xiàng)式對(duì)于次數(shù) n 的的多項(xiàng)多項(xiàng)式是式是精確精確的。的。0)()1( xfn0)( xRnQuiz: 給定給定 xi = i +1, i = 0, 1, 2, 3, 4, 5. 下面哪個(gè)是下面哪個(gè)是 l2(x)的圖像？的圖像？ y 0 - - - 1 0.5 -0.5 1 2 3 4 5 6 x y 0 - - - 1

15、 0.5 -0.5 1 2 3 4 5 6 x y 0 - - - 1 0.5 -0.5 1 2 3 4 5 6 x ABC 1 Lagrange Polynomial例例1：已知已知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)

16、()2( = = =xxxfxxf而而)4)(6(!2)()(,23sin21)2(1 = = xxfxRxx00762. 0)185(01319. 01 Rsin 50 = 0.7660444)185(50sin10 L0.77614外推外推 /* extrapolation */ 的實(shí)際誤差的實(shí)際誤差 0.01010.01013,421 = = =xx利用利用sin 50 0.76008, 00660. 018500538. 01 R內(nèi)插內(nèi)插 /* interpolation */ 的實(shí)際誤差的實(shí)際誤差 0.005960.00596內(nèi)插通常優(yōu)于外推。選擇內(nèi)插通常優(yōu)于外推。選擇要計(jì)算的要計(jì)算

17、的 x 所在的區(qū)間的所在的區(qū)間的端點(diǎn)，插值效果較好。端點(diǎn)，插值效果較好。1 Lagrange Polynomialn = 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.000610.00061高次插值通常優(yōu)于高次插值通常優(yōu)于低次插值低次插值但絕對(duì)不是次數(shù)越但絕對(duì)不是次數(shù)越高就越好，嘿高就越好，嘿嘿嘿例2

18、:已知 y = f(x) = ln(1+x) 的值如下xi123yi0.71.11.420 01 12 2( )( )( )( )L xy lxy l xy lx=(1) 求Lagrange插值多項(xiàng)式L2(x)(2) 求L2(2.5). (3)求插值余項(xiàng)R2(x) ，并估計(jì)R2(x)。 (1) .由公式得2(2)(3)(1)(3)(1)(2)0.71.11.4(1 2)(1 3)(2 1)(23)(3 1)(32)0.050.550.2xxxxxxxx= (2)因?yàn)?所以2( )( )(1)(2)(3),(1,3)3!fRxxxx=而32( ) ln(1)(1)fxxx=(3)因?yàn)椋?(2.5)1.2625,L=2(2.5)(2.5)1.2625.fL=從而進(jìn)而131max( )4xfx21( )(1)(2)(3)