第2章_插值法

1、第第2 2章章 插值法插值法2.12.1 引言引言2.22.2 拉格朗日插值拉格朗日插值2.32.3 均差與牛頓插值多項(xiàng)式均差與牛頓插值多項(xiàng)式2.42.4 埃爾米特插值埃爾米特插值2.52.5 分段低次插值分段低次插值2.62.6 三次樣條插值三次樣條插值o插值法是一種古老的數(shù)學(xué)方法，早在一千多年插值法是一種古老的數(shù)學(xué)方法，早在一千多年前的隋唐時期定制前的隋唐時期定制歷法歷法時就廣泛應(yīng)用了二次插時就廣泛應(yīng)用了二次插值。劉焯將等距節(jié)點(diǎn)的二次插值應(yīng)用于天文計(jì)值。劉焯將等距節(jié)點(diǎn)的二次插值應(yīng)用于天文計(jì)算。算。o插值理論卻是在插值理論卻是在1717世紀(jì)微積分產(chǎn)生后才逐步發(fā)世紀(jì)微積分產(chǎn)生后才逐步發(fā)展起來的

2、，展起來的，NewtonNewton插值公式理論是當(dāng)時的重要插值公式理論是當(dāng)時的重要成果。成果。o由于計(jì)算機(jī)的使用以及航空、造船、精密儀器由于計(jì)算機(jī)的使用以及航空、造船、精密儀器的加工，插值法在理論和實(shí)踐上都得到進(jìn)一步的加工，插值法在理論和實(shí)踐上都得到進(jìn)一步發(fā)展，獲得了廣泛的應(yīng)用。發(fā)展，獲得了廣泛的應(yīng)用。當(dāng)精確函數(shù)當(dāng)精確函數(shù) y = f(x) 非常復(fù)雜或未知時，在一非常復(fù)雜或未知時，在一系列節(jié)點(diǎn)系列節(jié)點(diǎn) x0 xn 處測得函數(shù)值處測得函數(shù)值 y0 = f(x0), yn = f(xn)，由此構(gòu)造一個簡單易算的近似函，由此構(gòu)造一個簡單易算的近似函數(shù)數(shù) P(x) f(x)，滿足條件，滿足條件P(x

3、i) = f(xi) (i = 0, n)。這里的。這里的 P(x) 稱為稱為f(x) 的的插值函數(shù)插值函數(shù)。最常。最常用的插值函數(shù)是用的插值函數(shù)是 ?多項(xiàng)式多項(xiàng)式x0 x1x2x3x4xP(x) f(x)插值問題插值問題上的代數(shù)插值多項(xiàng)式為在區(qū)間設(shè)函數(shù),)(baxfy nnnxaxaxaaxP2210)(且滿足且滿足niyxPiin,2 , 1 ,0)(滿足這種條件的滿足這種條件的n次插值多項(xiàng)式是否唯一？次插值多項(xiàng)式是否唯一？唯一的！唯一的！滿足線性方程組的系數(shù)即多項(xiàng)式nnaaaaxP,)(21000202010yxaxaxaann11212110yxaxaxaannnnnnnnyxaxax

4、aa2210上述方程組的系數(shù)行列式為上述方程組的系數(shù)行列式為n+1n+1階范德蒙行列式階范德蒙行列式nnnnnnxxxxxxxxxV212110200111101)(ninijijxxjixx 0由由CramerCramer法則法則, ,線性方程組線性方程組(2)(2)有唯一解有唯一解唯一解唯一解定理定理1.1. nnnxaxaxaaxP2210)(niyxPiin,2 , 1 ,0)(),(jixxji若插值節(jié)點(diǎn)則滿足插值條件則滿足插值條件的插值多項(xiàng)式的插值多項(xiàng)式存在且唯一存在且唯一.反證：若不唯一，則除了反證：若不唯一，則除了Pn(x) 外還有另一外還有另一 n 階多項(xiàng)階多項(xiàng)式式 Ln(x

5、) 滿足滿足 Ln(xi) = yi 。考察考察 則則 Qn 的階數(shù)的階數(shù), )()()(xLxPxQnnn n而而 Qn 有有 個不同的根個不同的根n + 1x0 xn注：注：若不將多項(xiàng)式次數(shù)限制為若不將多項(xiàng)式次數(shù)限制為 n ，則插值多項(xiàng)式，則插值多項(xiàng)式不唯一不唯一。例如例如 也是一個插值也是一個插值多項(xiàng)式，其中多項(xiàng)式，其中 可以是任意多項(xiàng)式?？梢允侨我舛囗?xiàng)式。 niinxxxpxLxP0)()()()()(xp為了求得便于使用的簡單的插值多項(xiàng)式為了求得便于使用的簡單的插值多項(xiàng)式P(x),我們先討論我們先討論n=1的情形的情形111,(),()kkkkkxxyf xyf xk假定已知區(qū)間端點(diǎn)

6、處的函數(shù)值要求線性插值多項(xiàng)式要求線性插值多項(xiàng)式L1(x),使它滿足使它滿足：1111(),()kkkkL xyL xyL1(x)的幾何意義就是通過這兩點(diǎn)的直線；的幾何意義就是通過這兩點(diǎn)的直線；11111111( )()( )(kkkkkkkkkkkkkkyyL xyxxxxxxxxL xyyxxxx點(diǎn)斜式）兩點(diǎn)式）yx由兩點(diǎn)式可以看出，由兩點(diǎn)式可以看出， L L1 1(x)(x)是由兩個線性函數(shù)是由兩個線性函數(shù)1111kkkkkkkxxxxyxxxxk和線性組合得到，其系數(shù)分別為y 及11( )( )( )k kkkxy lxylx1即L也是線性插值多項(xiàng)式也是線性插值多項(xiàng)式1() 1()0kk

7、kkl xlx111()0()1kkkkl xlx1( )( )kklxlx和線性無關(guān)稱為線性插值基函數(shù)稱為線性插值基函數(shù)11111( )(kkkkkkkkxxxxL xyyxxxx兩點(diǎn)式）n=2的情況，假定插值節(jié)點(diǎn)為的情況，假定插值節(jié)點(diǎn)為112,( )()(1, ,1)kkkjjxxxxL xyjkk k2要求一個二次插值多項(xiàng)式L，使它滿足211( ),),),)kkkyL xyyyk-1kk+1在幾何上就是通過三點(diǎn)(x(x(x的拋物線為了求出為了求出L L2 2(x)(x)的表達(dá)式，可采用基函數(shù)方法的表達(dá)式，可采用基函數(shù)方法11kkklll此時基函數(shù) ， ，是二次函數(shù)，且在節(jié)點(diǎn)上滿足條件1

8、11111()1()0()1()0()1()0kkkjkkkjkkkjlxlxlxlxlxlx ， (j=k,k+1) ， (j=k-1,k+1) ， (j=k-1,k)1111( ),()()0kkkkklxlxlx如求：因?yàn)?1( )()()kkklxA xxxx可以表示為111111()1()()kkkkkklxAxxxx 11111()()( )()()kkkkkkkxxxxlxxxxx同理同理111111111()()()()( ),( )()()()()kkkkkkkkkkkkkkxxxxxxxxlxlxxxxxxxxx線性無關(guān)，作為二次插值基函數(shù)線性無關(guān)，作為二次插值基函數(shù)得到二

9、次插值多項(xiàng)式得到二次插值多項(xiàng)式211112( )( )( )( )()(1, ,1)kkk kkkjjL xylxy lxylxL xyjkk k顯然它滿足例1:15)225(,13)169(,12)144()(fffxf滿足已知.)175(,)(的近似值并求插值多項(xiàng)式的二次作fLagrangexf解:225,169,144210 xxx設(shè))(0 xl插值基函數(shù)為的二次則Lagrangexf)()()(201021xxxxxxxx2025)225)(169(xx)(1xl)()(210120 xxxxxxxx1400)225)(144(xx)(2xl)()(120210 xxxxxxxx453

10、6)169)(144(xx15,13,12210yyy插值多項(xiàng)式為的二次因此Lagrangexf)()()()()(2211002xlyxlyxlyxL且)175(f)175(2L)175(15)175(13)175(12210lll73158230.13在例在例1中中,如果只給出兩個節(jié)點(diǎn)如果只給出兩個節(jié)點(diǎn)169和和225,也可以作插值也可以作插值多項(xiàng)式多項(xiàng)式,即即1次次Lagrange插值多項(xiàng)式插值多項(xiàng)式,有兩個插值基函數(shù)有兩個插值基函數(shù),這種插值方法稱為這種插值方法稱為Lagrange線性插值線性插值,也可以在也可以在n+1個個節(jié)點(diǎn)中取相鄰的兩個節(jié)點(diǎn)作線性插值節(jié)點(diǎn)中取相鄰的兩個節(jié)點(diǎn)作線性插

11、值17513.228756555322952.例2.).175(1fLagrange中的線性插值多項(xiàng)式求例用之間與在由于插值點(diǎn)22516917521xxx解:為插值節(jié)點(diǎn)與因此取22516921xx)(1xl212xxxx56225x)(2xl121xxxx56169xLagrange插值基函數(shù)為Lagrange線性插值多項(xiàng)式為)()()(22111xlyxlyxL5622513x5616915x)175(f5622517513561691751571285214.13所以所以17513.228756555322952.考慮通過n+1個節(jié)點(diǎn)01( )()(0,1)njjxxxnxxyjnnn 的

12、 次插值多項(xiàng)式L，要滿足條件L( )xn如何構(gòu)造Ln 1希望找到希望找到li(x)，i = 0, , n 使得使得 li(xj)= ij ；然后令；然后令 niiinyxlxP0)()(，則顯然有，則顯然有Pn(xi) = yi 。li(x)每個每個 li 有有 n 個根個根 x0 xi xn njj i jiniiixxCxxxxxxCxl00)().().()( j i jiiiixxCxl)(11)( njijjijixxxxxl0)()()( niiinyxlxL0)()(Lagrange Polynomial與與 有關(guān)，而與有關(guān)，而與 無關(guān)無關(guān)節(jié)點(diǎn)節(jié)點(diǎn)f插值余項(xiàng)插值余項(xiàng)Remaind

13、er插值的從上節(jié)可知Lagrangexfy)(,滿足nixfxLiin, 1 , 0)()(,bax但)()(xfxLn不會完全成立不會完全成立因此因此, ,插值多項(xiàng)式存在著截斷誤差插值多項(xiàng)式存在著截斷誤差, ,那么我們怎樣估那么我們怎樣估計(jì)這個截斷誤差呢？計(jì)這個截斷誤差呢？niiinxlyL0)()()(,xPxfban的插值多項(xiàng)式為上假設(shè)在區(qū)間)()()(xPxfxRnn令上顯然在插值節(jié)點(diǎn)為), 1 , 0(nixi)()()(iniinxPxfxRni, 1 , 0,0個零點(diǎn)上至少有在因此1,)(nbaxRn)()()(1xxKxRnn設(shè))()()(101nnxxxxxxx為待定函數(shù))(

14、xK其中)()()()()(1xxKxPxfxRnnn)()()()(1xxKxPxfnn0)()()()()(1txKtPtftnn若引入輔助函數(shù))(x則有0的區(qū)分與注意xt)(ix且)()()(1ininxxKxR0即個零點(diǎn)上至少有在區(qū)間若令因此,2,)(,nbatxxi,0)(xni, 1 , 0nixi, 2 , 1 , 0,0)(也可微則可微因此若為多項(xiàng)式和由于)(,)(,)()(1txfxxPnn)()()()(1xxKxPxfnn)()()()(1ininixxKxPxf近似函數(shù)近似函數(shù)誤差誤差根據(jù)根據(jù)RolleRolle定理定理, ,個零點(diǎn)上有至少在區(qū)間1),()(nbat再由

15、再由RolleRolle定理定理, ,個零點(diǎn)上有至少在區(qū)間nbat),()( 依此類推階導(dǎo)數(shù)為零的使得內(nèi)至少有一個點(diǎn)在區(qū)間1)(,),(ntba0)()1(n)()1(tn)()()()()(1txKtPtftnn)()()()()1(1)1()1(txKtPtfnnnnn由于)()()()()()1(1)1()1()1(nnnnnnxKPf因此)!1()()()1(nxKfn0( )( )tt在的兩個零點(diǎn)間至少有一個零點(diǎn))!1()()()1(nfxKn)()()(1xxKxRnn)()!1()(1)1(xnfnn所以)()()(截斷誤差的余項(xiàng)為插值多項(xiàng)式稱xPxRnn定理定理2 2.有則插值

16、節(jié)點(diǎn)為次插值多項(xiàng)式上的在為階可微上在區(qū)間設(shè),)()(,1,)(0baxbaxnbaxfxPnbaxfniin)(xRn)()!1()(1)1(xnfnn,)()(01niinxxx其中.,),(xba且依賴于Lagrange型余項(xiàng)1n 時線性插值余項(xiàng)為 12010111( )( )( )( )()(),22R xfxfxxxxxx 2012021( )( )()()(),6R xfxxxxxxxx2n 時線性插值余項(xiàng)為注：注： 通常不能確定通常不能確定 x , 而是估計(jì)而是估計(jì) , x (a,b) 將將 作為誤差估計(jì)上限。作為誤差估計(jì)上限。1)1()( nnMxf niinxxnM01|)!1

17、(當(dāng)當(dāng) f(x) 為任一個次數(shù)為任一個次數(shù) n 的的多項(xiàng)式多項(xiàng)式時，時， , 可知可知 ，即插值多項(xiàng)式對于次數(shù)，即插值多項(xiàng)式對于次數(shù) n 的的多項(xiàng)多項(xiàng)式是式是精確精確的。的。0)()1( xfn0)( xRn|)(|max)1(1xfMnbxan|)(|)(|011niinnxxxN設(shè)設(shè)|)(|xRn則)()!1()(1)1(xnfnn11)!1(1nnNMn例：例：已知已知233sin,214sin,216sin 分別利用分別利用 sin x 的的1次、次、2次次 Lagrange 插值計(jì)算插值計(jì)算 sin 50 并估計(jì)誤差。并估計(jì)誤差。 解：解：0 x1x2x185500 n = 1分別利

18、用分別利用x0, x1 以及以及 x1, x2 計(jì)算計(jì)算4,610 xx利用利用216/4/6/214/6/4/)(1 xxxL這里這里)3,6(,sin)(,sin)()2( xxxfxxf而而)4)(6(!2)()(,23sin21)2(1 xxfxRxx00762. 0)185(01319. 01 Rsin 50 = 0.7660444)185(50sin10 L0.77614外推外推 /* extrapolation */ 的實(shí)際誤差的實(shí)際誤差 0.010010.010013,421 xx利用利用sin 50 0.76008, 00660. 018500538. 01 R內(nèi)插內(nèi)插 /*

19、 interpolation */ 的實(shí)際誤差的實(shí)際誤差 0.00596 0.00596內(nèi)插通常優(yōu)于外推。選擇內(nèi)插通常優(yōu)于外推。選擇要計(jì)算的要計(jì)算的 x 所在的區(qū)間的所在的區(qū)間的端點(diǎn)，插值效果較好。端點(diǎn)，插值效果較好。n = 223)()(21)()(21)()()(4363463464363646342 xxxxxxxL)185(50sin20 L0.7654323cos21;)3)(4)(6(!3cos)(2 xxxxxxR 00077. 018500044. 02 Rsin 50 = 0.76604442次插值的實(shí)際誤差次插值的實(shí)際誤差 0.00061 0.00061高次插值通常優(yōu)于高次

20、插值通常優(yōu)于低次插值低次插值但絕對不是次數(shù)越但絕對不是次數(shù)越高就越好，嘿高就越好，嘿嘿嘿例225,169,144,)(,. 1三個節(jié)點(diǎn)為若中在上節(jié)例xxf線性插值的余項(xiàng)為設(shè)LagrangexR)(1插值的余項(xiàng)為二次LagrangexR)(2解:.)175(截斷誤差近似值的線性和二次插值做試估計(jì)用fLagrangexxf21)(2341)( xxf2583)( xxf|)(|max2251692xfMx |)169(| f 41014. 1|)(|max2251443xfMx |)144(| f 61051. 1|)(|22xN|)225175)(169175(|300|)(|33xN|)225

21、175)(169175)(144175(|9300|)(|1xR22! 21NM3001014. 121421071. 1|)(|2xR33! 31NM93001051. 161631035. 2誤差更小二次插值比線性插值的用時在求從以上分析可知Lagrange175, niiinyxlxL0)()( njijjijixxxxxl0)()()(其中其中)(xRn)()!1()(1)1(xnfnn余項(xiàng)：余項(xiàng)：LagrangeLagrange插值多項(xiàng)式的缺點(diǎn)：插值多項(xiàng)式的缺點(diǎn)：插值基函數(shù)計(jì)算復(fù)雜插值基函數(shù)計(jì)算復(fù)雜高次插值的精度不一定高高次插值的精度不一定高Lagrange插值多項(xiàng)式的缺點(diǎn))(xlj

22、njiiijixxxx0)()(nj,2 , 1 ,0我們知道我們知道,Lagrange,Lagrange插值多項(xiàng)式的插值基函數(shù)為插值多項(xiàng)式的插值基函數(shù)為理論分析中很方便，理論分析中很方便，但是但是當(dāng)當(dāng)插值節(jié)點(diǎn)增減插值節(jié)點(diǎn)增減時時全部插值全部插值基函數(shù)基函數(shù)就要隨之就要隨之變化變化，整個公式也將發(fā)生變化，這在，整個公式也將發(fā)生變化，這在實(shí)際計(jì)算中是很實(shí)際計(jì)算中是很不方便不方便的；的；Lagrange 插值雖然易算，但若要增加一個節(jié)點(diǎn)時，插值雖然易算，但若要增加一個節(jié)點(diǎn)時，全部基函數(shù)全部基函數(shù) li(x) 都需重新算過。都需重新算過。解決由線性代數(shù)的知識可知由線性代數(shù)的知識可知, ,任何一個任何

23、一個n n次多項(xiàng)式都可以表示成次多項(xiàng)式都可以表示成, 1,0 xx ),)(10 xxxx)()(110nxxxxxx,共共n+1n+1個多項(xiàng)式的線性組合個多項(xiàng)式的線性組合那么，是否可以將這那么，是否可以將這n+1n+1個多項(xiàng)式作為插值基函數(shù)呢？個多項(xiàng)式作為插值基函數(shù)呢？, 1,0 xx ),)(10 xxxx)()(110nxxxxxx,顯然，多項(xiàng)式組顯然，多項(xiàng)式組線性無關(guān)，線性無關(guān)， 因此，因此，可以作為插值基函數(shù)可以作為插值基函數(shù),ix設(shè)插值節(jié)點(diǎn)為nifi, 1 , 0,函數(shù)值為1,2 , 1 ,0,1nixxhiiinifxPii, 1 , 0,)(插值條件為具有如下形式設(shè)插值多項(xiàng)式)

24、(xP01,na aa其中 為待定系數(shù)基函數(shù))()()()()(110102010nnxxxxxxaxxxxaxxaaxP)()()()()(110102010nnxxxxxxaxxxxaxxaaxPnifxPxPii, 1 , 0,)()(應(yīng)滿足插值條件000)(afxP有)()(011011xxaafxP00fa 01011xxffa)()()(12022021022xxxxaxxaafxP12010102022xxxxffxxffa再繼續(xù)下去待定系再繼續(xù)下去待定系數(shù)的形式將更復(fù)雜數(shù)的形式將更復(fù)雜 。為此引入差商和差分的概念為此引入差商和差分的概念 divided difference *

25、/),()()(,jijijijixxjixxxfxfxxf 1階差商階差商 /* the 1st divided difference of f w.r.t. xi and xj */)(,kixxxxfxxfxxxfkikjjikji 2階差商階差商定義定義2.2.nifxxfii, 1 , 0,)(處的函數(shù)值為在互異的節(jié)點(diǎn)設(shè)11101010111010,.,.,.,.,., kkkkkkkkkkkxxxxxfxxxfxxxxxfxxxfxxf(k+1)階階差差商商)()()()()()(4433221100 xfxxfxxfxxfxxfxxfxkk四階差商三階差商二階差商一階差商差商的計(jì)

26、算方法差商的計(jì)算方法( (表格法表格法):):,10 xxf,21xxf,32xxf,43xxf,210 xxxf,321xxxf,432xxxf,3210 xxxxf,4321xxxxf,410 xxxf規(guī)定函數(shù)值為規(guī)定函數(shù)值為零階差商零階差商差商表差商表例例 列出列出f(x)=x3在節(jié)點(diǎn)在節(jié)點(diǎn)x=0,2,3,5,6上的各階差商值。上的各階差商值。ix02356if x08271252161,iif x x 80420 2781932 125274953 2161259165 12 ,iiif x xx 194530 49 191052 91491463 105150 14 10162 1

27、1060 三階差商三階差商 四階差商四階差商解：解：列表計(jì)算列表計(jì)算差商具有如下性質(zhì)差商具有如下性質(zhì): :且的線性組合表示可由函數(shù)值階差商的,)(,),(),(,)()1(10110kkkxfxfxfxxxxfkxf,110kkxxxxfkikiiiiiiixxxxxxxxxf0110)()()()( Warning: my head is explodingWhat is the point of this formula?差商的值與差商的值與 xi 的順序無關(guān)！的順序無關(guān)！NewtonNewton插值公式及其余項(xiàng)插值公式及其余項(xiàng),)()()(000 xxfxxxfxf ,)(,101100

28、 xxxfxxxxfxxf ,.,)(,.,.,0010nnnnxxxfxxxxfxxxf 12 n+11+ (x x0) 2+ + (x x0)(x xn 1) n+1.)(,)(,)()(102100100 xxxxxxxfxxxxfxfxf).(,.,100 nnxxxxxxf)().(,.,100nnnxxxxxxxxxf Nn(x)Rn(x)ai = f x0, , xi NewtonNewton插值公式及其余項(xiàng)插值公式及其余項(xiàng)ix0 x1x2x3xif x0()f x1()f x2()f x3()f x1,iif x x 01,f xx12,f x x23,f xx12,iiif

29、x xx 012,f xx x123,f x xx123 ,iiiif x xxx 0123,f xx xx00100121001110( )()() ,()() ,()()() ,nnnP xf xxxf x xxxxxf xx xxxxxxxf xx x 例：例： 已知已知x=1,4,9的平方根為的平方根為1,2,3，利用牛頓基本差商，利用牛頓基本差商 公式求公式求 的近似值。的近似值。ix149ix1231,iif x x 2 10 333334 1. 320 294. 12 ,iiif x xx 0 20 333330 0166791. 7解：解：從而得二階牛頓基本差商公式為從而得二階

30、牛頓基本差商公式為210 3333310 0166714( ).().()()P xxxx 272 69992( ).P 因此計(jì)算得因此計(jì)算得 的近似值為的近似值為7性質(zhì)性質(zhì)3 3上面我們討論了節(jié)點(diǎn)任意分布的插值公式，但實(shí)際應(yīng)上面我們討論了節(jié)點(diǎn)任意分布的插值公式，但實(shí)際應(yīng)用時經(jīng)常會遇到等距節(jié)點(diǎn)的情形，這時插值公式可以用時經(jīng)常會遇到等距節(jié)點(diǎn)的情形，這時插值公式可以進(jìn)一步簡化，計(jì)算也簡單多了，為了給出等距節(jié)點(diǎn)的進(jìn)一步簡化，計(jì)算也簡單多了，為了給出等距節(jié)點(diǎn)的插值公式，我們先來看一個新概念；插值公式，我們先來看一個新概念；稱處的函數(shù)值為在等距節(jié)點(diǎn)設(shè), 1 , 0,)(0nkfkhxxxfkkkkkff

31、f1處的一階向前差分在為kxxf)(1, 1 ,0nk1kkkfff處的一階向后差分在為kxxf)(nk,2 , 11122(/ 2)(/ 2)kkkkkff xhf xhff( )kf xx為在處的中心差分不在函數(shù)表上，要用到不在函數(shù)表上，要用到函數(shù)表上的值函數(shù)表上的值111122,kkkkkkffffffkkkfff12處的二階向前差分在為kxxf)(12kkkfff處的二階向后差分在為kxxf)(利用一階差分可以定義二階差分利用一階差分可以定義二階差分差分差分kmkmkmfff111階向前差分處的在為mxxfk)(階向后差分處的在為mxxfk)(111kmkmkmfff可以用歸納法證明m

32、kmkmff1kkff222kkff333kkff如差分差分4433221100fxfxfxfxfxfxkk四階差分三階差分二階差分一階差分0f1f2f3f02f12f22f03f13f04f差分表差分表4f3f2f1f42f32f22f43f33f44f差分與函數(shù)值之間的關(guān)系差分與函數(shù)值之間的關(guān)系010121232,yyyyyyyyy 201021021213212232432222yyyyyyyyyyyyyyyyyy 2222()abaabb 1()abab 322010321032212143213222325432333333yyyyyyyyyyyyyyyyyyyyy 3223333(

33、)abaa babb 433010432104331215432143323265432464464464yyyyyyyyyyyyyyyyyyyyyyyy 4322443464()a baa ba babb 歸納可知，歸納可知，k階差商可表示為階差商可表示為 01111kii ki kiikkkkkkyyyCCyCCy 在等距節(jié)點(diǎn)的前提下在等距節(jié)點(diǎn)的前提下, ,差商與差分有如下關(guān)系差商與差分有如下關(guān)系,1iixxfhfi,21iiixxxf212hffii222hfihfi 12212hfxfii2222hfiiiiixxff112211,iiiiiixxxxfxxf,321iiiixxxxf

34、312223hffii33! 3 hfi332121,iiiiiiiixxxxxfxxxf3322223hfxfii333! 3 hfi,1miiixxxf依此類推mimhmf!mmimhmf!,10kxxxfkkhkf!0kkkhkf!即是等距節(jié)點(diǎn)如果節(jié)點(diǎn),10nxxxnabhnkkhxxk, 1 ,0,0,10kxxxfkkhkf!0由差商與向前差分的關(guān)系)(xNnnkkkxxxxff1100)(,Newton插值基本公式為如果假設(shè)thxx01.Newton向前向前(差分差分)插值公式插值公式10)(kjjxx)(xk1000)(kjjhxthx10)(kjhjtkkhkf!0nkf10)

35、(10kjhjt!0kfknkf10 )(10kjjt)(xNnnkkkxxxxff1100)(,)(0thxNn)(xRn)()!1()(1)1(xnfnn則插值公式化為其余項(xiàng))(0thxRn)!1()()1(nfnnjnjth01)(化為)(0thxRn)!1()()1(nfnnjnjth01)(!0kfknkf10 )(10kjjt)(0thxNn稱為Newton向前插值公式插值余項(xiàng)為NewtonNewton插值法的優(yōu)點(diǎn)是計(jì)算較簡單插值法的優(yōu)點(diǎn)是計(jì)算較簡單, ,尤其是增加節(jié)點(diǎn)時尤其是增加節(jié)點(diǎn)時, ,計(jì)算只要增加一項(xiàng)計(jì)算只要增加一項(xiàng), ,這點(diǎn)是這點(diǎn)是LagrangeLagrange插值無法

36、比的插值無法比的. .但是但是NewtonNewton插值仍然沒有改變插值仍然沒有改變LagrangeLagrange插值的插值曲線插值的插值曲線在節(jié)點(diǎn)處有尖點(diǎn)，不光滑，插值多項(xiàng)式在節(jié)點(diǎn)處不可導(dǎo)在節(jié)點(diǎn)處有尖點(diǎn)，不光滑，插值多項(xiàng)式在節(jié)點(diǎn)處不可導(dǎo)等缺點(diǎn)等缺點(diǎn). .,)(1010nnyyybxxxaxf處的函數(shù)值為在節(jié)點(diǎn)設(shè)值函數(shù)上的具有一階導(dǎo)數(shù)的插的在區(qū)間為設(shè),)()(baxfxP處必須滿足在節(jié)點(diǎn)顯然nxxxxP,)(10)(,)()1(一階光滑度上具有一階導(dǎo)數(shù)在若要求baxPiiiyxfxP)()(iiiyxfxP)()(ni, 1 ,0ni, 1 ,0-(1)個待定的系數(shù)可以解出22 n次的多項(xiàng)

37、式可以是最高次數(shù)為因此12)(nxP次多項(xiàng)式作為插值函數(shù)兩個節(jié)點(diǎn)就可以用311222n共個方程兩點(diǎn)三次兩點(diǎn)三次HermiteHermite插值插值例：例：設(shè)設(shè) x0 x1 x2, 已知已知 f(x0)、 f(x1)、 f(x2) 和和 f (x1), 求多項(xiàng)求多項(xiàng)式式 P(x) 滿足滿足 P(xi) = f (xi)，i = 0, 1, 2，且，且 P(x1) = f (x1), 并估計(jì)誤差。并估計(jì)誤差。模仿模仿 Newton 多項(xiàng)式的思想，設(shè)多項(xiàng)式的思想，設(shè)解：解：首先，首先，P 的階數(shù)的階數(shù) = 3),()()()()()(221033xxxxxxxKxPxfxR!4)()()4(xfxK

38、 )()( )(,)(,)()(210102100100 xxxxxxAxxxxxxxfxxxxfxfxPA為待定系數(shù)，可由為待定系數(shù)，可由P(x1) = f (x1)確定確定)(,)(,)(210121001101xxxxxxxfxxxxfxfA與與 Lagrange 分析分析完全類似完全類似應(yīng)滿足插值條件)(3xH003)(yxH113)(yxH003)(yxH113)(yxH 求求Hermite多項(xiàng)式的基本步驟：多項(xiàng)式的基本步驟： 寫出相應(yīng)于條件的、寫出相應(yīng)于條件的、 的組合形式；的組合形式；ii)()()()()(110011003xyxyxyxyxH 對每一個對每一個 找出盡可能多的

39、條件給出的根；找出盡可能多的條件給出的根；ii,其中其中1)(00 x0)(00 x1)(00 x0)(10 x0)(01x1)(11x0)(10 x0)(01x0)(11x0)(00 x0)(10 x0)(01 x0)(11 x0)(10 x0)(01 x1)(11 x 根據(jù)多項(xiàng)式的總階數(shù)和根的個數(shù)寫出表達(dá)式；根據(jù)多項(xiàng)式的總階數(shù)和根的個數(shù)寫出表達(dá)式；)()()(210baxxxx 根據(jù)尚未利用的條件解出表達(dá)式中的待定系數(shù)；根據(jù)尚未利用的條件解出表達(dá)式中的待定系數(shù)；1)(00 x0)(00 x由由可得可得310)(2xxa3100210)(2)(1xxxxxb)()()(210baxxxx21

40、)(xx 310)(2xxx3100210)(2)(1xxxxx21021)()(xxxx102xxx10021xxx01021xxxx2101xxxx)()(21(201xlxl 最后完整寫出最后完整寫出H(x)。)()()()()(110011003xyxyxyxyxH101121xxxxy2010 xxxx00 xxy2101xxxx2010 xxxx11xxy010021xxxxy2101xxxx兩點(diǎn)三次兩點(diǎn)三次HermiteHermite插值的誤差為插值的誤差為)()()(33xHxfxR0)()()(33iiixHxfxR0)()()(33iiixHxfxR1 , 0i因此可設(shè)的二

41、重零點(diǎn)均為,)(,310 xRxx21203)()()(xxxxxKxR待定其中)(xK21203)()()()()(xtxtxKtHtft構(gòu)造輔助函數(shù)0)()()()()(21203xxxxxKxHxfxiiiii0)()()()()(21203xxxxxKxHxfx均是二重根個零點(diǎn)至少有因此5)(t連續(xù)使用4次Rolle定理，可得，,10 xx至少存在一點(diǎn)使得0)()4(1 , 0i0)(! 4)()()4()4(xKf即! 4)()()4(fxK所以,兩點(diǎn)三次Hermite插值的余項(xiàng)為2120)4(3)()(! 4)()(xxxxfxR10 xx以上分析都能成立嗎？上述余項(xiàng)公式成立上存在

42、且連續(xù)時在當(dāng),)(10)4(xxxf一般的，總認(rèn)為次數(shù)越高，一般的，總認(rèn)為次數(shù)越高，逼近逼近f(x)f(x)的精度就越好，的精度就越好，但實(shí)際上并非如此。但實(shí)際上并非如此。2.5 分段低次插值分段低次插值 /* piecewise polynomial approximation */Remember what I have said? Increasing the degree of interpolating polynomial will NOT guarantee a good result, since high-degree polynomials are oscillating.

43、例：例：在在 5, 5上考察上考察 的的Ln(x)。取。取211)(xxf),., 0(105niinxi -5 -4 -3 -2 -1 0 1 2 3 4 5 -0.5 0 0.5 1 1.5 2 2.5 n 越大，越大，端點(diǎn)附近抖動端點(diǎn)附近抖動越大，稱為越大，稱為Runge 現(xiàn)象現(xiàn)象Ln(x) f (x) 分段分段低次低次插值插值-5-4-3-2-1012345-1.5-1-0.500.511.52n=2n=4n=6n=8n=10f(x)=1/(1+x2)不同次數(shù)的Lagrange插值多項(xiàng)式的比較圖Runge現(xiàn)象現(xiàn)象從上圖可以看出，隨著從上圖可以看出，隨著n n的增加，的增加，L Ln n

44、(x)(x)的計(jì)算結(jié)果和的計(jì)算結(jié)果和誤差的絕對值幾乎成倍的增加，這說明當(dāng)誤差的絕對值幾乎成倍的增加，這說明當(dāng)n n趨于無窮大趨于無窮大時，時， L Ln n(x)(x)在在-5-5，55上不收斂；上不收斂；-4-3-2-101234-1-0.8-0.6-0.4-0.200.20.40.60.81-4-3-2-101234-1-0.8-0.6-0.4-0.200.20.40.60.81-4-3-2-101234-1-0.8-0.6-0.4-0.200.20.40.60.81-4-3-2-101234-1-0.8-0.6-0.4-0.200.20.40.60.81-4-3-2-101234-1-0

45、.8-0.6-0.4-0.200.20.40.60.81的圖象分段線性插值)(1xLy 的一條折線實(shí)際上是連接點(diǎn)niyxkk, 1 , 0,),(也稱折線插值也稱折線插值, ,如右圖如右圖曲線的光滑性較差曲線的光滑性較差在節(jié)點(diǎn)處有尖點(diǎn)在節(jié)點(diǎn)處有尖點(diǎn) 但如果增加節(jié)點(diǎn)的數(shù)量但如果增加節(jié)點(diǎn)的數(shù)量減小步長減小步長, ,會改善插值效果會改善插值效果上連續(xù)在若,)(baxf因此因此)(lim10 xLh)(xf則則 分段線性插值分段線性插值 /* piecewise linear interpolation */在每個區(qū)間在每個區(qū)間 上，用上，用1階多項(xiàng)式階多項(xiàng)式 (直線直線) 逼近逼近 f (x):,1

46、 iixx11111)()( iiiiiiiiyxxxxyxxxxxPxf,for 1 iixxx記記 ，易證：當(dāng)，易證：當(dāng) 時，時，|max1iixxh 0h)()(1xfxPh一致一致失去了原函數(shù)的光滑性。失去了原函數(shù)的光滑性。 分段分段Hermite插值插值 /* Hermite piecewise polynomials */給定給定nnnyyyyxx ,.,;,.,;,.,000在在 上利用兩點(diǎn)的上利用兩點(diǎn)的 y 及及 y 構(gòu)造構(gòu)造3次次Hermite函數(shù)函數(shù),1 iixx導(dǎo)數(shù)一般不易得到。導(dǎo)數(shù)一般不易得到。How can we make a smooth interpolation

47、 without asking too much from f ?Headache 2.6 三次樣條插值三次樣條插值樣條本質(zhì)上是一段一段的樣條本質(zhì)上是一段一段的三次多項(xiàng)式三次多項(xiàng)式拼合而成的曲線拼合而成的曲線在拼接處在拼接處, ,不僅函數(shù)是連續(xù)的不僅函數(shù)是連續(xù)的, ,且一階和二階導(dǎo)數(shù)且一階和二階導(dǎo)數(shù)也是連續(xù)的也是連續(xù)的的一個分割為區(qū)間,10babxxxan:,)(上滿足條件在區(qū)間如果函數(shù)baxS,)(,)(),(),()1(2baCxSbaxSxSxS 即上連續(xù)都在區(qū)間上都是三次多項(xiàng)式在每個小區(qū)間,)()2(1kkxxxS上的三次樣條函數(shù)為區(qū)間則稱,)(baxS處的函數(shù)值為在節(jié)點(diǎn)如果函數(shù)nxx

48、xxf,)()3(10njyxfjj, 1 , 0,)(滿足而三次樣條函數(shù))(xSnjyxSjj, 1 , 0,)(上的三次樣條插值函數(shù)在為則稱,)()(baxfxS-(1)注：注：三次樣條與分段三次樣條與分段 Hermite 插值的根本區(qū)別在于插值的根本區(qū)別在于S(x)自自身光滑身光滑，不需要知道，不需要知道 f 的導(dǎo)數(shù)值（除了在的導(dǎo)數(shù)值（除了在2個端點(diǎn)可能需個端點(diǎn)可能需要）；而要）；而Hermite插值依賴于插值依賴于f 在所有插值點(diǎn)的導(dǎo)數(shù)值。在所有插值點(diǎn)的導(dǎo)數(shù)值。f(x)H(x)S(x)要求出要求出S(x)S(x)，則在每個小區(qū)間上，則在每個小區(qū)間上 要確定要確定4 4個待定系數(shù)，共有個

49、待定系數(shù)，共有n n個小區(qū)間，所以應(yīng)確定個小區(qū)間，所以應(yīng)確定4n4n個參數(shù)。個參數(shù)。1,jjxx(0)(0)(0)(0)(0)(0)jjjjjjS xS xS xS xSxSx( ) , (1,2,1)jS xa bx jn根據(jù)在上二階導(dǎo)數(shù)連續(xù) 在節(jié)點(diǎn)處就應(yīng)滿足連續(xù)性條件共共(n+1)+(3n-3)=4n-2(n+1)+(3n-3)=4n-2個條件，因此還需要兩個個條件，因此還需要兩個條件才能確定條件才能確定S(x)S(x)可在區(qū)間端點(diǎn)可在區(qū)間端點(diǎn)a,ba,b上各加一個條件（邊界條件），上各加一個條件（邊界條件），具體要根據(jù)實(shí)際問題要求給定；具體要根據(jù)實(shí)際問題要求給定；00)(fxSnnfxS

50、)(00)(fxS ()nnSxf 其特殊情況為其特殊情況為0()()0nSxSx0nxx000(0)(0)(0)(0)(0)(0)nnnS xS xS xS xSxSx0nyy且此時加上任何一類邊界條件加上任何一類邊界條件( (至少兩個至少兩個) )后后一般使用第一、二類邊界條件一般使用第一、二類邊界條件, , 常用第二類邊界條件常用第二類邊界條件即jjkyxS)()(lim)(lim1xSxSkxxkxxkk)(lim)(lim1xSxSkxxkxxkk)(lim)(lim1xSxSkxxkxxkk 1,2 , 1nknj, 1 , 01,2 , 1nk1,2 , 1nkkm00)(fxSnnfxS)(00)(fxS nnfxS )(或()(0,1, )()(0,1, )jjjjS xmjnS xyjn再由0( )( )( )njjjjjS xyxmxnj,1,0插值多項(xiàng)式上的兩點(diǎn)三次表示為將HermitexxxSkkk,)(1)(xSk)()()()()()(11)(0)(11)(0)(3xmxmxyxyxHkkkkkkkkk11121kkkkxxxxy21kkkxxxxkkxxm211kkkxxxx21kkkxxxx11kkxxmkkkkxxxxy121211kkkxxxx1, 1 ,01nkxxhkkk，令kkkkkkyxxhxxhxS213)