數(shù)值分析 多項(xiàng)式插值

1、第四章第四章 數(shù)據(jù)建模數(shù)據(jù)建模第一節(jié)第一節(jié) 多項(xiàng)式插值多項(xiàng)式插值數(shù)據(jù)建模數(shù)據(jù)建模: 插值和擬合插值和擬合插值與擬合插值與擬合 插值插值 擬合擬合多項(xiàng)式插值多項(xiàng)式插值q 當(dāng)函數(shù)當(dāng)函數(shù) y = f(x) 非常復(fù)雜或未知時(shí)，在一系列節(jié)點(diǎn)非常復(fù)雜或未知時(shí)，在一系列節(jié)點(diǎn) x0 , , xn 處測(cè)得函數(shù)值處測(cè)得函數(shù)值 y0 = f(x0)， ，yn = f(xn)，由由此構(gòu)造一個(gè)此構(gòu)造一個(gè)簡(jiǎn)單易算簡(jiǎn)單易算的近似函數(shù)的近似函數(shù) g(x) f(x)，滿足條滿足條件件g(xi) = f(xi) (i = 0, n)。稱稱g(x) 為為f(x) 的的插值函數(shù)插值函數(shù)。q 最常用的插值函數(shù)是最常用的插值函數(shù)是 ?多

2、項(xiàng)式多項(xiàng)式x0 x1x2x3x4xg(x) f(x)插值區(qū)間插值區(qū)間I=min(x0,x2,xn), max,當(dāng)插值點(diǎn)當(dāng)插值點(diǎn)x I, 稱內(nèi)插稱內(nèi)插(Interpolation), 當(dāng)插值點(diǎn)當(dāng)插值點(diǎn)x I, 稱稱外推外推(Extrapolation)多項(xiàng)式插值多項(xiàng)式插值滿足條件滿足條件 p(xi) = yi (i = 0, n) （4-1）則稱則稱 p(x) 為為 f(x) 的的 n 次次插值多項(xiàng)式插值多項(xiàng)式。q 求函數(shù)求函數(shù) f(x) 的近似表達(dá)式的近似表達(dá)式 p(x) 的方法就稱為的方法就稱為插值插值法法。插值區(qū)間插值區(qū)間插值節(jié)點(diǎn)插值節(jié)點(diǎn)插值條件插值條件定義定義 設(shè)設(shè) y = f(x) 在

3、區(qū)間在區(qū)間a,b 上有定義，且已知它在上有定義，且已知它在n+1個(gè)互異點(diǎn)個(gè)互異點(diǎn) 上的函數(shù)值上的函數(shù)值 y0, y1 , , yn ，若存在一個(gè)次數(shù)不超過(guò)若存在一個(gè)次數(shù)不超過(guò) n 次的多項(xiàng)式次的多項(xiàng)式01.( )nna xxpaxa 01.nxbaxx插值多項(xiàng)式的唯一性插值多項(xiàng)式的唯一性定理定理 (唯一性唯一性) 滿足滿足n+1個(gè)插值條件的個(gè)插值條件的n 次插值次插值多項(xiàng)式存在且唯一。多項(xiàng)式存在且唯一。證明：證明： 設(shè)所要構(gòu)造的插值多項(xiàng)式為：設(shè)所要構(gòu)造的插值多項(xiàng)式為： nnnxaxaxaaxP 2210)(由插值條件由插值條件 (), 0,1,niiP xyin得到如下線性代數(shù)方程組：得到如下

4、線性代數(shù)方程組：001000111101111nnnnnnnnnax ax ayax ax ayax ax ay 存在唯一性定理證明(續(xù)) 此方程組的系數(shù)行列式為此方程組的系數(shù)行列式為 nijjixx0)(范德蒙行列式范德蒙行列式 ！當(dāng)當(dāng) jixx 時(shí)時(shí)， ;, 2 , 1ninj, 2 , 1D 0， 因此，因此，P Pn n( (x) )由由a0 0, , a1 1, , , an n唯一確定。唯一確定。nnnnnnxxxxxxxxxD212110200111 插值多項(xiàng)式的唯一性插值多項(xiàng)式的唯一性定理定理 (唯一性唯一性) 滿足滿足n+1個(gè)插值條件個(gè)插值條件的的n 次插值多次插值多項(xiàng)式存在

5、且唯一。項(xiàng)式存在且唯一。注：該定理的證明過(guò)程實(shí)質(zhì)上給出了一種求插值注：該定理的證明過(guò)程實(shí)質(zhì)上給出了一種求插值多項(xiàng)式的一個(gè)方法，但此方法不適合計(jì)算機(jī)求解。多項(xiàng)式的一個(gè)方法，但此方法不適合計(jì)算機(jī)求解。我們要尋找用計(jì)算機(jī)的求解方法。我們要尋找用計(jì)算機(jī)的求解方法。插值基函數(shù)插值基函數(shù)q 令令 Pn(x)=次數(shù)不超過(guò)次數(shù)不超過(guò) n 的多項(xiàng)式的全體的多項(xiàng)式的全體，則，則Pn(x) 構(gòu)成一個(gè)構(gòu)成一個(gè) n+1 維線性空間，設(shè)其一組基為維線性空間，設(shè)其一組基為則插值多項(xiàng)式則插值多項(xiàng)式 pn(x)可以被這組基線性表出，即：可以被這組基線性表出，即：這樣就可以通過(guò)這樣就可以通過(guò)不同的基不同的基來(lái)構(gòu)造插值多項(xiàng)式來(lái)構(gòu)造

6、插值多項(xiàng)式 pn(x)項(xiàng)，這樣的方法稱為項(xiàng)，這樣的方法稱為基函數(shù)法基函數(shù)法。q 基函數(shù)法基本步驟：基函數(shù)法基本步驟： 1) 尋找特殊的基函數(shù)組（尋找特殊的基函數(shù)組（插值基函數(shù)插值基函數(shù)） 2) 確定插值多項(xiàng)式在這組基下的表示系數(shù)。確定插值多項(xiàng)式在這組基下的表示系數(shù)。01( ), ( ), ., ( )nxxx0011( )( ).( ).(nnxxp xaaax 一次一次Lagrange插值多項(xiàng)式插值多項(xiàng)式 已知函數(shù)已知函數(shù) 在點(diǎn)在點(diǎn) 上的值為上的值為 ，要求多項(xiàng)，要求多項(xiàng)式式 , ,使使 ， 。其幾何意義，就是通。其幾何意義，就是通過(guò)兩點(diǎn)過(guò)兩點(diǎn) 的一條直線，如圖所示。的一條直線，如圖所示。0

7、1,xx0011(,),(,)A xyB xy( )yf x 01,yy100()p xy 1( )yp x 111()p xy 一次一次Lagrange插值多項(xiàng)式插值多項(xiàng)式 由直線兩點(diǎn)式可知，通過(guò)由直線兩點(diǎn)式可知，通過(guò)A A, ,B B 的直線方程為的直線方程為 它也可變形為它也可變形為 1000110( )yyyyxxp xxx 10011( )( )( )xlx ylx yp01010110( ), ( )xxxxlxlxxxxx 顯然有：顯然有：00110110100111()()1, ()()0,(), (),xlxxlxp xyp xlly拉格朗日（拉格朗日（Lagrange）插值

8、）插值q 由構(gòu)造法可得由構(gòu)造法可得q 可以證明可以證明 l0(x), l1(x), , ln(x) 線性無(wú)關(guān)，即它們線性無(wú)關(guān)，即它們構(gòu)成線性空間構(gòu)成線性空間 Pn(x) 的一組基。的一組基。與與節(jié)點(diǎn)節(jié)點(diǎn)有關(guān)，有關(guān)， 但與但與f(x)無(wú)關(guān)無(wú)關(guān).則稱則稱 lk(x)為節(jié)點(diǎn)為節(jié)點(diǎn) x0 , , xn 上的上的拉格朗日插值基函數(shù)拉格朗日插值基函數(shù)。定義定義 若存在一個(gè)次數(shù)為若存在一個(gè)次數(shù)為 n 的多項(xiàng)式的多項(xiàng)式lk(x)，在在n+1個(gè)節(jié)點(diǎn)個(gè)節(jié)點(diǎn) x0 , , xn 上滿足：上滿足：1, 0,) (kikiilxkki Lagrange插值插值q 設(shè)設(shè) f(x) 的的 n 次次插值多項(xiàng)式插值多項(xiàng)式為為將

9、將 x0 , , xn 分別代入即可得：分別代入即可得： ai = yi (i = 0, n) 滿足插值條件：滿足插值條件： p(xi) = yi (i = 0, n) 所以所以稱為稱為拉格朗日插值多項(xiàng)式拉格朗日插值多項(xiàng)式，記作，記作 Ln(x)，即，即線性插值與拋物插值線性插值與拋物插值q 當(dāng)當(dāng) n =1 時(shí)時(shí)線性插值多項(xiàng)式（一次插值多項(xiàng)式）線性插值多項(xiàng)式（一次插值多項(xiàng)式）q 當(dāng)當(dāng) n =2 時(shí)時(shí)拋物拋物(線線)插值多項(xiàng)式（二次插值多項(xiàng)式）插值多項(xiàng)式（二次插值多項(xiàng)式）插值舉例插值舉例q 例：已知函數(shù)例：已知函數(shù) y = lnx 的函數(shù)值如下的函數(shù)值如下解：解：在插值計(jì)算中，為了減小截?cái)嗾`差，

10、通常選取與在插值計(jì)算中，為了減小截?cái)嗾`差，通常選取與插值點(diǎn)插值點(diǎn) x 鄰接的插值節(jié)點(diǎn)。鄰接的插值節(jié)點(diǎn)。x1011121314lnx2.3026 2.3979 2.4849 2.5649 2.6391試分別用線性插值和拋物插值計(jì)算試分別用線性插值和拋物插值計(jì)算 ln11.75的近似值。的近似值。線性插值線性插值：?。喝?x0=11, x1=12 得得0110101100.087(1)()( )(440).9()xxxxxyyxxxxxL 插值舉例插值舉例拋物插值拋物插值：?。喝?x0=11, x1=12, x2=13 。將將 x=11.75 代入可得：代入可得：可以計(jì)算出可以計(jì)算出 ln11.7

11、5 的近似值為：的近似值為：可見(jiàn)，拋物插值的精度比線性插值要高?？梢?jiàn)，拋物插值的精度比線性插值要高。Lagrange插值多項(xiàng)式簡(jiǎn)單方便插值多項(xiàng)式簡(jiǎn)單方便, , 只要取定節(jié)點(diǎn)就可寫(xiě)只要取定節(jié)點(diǎn)就可寫(xiě)出基函數(shù)出基函數(shù), ,進(jìn)而得到插值多項(xiàng)式。易于計(jì)算機(jī)實(shí)現(xiàn)。進(jìn)而得到插值多項(xiàng)式。易于計(jì)算機(jī)實(shí)現(xiàn)。將將 x=11.75 代入可得：代入可得：插值余項(xiàng)插值余項(xiàng)由插值條件可知：由插值條件可知：Rn(xi)=0, i=0,1, , n ，即，即Rn(x) 在在a,b上至少有上至少有 n+1 個(gè)零點(diǎn)個(gè)零點(diǎn) 如何估計(jì)用如何估計(jì)用 Ln(x) 近似近似 f(x) 的誤差？的誤差？問(wèn)問(wèn) 題題插值余項(xiàng)插值余項(xiàng))()()(

12、xLxfxRnn 作輔助函數(shù)作輔助函數(shù)這里把這里把 x 看作一個(gè)固定點(diǎn)，且看作一個(gè)固定點(diǎn)，且 ，則，則有有 n+2 個(gè)不同的零點(diǎn)：個(gè)不同的零點(diǎn)：x, x0 , , xn 。羅爾羅爾定理定理插值余項(xiàng)插值余項(xiàng)由由Rolle定理定理可知可知 有有 n+1 個(gè)不同的零點(diǎn)。個(gè)不同的零點(diǎn)。同理可知同理可知 有有 n 個(gè)零點(diǎn)，個(gè)零點(diǎn)，最后可以推出在，最后可以推出在(a,b)內(nèi)內(nèi)至少存在一點(diǎn)至少存在一點(diǎn) ，使得，使得 ，即，即 , baCfn 設(shè)設(shè) f 滿足條件滿足條件 ，且，且 f(n+1) 在在 a , b 內(nèi)存在。內(nèi)存在。又又Ln是是n次多項(xiàng)式次多項(xiàng)式是是 n+1 次多項(xiàng)式次多項(xiàng)式所以所以插值余項(xiàng)插值余

13、項(xiàng)即得即得 n 次插值多項(xiàng)式的次插值多項(xiàng)式的余項(xiàng)余項(xiàng) niixnnxxnfxR0) 1()(! ) 1()()( 且依賴于且依賴于x 。當(dāng)當(dāng) f(x) 為任一個(gè)次數(shù)為任一個(gè)次數(shù) n 的多項(xiàng)式時(shí)，的多項(xiàng)式時(shí)， , 可知可知 ，即，即 經(jīng)過(guò)經(jīng)過(guò)n+1個(gè)節(jié)點(diǎn)的個(gè)節(jié)點(diǎn)的n 次插值多項(xiàng)式次插值多項(xiàng)式對(duì)于次數(shù)對(duì)于次數(shù) n 的的多項(xiàng)式是多項(xiàng)式是精確精確的。的。0)()1( xfn0)( xRn注注計(jì)算插值點(diǎn)計(jì)算插值點(diǎn) x 上的近似值時(shí)上的近似值時(shí),應(yīng)選取與應(yīng)選取與 x 相近插值節(jié)點(diǎn)相近插值節(jié)點(diǎn). 通常通常 x 無(wú)法確定無(wú)法確定, 但可以估計(jì)但可以估計(jì) , x (a,b)將將 作為作為 誤差估計(jì)上限誤差估計(jì)上

14、限。1)1()( nnMxf niinxxnM01|)!1(|( )( )|nf xLx 插值誤差舉例插值誤差舉例q 例：已知函數(shù)例：已知函數(shù) y = lnx 的函數(shù)值如下的函數(shù)值如下解：解：x1011121314lnx2.3026 2.3979 2.4849 2.5649 2.6391試給出線性插值和拋物插值計(jì)算試給出線性插值和拋物插值計(jì)算 ln11.75的誤差。的誤差。線性插值的誤差線性插值的誤差101232( )(11.75)(11.75)21)(11.75)1121010|(11.75(11.7511120.774790.5,Rfxx 有有1+2=3位有效數(shù)字位有效數(shù)字.10101(

15、)( )()(), (,)2!fxxxxxxxR 20111, 12, (11,12( )1/, )xfxxx 又又且且插值誤差舉例插值誤差舉例高次插值通常優(yōu)于低次插值高次插值通常優(yōu)于低次插值拋物插值的誤差拋物插值的誤差23542(11.75)(11.75)(1|(11.75111213 1.75)1161010.586960.5,0R 有有1+4=5位有效數(shù)字位有效數(shù)字.321|0.774790.5,(11.75)1010R 但絕對(duì)不是次數(shù)越高就越好但絕對(duì)不是次數(shù)越高就越好有有1+2=3位有效數(shù)字位有效數(shù)字.(3)101202( )( )()()(), (,)3!fxxxxxRxxxx (3

16、)3( )2/, (11,13)fxx 又又(3)33( )2/2/11fHermite插值插值 具有節(jié)點(diǎn)的導(dǎo)函數(shù)值約束的插值具有節(jié)點(diǎn)的導(dǎo)函數(shù)值約束的插值 已知已知求不超過(guò)求不超過(guò)3次多項(xiàng)式次多項(xiàng)式H3(x)使?jié)M足使?jié)M足n存在唯一性存在唯一性n計(jì)算公式計(jì)算公式n余項(xiàng)公式余項(xiàng)公式(截?cái)嗾`差截?cái)嗾`差)00110011(),(),(),()yf xyf xyfxyfx300311300311(),(),(),()HxyHxy HxyHxy存在唯一性存在唯一性2330123( )Hxaa xa xa x2301020300230112131121203002121311 23 23aa xa xa x

17、yaa xa xa xyaa xa xyaa xa xy 230002341111020021111()001230123xxxxxxxxxxxx 導(dǎo)出計(jì)算公式導(dǎo)出計(jì)算公式 (基函數(shù)法基函數(shù)法)300110011 ( )( )( )( )( )( ),Hxg tytythythyt設(shè)設(shè)333( )( )( ) ( )( ), dHxdHxdg tdtg tHxhdxdxdtdx令令則則0011001100110011(0)1(0)0(0)0(0)0(1)0(1)0(1)1(1)0, , , (0)0(0)1(0)0(0)0(1)0(1)0(1)0(1)1其中其中基函數(shù)基函數(shù) 均為均為3次多項(xiàng)式，且滿足次多項(xiàng)式，且滿足:0101( ),( ),( ),( )tttt300311), (1)(0)(,)gHxHyxgy 310310), (1)(0)(,hghghHxyHxyh 插值條件變?yōu)椴逯禇l件變?yōu)?01001, , , 0,1xxthxxxhxxt 變變量量代代換換321323202212( )( 23)23 ,( )(1)2, ( )(1)ttttttt ttttttttt 300110011( )( )( )( )( )Hxytythythyt從而從而Hermite 插值公式為：插值公式