1、會(huì)計(jì)學(xué)1計(jì)算機(jī)如何表達(dá)函數(shù)計(jì)算機(jī)如何表達(dá)函數(shù) 實(shí)際中，f(x)多樣，復(fù)雜，通常只能觀測(cè)到一些離散數(shù)據(jù)；或者f(x)過(guò)于復(fù)雜而難以運(yùn)算。這時(shí)我們要用近似函數(shù)g(x)來(lái)逼近f(x)。 自然地，希望g(x)通過(guò)所有的離散點(diǎn)x0 x1x2x3x4xg(x) f(x)第1頁(yè)/共63頁(yè)定義： 為定義在區(qū)間 上的函數(shù)， 為區(qū)間上n+1個(gè)互不 相同的點(diǎn)， 為給定的某一函數(shù)類(lèi)。求 上的函數(shù) 滿(mǎn)足)(xfba,0niix)(xgnixfxgii, 0 , )()(l是否存在唯一l如何構(gòu)造l誤差估計(jì)第2頁(yè)/共63頁(yè)0000( )( )( )()()()()mmiiimmig xaxaxg xfxaxax設(shè)則0001

2、1000001111110011()()()()()()()()()()()()mmmmnnmmnnaxaxaxf xaxaxaxf xaxaxaxf x所以 有唯一解，當(dāng)且僅當(dāng)m=n，且系數(shù)行且系數(shù)行列式不為列式不為00 niia第3頁(yè)/共63頁(yè)定理1.1 ： 為n1個(gè)節(jié)點(diǎn)， n+1維空間，則插值函數(shù)存在唯一，當(dāng)且僅當(dāng) 0niix,10nspan0)()()()(0000nnnnxxxx第4頁(yè)/共63頁(yè)1. 與基函數(shù)無(wú)關(guān)2. 與原函數(shù)f(x)無(wú)關(guān)3. 基函數(shù)個(gè)數(shù)與點(diǎn)個(gè)數(shù)相同特點(diǎn)：特點(diǎn)：第5頁(yè)/共63頁(yè), 1)(2nnxxxspanx對(duì)應(yīng)于對(duì)應(yīng)于則則001001101nnijj i nnnnx

3、xxxxxxx Vandermonde行列式病態(tài)第6頁(yè)/共63頁(yè)在基函數(shù)上下功夫，取基函數(shù)為nniixl 0)(要求jijixlijji, 1,0)(則)()()(0iniixfxlxg第7頁(yè)/共63頁(yè)求niixl0)(，易知：)()()()(110niiiixxxxxxxxaxl)()()(1110niiiiiiixxxxxxxxa011011()()()()()()()()iiniiiiiiinxxxxxxxxlxxxxxxxx0()()nniixxx記()() ()()niniixlxxxx第8頁(yè)/共63頁(yè)l 線(xiàn)性插值01011010)( , )(xxxxxlxxxxxl)()()()(

4、)(11001xlxfxlxfxL第9頁(yè)/共63頁(yè)1200102()()( ) ()()xxxxlxxxxx2001122( )() ( )() ( )() ( )L xf x lxf x l xf x lx0211012()()( )()()xxxxl xxxxx0122021()()( )()()xxxxlxxxxx第10頁(yè)/共63頁(yè)) 3 , 3(),1 , 2(),0 , 0(),2 , 1(例：)31)(21)(01()3)(2)(0()(0 xxxxl)23)(03)(13()2)(0)(1()(3xxxxl)32)(02)(12()3)(0)(1()(2xxxxl)30)(20)

5、(10()3)(2)(1()(1xxxxl)(3)(1)(0)(2)(3210 xlxlxlxlxg第11頁(yè)/共63頁(yè)算法：fx=0.0for(i=0;i=n;i+) tmp=1.0; for(j=0;ji;j+) tmp=tmp*(x-xj)/(xi-xj); for(j=i+1;j=n;j+) tmp=tmp*(x-xj)/(xi-xj); fx=fx+tmp*yi;return fx;011011()()()()()()()()iiniiiiiiinxxxxxxxxlxxxxxxxx第12頁(yè)/共63頁(yè)21( ), 5,51f xxx 對(duì)函數(shù)構(gòu)造插值，并求55max( )( )max()(

6、) ,5,0,50050iiixiif xp xf yp yyi 為近似的誤差。插值節(jié)點(diǎn)取為：105,0,1,ixi iNN (1)215cos,0,1,22iixiNN (2)對(duì)N=5，10，20，40比較以上兩組節(jié)點(diǎn)的結(jié)果。Chebyshev點(diǎn)第13頁(yè)/共63頁(yè)Sample Output ( represents a space)第1組節(jié)點(diǎn)，誤差為n=5,0.244934066848e+001n=10,0.534607244904e+001.第2組節(jié)點(diǎn)，誤差為n=5,0.244934066848e+001n=10,0.534607244904e+001.第14頁(yè)/共63頁(yè))()()(xLx

7、fxRnn解：)()()(, 0 , 0)(, 0 , )()(0nnininixxxxxkxRnixRnixLxf求?)(xk0)( and , 0, 0)()()()()()(?)(,0anixxtxtaktLtftakainn設(shè)易知第15頁(yè)/共63頁(yè))(t有n+2個(gè)零點(diǎn))!1()()( )!1)()()( 0)( , )1()1()1()1(nfaknakfnnnn)()()!1()()(0)1(nnnxxxxnfxR由a的任意性第16頁(yè)/共63頁(yè)例：例：已知已知233sin,214sin,216sin 分別利用分別利用 sin x 的的1次、次、2次次 Lagrange 插值計(jì)算插值計(jì)

8、算 sin 50 并估計(jì)誤差。并估計(jì)誤差。 第17頁(yè)/共63頁(yè)解：解：0 x1x2x185500 n = 1分別利用分別利用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.01001

9、3,421 xx利用利用sin 50 0.76008, 00660. 018500538. 01 R內(nèi)插內(nèi)插 /* interpolation */ 的實(shí)際誤差的實(shí)際誤差 0.005960.00596內(nèi)插通常優(yōu)于外推。選擇內(nèi)插通常優(yōu)于外推。選擇要計(jì)算的要計(jì)算的 x 所在的區(qū)間的所在的區(qū)間的端點(diǎn)，插值效果較好。端點(diǎn)，插值效果較好。第18頁(yè)/共63頁(yè)n = 223)()(21)()(21)()()(4363463464363646342 xxxxxxxL)185(50sin20 L0.7654323cos21;)3)(4)(6(!3cos)(2 xxxxxxR 00077. 018500044.

10、02 Rsin 50 = 0.76604442次插值的實(shí)際誤差次插值的實(shí)際誤差 0.000610.00061高次插值通常優(yōu)高次插值通常優(yōu)于低次插值于低次插值第19頁(yè)/共63頁(yè)給定 10niix任取n+1個(gè)構(gòu)造)(xLn)( 1, 1)( , 0 xLnixLninn如：另取則)()()!1()()()()()()!1()()()(112)1(01)1(nnnnnnxxxxnfxLxfxxxxnfxLxf第20頁(yè)/共63頁(yè)近似)()(2)1(1)1(nnff則)()()()()()()()()()()( 10001010110 xLxLxxxxxLxfxLxxxxxLxxxxxfxxxxxLxf

11、xLxfnnnnnnnnnnnn第21頁(yè)/共63頁(yè) , 1 , 0),( nixli1.證明線(xiàn)性無(wú)關(guān)2.若，記kiiP,0為節(jié)點(diǎn)ikixx,0上的k次插值多項(xiàng)式試證明：jiniiinjjjnxxxPxxxPxxxL)()()()()(,1,1,1 ,0,1,1,1 ,0第22頁(yè)/共63頁(yè)無(wú)承襲性。增加一個(gè)節(jié)點(diǎn)，所有的基函數(shù)都要重新計(jì)算第23頁(yè)/共63頁(yè)為實(shí)數(shù),110nxxx,10nxxx易知1()()() , 0,niniiNxNxf xin)()()(011nnnxxxxaxq同樣)()()( 10nnnxxxxaxq)()()(1xqxNxNnnn承襲性承襲性：)()()(11xqxNxN

12、nnn1nP第24頁(yè)/共63頁(yè))()()()( 10010nnnxxxxaxxaaxN而且有：)()()()()()()()()()()()()()(1001021202202102101101000nnnnnnnnnnnxfxxxxaxxaaxNxfxxxxaxxaaxNxfxxaaxNxfaxN第25頁(yè)/共63頁(yè)這樣：)(00 xfa 01011)()(xxxfxfa10202122)()(1axxxfxfxxa30312323031()()11f xf xaaaxxxxxx第26頁(yè)/共63頁(yè)01010010110,)()(,xxxxfxxfxxfxxxfxfxxfkkkk稱(chēng)為k階差商稱(chēng)為

13、1階差商定義：差商差商第27頁(yè)/共63頁(yè)差商的一個(gè)性質(zhì)差商的一個(gè)性質(zhì)： （用歸納法易證） 對(duì)稱(chēng)性：,00kiikxxfxxf定義關(guān)鍵：找不同的元素相減作分母的任意排列是kiik,0,0?3213103210,xxxxxfxxxfxxxxf第28頁(yè)/共63頁(yè))(00 xfa ,)()(1001011xxfxxxfxfa,1 )()(101201021210202122xxxfxxfxxfxxaxxxfxfxxa由歸納：,0nnxxfa第29頁(yè)/共63頁(yè))(,00 xfx)(,11xfx)(,22xfx)(,nnxfx,10 xxf,12xxf,1nnxxf,012xxxf,21nnnxxxf,0

14、 xxfn1、先構(gòu)造差商表第30頁(yè)/共63頁(yè)2點(diǎn)Newton型插值)()()()()(0010101xxxxxfxfxfxN2、利用差商表的最外一行，構(gòu)造插值多項(xiàng)式)()(,)(,)()(1000100nnnxxxxxxfxxxxfxfxN第31頁(yè)/共63頁(yè)差商表求值算法：for(i=1;i=i;j-) yj=(yj-yj-1)/(xj-xj-i);fx=yn;for(i=n;i=1;i-) fx=yi-1+(x-xi-1)fx;第32頁(yè)/共63頁(yè)問(wèn)題：如果要做到增加一個(gè)點(diǎn)，而盡可能減少重復(fù)計(jì)算，要如何改進(jìn)前面的算法？第33頁(yè)/共63頁(yè)niniiiiiiinnnnxxxxxxxxxfxxfxx

15、LxN01100)()()()(, )()( 的系數(shù)一樣性質(zhì)2第34頁(yè)/共63頁(yè)誤差00100100 Newton( ) ( )( ), ()() ( )( )( )( ), ()()niinniinnnnnnnnxNxxaNtN tf xx a txtxNaf af aN af xx a axax另一方面設(shè)插值為則有為顯然(1)0(),(1)!nnffxxan性質(zhì)3(1)0( ) ( ) ( )()()(1)!nnnnfNxR xxxxxn同樣的誤差為第35頁(yè)/共63頁(yè)niniiiiiiinxxxxxxxxxfxxf01100)()()()(,00niinxxfxxf( )0( ),!nnf

16、f xxnnknkaxxfxPxfnkn, 0,),()(0推論：若第36頁(yè)/共63頁(yè)011, mm kkfmkf x xxx若 則 PP證明作為作業(yè)第37頁(yè)/共63頁(yè) 有時(shí)候，構(gòu)造插值函數(shù)除了函數(shù)值的條件以外，還需要一定的連續(xù)性條件，如一階導(dǎo)數(shù)值等，這種插值稱(chēng)為Hermite插值。( )00 ,( ),( ,( ),1,), Hermitenkniiiiiiixf xxfxkk定義：滿(mǎn)足和條件的插值稱(chēng)為插值niiiniiiixfxxfxk00)( ,)(, 1和滿(mǎn)足一階導(dǎo)條件為例，即每個(gè)點(diǎn)上還要以所有稱(chēng)為二重密切Hermite插值第38頁(yè)/共63頁(yè)例：例：設(shè)設(shè) x0 x1 x2, 已知已知

17、f(x0)、 f(x1)、 f(x2) 和和 f (x1), 求多項(xiàng)式求多項(xiàng)式 P(x) 滿(mǎn)足滿(mǎn)足 P(xi) = f (xi)，i = 0, 1, 2，且且 P(x1) = f (x1), 并估計(jì)誤差。并估計(jì)誤差。模仿模仿 Lagrange 多項(xiàng)式的思想，設(shè)多項(xiàng)式的思想，設(shè)解：解：首先，首先，P 的階數(shù)的階數(shù) = 3213)()()()()(0iiixhx1f xhxfxP h0(x)有根有根x1, x2，且且 h0(x1) = 0 x1 是重根。是重根。)()()(22100 xxxxCxh 又又: h0(x0) = 1 C0 )()()()()(202102210 xxxxxxxxxh

18、h2(x)與與h0(x) 完全類(lèi)似。完全類(lèi)似。其中其中 hi(xj) = ij , hi(x1) = 0, (xi) = 0, (x1) = 1 h1 h1第39頁(yè)/共63頁(yè)h1(x)有根有根 x0, x2 )()()(201xxxxBAxxh 由余下條件由余下條件 h1(x1) = 1 和和 h1(x1) = 0 可解?？山?。 (x) h1有根有根 x0, x1, x2 h1)()()(2101xxxxxxCx h1又又: (x1) = 1 C1 可解?？山狻?,()()()()()(221033xxxxxxxKxPxfxR !4)()()4(xfxK 與與 Lagrange 分析分析完全類(lèi)

19、似完全類(lèi)似第40頁(yè)/共63頁(yè))()( ,)()( )()()()(12000012xPxgxhxfxgxfxhxHnniiniiniiiniiin問(wèn)題變?yōu)榍蠛瘮?shù)設(shè)，ijjijijiijjixgxgxhxh)( 0)( , 0)( )( 同樣： 仿照Lagrange插值的做法，首先確定多項(xiàng)式插值空間的維數(shù)，注意到，我們的條件共有2(n+1)個(gè)條件，所以，最高次數(shù)為2n+1l對(duì)二重密切Hermite插值第41頁(yè)/共63頁(yè)10000100001000010000nnnnxxxxgghh第42頁(yè)/共63頁(yè)l 整個(gè)構(gòu)造步驟如下：1、確定多項(xiàng)式的最高項(xiàng)次數(shù)，就是函數(shù)空間的維數(shù)2、假設(shè)一組基函數(shù)，列出插值多

20、項(xiàng)式3、列出基函數(shù)滿(mǎn)足的公式（畫(huà)表），求基函數(shù)稱(chēng)為構(gòu)造基函數(shù)方法第43頁(yè)/共63頁(yè)類(lèi)似Lagrange插值的分析方法000000110110(1)(1)0(1)0( )( )( ) ,( )( )( )()()( )( )( )( )()()( )( )( )(1)!( )( )(1)!nnnnnnkknkknkknkknnkknnR xf xH xxxR xR xk x xxxxtf tH tk x txtxfk x kknfR xkkn 易知，為若干重根記0110)()nkknxxxx第44頁(yè)/共63頁(yè)(22)220( )( )()()(22)!nnfR xxxxxn第45頁(yè)/共63頁(yè)例：

21、例：在在 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)附近抖動(dòng)端點(diǎn)附近抖動(dòng)越大越大Ln(x) f (x) 是否次數(shù)越高越好呢？第46頁(yè)/共63頁(yè)例： 1 , 1 2511)(2xxxf等距節(jié)點(diǎn)構(gòu)造10次Lagrange插值多項(xiàng)式)(10 xLx)()(10 xLxf-0.900.047061.57872-0.700.07547-0.22620-0.500.137930.25376-0.300.307690.235351901年

22、，Runge等距高次插值，數(shù)值穩(wěn)定性差，本身是病態(tài)的。第47頁(yè)/共63頁(yè)每個(gè)小區(qū)間上，作線(xiàn)性插值,),()()(11111iiiiiiiiiiixxxxfxxxxxfxxxxxs, )()(1iiinxxxxSxp(1),)(baCxpn(2)(xpn在每個(gè)小區(qū)間上為一個(gè)不高于1次的多項(xiàng)式特性特性第48頁(yè)/共63頁(yè)l誤差,1iixxx2121)2(22M )(!2)()()(iiiinxxxxxxfxpxf22212822M)()(hMxxMaxxpxfiinn可以看出nxfxpn),()(第49頁(yè)/共63頁(yè)收斂，可惜只一階精度，不夠光滑。類(lèi)似，可以作二重密切Hermite插值關(guān)鍵： 分段、低

23、階插值第50頁(yè)/共63頁(yè) 分段低階插值，收斂性好，但光滑性不夠理想。在工業(yè)設(shè)計(jì)中，對(duì)曲線(xiàn)光滑性要求高，如：流線(xiàn)型 設(shè)想這樣一曲線(xiàn)：插值，次數(shù)不高于3次，整個(gè)曲線(xiàn)2階連續(xù)導(dǎo)數(shù)，稱(chēng)為三次樣條函數(shù)插值。第51頁(yè)/共63頁(yè)每個(gè)小區(qū)間不高于3次，,)(123iiiiiiixxxdxcxbxaxS1, 0ni有4n個(gè)未知數(shù)，我們的已知條件如下：(0)(0)(0)(0)(0)(0)( )( )iiiiiiiiS xS xS xS xSxSxS xf x1, 1nini, 0 1, 1ni1, 1ni共3n-3+n+1=4n-2個(gè)條件第52頁(yè)/共63頁(yè)需要附加2個(gè)條件，通常在邊界處給出設(shè),)(,)()()(),()(,)(11111iiiiiiiiiiiiiiiiixxxmxSmxSxfxSxfxSmxS則所以，是3次二重Hermite插值，記iiixxh1第53頁(yè)/共63頁(yè)213211321221121( )2()()( )1 2()()()1 ()()1 ()()iiiiiiiiiiiiiiiiiiiS xhxxxxf xhhxxxxf xhxxxxmhxxxxmh第54頁(yè)/共63頁(yè)131312126 ( )2() ( )6 2() ()1 6()2 1 6()2 iiiiiiiiiiiiiiiiiSxhxxf xhhxxf xhxxh