第四章 插值方法(1)

1、計算方法 (力學(xué)系本科生)4.1 問題的提出 第四章插值方法實際背景4.1 問題的提出表4-1xy0 x0y1x2xnx1y2yny 實驗和觀察得到的一些離散數(shù)據(jù)點 需要用這些離散數(shù)據(jù)點給出簡單的函數(shù)表達式 來近似原來函數(shù) 。 ( ,),( ),0,1,2,., ,iiiix yyf xin( ) x( )f xRemark: 函數(shù) 的類型有多種選擇，例如代數(shù)多項式、三角函數(shù)，有理函數(shù)等，相應(yīng)的插值多項式叫代數(shù)插值，三角多項式插值，有理函數(shù)插值。最常用的類型是代數(shù)多項式 。( ) x4.1 問題的提出 函數(shù) 有明確表達式，但比較復(fù)雜,不易計算和使用,希望用簡單函數(shù) 近似原來函數(shù) ，便于計算函數(shù)

2、值和研究函數(shù)特性 。( ) x( )f x( )f x4.1 問題的提出拉格朗日插值的提法 已知離散數(shù)據(jù)(xi,yi),i=0,1,2,n，其中a=x0 x1 x2 xn =b，尋求一個次數(shù)盡可能低的多項式函數(shù)P(x)，滿足條件P(xi)=yi, i=0,1,2,n 從幾何上看，就是在通過給定的n+1個點(xi,yi),i=0,1,2,n，的所有多項式曲線，尋找出次數(shù)最低的一個,如圖4-1所示。 4.1 問題的提出yxo(x0,y0)(xn,yn)圖4-1 有無數(shù)條曲線經(jīng)過n+1個點4.1 問題的提出 定義：如果P(x)是滿足P(xi)=yi=f(xi)，i=0,1,n，的次數(shù)最低的代數(shù)多項式

3、，并且用P(x)來近似函數(shù)f(x) ，則稱P(x)是f(x)的拉格朗日插值多項式，x0,x1,xn稱為插值節(jié)點，簡稱節(jié)點；節(jié)點所在區(qū)間a,b稱為插值區(qū)間，條件P(xi)=yi ，稱為插值條件， f(x)稱為被插函數(shù)。 4.1 問題的提出【歷史注記】插值法歷史悠久。據(jù)考證，在公元六世紀時，我國劉焯(zhuo)已經(jīng)把等距二次插值法應(yīng)用于天文計算。十七世紀時，Newton和Gregory(格雷格里)建立了等距節(jié)點上的一般插值公式，十八世紀時，Lagrange(拉格朗日)給出了更一般的非等距節(jié)點插值公式。4.1 問題的提出(1) 尋找滿足插值條件的分段多項式; 插值問題的進一步提法有：(2) 在插值條

4、件中附加某些節(jié)點上的導(dǎo)數(shù)值，尋找相應(yīng)的多項式。 4.1 問題的提出本章主要學(xué)習內(nèi)容 拉格朗日插值多項式存在性和唯一性；拉格朗日插值多項式構(gòu)造法；誤差估計(插值余項)。v拉格朗日插值多項式4.1 問題的提出v差商與差分及其性質(zhì)v牛頓插值公式牛頓插值多項式構(gòu)造法；誤差估計(插值余項)。4.1 問題的提出v分段插值法分段線性插值；分段三次插值 (Hermite)。v三次樣條插值v曲線擬合的最小二乘法4.2 拉格朗日插值(Lagrange interpolation)第四章插值方法4.2.1 拉格朗日插值多項式存在性和唯一性4.2 拉格朗日插值v 定理4-1:滿足條件P(xi)=yi, xixj,(i

5、 j) i=0,1,2,n 的拉格朗日插值多項式0( ),nknkkkP xc xcR存在且唯一。4.2.1 存在性和唯一性證明：由插值條件知1110.,0,1,.,nnniniiic xcxc xcyin 這是一個關(guān)于c0,c1,cn 的線性方程組，如果方程組系數(shù)行列式不為零，則能唯一確定出c0,c1,cn 方程組行系數(shù)列式是Vandermonde(范德蒙)行列式：4.2.1 存在性和唯一性10001111111111.1.1().1.1nnnnijj i nnnnnnnnnnnxxxxxxxxxxxxxx 由于節(jié)點xixj,(i j),所以上面行列式不為零。于是插值多項式存在且唯一。4.2

6、.1 存在性和唯一性4.2 拉格朗日插值多項4.2.2 拉格朗日插值多項式的構(gòu)造4.2.2 插值多項式的構(gòu)造 給定兩個節(jié)點(x0,y0), (x1,y1)，構(gòu)造線性多項式L1(x)，使得L1(x0)=y0, L1(x1)=y1。 L1(x)的幾何意義是過兩點(x0,y0), (x1,y1)的直線。 線性插值(兩點插值)yx0oxx1y=L1(x)y=f(x)4.2.2 插值多項式的構(gòu)造 由解析幾何易知該直線方程是：1010010( )(), (yyL xyyxxxx點斜式)011010110( ), ()xxxxL xyyyxxxx兩點式4.2.2 插值多項式的構(gòu)造001010 xxyyxxy

7、y其中 l0(x), l1(x) 為次數(shù)不高于1的多項式 ，且滿足將 L1(x) 寫成10 01 1( )( )( )L xy l xy l x0011( )0 xxlxxx0110( )1xxl xxx顯然， L1(x)滿足插值條件。 4.2.2 插值多項式的構(gòu)造因為 l0(x1)=0, l1(x0)=0，故可設(shè) 001110( )(),( )()lxxxl xxx由 l0(x0)=1, l1(x1)=1，得 01011011,xxxx所以01010110( ),( )xxxxlxl xxxxx4.2.2 插值多項式的構(gòu)造 l0(x), l1(x)稱為線性插值基函數(shù)。于是得到線性插值多項式：

8、10 01 101010110( )( )( )L xy lxy l xxxxxyyxxxx4.2.2 插值多項式的構(gòu)造拋物線插值(三點二次插值) 設(shè)插值節(jié)點為(x0,y0), (x1,y1), (x2,y2), 求次數(shù)不高于二次的插值多項式 L2(x)，使它滿足 L2(xi)=yi, i=0,1,2 使用構(gòu)造法，設(shè)2001122( )( )( )( )L xlx yl x ylx y其中l(wèi)i(x), i=0,1,2, 是二次插值基函數(shù)， 4.2.2 插值多項式的構(gòu)造且在節(jié)點上滿足00121( )00 xxl xxxxx01120( )10 xxl xxxxx02120( )01xxl xxx

9、xx由此可以求出 li(x), i=0,1,2于是得到拋物線插值多項式0201122012010210122021()()()()()()( )()()()()()()xxxxxxxxxxxxL xyyyxxxxxxxxxxxx4.2.2 插值多項式的構(gòu)造一般情形的拉格朗日插值多項式設(shè)離散數(shù)據(jù)為(xk,ik), k=0,1,2,n, i 是固定的非零整數(shù) ,且 , ik是Kronecher記號 0in 01.nxxx1,0,ikikik4.2.2 插值多項式的構(gòu)造現(xiàn)在求插值多項式，記為ln,i(x)，滿足插值條件 ln,i(xk)=ik, k=0,1,n，即 ,1,()0,n ikkilxki

10、這說明 x0,xi-1 , xi+1, xn 是 ln,i(x)=0 的根，因而 ln,i(x) 必然有形式：,011( )().()().()n iiinlxa xxxxxxxx4.2.2 插值多項式的構(gòu)造利用 ln,i(xi)=1 確定系數(shù) a0111().()().()iiiiiinaxxxxxxxx于是011,011().()().()().()().()iinn iiiiiiinxxxxxxxxlxxxxxxxx4.2.2 插值多項式的構(gòu)造 n+1 個 n 次多項式 ln,0, ln,1, ln,n 稱為以 x0, x1, xn 為節(jié)點的拉格朗日n次插值基函數(shù)，簡記為 l0, l1,

11、 ln v 定義：4.2.2 插值多項式的構(gòu)造 現(xiàn)在考慮一般情況。已知節(jié)點 (xi, yi), i=0,1,n, x0 x1xn, 則 00110011( )( )().()().()().()().()nni iiniiniiiiiiiinL xyl xxxxxxxxxyxxxxxxxx是節(jié)點(xi, yi), i=0,1,n, 的拉格朗日插值多項式。4.2.2 插值多項式的構(gòu)造 Ln(x)是次數(shù)不超過 n 的多項式，且滿足插值條件，由拉格朗日插值多項式存在唯一性定理知 Ln(x) 為拉格朗日插值多項式。4.2.2 插值多項式的構(gòu)造4.2.3 拉格朗日插值余項(插值誤差) 4.2 拉格朗日插

12、值4.2.3 拉格朗日插值余項 如果僅僅知道離散數(shù)據(jù)，利用插值來得到連續(xù)模型，那么對于得到的插值多項式不存在截斷誤差分析。 如果用插值多項式逼近已知函數(shù)，存在用插值多項式代替已知函數(shù)時的精度問題，需要截斷誤差分析。 a,b上用拉格朗日插值多項式 Ln(x) 逼近已知函數(shù) f(x)，節(jié)點為 x0,x1,xna,b，xixj, (ij) ,f(xi)=yi, i=0,1,n4.2.3 拉格朗日插值余項 則截斷誤差Rn(x)是a,b上的函數(shù)，Rn(x)=f(x)-Ln(x)，Rn(x)也叫Ln(x)的余項。v 定理 如果f(x) Cna,b,且在(a,b)上有n+1階導(dǎo)數(shù),則對任何xa,b,存在(

13、)( , )xa b(1)0( )( )( )( )()(1)!nnnniifR xf xL xxxn成立。4.2.3 拉格朗日插值余項 使羅爾(Rolle)定理：若f(x)在a,b上連續(xù),在(a,b)上可導(dǎo), 且f(a)=f(b), 則存在 滿足 。( , )a b( )0f4.2.3 拉格朗日插值余項證明： Rn(xi)=f(xi)-Ln(xi)=0, i=0,1,n可以假定010( )( )()().()( )()nnniiRxk x xxxxxxk xxx于是，問題變?yōu)榇_定k(x)的形式。考慮任一固定xa,b, xxi, i=0,1,n, 求k(x) 。 做輔助函數(shù)g(t)00( )(

14、 )( )()( )( )( )()nnniniiig tR tk xtxf tL tk xtx4.2.3 拉格朗日插值余項 t=x時，有000( )( )( )()( )()( )()0nnnniiiiiig xR xk xxxk xxxk xxx所以 g(t)有 x,x0,x1,xn共n+2個相異零點, 且g(t)在(a,b) 上存在n+1階導(dǎo)數(shù),依次對函數(shù)g,g,g,g(n)分別運用羅爾定理,至少有n+1,n,1個相異零點,于是 使( , )a b 1(1)(1)(1)10( )( )( )( )()0nnnnnnitnidgfLk xtxdt4.2.3 拉格朗日插值余項Ln(x)是n次

15、多項式，(1)( )0nnL 的首項為 ，0()niitx1nt110()(1)!nnitnidtxndt于是(1)( )( )(1)!nfk xn故(1)0( )( )()(1)!nnniifR xxxn4.2.3 拉格朗日插值余項Remark(1) 余項表達式只有在 f(x) 的高階導(dǎo)數(shù)存在時才能應(yīng)用。 (2) 雖然 在(a,b)內(nèi)不可能具體給出，但我們可以求出 ，于是用插值多項式Ln(x)近似f(x)的截斷誤差限是 (1)1max( )nna x bfxM 11( )( )(1)!nnnMR xxn由此可以看出4.2.3 拉格朗日插值余項(3) 的大小除了與 Mn+1 有關(guān)外，還與 有關(guān)

16、，此值與x0,x1,xn的選擇和x的位置有關(guān)。( )nR x1( )nx(4) 如果f(x)本身為次數(shù)不超過n的多項式，則余項為0，插值多項式為其本身。特別地，若f(x)=1，可以得到01( )( ).( )1nlxl xlx4.2.3 拉格朗日插值余項(5) 插值多項式只與數(shù)據(jù)點(xi,yi)有關(guān)，而余項卻與整個區(qū)域上的f(x)有關(guān)。(6) 拉格朗日插值適用于非等步長情形。(7) 當節(jié)點數(shù)目變化時，需要重新計算全部拉格朗日基函數(shù)，因為基函數(shù)和每一個節(jié)點有關(guān)。(8) n+1個節(jié)點插值多項式次數(shù)不超過n。4.2.3 拉格朗日插值余項例4-1 利用100，121的開方求 。4.2.4 拉格朗日插值

17、例題115解：設(shè) ，已知兩個節(jié)點x0=100, x1=121，構(gòu)造線性插值函數(shù)并求在點115處的函數(shù)值。插值函數(shù)為 ( )yf xx211121221( )1211001011100 121121 100 xxxxL xyyxxxxxx于是1115(115)10.71428L例4-2 對任意x，以表距為0.02的正弦表，如果使用線性插值求sin(x)的近似值，試估計其誤差。4.2.4 拉格朗日插值例題解： 設(shè)x在區(qū)間xi, xi+1上, xi+1- xi=0.02,作線性插值，其誤差限為12121211( )max ()()(0.02)22iiiixx xR xMxxxxM 其中112max(

18、 )maxsin( )1iiiixx xxx xMfxx 于是4112( )10R x例4-3 設(shè)f(x)=e-x在x0=0.10, x1=0.15, x2=0.25, x3=0.30的值分別為0.904837, 0.860708, 0.778801, 0.740818,試構(gòu)造拉格朗日插值多項式，求e-x在x=0.20的近似值并估計誤差。4.2.4 拉格朗日插值例題解：拉格朗日插值多項式為30 01 12 23 3( )( )( )( )( )L xy lxy l xy lxy l x于是30 0112 23 3(0.20)(0.20)(0.20)(0.20)(0.20)0.818730Lyl

19、ylylyl4.2.4 拉格朗日插值例題插值余項(4)34( )( )( )4!fR xx所以(4)30123( )(0.20)(0.20)(0.20)(0.20)(0.20)4!fRxxxx由于(4)0.10.10.3( )max0.91xxfeee 所以63(0.20)0.95 10R例4-4 設(shè)x0, x1, ,xn,為n+1個互異節(jié)點，li(x)為拉格朗日插值基函數(shù)，即 4.2.4 拉格朗日插值例題0,( )njijj iijxxl xxx試證：0(1)( ),1,2,.,nkkiiix l xxkn0(2)()( )0,1,2,.,nkijixxlxkn00( )( ) ( )()n

20、niiiiip xp x l xxx(3) p(x)是最高次項系數(shù)為1的n+1次多項式， 則4.2.4 拉格朗日插值例題且有插值余項證：(1)記 ， 則 以 為插值節(jié)點的拉格朗日插值多項式為( ),0,1,.,kkxxkn( )kx012,.,nx x xx0( ) ( )nkiiix l x(1)00( )( )( ) ( )()(1)!nnnkkkiiiiixx l xxxn由于 是次數(shù)不超過n的多項式 ，則 ( )kx(1)00()( )()0(1)!knnnxkkiiiiixxx l xxxn4.2.4 拉格朗日插值例題于是0( ),0,1,2,.,nkkiiix l xxkn (2)

21、記 , 則 以 為插值節(jié)點的拉格朗日插值多項式為( )() ,0,1,.,kkxxtkn( )kx012,.,nx x xx0( ) ( )nkiiix l x且有插值余項(1)00( )( )( ) ( )()(1)!nnnkkiiiiixx l xxxn4.2.4 拉格朗日插值例題由于 是次數(shù)不超過n的多項式 ，則 ( )kx(1)00() ()()( )()0(1)!knnnixkkiiiiixtxtxt l xxxn于是0()( )() ,1,2.,nkkiiixtl xxtkn在上式中，令 t=x，即得0()( )0,1,2,.,nkiiixxl xkn(3) 由插值余項公式有 4.

22、2.4 拉格朗日插值例題(1)0000( )( )( ) ( )()(1)!(1)!()()(1)!nnniiiiinniiiipp xp x l xxxnnxxxxn4 插值方法4.3 差商與差分及其性質(zhì)Difference quotient and difference 4.3 差商和差分差商v 定義函數(shù)f(x)在xi處的值fxi=f(xi)，fxi稱為f關(guān)于xi的零階差商；f(x)關(guān)于xi與xi+1的一階差商記為fxi,xi+1, 一般地，f(x)關(guān)于 xi, xi+1, ., xi+k,的k階差商記為fxi,xi+1,.,xi+k12111,., ,., ,.,iii kiii kii

23、i ki kif xxxf x xxf x xxxx 111 ,iiiiiif xf xf x xxx 差商的性質(zhì)： 性質(zhì)1：差商和函數(shù)值有關(guān)系0100111(),.,()().()().()njnjjjjjjjjnf xf xxxxxxxxxxxxx證明：用數(shù)學(xué)歸納法。n=1時010101010110()()()(),f xf xf xf xf xxxxxxxx所以n=1時成立。4.3 差商和差分設(shè)n=m-1時成立，即有 101100111(),.,().()().()mjmjjjjjjjmf xf xxxxxxxxxxx121111() ,.,().()().()mjmjjjjjjjmf

24、xf x xxxxxxxxxx于是由差商定義有：01112020,. ,.,.,mmmmf x xxf x xxf x xxxx4.3 差商和差分10001111111()1().()().()()().()().()mjjmjjjjjjmmjjjjjjjjmf xxxxxxxxxxxf xxxxxxxxx4.3 差商和差分1100111001020111111121()1().()().()()()().()()().()().()()()().()mjjmjjjjjjmmmjjjjjjjjmmmmmmf xxxxxxxxxxxf xxxxxxxf xxxxxxxxxf xxxxxxx4.3

25、 差商和差分11011110001020100121()1().()().()11()()()().()()()()()().()mjjmjjjjjjmjjmmmmmmmmmf xxxxxxxxxxxxxxxf xxxxxxxxxf xxxxxxxxx4.3 差商和差分1101110010010011()().()().()()()()().()().()()().()().()mjjjjjjjjmjmmmmmmmjjjjjjjjmf xxxxxxxxxxxf xf xxxxxxxxxf xxxxxxxxx4.3 差商和差分差商性質(zhì)2：差商關(guān)于所含節(jié)點對稱，即 0110,., ,.,.nnf

26、x xxf x xx即可以任意調(diào)換xi,xj的次序而值不變。4.3 差商和差分例 4.3 差商和差分Remark: 一階差商實際上是微商的離散形式 4.3 差商和差分( )()()limlim ,ijijijjijxxxxijf xf xfxf x xxxv定義：設(shè)有等距節(jié)點xi=x0+ih, i=0,1,2，其中h是常數(shù)，稱為步長，記函數(shù)f的值 ( )iiff x12(),0,1,2,.2iihff xi令1iiifff1iiifff1122iiifff4.3 差商和差分稱 為f在xi的一階向前差分， 為f在xi的一階向后差分， 為f在xi的一階中心差分，分別稱為 (向前，向后，中心)差分算

27、子。ififif, n階(向前,向后,中心)差分分別為 111nnniiifff 111nnniiifff 112211nnniiifff4.3 差商和差分零階差分為 000iiiiffff 位移算子 ()tEtRtii tE ff即 ( )()tiE f xf xth單位算子I iiIff由 1()iiiiiifffEfIfEI f得 EI 4.3 差商和差分由111()iiiiiifffIfEfIEf得1IE 由得111122221122()iiiiiifffE fEfEEf1122EE4.3 差商和差分一階差分4.3 差商和差分010fff121fff11nnnfff二階差分201021

28、02ffffff 21213212ffffff 2212122nnnnnnffffff 用數(shù)學(xué)歸納法可以證明:4.3 差商和差分12(1)1!2!.( 1)mkk mk mk mmkmm mfffff n4:4.3 差商和差分 證明當節(jié)點是等距時，差分與差商存在關(guān)系 001(),.,!nnnf xf x xxn h證明：用數(shù)學(xué)歸納法。 n=1時1000110()()(),f xf xf xf xxxxh 假設(shè)n=m-1時成立，即有 4.3 差商和差分于是100111(),.,(1)!mmmf xf x xxmh11121( ) ,.,(1)!mmmf xf x xxmh12011010 ,.,

29、.,.,mmmmf x xxf x xxf x xxxx證畢。4.3 差商和差分1101110()()1(1)!(1)!mmmmmf xf xxxmhmh111001()()()(1)!mmmmmf xf xf xmhmhm h 如果f(x)是x的n次多項式，記()( )ff xhf x 則其k階差分 是x的n-k次多項式，高于n階的差分均為零。 ( ), (0)kf xkn(用數(shù)學(xué)歸納法和泰勒公式 證明)21( )(1)( )()( )( )( ).( )( )2!(1)!nnnnf xf xhf xhhhhfxfxfxfnn4.3 差商和差分4.4 牛頓插值公式 Newton interp

30、olation4 插值方法由差商定義知： 4.4 牛頓插值公式000( )() ,()f xf xf x xxx001011 , ,()f x xf x xf x x xxx010120122 , ,()f x x xf x x xf x x x xxx01010 ,.,., ,.,()nnnnf x xxf x xxf x xxxx.從最后一個式子開始, 把后一個式子代入前一個式子，得 000100112010101110 ,.( )(),(),()().,.,()().(.,()().)()nnnnnnf xf xf x xxxf x x xxxxxf xf x x xxxxxxxxRxx

31、xxxxxxxNx4.4 牛頓插值公式其中Nn(x)叫n次牛頓插值多項式，Rn(x)為插值余項。4.4 牛頓插值公式00100120101011( )(),(),()().,.,()().()nnnNxf xf x xxxf x x xxxxxf x xxxxxxxx4.4 牛頓插值公式 Nn(x)的次數(shù)小于等于nRn(xi)=0 Nn(xi)=f(xi), i=0,1,2,n 101210( )( ),.,()nnnniiNxNxf x x xxxx Remark: 4.4 牛頓插值公式牛頓向前插值公式001,.,!nnnyf x xxn h代入牛頓插值公式得200100020110()()

32、( )()()().2!()().()()!nnnnxxxxxxNxf xf xf xhhxxxxxxf xn h如果節(jié)點等距，xi=x0+ih, i=0n利用4.4 牛頓插值公式牛頓向后插值公式11211010( )(),(),()().,.,()().()nnnnnnnnnnnnnnNxf xf xxxxf xxxxxxxf xxxxxxxxx120,.,nnnxxxx節(jié)點逆序排列4.4 牛頓插值公式01,.,!nnnnyf x xxn h代入牛頓插值公式得利用21210()()( )()()().2!()().()()!nnnnnnnnnnnnxxxxxxNxf xf xf xhhxxx

33、xxxf xn h由于插值多項式的唯一性，所以L(x)=N(x)，即拉格朗日插值多項式等價于牛頓插值多項式。4.4 牛頓插值公式同時，拉格朗日插值的插值余項和牛頓插值余項也相等。 0011(1)00( ) ,.,()().()( )(),(1)!nnnnniniR xf x xxxxxxxxfxxx xn 如果插值節(jié)點xi=x0+ih, i=0,1,n為等距節(jié)點并要計算x0附近點x (x0 xx1)的函數(shù)值，令 4.4 牛頓插值公式0, 01xxtht 代入牛頓向前插值公式，即得200000(1)(1).(1)().2!nt tt ttnN xthyt yyyn 由余項公式得余項 1(1)0(

34、1).()( )( ),(,)(1)!nnnnt ttnR xhfx xn 如果要xn計算附近點x (xn-1xxn)的函數(shù)值，令x=xn+th, (-1t0)，代入牛頓向后插值公式得 4.4 牛頓插值公式2(1)().2!(1).(1)!nnnnnnt tNxthyt yyt ttnyn 1(1)0(1).()( )( ),(,)(1)!nnnnt ttnR xhfx xn牛頓插值多項式的另一種解釋 4.4 牛頓插值公式記Lk(x)為以(xi,yi),i=0,1,k為插值數(shù)據(jù)點的k次拉格朗日插值多項式，則可以把n次拉格朗日多項式寫為 010211( )( )( )( )( )( ) . (

35、)( )nnnL xL xL xL xL xL xL xLx若記 ，則它是一個k次多項式。1( )( )( )kkkQ xL xLx于是4.4 牛頓插值公式01( )( )nnkkLL xQ x為計算Qk(x)，注意到1( )( )( )0,0,1,.,1kininiiiQ xL xLxyyik而Qk(x)為k次多項式，故Qk(x)有形式011( )()().()kkkQ xaxxxxxx4.4 牛頓插值公式代入 得01( )( )( )nnkkL xL xQx010201011( )()()().()().()nnkL xaa xxaxxxxaxxxxxx由插值條件Pn(xi)=yi知00a

36、y01101()aa xxy0120220212()()()aa xxaxxxxy于是可以逐個解出 4.4 牛頓插值公式01020101()()().().()nnnnnnnnaa xxaxxxxaxxxxy00ay11010()/()ayyxx22020101021()/()()/()/()ayyxxyyxxxx注意到 4.4 牛頓插值公式00af x101,af x x2012,af x x x01,.,nnaf x xx于是把上式代入Ln得到牛頓插值多項式 001001011( ),().,.,()().()nnnNxf xf x xxxf x xxxxxxxx例4-5: (中南大學(xué)20

37、01年博士研究生入學(xué)試題)求一個次數(shù)不高于3的多項式P3(x) ,滿足:4.4 牛頓插值公式3333(1)2;(2)4;(3)12;(2)3PPPP解:滿足 的拉格朗日插值多項式為:222(1)2;(2)4;(3)12LLL22222(2)(3)(1)(3)(1)(2)( )(1)(2)(3)(1 2)(1 3)(2 1)(23)(3 1)(32)376xxxxxxL xLLLxx 設(shè)4.4 牛頓插值公式32( )( )(1)(2)(3)P xL xA xxx 由 得3(2)3P2A 所以323( )29156P xxxx例4-6:給定數(shù)據(jù)表4.4 牛頓插值公式由求4次牛頓插值多項式及余項。解

38、:由所給的5個數(shù)據(jù)點做差商表4.4 牛頓插值公式457( )43(1)(1)(2)(1)(2)(4)6601(1)(2)(4)(6)180Nxxxxxxxxxxx4.4 牛頓插值公式(5)4( )( )( )( )(1)(2)(4)(6)(7)5!(1,7)fR xf xNxxxxxx插值余項為4.4 牛頓插值公式21( )1f xx!1 設(shè)函數(shù)寫出它在插值節(jié)點1, 0, 1上的插值多項式。2 設(shè) 且 互不相等,證明1( )f xax01,.,na x xx012011,.,()().()1,2,.kkf x x xxaxaxaxkn，4.4 牛頓插值公式3 設(shè) 為 n+1個互異的節(jié)點, li

39、(x) (i=0,1,n) 為拉格朗日插值基函數(shù),令li(x)=ci ,證明:01,.,nx xx00 121,00,1,2,.,( 1).,1nkiiinkc xknx x xxkn4 插值方法4.5 分段插值法 通常為了獲得好的逼近效果，插值節(jié)點的間距應(yīng)當較小，節(jié)點數(shù)目應(yīng)該較多。這時，如果采用整體(一個插值多項式)插值，則關(guān)于給定函數(shù)值的插值多項式的次數(shù)一般很高，稱為高次插值。4.5 分段插值法當次數(shù)太高時，會出現(xiàn)龍格現(xiàn)象(C. Runge)，這個現(xiàn)象是龍格在1901年發(fā)現(xiàn)的:用高次插值多項式可能產(chǎn)生極大誤差。4.5 分段插值法龍格用了實例來說明這個現(xiàn)象：設(shè)f(x)是定義在-5,5上的函數(shù)

40、 21( )1f xx對于n個節(jié)點(n=1,2,)，由等距節(jié)點集105,0,1,.,niiSxinn 決定一個拉格朗日插值多項式 Ln(x)201( )( )1nniiiL xl xx4.5 分段插值法在 附近，Ln(x)離開f(x)很遠。 5x 4.5 分段插值法用相對較少的數(shù)據(jù)點作插值節(jié)點，可以避免大的誤差。但是我們既然有了很多數(shù)據(jù)點，就當然希望在插值時能夠全部用上這些數(shù)據(jù)點，用得越多越好。 4.5 分段插值法 problem 解決這一矛盾的辦法是分段插值，即，用分段多項式來代替單一多項式進行插值。4.5 分段插值法 solution 4.5.1 分段線性插值 4.5 分段插值法v 定義：

41、設(shè)a=x0 x1xn=b節(jié)點上的函數(shù)值為y0,y1,yn，若插值函數(shù)S1(x)滿足 4.5.1 分段線性插值(1) 即在區(qū)間上連續(xù) 01( ) , S xC a b(2)1( ),0,1,2,.,iiS xyin(3) S1(x)在每個子區(qū)間xi,xi+1 , i=0,1,2n-1都是線性函數(shù) 那么，S1(x)叫a,b上的分段線性插值函數(shù)。 S1(x)在區(qū)間xi,xi+1上的拉格朗日形式是 4.5.1 分段線性插值11111111( ),iiiiiiiiiiiiiixxxxS xyyxxxxl ylyxxx S1(x)在區(qū)間xi,xi+1上的牛頓形式是 111( ) ,(),iiiiiiS x

42、yf x xxxxxx4.5.1 分段線性插值 S1(x)在區(qū)間a,b上可用插值基函數(shù)表示為 10( )( )niiiS xl x y其中l(wèi)i(x)叫分段線性插值基函數(shù)11111111,( ),0, , iiiiiiiiiiiiixxxxxxxxxl xxxxxxxxxxa b且1,2,.1in 分段線性插值基函數(shù)li(x)在xi附近不為零，在其它地方都為零。這種性質(zhì)叫局部非零性質(zhì)，當插值點函數(shù)值有誤差時，這種性質(zhì)可以把誤差控制在一個局部區(qū)域內(nèi)。 4.5.1 分段線性插值4.5.2 分段三次插值(Hermite)4.5 分段插值法 有些實際問題中不但要求插值函數(shù)P(x)在節(jié)點處的函數(shù)值與f(x

43、)在節(jié)點處的值相等，而且要求P(x)與f(x)在節(jié)點處的導(dǎo)數(shù)值也相等。4.5.2 分段三次插值4.5.2 分段三次插值v 定義：設(shè)函數(shù)f(x)在節(jié)點a=x0 x1 xn=b上的函數(shù)值為y0, y1, , yn其導(dǎo)數(shù)值為 ，如果S3(x)滿足 01,.,nyyy(1) S3(x)在a,b上一階導(dǎo)數(shù)連續(xù)(2) S3(xi)=yi,3( ),0,1,.,iiSxyin(3) S3(x)在每個子區(qū)間xi, xi+1上是次數(shù)小于等于3的多項式 則稱S3(x)為插值區(qū)間a,b上的分段三次插值函數(shù)或Hermite插值函數(shù)。 S3(x)在區(qū)間xi, xi+1上的表達式為 4.5.2 分段三次插值31111(

44、)( )( )( )( )iiiiiiiiSxyxyxyxyx滿足 Si(xi)=yi, Si(xi+1)=yi+1, 3( )iiSxy311()iiSxy4.5.2 分段三次插值由 Si(xi)=yi 得31111( )( )( )( )( )iiiiiiiiiiiiiiSxxyxyxyxyyai(x)ai+1(x)bi(x)bi+1(x)f(xi)f(xi+1)f(1)(xi)f(1)(xi+1)4.5.2 分段三次插值由 Si(xi)=yi 得31111( )( )( )( )( )iiiiiiiiiiiiiiSxxyxyxyxyyai(x)ai+1(x)bi(x)bi+1(x)f(x

45、i)1000f(xi+1)f(1)(xi)f(1)(xi+1)4.5.2 分段三次插值由 Si(xi+1)=yi+1 得ai(x)ai+1(x)bi(x)bi+1(x)f(xi)1000f(xi+1)f(1)(xi)f(1)(xi+1)31111111111()()()()()iiiiiiiiiiiiiiSxyxxyxyxyy4.5.2 分段三次插值由 Si(xi+1)=yi+1 得ai(x)ai+1(x)bi(x)bi+1(x)f(xi)1000f(xi+1)0100f(1)(xi)f(1)(xi+1)31111111111()()()()()iiiiiiiiiiiiiiSxyxxyxyxy

46、y4.5.2 分段三次插值ai(x)ai+1(x)bi(x)bi+1(x)f(xi)1000f(xi+1)0100f(1)(xi)f(1)(xi+1)由 得3( )iiSxy31111( )( )( )( )( )iiiiiiiiiiiiiiSxyxyxyyxyx4.5.2 分段三次插值ai(x)ai+1(x)bi(x)bi+1(x)f(xi)1000f(xi+1)0100f(1)(xi)0010f(1)(xi+1)由 得3( )iiSxy31111( )( )( )( )( )iiiiiiiiiiiiiiSxyxyxyyxyx4.5.2 分段三次插值ai(x)ai+1(x)bi(x)bi+1

47、(x)f(xi)1000f(xi+1)0100f(1)(xi)0010f(1)(xi+1)由 得311()iiSx)()()()()iiiiiiiiiiiiiiSxyxyxyxyyx 4.5.2 分段三次插值ai(x)ai+1(x)bi(x)bi+1(x)f(xi)1000f(xi+1)0100f(1)(xi)0010f(1)(xi+1)0001由 得311()iiSx)()()()()iiiiiiiiiiiiiiSxyxyxyxyyx 4.5.2 分段三次插值4.5.2 分段三次插值由此可以求出 11( ),( ),( ),( )iiiix

48、xxx例如求 ( )ix由于 11()()0iiiixx可知xi+1是 的兩重零點，又 最高三次，可設(shè)其形式為 ( )ix( )ix21( )()()iixaxb xx利用 可以確定系數(shù) ( )1iix( )0iix4.5.2 分段三次插值得到 2111( )(12)()iiiiiiixxxxxxxxx于是 211111(12)() , ,( )0, , , iiiiiiiiiiixxxxxx xxxxxxxx xxa b且4.5.2 分段三次插值同樣可得21111()() , ,( )0, , , iiiiiiiiixxxxxx xxxxxx xxa b且4.5.2 分段三次插值211111

49、1(12)() , ,( )0, , , iiiiiiiiiiixxxxxx xxxxxxxx xxa b且211111()() , ,( )0, , , iiiiiiiiixxxxxx xxxxxx xxa b且4.5.2 分段三次插值4.5.2 分段三次插值于是 時，由1,iixxx2111111(12)() ,( )0, , kkkkkkkkkkkxxxxxxxxxxxxxxxxa b且1ki 211111(12)() ,( )0, , iiiiiiiiiiixxxxxxxxxxxxxxxxa b且4.5.2 分段三次插值由211111()() ,( )0, , kkkkkkkkkxxx

50、xxxxxxxxxxxa b且1ki 21111()() ,( )0, , iiiiiiiiixxxxxxxxxxxxxxa b且4.5.2 分段三次插值30( )( )( ), , niiiiiSxyxyxxa b 例:設(shè) ，在1,4中構(gòu)造 三次Hermite插值多項式.4.5.2 分段三次插值( )f xx解:01011,4,11,42xxyy1( )2fxx(1)0.5,(4)0.25,ff4.5.2 分段三次插值201( )(12 )(4)27xx x201( )(1)(4)9xxx211( )(112 )(1)27xx x211( )(4)(1)9xxx2232212( )(12 )

51、(4)(11 2 )(1)272711(1)(4)(4)(1)1836Hxx xx xxxxx4 插值方法4.6 三次樣條插值4.6.1 問題的提出4.6 三次樣條插值 在分段多項式插值中，分段線性插值函數(shù)在節(jié)點處連續(xù)，但不可導(dǎo)，分段三次Hermite插值多項式在節(jié)點處有連續(xù)一階導(dǎo)數(shù)，但是這種連續(xù)一階導(dǎo)數(shù)的光滑程度有時并不能滿足實際問題要求，例如，有時我們需要插值函數(shù)的曲率連續(xù)，這就要求二階導(dǎo)數(shù)連續(xù)。 4.6.1 問題的提出 飛機外形的理論模線，船體放樣型值線通常要求二階光滑，即具有連續(xù)二階導(dǎo)數(shù)，最初工程師在繪制這類線型構(gòu)件的外形輪廓時，使用一種叫“樣條”(spline)的繪圖工具，這個工具是

52、具有彈性的細木條或有機玻璃條，使它逐個通過所繪的數(shù)據(jù)點，在這些數(shù)據(jù)點處分別用壓鐵壓住，在其它地方讓其自然彎曲，沿這樣的樣條壓出來的曲線叫樣條曲線。 4.6.1 問題的提出 如果把樣條看作彈性細梁，壓鐵看作作用在梁上的集中載荷，則樣條曲線在力學(xué)上可當作細彈性梁在集中載荷作用下的彎曲變形曲線。設(shè)曲線方程為y=y(x),則由材料力學(xué)知y=y(x)在整體上具有二階連續(xù)導(dǎo)數(shù)，在每一個小段(即相鄰兩壓鐵之間)上是三次多項式。這就是樣條插值的一個工程背景。 4.6.1 問題的提出4.6.2 三次樣條插值的定義4.6 三次樣條插值v 定義：給定區(qū)間a,b的一個劃分a=x0 x1xn=b,如果函數(shù)S(x)滿足條

53、件：(1)在整個區(qū)間a,b上具有二階連續(xù)導(dǎo)數(shù)；(2)在每個子區(qū)間xi-1, xi (i=1, 2, , n) 上是x的三次多項式。則稱S(x)是以 x0, x1,xn,為節(jié)點的三次樣條函數(shù)。4.6.2 三次樣條插值定義 如果給定函數(shù)y=f(x)在xi點的值為yi, (i= 0, 1, n),而S(x)滿足S(xi)=yi, (i=0,1,n),則稱S(x)為f(x)的三次樣條插值函數(shù)。 要確定S(x)在每個區(qū)間上的三次多項式，S(x)=a0+a1x+a2x2+a3x3共需要確定4n個待定系數(shù)，由S(xi)=yi,(i=0,1,n)可有n+1個條件，由S(x)在整個區(qū)間上具有連續(xù)二階導(dǎo)數(shù)知在內(nèi)部

54、節(jié)點xi (i=1,n-1)處，S(x),S(x),S(x)連續(xù), 這樣又有3(n-1)個條件，所以共有n+1+3(n-1)=4n-2個條件。 4.6.2 三次樣條插值定義還差2個條件。 為了唯一確定4n個待定系數(shù)，需要在a,b端點補充兩個邊界條件，即端點條件。常見的邊界條件有：4.6.2 三次樣條插值定義 第一種邊界條件：在端點x0,xn,處給定一階導(dǎo)數(shù)的值，即給定端點的轉(zhuǎn)角，S(x0)=m0, S(xn)=mn 第二種邊界條件：給定端點x0,xn處的二階導(dǎo)數(shù)值, 即給出了端點處的曲率或彎矩, S(x0)=M0, S(xn)=Mn 特別地，當S(x0)= S(xn)=0時為簡支情況，稱為自然

55、邊界條件；否則，稱為固支邊界。 4.6.2 三次樣條插值定義4.6.3 三次樣條插值函數(shù)的構(gòu)造 三轉(zhuǎn)角方程4.6 三次樣條插值 如何在子區(qū)間xi, xi+1, (i=1,n)上寫出三次樣條插值函數(shù)的表達式S(x)？4.6.3 三轉(zhuǎn)角方程第一種邊界條件，轉(zhuǎn)角邊界。假設(shè)已經(jīng)知道節(jié)點xi (i=0,1,n)處的一階導(dǎo)數(shù)值，即S(xi)=mi, (i=0,1,n)。可以發(fā)現(xiàn)，S(x)就是分段三次Hermite插值多項式,即 0( )( )( )niiiiiS xyxmx其中 是插值基函數(shù)：( ),( )iixx2111121111() (12),0( )() (12),0,iiiiiiiiiiiiii

56、iiixxxxxxxixxxxxxxxxxxxinxxxx其它4.6.3 三轉(zhuǎn)角方程 顯然，S(x)以及S(x)在整個區(qū)間a,b上是連續(xù)的.21112111() (),0( )() (),0,iiiiiiiiiiiiixxxxxxxixxxxxxxxxxinxx其它4.6.3 三轉(zhuǎn)角方程 S(x)在xi,xi+1上的表達式是 1111( )( )( )( )( )iiiiiiiiS xyxyxmxmx 于是 1111( )( )( )( )( )iiiiiiiiS xyxyxmxmx 驗證 11( ),()iiiiS xmS xm4.6.3 三轉(zhuǎn)角方程進一步有111111122113( )(

57、)( )( )( )6246426(2 )()iiiiiiiiiiiiiiiiiiiiiSxyxyxmxmxxxxxxxmmhhxxxyyh 其中 hi=xi+1-xi4.6.3 三轉(zhuǎn)角方程于是得112426( )()iiiiiiiiSxmmyyhhh 同理可得S(x)在區(qū)間xi-1,xi上的表達式111111122111121( )( )( )( )( )6246426(2 )()iiiiiiiiiiiiiiiiiiiiiSxyxyxmxmxxxxxxxmmhhxxxyyh其中 hi-1=xi-xi-1 4.6.3 三轉(zhuǎn)角方程所以有112111246( )()iiiiiiiiSxmmyyhh

58、h由 得( )( )iiSxSx11112211111112()3(),(1,2,.,1)iiiiiiiiiiiiiyyyymmmhhhhhhin11, ,iiiiiiiffyff x xh用 除兩邊，并利用111iihh4.6.3 三轉(zhuǎn)角方程上式整理為112,1,2,.,1iiiiiimmmgin其中11111,3(, ,),(1,2,.,1)iiiiiiiiiiiiiihhhhhhgf xxf x xin4.6.3 三轉(zhuǎn)角方程這是一組有n+1個未知數(shù)mi, i=0,1,n的n-1個方程。補充上邊界條件S(x0)=m0, S(xn)=mn, 則得到關(guān)于mi, i=1,2,n-1的一個方程組

59、1111022221111(1) (1)20020.002nnnnnnnmgmmgmgm 4.6.3 三轉(zhuǎn)角方程在上面方程組中，由于01012hhh11112,1,2,.,2iiiiiiiihhinhhhh 11212iniihhh所以方程組對角占優(yōu)，可以通過追趕法求解。4.6.3 三轉(zhuǎn)角方程4.6.4 三次樣條插值函數(shù)的構(gòu)造 三彎矩方程4.6 三次樣條插值假設(shè)二階導(dǎo)數(shù)值S(xi)=Mi, i=0,1,2,n來表示S(x)。 4.6.4 三彎矩方程由于S(x)在區(qū)間xi,xi+1上是三次多項式，所以S(x)在xi,xi+1上是線性函數(shù)，對Mi,Mi+1進行拉格朗日插值 11( )iiiiiix

60、xxxSxMMhh這樣得到了二階導(dǎo)數(shù)在xi,xi+1上的表達式，并且滿足S(xi)=Mi, S(xi1) =Mi1, 4.6.4 三彎矩方程4.6.4 三彎矩方程對S(x)積分兩次得到S(x) 331112()()( )66iiiiiixxxxS xMMc xchh11( )iiiiiixxxxSxMMhh4.6.4 三彎矩方程由S(xi)=yi, S(xi+1)=yi+1,定出積分常數(shù)，得332111211()()( )()666(),0,1,.,16iiiiiiiiiiiiiiiixxxxM hxxS xMMyhhhMhxxyinh對S(x)求導(dǎo)得 4.6.4 三彎矩方程221111()(