數(shù)值分析插值ppt

1、第三章 插 值 法 v引言 v拉格朗日插值公式 v牛頓 (Newton) 插值v埃爾米特 (Hermite) 插值v逐步線性插值v樣條插值v數(shù)據(jù)擬合1 引 言1. 發(fā)展歷史發(fā)展歷史2. 應(yīng)用應(yīng)用3. 插值問題的提出插值問題的提出4. 插值問題所需研究的問題插值問題所需研究的問題等距節(jié)點內(nèi)插公式劉焯（隋 公元544610年）不等距節(jié)點內(nèi)插公式張遂（唐 公元683727年）等距節(jié)點一般插值公式Newton & Gregory (17世紀(jì)）非等距節(jié)點一般插值公式J.L.Lagrange (18世紀(jì)）發(fā)展歷史應(yīng)應(yīng) 用用v對觀測數(shù)據(jù)的處理對觀測數(shù)據(jù)的處理v函數(shù)的近似表示函數(shù)的近似表示v曲線曲面擬

2、合曲線曲面擬合v導(dǎo)出其它數(shù)值方法的依據(jù)（如數(shù)值積分、導(dǎo)出其它數(shù)值方法的依據(jù)（如數(shù)值積分、數(shù)值微分、微分方程數(shù)值解等）數(shù)值微分、微分方程數(shù)值解等）以近似計算函數(shù)值為例來說明散點上的函數(shù)值，即已知函數(shù)表例：設(shè)在實際問題中，某些變量之間的函數(shù)關(guān)系是存在的，但通常不能用式子表示，只能由實驗、觀測得到 yf x 在一系列離xy0 xnx1x0y1yny ijxxij,如何計算 fx 01ixx in, , ？我們希望尋求一個簡單且易于計算的函數(shù) P x來近似 fx f xP x ，即，一般 P x可選為多多項式、三角多項式、有理函數(shù)或樣條函數(shù)等。有些函數(shù)雖有表達式，但較復(fù)雜，計算函數(shù)值不經(jīng)濟，這時也希望

3、用簡單的函數(shù)來逼近。插值問題的提出 已知函數(shù)已知函數(shù) 在區(qū)間在區(qū)間 上有上有yf x( ) 01naxxxb ，求一個多 iiyfxin(),0,1, a b,定義，且已知 ，其中 yP x 項式,使其滿足 iiP xy( ) , ,i0 1n 即要求該多項式的函數(shù)曲線要經(jīng)過 ( )yf x 上已知的這n+1個點 0011nnx yx yx y,同時在其它點 上估計誤差為 ,xa b ( )( )( )R xf xP xY( )p x( )f x0 x1x1nxnx2x0y1y2y1nynyX研究問題若滿足條件的若滿足條件的 存在，又如何構(gòu)造？存在，又如何構(gòu)造？ nPx nPx滿足插值條件的多

4、項式滿足插值條件的多項式 是否存在，是否存在，唯一？唯一？ nPx fx用用 近似代替近似代替 的誤差估計？的誤差估計？2 拉格朗日插值v插值多項式的存在唯一性插值多項式的存在唯一性 v拉格朗日插值多項式拉格朗日插值多項式 插值基函數(shù)插值基函數(shù) 插值基函數(shù)的構(gòu)造插值基函數(shù)的構(gòu)造 n次拉格朗日型插值多項式次拉格朗日型插值多項式v截斷誤差截斷誤差v數(shù)值實例數(shù)值實例v拉格朗日插值多項式的優(yōu)缺點拉格朗日插值多項式的優(yōu)缺點插值多項式的存在唯一性Theorem. 存在唯一的存在唯一的n 次多項式次多項式 （1.1) 滿足條件滿足條件01( )nnnP xaa xa x0 1, , .niiPxyin證明：

5、由證明：由(1.1)可得可得 (1.2) （1.21.2）為一個你）為一個你n n1 1未知量未知量 的線性方程的線性方程組，要證明插值多項式存在唯一，只要證組，要證明插值多項式存在唯一，只要證明參數(shù)明參數(shù) 存在且唯一，即只要證明其系數(shù)存在且唯一，即只要證明其系數(shù)行列式不為零即可。行列式不為零即可。 nnnnnnnnnaa xa xyaa xa xyaa xa xy010000111101 iaia 方程組（方程組（1.21.2）的系數(shù)行列式為）的系數(shù)行列式為 此為范德蒙行列式。利用行列式性質(zhì)可此為范德蒙行列式。利用行列式性質(zhì)可得系數(shù)行列式為得系數(shù)行列式為 nnnnnnnnxxxxxxVxxx

6、xxx2000211101211(,)1 ninnijijVxxxxx10110(,)() 由于由于 時時 ，故所有因子，故所有因子 ，于是于是 即插值多項式存在唯一。即插值多項式存在唯一。 ij ijxx ijxx0 nnVxxx01(,)0 2001 ! 1.2121 120,9.7 10niinnannnnn如果線性方程組（）的系數(shù)行列式不為零，則該方程組有唯一解。若由克萊姆(Cramer)法則求解，則需要計算個階行列式并作次除法，而每個階行列式計算需作次乘法，計算量十分驚人。如階線性方程組 需次乘法。如果用每秒一億次乘法運算的計算機要?？梢娖湓诶碚撋鲜墙^對正確，但在 較大時，在實際計算

7、中確實不30萬年可行的。 由方程組（由方程組（1.2）求）求 的系數(shù)的系數(shù) ，計算量大，計算量大， 且難于得到且難于得到 的簡單表達式，下面通過找插值的簡單表達式，下面通過找插值 基函數(shù)的方法，可得到插值多項式基函數(shù)的方法，可得到插值多項式 的簡單表的簡單表 達式。達式。( )nP x ia( )nP x( )nP x線性插值線性插值。xpxxxxyyyxpyxyxxpyxpyxpxp達方式但是我們可以換一種表當(dāng)然是唯一的一次多項式由直線的點斜式可得的一條直線和為過兩點滿足條件求作一次多項式問題,)()()(:),(),()()(,)(),(:10010101110011110011問題 求作

8、一次式求作一次式 ，使?jié)M足條件，使?jié)M足條件 從幾何圖形上看，從幾何圖形上看， 表示過兩點表示過兩點 的直線，的直線，因此可表為如下對稱形式：因此可表為如下對稱形式：其中其中 和和 分別滿足條件分別滿足條件 可見，插值問題的解可見，插值問題的解 可以通過插值基函數(shù)可以通過插值基函數(shù) 和和 的組合得出，且組合系數(shù)分別是所給數(shù)據(jù)的組合得出，且組合系數(shù)分別是所給數(shù)據(jù) 。100111,pxypxy 1px 1ypx0011(,),( ,)xyx y 1px 01010110,xxxxlxlxxxxx 10 01 1pxy lxy lx 0lx 1lx000111101,0,1,0lxlxlxlx 0lx

9、 1lx01,yy拋物插值拋物插值問題 求作二次式求作二次式 ，使?jié)M足條件，使?jié)M足條件二次插值的幾何解釋是用通過三個點二次插值的幾何解釋是用通過三個點 的拋物線的拋物線 來近似考察曲線，故稱為拋物插值。類似于線性插來近似考察曲線，故稱為拋物插值。類似于線性插值，令值，令易知，易知， 應(yīng)滿足條件應(yīng)滿足條件所以有因子所以有因子 , ,故有，故有，類似的可以構(gòu)造出類似的可以構(gòu)造出 。 2px200211222,pxypxy pxy001122(,),( ,),(,)xyx yxy 2ypx 0lx0001021,0lxlxlx 1200102xxxxlxxxxx 2001122pxlx ylx yl

10、x y 12,lx lx1)(,0021xlxxxx又和拉格朗日插值多項式拉格朗日插值多項式1.插值基函數(shù)插值基函數(shù)定義：若定義：若n次多項式次多項式 在在n+1個節(jié)點個節(jié)點 上滿足條件上滿足條件則稱這則稱這n+1個個n次多項式次多項式 為節(jié)為節(jié)點上的點上的n次插值基函數(shù)。次插值基函數(shù)。01( ), ( ),( )nlx l xlx01( ),( ),( )nlxlxlx01nxxx 10 10, , jkkjlxj knkj2. 基函數(shù)的構(gòu)造基函數(shù)的構(gòu)造 由上述定義由上述定義 ，知存在常，知存在常數(shù)數(shù) ，使得，使得由由 ，可以定出，可以定出 ，進而得到：，進而得到： 令令()0,ikl xk

11、i011( )()()()()iiiinl xA xxxxxxxxiA()1iil xiA011011()()()()( )()()()()iiniiiiiiinxxxxxxxxl xxxxxxxxx)()()(101nnxxxxxxx則則 于是于是 可改寫成可改寫成 1011( )()()()() niiiiiiinxxxxxxxxx()ilx110 1( )( ), ,()() niinixl xinxxx3. 3. n n次拉格朗日型插值多項式次拉格朗日型插值多項式 是是n+1個個n次插值基本多項式次插值基本多項式 的線性組合，相應(yīng)的組合系數(shù)是的線性組合，相應(yīng)的組合系數(shù)是即即 是一個次數(shù)

12、不超過是一個次數(shù)不超過n的多項式的多項式,且滿足且滿足( )nP x( )nP x01( ), ( ),( )nlx l xlx01,nyyy0 01 10( )( )( )( )( )nnn nk kkP xy lxy l xy lxy lx()niiPxy0,1,in，。拉格朗日插值多項式的截斷誤差拉格朗日插值多項式的截斷誤差 若在若在a,b上用多項式上用多項式 來近似代替來近似代替函數(shù)函數(shù)f (x) ,其截斷誤差記作其截斷誤差記作 ，即，即 也稱為插值多項式的余項，關(guān)于插值也稱為插值多項式的余項，關(guān)于插值余項估計，有以下定理：余項估計，有以下定理：( )nP x( )nR x( )( )

13、( )nnR xf xP x( )nR x定理：定理：設(shè)函數(shù)設(shè)函數(shù)y=f (x) 的的n 階導(dǎo)數(shù)階導(dǎo)數(shù) y =f (n)(x)在在a,b上連續(xù)，上連續(xù)，y=f (n+1)(x)在在(a,b)上存在，上存在，插值節(jié)點為插值節(jié)點為ax0 x1xnb, 是是n次次拉格朗日插值多項式，則對任意拉格朗日插值多項式，則對任意x a,b有：有：其中其中(1)1( )( )( )(1)!nnnR xfxn (a,b), ，01( ) ()()()nnxx xx xx x( )nP x證明證明：由插值多項式的定義，顯然有：由插值多項式的定義，顯然有構(gòu)造輔助函數(shù)構(gòu)造輔助函數(shù)有有 。反復(fù)利用。反復(fù)利用Rolle定理

14、，存在定理，存在 (a,b), 使得使得g(n+1)( )=0,即即 ，結(jié)論成立。，結(jié)論成立。()( )( )0,0,1,niiniR xf xP xin nntg tf tP tf xP xx 000 1, ,ig xg xin 110! nnnffxPxx數(shù)值實例數(shù)值實例例求過點例求過點(2,0)(4,3)(6,5)(8,4)(10,1)的拉格的拉格朗日型插值多項式。朗日型插值多項式。解解：用：用4次插值多項式對次插值多項式對5個點插值個點插值 00112233442 04 36 58 410 1,xyx yxyx yxy0(4)(6)(8)(10)1( )(4)(6)(8)(10)(2

15、4)(2 6)(2 8)(2 10)384xxxxl xxxxx 1(2)(6)(8)(10)1( )(2)(6)(8)(10)(4 2)(4 6)(4 8)(4 10)96xxxxl xxxxx2(2)(4)(8)(10)1( )(2)(4)(8)(10)(6 2)(6 4)(6 8)(6 10)64xxxxl xxxxx3(2)(4)(6)(10)1( )(2)(4)(6)(10)(8 2)(8 4)(8 6)(8 10)96xxxxl xxxxx4(2)(4)(6)(8)1( )(2)(4)(6)(8)(10 2)(10 4)(10 6)(10 8)384xxxxl xxxxx40 01

16、 12 23 34 4( )( )( )( )( )( )P xy l xy l xy l xy l xy l x13(4)(6)(8)(10)(2)(6)(8)(10)3849654(2)(4)(8)(10)(2)(4)(6)(10)64961(2)(4)(6)(8)384xxxxxxxxxxxxxxxxxxxx于是有例例. . 已知已知 sin0.32=0.314567,sin0.34=0.333487,sin0.36=0.352274, 用用Lagrange插值計算插值計算sin0.3367的值，并估計截斷誤差。的值，并估計截斷誤差。解解：f (x)= sinx ,取取 12021020

17、12010210122120 x x x xx x x xx x x xP xyyyx x x xx x x xx x x x 0011220 32 0 3145670 34 0 3334870 36 0 352274,., .,., .,., .x yx yx y于是有于是有可以發(fā)現(xiàn)，結(jié)果有六位有效數(shù)字的可以發(fā)現(xiàn)，結(jié)果有六位有效數(shù)字的sin x表表完全一致。完全一致。44407689 1003367031456700008389 1005511 1003334870352274000040000803303742.sin0.3367P.截斷誤差為截斷誤差為其中其中 故有故有 32012013

18、,! fRxxxxxxxxx x 3201 03145670828coscos. fx01, xx2260 33670 33670 33670 8280 01670 0330 02330 178 10.sin .1 n時恒為時恒為0證明證明: 運用Newton插值公式(6)進行計算時,先計算f(x)關(guān)于節(jié)點x0,xn的各階差商.計算過程如下表所示 . xk f(xk) 一階差商 二階差商 三階差商 n 階差商123onxxxxx0123 nf xf xf xf xf x0112231, ,nnf x xf x xf x xf xx01212321 , ,nnnf x x xf x x xf x

19、xx0123321 , , , nnnnf x x x xf xxxx0 1 , , , nf x xx計算Nn(x)時,常采用秦九韶算法,即 .00010101201101000110122012101( )( ) () , ()() , , ()() () , , , ( ) ()( , ()( , , ()( , , , () , ,) )nnnnnnnN xf xx x f x xx x x x f x x xx x x xx xf x xxf xx x f x xx x f x x xx xf x xxx xf x xx 下面給出下面給出Newton插值法的計算機插值法的計算機算法算

20、法.開始時開始時,f(k)存放函存放函數(shù)值數(shù)值f(xk),運算完畢運算完畢f(xié)(k)存放存放k階差商階差商fx0,xkNewton插值算法(1) 輸入: xi, fi;(2)di=fi (i=0,1,n);(3)計算差商 對i=1,2,n 做 (3.1) 對j=i,i+1,n 做 fj=(dj-dj-1)/(xj-xj-i); (3.2) 對j=i,i+1,n 做 dj=fj;(4) 計算插值N(u) (4.1)輸入插值點u; (4.2) v=0; (4.3) 對i=n,n-1,1,0 做 v=v(u-xi)+fi;(5) 輸出u,v.五 等距節(jié)點的Newton插值公式與差分 當(dāng)插值節(jié)點x0,x

21、n為等距分布時,Newton插值公式(6)可以簡化. 設(shè)插值節(jié)點xj=x0+jh, j=0,1,n; h=(b-a)/n稱為步長,且x0=a, xn=b. 令x=x0+th,則當(dāng)x0 xxn時,0tn. 基函數(shù) 此時差商也可進一步化簡,為此引進差分的概念. 定義 稱 f(xi)=f(xi+h)-f(xi) 和 f(xi)= f(xi)-f(xi-h)分別為函數(shù)f(x)在點xi處的一階向前差分和一階向后差分. .011( )()()()(1)(2)(1)iiixxxxxxxt tttih 一般地,稱k階差分的差分為k+1階差分,如二階向前和向后差分分別為 計算各階差分可按如下差分表進行.22(

22、)( )( ()( )()( )(2 )2 ()( )( )( )( ( )()( )()( )2 ()(2 )iiiiiiiiiiiiiiiiiif xf xf xhf xf xhf xf xhf xhf xf xf xf xf xhf xf xhf xf xhf xh 2300110222102333210231230niiiiiinnnnnnxfffffxfxffxfffxffffxfffff 向前差分表向前差分表 差分具有如下性質(zhì): . 性質(zhì)1(差分與函數(shù)值的關(guān)系) 各階差分均可表示為函值fj=f(xj)的線性組合: 性質(zhì)2(前差與后差的關(guān)系): 性質(zhì)3(多項式的差分)若f(x)Pn(

23、n次多項式類), 則00( 1),( 1)!()!kkkjjkkjjikij kikij kjjjkfC ffC fkCj kj kkii kff ,()!,0,nkknnPknfxa h nknkn其中其中 性質(zhì)4(差分與差商的關(guān)系): 性質(zhì)5(差分與導(dǎo)數(shù)的關(guān)系 利用這些性質(zhì),可將Newton公式 Nn(x)= f(x0)+(x-x0) fx0,x1+(x-x0)(x-x1) fx0,x1,x2 +(x-x0)(x-xn-1) fx0,xn進一步簡化11,!,!kiiiikkkiiiikkffxxxkhffxxxkh1( )! ,( ),()kkiiii kkkii kfk h f x xx

24、h fxx020000( )()(1)(1) (1)1!2!nnnN xN xthtt tt tt nffffn (11)稱公式稱公式(11)為為Newton向前差分插值公式向前差分插值公式,其余項為其余項為1(1)00(1)()( )()( )(1)!(,)nnnnnt ttnR xR xthhfnx x(12)如果將式如果將式(6)改為按節(jié)點改為按節(jié)點xn,xn-1,x0的次序排列的的次序排列的Newton插插值公式值公式,即即11110( )() () ,()()() ,nnnnnnnnnN xf xxxf x xxxxxxxf x xx 令令x=xn-th, 則當(dāng)則當(dāng)x0 xxn時時,0tn.利用差商與向后利用差商與向后差分的關(guān)系差分的關(guān)系, 式式(13)可簡化為可簡化為22()()(1)(1)2!(1)(1)(1)!nnnnnnnnnNxNxtht tftfft ttnfn (13)(14)稱式稱式(14)為為Newton向后差分插值公式向后差分插值公式,其余項為其余項為(1)110( )( )()( 1)(1)()(1)!nnnnnnnfRxRxthht ttnnxx22120,nnnnnnnffffff 若要計算的插值點若要計算的插值點x較靠近點較靠近點x0,則用向前插值公式則用向前插值公式