計算方法-插值a

1、第三章第三章 插值插值 /* Interpolation */當精確函數(shù)當精確函數(shù) y = f(x) 非常復雜或未知時，在一非常復雜或未知時，在一系列節(jié)點系列節(jié)點 x0 xn 處測得函數(shù)值處測得函數(shù)值 y0 = f(x0), yn = f(xn)，由此構造一個簡單易算的近似函，由此構造一個簡單易算的近似函數(shù)數(shù) g(x) f(x)，滿足條件，滿足條件g(xi) = f(xi) (i = 0, n)。這里的。這里的 g(x) 稱為稱為f(x) 的的插值函數(shù)插值函數(shù)。最常。最常用的插值函數(shù)是用的插值函數(shù)是 ?多項式多項式x0 x1x2x3x4xg(x) f(x)f(x)g(x) 已知函數(shù)已知函數(shù)y=

2、f(x)在區(qū)間在區(qū)間a, b內(nèi)一系列點內(nèi)一系列點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， 稱點稱點xi為為插值節(jié)點插值節(jié)點/* interpolating points */ ，a, b為為插值區(qū)間插值區(qū)間/* interpolating region */ ，P(x)為為插值函數(shù)插值函數(shù)/* interpolatingfunction */ ，求，求P(x)的過程為的過程為函數(shù)插值函數(shù)插值/* function interpolating */ ，求，求P(x)的方法為的方法為插

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

4、lation */niyxLiin,., 0,)( 求求 n 次多項式次多項式 使得使得nnnxaxaaxL10)(條件：條件：無重合節(jié)點，即無重合節(jié)點，即jixx ji n = 1線性插值線性插值已知已知 x0 , x1 ; y0 , y1 ，求，求xaaxL101)(使得使得111001)(,)(yxLyxL 可見可見 L1(x) 是過是過 ( x0 , y0 ) 和和 ( x1, y1 ) 兩點的直線。兩點的直線。)()(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)每個每個 li 有有 n 個零點個零點 x0 xi xn - - - - - - njj i jiniiixxCxxxxxxCxl00)().().()( - - j i jiiiixxCxl)(11)( - - - njijjijixxxxxl0)()()(n

9、iiinyxlxL0)()(Lagrange Polynomial與與 有關，而與有關，而與 無關無關節(jié)點節(jié)點f3.1 Lagrange InterpolationQuiz: 給定給定 xi = i +1, i = 0, 1, 2, 3, 4, 5. 下面哪個是下面哪個是 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 階插值多階插值多項式是唯一存在的。項式是唯一存在的。niyxLiin,., 0,)(證明：證明： 由插值條件可知，插值多項式由插值條件可知，插值多項式Ln(x)的系數(shù)的系數(shù)ai滿足線性滿足線性方程組方程組 nnnnnnnyyyaaaxxxxxx10101100111 nnnnnxxxxxxV1111100其系數(shù)行列式是其系數(shù)行列式是n+1階階范德蒙范德蒙(Vandermonde)行列式行列式 - - - - niijjixx010)(因為因為xixj，于是，于是V0，方程組的解存在且唯一，方程組的解存在且唯一 3.1 Lagrange Interpolation 插值余項插

11、值余項 /* Remainder */bxxxan 10 b a, )()!1()()()()(0)1(-nkknnnxxnfxLxfxR定理定理 設節(jié)點設節(jié)點 ，而，而f(x)在在a, b內(nèi)有直到內(nèi)有直到n+1階導數(shù)，且已知階導數(shù)，且已知f(xi)=yi, i=0, 1, , n, 則當則當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) 至少有至少有 個根個根n+1 - - niinxxxKxR0)()()(任意固定任意固定 x xi (i = 0, , n), 考察考察 - - - niixtxKtRnt0)()()()( (t)有有 n+2 個不同的根個不同的根 x0 xn x),(, 0)()1(baxxn !)1()()()1(-nxKRxnn 注意這里是對注意這里是對 t 求導求導 - - - !)1)()()()1()1(nxKLfxnnxn !)1()()()1( nfxKxn - - niixnnxxnfxR0)1()(! ) 1()()( 3.

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

14、例：已知已知233sin,214sin,216sin 分別利用分別利用 sin x 的的1次、次、2次次 Lagrange 插值計算插值計算 sin 50 并估計誤差。并估計誤差。 解：解：0 x1x2x185500 n = 1分別利用分別利用x0, x1 以及以及 x1, x2 計算計算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 */的實際誤差的實際誤差 - -0.010010.010013,421 xx利用利用sin 50 0.76008, 00660. 01851 R內(nèi)插內(nèi)插/* interpolation */ 的實際誤差的實際誤差 0.005960.00596內(nèi)插通常優(yōu)于外推。選擇內(nèi)插通常優(yōu)于外推。選擇要計算的要計算的 x 所在的區(qū)間的所在的區(qū)間的端點，插值效果較好。端點，插值效果較好。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次插值的實際誤差次插值的實際誤差 0.000610.00061高次插值通常優(yōu)于高次插值通常優(yōu)于低次插值低次插值但絕對不是次數(shù)越但絕對不是次數(shù)越高就越好，嘿高就越好，嘿嘿嘿3.1 Lagrange Interpolation 插值誤差的實用估計法插值誤差的實用估計法設設Ln(x) 和和Ln*(x)分別是以分別是以x0，x1,xn和和x1, x2,xn1為節(jié)

17、點的為節(jié)點的插值多項式。則插值多項式。則 )()!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)只相只相差一個節(jié)點，可以差一個節(jié)點，可以設想設想f(n+1)() f(n+1) (*) 10111n

18、)xx)(xx()xx()!n()(f)x(L)x(Lnn)n(n- - - - - - 3.1 Lagrange Interpolation程序設計程序設計 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)的的零點零點為為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)的零點、極值點、的零點、極值點、x=1x=1處導數(shù)和積分處導數(shù)和積分 20dxxf)(極值點極值點x=0;x=0;f f(1)=2 ;(1)=2 ;3.1 Lagrange Interpolation例例(P.84 6.) 設設x0,x1,xn是互不相同的節(jié)點，是互不相同的節(jié)點，li(x)是拉格朗日插值是拉格朗日插值基函數(shù)，求證：基函數(shù)，求證： 證明證明(1)：設：設f(x)=xk,k=0,1,2,n, 求求f(x)的次拉格朗日插值多的次拉格朗日插值多項式，得到項式，得到;,.,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.) 設設x0,x1,xn是互不相同的節(jié)點，是互不相同的節(jié)點，li(x)是拉格朗日插值是拉格朗日插值基函數(shù)，求證：基函數(shù)，求證： 證明證明(2)： - - - - - - nikjjkjiikiniixxjkxlxxxl000)()()( )( - - - - - - - - kjniijkjikjijkjinixlxxjkxlxxjk0000)()()()( - - - -kjniijijkxlxxjk00)()( - - - -kjjjkxxjk0)(0)( - -kx