計(jì)算方法-插值a

1、第三章第三章 插值插值 /* Interpolation */當(dāng)精確函數(shù)當(dāng)精確函數(shù) y = f(x) 非常復(fù)雜或未知時(shí)，在一非常復(fù)雜或未知時(shí)，在一系列節(jié)點(diǎn)系列節(jié)點(diǎn) x0 xn 處測得函數(shù)值處測得函數(shù)值 y0 = f(x0), yn = f(xn)，由此構(gòu)造一個(gè)簡單易算的近似函，由此構(gòu)造一個(gè)簡單易算的近似函數(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)f(x)g(x) 已知函數(shù)已知函數(shù)y=

2、f(x)在區(qū)間在區(qū)間a, b內(nèi)一系列點(diǎn)內(nèi)一系列點(diǎn)xi上的函數(shù)值上的函數(shù)值f(xi)=yi, i=0,1,n，求一簡單函數(shù)，求一簡單函數(shù)P(x)，使?jié)M足條件，使?jié)M足條件P(xi)=yi, i=0,1,n， 稱點(diǎn)稱點(diǎn)xi為為插值節(jié)點(diǎn)插值節(jié)點(diǎn)/* interpolating points */ ，a, b為為插值區(qū)間插值區(qū)間/* interpolating region */ ，P(x)為為插值函數(shù)插值函數(shù)/* interpolatingfunction */ ，求，求P(x)的過程為的過程為函數(shù)插值函數(shù)插值/* function interpolating */ ，求，求P(x)的方法為的方法為插

3、值法插值法/* interpolation */ 。定義定義 由于代數(shù)多項(xiàng)式的結(jié)構(gòu)簡單，數(shù)值近似和理論分析都由于代數(shù)多項(xiàng)式的結(jié)構(gòu)簡單，數(shù)值近似和理論分析都方便，實(shí)用中常取代數(shù)多項(xiàng)式方便，實(shí)用中常取代數(shù)多項(xiàng)式作為插值函數(shù)，稱其為作為插值函數(shù)，稱其為n次插值多項(xiàng)式次插值多項(xiàng)式/* n-degree Interpolating polynomial */ ，求，求Pn(x)的過程也叫做的過程也叫做拉格朗日拉格朗日插值插值/* Lagrange Interpolation */ 。nnnxaxaxaaxP 2210)(點(diǎn)斜式點(diǎn)斜式3.1 拉格朗日插值拉格朗日插值 /* Lagrange Interpo

4、lation */niyxLiin,., 0,)( 求求 n 次多項(xiàng)式次多項(xiàng)式 使得使得nnnxaxaaxL10)(條件：條件：無重合節(jié)點(diǎn)，即無重合節(jié)點(diǎn)，即jixx ji n = 1線性插值線性插值已知已知 x0 , x1 ; y0 , y1 ，求，求xaaxL101)(使得使得111001)(,)(yxLyxL 可見可見 L1(x) 是過是過 ( x0 , y0 ) 和和 ( x1, y1 ) 兩點(diǎn)的直線。兩點(diǎn)的直線。)()(0010101xxxxyyyxL- - - - 101xxxx- - -010 xxxx- - -= y0 + y1l0(x)l1(x) 10)(iiiyxl稱為稱為拉

5、氏基函數(shù)拉氏基函數(shù) /* Lagrange Basis */，滿足條件滿足條件 li(xj)= ij /* Kronecker Delta */n = 2拋物線插值拋物線插值已知已知 x0 , x1 , x2 ; y0 , y1 , y2 ，求，求L2(x)=a0+a1x + a2x2, 使使得得L2(xi)= yi , i=0,1,2.用基函數(shù)表示用基函數(shù)表示3.1 Lagrange Interpolation其中其中l(wèi)0(x)、l1(x)、l2(x)為為二次式二次式，且滿足以下條件，且滿足以下條件2211002)()()()(yxlyxlyxlxL100010001 )(x, l)(x,

6、l)(xl)(x, l)(x, l)(xl)(x, l)(x, l)(xl221202211101201000li(xj)= ij)()(210 xxxxcxl- - - )(12010 xxxxc- - - )()()(2010210 xxxxxxxxxl- - - - - )()()( ,)()()(12021022101201xxxxxxxxxlxxxxxxxxxl- - - - - - - - - - yxxxxxxxxyxxxxxxxxyxxxxxxxxxL)()( )()()()()(120210121012002010212- The mathematician S. had t

7、o move to a new place. His wife didnt trust him very much, so when they stood down on the street with all their things, she asked him to watch their ten trunks, while she got a taxi. Some minutes later she returned. Said the husband: I thought you said there were ten trunks, but Ive only counted to

8、nine! The wife said: No, theyre TEN! But I have counted them: 0, 1, 2, . n 1希望找到希望找到li(x)，i = 0, , n 使得使得 li(xj)= ij ；然后令；然后令 niiinyxlxL0)()(，則顯然有，則顯然有Ln(xi) = yi 。li(x)每個(gè)每個(gè) li 有有 n 個(gè)零點(diǎn)個(gè)零點(diǎn) x0 xi xn - - - - - - njj i jiniiixxCxxxxxxCxl00)().().()( - - j i jiiiixxCxl)(11)( - - - njijjijixxxxxl0)()()(n

9、iiinyxlxL0)()(Lagrange Polynomial與與 有關(guān)，而與有關(guān)，而與 無關(guān)無關(guān)節(jié)點(diǎn)節(jié)點(diǎn)f3.1 Lagrange InterpolationQuiz: 給定給定 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 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 3.1 Lagrange Interpolation定理定理 (唯一性唯一性)

10、滿足滿足 的的 n 階插值多階插值多項(xiàng)式是唯一存在的。項(xiàng)式是唯一存在的。niyxLiin,., 0,)(證明：證明： 由插值條件可知，插值多項(xiàng)式由插值條件可知，插值多項(xiàng)式Ln(x)的系數(shù)的系數(shù)ai滿足線性滿足線性方程組方程組 nnnnnnnyyyaaaxxxxxx10101100111 nnnnnxxxxxxV1111100其系數(shù)行列式是其系數(shù)行列式是n+1階階范德蒙范德蒙(Vandermonde)行列式行列式 - - - - niijjixx010)(因?yàn)橐驗(yàn)閤ixj，于是，于是V0，方程組的解存在且唯一，方程組的解存在且唯一 3.1 Lagrange Interpolation 插值余項(xiàng)插

11、值余項(xiàng) /* Remainder */bxxxan 10 b a, )()!1()()()()(0)1(-nkknnnxxnfxLxfxR定理定理 設(shè)節(jié)點(diǎn)設(shè)節(jié)點(diǎn) ，而，而f(x)在在a, b內(nèi)有直到內(nèi)有直到n+1階導(dǎo)數(shù)，且已知階導(dǎo)數(shù)，且已知f(xi)=yi, i=0, 1, , n, 則當(dāng)則當(dāng)xa,b成立成立Rolles Theorem: 若若 充分光滑，充分光滑， ，則，則存在存在 使得使得 。)(x 0)()(10 xx ),(10 xx 0)( 推廣：推廣：若若0)()()(210 xxx ),(),(211100 xxxx 使得使得0)()(10 ),(10 使得使得0)( 0)()(

12、0 nxx 存在存在),(ba 使得使得0)()( nRn(x) 至少有至少有 個(gè)根個(gè)根n+1 - - niinxxxKxR0)()()(任意固定任意固定 x xi (i = 0, , n), 考察考察 - - - niixtxKtRnt0)()()()( (t)有有 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()()( 3.

13、1 Lagrange Interpolation - - niixnnxxnfxR0) 1()(! ) 1()()( 注：注： 通常不能確定通常不能確定 , 而是估計(jì)而是估計(jì) , x (a,b) 將將 作為誤差估計(jì)上限。作為誤差估計(jì)上限。1)1()( nnMxf - - niinxxnM01|)!1(內(nèi)插內(nèi)插比比外推外推效果好。效果好。當(dāng)當(dāng) f(x) 為任一個(gè)次數(shù)為任一個(gè)次數(shù) n 的的多項(xiàng)式多項(xiàng)式時(shí)，時(shí)，f(n+1)(x)=0 , 可知可知Rn(x)=0，即插值多項(xiàng)式對(duì)于次數(shù)，即插值多項(xiàng)式對(duì)于次數(shù) n 的的多項(xiàng)式多項(xiàng)式是是精確精確的。的。3.1 Lagrange Interpolation例：

14、例：已知已知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),(,sin)(,sin)(46 - xxxfxxf而而| )( |)(!)()(,sin)(4642462221 - xxxxfxRfxxx0107701851.)( Rsin 50 = 0.7660444)1

15、85(50sin10 L0.77614外推外推 /* extrapolation */的實(shí)際誤差的實(shí)際誤差 - -0.010010.010013,421 xx利用利用sin 50 0.76008, 00660. 01851 R內(nèi)插內(nèi)插/* interpolation */ 的實(shí)際誤差的實(shí)際誤差 0.005960.00596內(nèi)插通常優(yōu)于外推。選擇內(nèi)插通常優(yōu)于外推。選擇要計(jì)算的要計(jì)算的 x 所在的區(qū)間的所在的區(qū)間的端點(diǎn)，插值效果較好。端點(diǎn)，插值效果較好。3.1 Lagrange Interpolationn = 223)()(21)()(21)()()(4363463464363646342 -

16、- - - - - - - - - - - - - - xxxxxxxL)185(50sin20 L0.7654323cos; )3)(4)(6(!3cos)(2-xxxxxxR 0007701852.R sin 50 = 0.76604442次插值的實(shí)際誤差次插值的實(shí)際誤差 0.000610.00061高次插值通常優(yōu)于高次插值通常優(yōu)于低次插值低次插值但絕對(duì)不是次數(shù)越但絕對(duì)不是次數(shù)越高就越好，嘿高就越好，嘿嘿嘿3.1 Lagrange Interpolation 插值誤差的實(shí)用估計(jì)法插值誤差的實(shí)用估計(jì)法設(shè)設(shè)Ln(x) 和和Ln*(x)分別是以分別是以x0，x1,xn和和x1, x2,xn1為節(jié)

17、點(diǎn)的為節(jié)點(diǎn)的插值多項(xiàng)式。則插值多項(xiàng)式。則 )()!1()()()()()!1()()()(11)1(n0)1(-nkknnkknnxxnfxLxfxxnfxLxf 1nn xxxxx210Ln(x)L*n(x) 101n11xx)x(L)x(L)xx()xx()!n()(fnnn)n(- - - - - - )xx(xx)x(L)x(L)x(L)x(f)xx(xx)x(L)x(L)x(L)x(fnnnnnn101nn010n - - - - - - - - - - -Ln(x) 和和Ln*(x)只相只相差一個(gè)節(jié)點(diǎn)，可以差一個(gè)節(jié)點(diǎn)，可以設(shè)想設(shè)想f(n+1)() f(n+1) (*) 10111n

18、)xx)(xx()xx()!n()(f)x(L)x(Lnn)n(n- - - - - - 3.1 Lagrange Interpolation程序設(shè)計(jì)程序設(shè)計(jì) f0,.,n ,i10 f output x, yx,input nii， - - - njijjijixxxxxl0)()()( niiinyxlxL0)()(1l,.,n ,j10 ?i j )xx/()xx(*lljij-iylff*)(3.1 Lagrange Interpolation When you start writing the program, you will find how easy it is to cal

19、culate the Lagrange polynomial.Oh yeah? What if I find the current interpolation not accurate enough? Then you might want to take more interpolating points into account.Right. Then all the Lagrange basis, li(x), will have to be re-calculated. Excellent point !We will come to discuss this problemnext

20、 time.3.1 Lagrange Interpolation3.1 Lagrange Interpolation81. 019. 32)1(19. 0)2(81. 02)2)(1()(2- - - - - - - - - - xxxxxxxxf因此，因此， f(x)f(x)的的零點(diǎn)零點(diǎn)為為x x1 1=-0.9, x=-0.9, x2 2=0.9;=0.9;04666. 1)(20 dxxf解解：由二次插值由二次插值例例(P.84 5.) 已知二次式已知二次式f(x)f(x)在在x=0,1,2x=0,1,2的值分別為的值分別為-0.81,0.19, -0.81,0.19, 3.19, 3.

21、19, 求求f(x)f(x)的零點(diǎn)、極值點(diǎn)、的零點(diǎn)、極值點(diǎn)、x=1x=1處導(dǎo)數(shù)和積分處導(dǎo)數(shù)和積分 20dxxf)(極值點(diǎn)極值點(diǎn)x=0;x=0;f f(1)=2 ;(1)=2 ;3.1 Lagrange Interpolation例例(P.84 6.) 設(shè)設(shè)x0,x1,xn是互不相同的節(jié)點(diǎn)，是互不相同的節(jié)點(diǎn)，li(x)是拉格朗日插值是拉格朗日插值基函數(shù)，求證：基函數(shù)，求證： 證明證明(1)：設(shè)：設(shè)f(x)=xk,k=0,1,2,n, 求求f(x)的次拉格朗日插值多的次拉格朗日插值多項(xiàng)式，得到項(xiàng)式，得到;,.,1 , 0 ,)( )1(0nkxxlxkniiki ;,.,1 , 0 , 0)( )

22、( )2(0nkxxxlkinii - - - - 1,)1(,.,2 , 1 , 00 , 1)0( )3(100nkxxxnkkxlnnkiniikniikiniiixxlxxlxfxf 00)()()()(3.1 Lagrange Interpolation例例(P.84 6.) 設(shè)設(shè)x0,x1,xn是互不相同的節(jié)點(diǎn)，是互不相同的節(jié)點(diǎn)，li(x)是拉格朗日插值是拉格朗日插值基函數(shù)，求證：基函數(shù)，求證： 證明證明(2)： - - - - - - nikjjkjiikiniixxjkxlxxxl000)()()( )( - - - - - - - - kjniijkjikjijkjinixlxxjkxlxxjk0000)()()()( - - - -kjniijijkxlxxjk00)()( - - - -kjjjkxxjk0)(0)( - -kx