【正文】 科學(xué)和工程計(jì)算 第 4章 插值法 插值法 ? 插值法是一種古老的數(shù)學(xué)方法，早在一千多年前的隋唐時(shí)期定制 歷法 時(shí)就廣泛應(yīng)用了二次插值。劉焯將等距節(jié)點(diǎn)的二次插值應(yīng)用于天文計(jì)算。 ? 插值理論卻是在 17世紀(jì)微積分產(chǎn)生后才逐步發(fā)展起來(lái)的， Newton插值公式理論是當(dāng)時(shí)的重要成果。 ? 由于計(jì)算機(jī)的使用以及航空、造船、精密儀器的加工，插值法在理論和實(shí)踐上都得到進(jìn)一步發(fā)展，獲得了廣泛的應(yīng)用。 1. 引言 2. 拉格朗日插值 3. 均差與牛頓插值公式 4. 差分與等距節(jié)點(diǎn)插值 5. 埃爾米特插值 6. 分段低次插值 7. 三次樣條插值 插值法 且不利于在計(jì)算機(jī)上其函數(shù)形式可能很復(fù)雜對(duì)函數(shù) ,),( xf個(gè)不同的點(diǎn)上的一組在區(qū)間可以獲得量假如可以通過(guò)實(shí)驗(yàn)或測(cè)運(yùn)算1],[)(,?nbaxfbxxxxa n ?????? ?210nixfy ii ,2,1,0),( ???上的函數(shù)值能否存在一個(gè)性能優(yōu)良、便于計(jì)算的函數(shù) )( xP比如多項(xiàng)式函數(shù)一、插值問(wèn)題 niyxP ii ,2,1,0)( ???)()( xfxP 近似代替并且用(1) 這就是插值問(wèn)題 , (1)式為插值條件 , 個(gè)等分點(diǎn)上若給定如函數(shù) 5],0[,s i n ?xy ?其插值函數(shù)的圖象如圖 為插值區(qū)間稱區(qū)間 ],[ ba為插值節(jié)點(diǎn)稱點(diǎn) nix i ,2,1,0, ??則稱之為插值多項(xiàng)式為多項(xiàng)式函數(shù)如果 ,)( xP的插值函數(shù)為函數(shù)稱函數(shù) )()( xfxP0 1 2 3 01sinx的的的xy 1 2 3 1sinx的的的xyxy0 1 2 3 01sinx的的的xy)()( xPxf 和插值函數(shù)對(duì)于被插函數(shù)處的函數(shù)值必然相等在節(jié)點(diǎn) ix)()( xfxP 的值可能就會(huì)偏離但在節(jié)點(diǎn)外必然存在著誤差近似代替因此 )()( xfxP整體誤差的大小反映了插值函數(shù)的好壞 為了使插值函數(shù)更方便在計(jì)算機(jī)上運(yùn)算 ,一般插值函 數(shù)都使用代數(shù)多項(xiàng)式和有理函數(shù)。 x0 x1 x2 x3 x4 x P(x) ? f(x) Lagrange插值多項(xiàng)式 為了求得便于使用的簡(jiǎn)單的插值多項(xiàng)式 P(x), 我們先討論 n=1的情形 ? ?1 1 1, ( ) , ( )k k k k kx x y f x y f x? ? ???k假 定 已 知 區(qū) 間 端 點(diǎn) 處 的 函 數(shù) 值要求線性插值多項(xiàng)式 L1(x),使它滿足 ： 1 1 1 1( ) , ( )k k k kL x y L x y????L1(x)的幾何意義就是通過(guò)這兩點(diǎn)的直線； 11111111( ) ( ) (( ) (kkkkkkkkkkk k k kyyL x y x xxxx x x xL x y yx x x x???????? ? ????????點(diǎn) 斜 式 ）兩 點(diǎn) 式 ）由兩點(diǎn)式可以看出， L1(x)是由兩個(gè)線性函數(shù) 1111kkkk k k kx x x x yx x x x???????? k和 線 性 組 合 得 到 ， 其 系 數(shù) 分 別 為 y 及11( ) ( ) ( )k k k kx y l x y l x????1即 L也是線性插值多項(xiàng)式 1( ) 1( ) 0kkkklxlx???111( ) 0( ) 1kkkklxlx?????1( ) ( )kkl x l x?和 線 性 無(wú) 關(guān)稱為線性插值基函數(shù) 11111( ) (kk kkk k k kx x x xL x y yx x x x???????? 兩 點(diǎn) 式 ）n=2的情況，假定插值節(jié)點(diǎn)為 112, , , ( )( ) ( 1 , , 1 )k k kjjx x x xL x y j k k k??? ? ? ?2要 求 一 個(gè) 二 次 插 值 多 項(xiàng) 式 L ， 使 它 滿 足2 1 1( ) , ) , , ) , , )k k ky L x y y y??? k 1 k k + 1在 幾 何 上 就 是 通 過(guò) 三 點(diǎn) ( x ( x ( x 的 拋 物 線為了求出 L2(x)的表達(dá)式，可采用基函數(shù)方法 11k k kl l l??此 時(shí) 基 函 數(shù) ， ， 是 二 次 函 數(shù) ， 且 在 節(jié) 點(diǎn) 上 滿 足 條 件1 1 11 1 1( ) 1 ( ) 0( ) 1 ( ) 0( ) 1 ( ) 0k k k jk k k jk k k jl x l xl x l xl x l x? ? ?? ? ??????? ， 　 (j=k,k+1) ， 　 (j=k1,k+1) ， 　 (j=k1,k)1 1 1 1( ) , ( ) ( ) 0k k k k kl x l x l x? ? ? ???如 求 ： 因 為11( ) ( ) ( )k k kl x A x x x x??? ? ? ?可 以 表 示 為111111( ) 1( ) ( )kkkk k kl x Ax x x x?????? ??? ???11111( ) ( )()( ) ( )kkkkk k kx x x xlxx x x x???????????同理 1 1 111 1 1 1 1( ) ( ) ( ) ( )( ) , ( )( ) ( ) ( ) ( )k k k kkkk k k k k k k kx x x x x x x xl x l xx x x x x x x x? ? ??? ? ? ? ?? ? ? ?? ? ? ?? ? ? ?線性無(wú)關(guān)，作為二次插值基函數(shù) 得到二次插值多項(xiàng)式 2 1 1 1 12( ) ( ) ( ) ( )( ) ( 1 , , 1 )k k k k k kjjL x y l x y l x y l xL x y j k k k? ? ? ?? ? ?? ? ? ?顯 然 它 滿 足考慮通過(guò) n+1個(gè)節(jié)點(diǎn) 01 ()( ) ( 0 , 1 )njjx x x n xx y j n????nn… … 的 次 插 值 多 項(xiàng) 式 L ，要 滿 足 條 件 L? ……… ()xn如 何 構(gòu) 造 L上的一組節(jié)點(diǎn)為區(qū)間如果 ],[210 babxxxxa n ?????? ?njxln j ,2,1,0),( ??次多項(xiàng)式我們作一組??? ??? njii ijixxxx0 )()( nj ,2,1,0 ??n+1次多項(xiàng)式 )())(())(()())(())(()(11101110njjjjjjjnjjj xxxxxxxxxxxxxxxxxxxxxl?????????????????????? )(1 jn x?則 )())(())(( 1110 njjjjjjj xxxxxxxxxx ????? ?? ??)())(( 10 nxxxxxx ??? ??? )(1 xn?令)())(())(()())(())(()(11101110njjjjjjjnjjj xxxxxxxxxxxxxxxxxxxxxl???????????????????nj ,2,1,0 ??且 )(ij xl??????jiji01 nji ,2,1,0, ??線性無(wú)關(guān)顯然 )(,),(),(),( 210 xlxlxlxl n?(請(qǐng)同學(xué)們思考 ) ))(()(11jjnnxxxx??? ????從而 n ? 1 希望找到 li(x)， i = 0, …, n 使得 li(xj)=?ij ；然后令 ? ? ? n i i i n y x l x P 0 ) ( ) ( ，則顯然有 Pn(xi) = yi 。 li(x) 每個(gè) li 有 n 個(gè)根 x0 … xi … xn ? ? ? ? ? ? ? ? n j j ? i j i n i i i x x C x x x x x x C x l 0 0 ) ( ) )...( )...( ( ) ( ? ? ? ? j ? i j i i i i x x C x l ) ( 1 1 ) ( ??? ??? njij jiji xxxxxl0)()()(??? niiin yxlxL0)()(Lagrange Polynomial 與 有關(guān)，而與 無(wú)關(guān) 節(jié)點(diǎn) f 例 1: 15)2 2 5(,13)1 6 9(,12)1 4 4()( ??? fffxf 滿足已知.)175(,)( 的近似值并求插值多項(xiàng)式的二次作 fL a g r a n g exf解 : 225,169,144210 ??? xxx設(shè))(0 xl插值基函數(shù)為的二次則 L a g r a n g exf )())(())((202221xxxxxxxx?????2 0 25)225)(169( ??? xx)(1 xl))(())((210120xxxxxxxx?????1 4 00)225)(144(???? xx)(2 xl))(())((120210xxxxxxxx?????4 5 36)169)(144( ??? xx15,13,12 210 ??? yyy插值多項(xiàng)式為的二次因此 L a g r a n g exf )()()()()( 2211002 xlyxlyxlyxL ???且 )175(f )175(2L?)1 7 5(15)1 7 5(13)1 7 5(12 210 lll ???731 5 82 3 ?在例 1中 ,如果只給出兩個(gè)節(jié)點(diǎn) 169和 225,也可以作插值 多項(xiàng)式 ,即 1次 Lagrange插值多項(xiàng)式 ,有兩個(gè)插值基函數(shù) , 這種插值方法稱為 Lagrange線性插值 ,也可以在 n+1個(gè) 節(jié)點(diǎn)中取相鄰的兩個(gè)節(jié)點(diǎn)作線性插值 ? 1 7 5 1 3 . 2 2 8 7 5 6 5 5 5 3 2 2 9 5 2 . . .?例 2. ).1 7 5(1 fL a g r a n g e 中的線性插值多項(xiàng)式求例用之間與在由于插值點(diǎn) 2 2 51 6 91 7 5 21 ??? xxx解 : 為插值節(jié)點(diǎn)與因此取 225169 21 ?? xx)(1 xl212xxxx???56225??? x )(2 xl121xxxx???56169?? xLagrange插值基函數(shù)為 Lagrange線性插值多項(xiàng)式為 )()()( 22111 xlyxlyxL ??562 2 513???? x561 6 915 ??? x)175(f562 2 51 7 513????5616917515 ????所以 Lagrange插值多項(xiàng)式的缺點(diǎn)： 插值基函數(shù)計(jì)算復(fù)雜 高次插值的精度不一定高 高次插值通常優(yōu)于低次插值 ? 1 7 5 1 3 . 2 2 8 7 5 6 5 5 5 3 2 2 9 5 2 . . .?但絕對(duì)不是次數(shù)越高就越好，嘿嘿 …… 三、插值余項(xiàng) Remainder 插值的從上節(jié)可知 L a g r a n g exfy )(, ????njjjn xlyxL0)()(滿足 nixfxLiin ,1,0)()( ???],[ bax ??但 )()( xfxL n ? 不會(huì)完全成立 因此 ,插值多項(xiàng)式存在著截?cái)嗾`差 ,那么我們?cè)鯓庸? 計(jì)這個(gè)截?cái)嗾`差呢？ )()(],[ xPxfba n的插值多項(xiàng)式為上假設(shè)在區(qū)間)()()( xPxfxR nn ??令 上顯然在插值節(jié)點(diǎn)為 ),1,0( nix i ??)()()( iniin xPxfxR ?? ni ,1,0,0 ???個(gè)零點(diǎn)上至少有在因此 1],[)( ?nbaxR n)()()( 1 xxKxR nn ?? ?設(shè) )())(()( 101 nn xxxxxxx ????? ?? 為待定函數(shù))( xK其中 )()()()()( 1 xxKxPxfxR nnn ???? ?)()()()( 1 xxKxPxf