第一講-插值方法

1、19761976年出生年出生于云南宣威于云南宣威，烏蒙山。，烏蒙山。2000-20032000-2003在在西安交通大學(xué)西安交通大學(xué)，博士。，博士。1997-20001997-2000在在蘭州大學(xué)，學(xué)蘭州大學(xué)，學(xué)士和碩士。士和碩士。2003-20112003-2011電子電子科技大學(xué)，數(shù)學(xué)科技大學(xué)，數(shù)學(xué)學(xué)院教學(xué)學(xué)院教學(xué)20122012至今至今華東理工華東理工大學(xué)。大學(xué)。計(jì)算方法的研究目標(biāo)：計(jì)算方法的研究目標(biāo)：研究科學(xué)問(wèn)題的求解方法和過(guò)程設(shè)計(jì)研究科學(xué)問(wèn)題的求解方法和過(guò)程設(shè)計(jì)科學(xué)問(wèn)題科學(xué)問(wèn)題模型建立模型建立計(jì)算方法和算法設(shè)計(jì)計(jì)算方法和算法設(shè)計(jì)程序語(yǔ)言程序語(yǔ)言結(jié)論展示或集成系統(tǒng)結(jié)論展示或集成系統(tǒng)研究

2、內(nèi)容研究?jī)?nèi)容信息安全；信息安全；云計(jì)算；云計(jì)算；大數(shù)據(jù)；大數(shù)據(jù)；物聯(lián)網(wǎng)；物聯(lián)網(wǎng)；決策支持等決策支持等42022-4-29 3 54 3 32 插值平均插值平均 Lagrange插值公式插值公式Aitken逐步插值算法逐步插值算法插值逼近插值逼近分段插值分段插值 3 1樣條插值樣條插值6 3 7曲線擬合的最小二乘法曲線擬合的最小二乘法52022-4-29實(shí)例實(shí)例1求求 sin3813查查 函函 數(shù)數(shù) 表表sinx62022-4-29實(shí)例實(shí)例2xy機(jī)翼下輪廓線求機(jī)翼下輪廓線上一點(diǎn)的近似數(shù)值求機(jī)翼下輪廓線上一點(diǎn)的近似數(shù)值該點(diǎn)的值是多少該點(diǎn)的值是多少?72022-4-29v對(duì)于諸如此類(lèi)的問(wèn)題，設(shè)法利用

3、已給數(shù)據(jù)表求出給定點(diǎn)x的函數(shù)值y，稱(chēng)為插值。目的在于通過(guò)盡可能簡(jiǎn)便的方法，利用所給數(shù)據(jù)表加工出插值點(diǎn)x上具有足夠精度的插值結(jié)果yvxi 稱(chēng)為插值節(jié)點(diǎn)，所要插值的點(diǎn)x稱(chēng)為插值點(diǎn)v現(xiàn)在的考慮：能否通過(guò)對(duì)表中數(shù)據(jù)進(jìn)行適當(dāng)?shù)募訖?quán)平均來(lái)得到想要的插值結(jié)果？即用y來(lái)近似f(x) ，其中v可以，關(guān)鍵在于i的選取yxf)(niiiniiixfyy00)(82022-4-29v 定義1：稱(chēng)近似關(guān)系式 具有m階精度，如果它對(duì)于次數(shù)m的多項(xiàng)式均能準(zhǔn)確成立v 特別地，當(dāng)y1時(shí)， 。所以，插值方法是平均化的過(guò)程，故稱(chēng)為插值平均niiiyxf0)(nii01插值的幾何意義插值的幾何意義92022-4-29102022-4

4、-29 2. Lagrange（拉格朗日）（拉格朗日）插值公式n 兩點(diǎn)插值：u 形式形式u 插值公式插值公式n 三點(diǎn)插值：n 形式形式n 插值公式插值公式1100yyy10100101yxxxxyxxxxy221100yyyy212021012101200201021)()()()()()(yxxxxxxxxyxxxxxxxxyxxxxxxxxy112022-4-29n 多點(diǎn)插值：u 形式形式u 插值公式插值公式 niiiyy0ininijjjijyxxxxy 00Lagrange插值公式特點(diǎn)：插值公式特點(diǎn)：各節(jié)點(diǎn)地位相同，形式對(duì)各節(jié)點(diǎn)地位相同，形式對(duì)稱(chēng)，但增加節(jié)點(diǎn)時(shí)，所有系數(shù)需要重新計(jì)算稱(chēng)，

5、但增加節(jié)點(diǎn)時(shí)，所有系數(shù)需要重新計(jì)算122022-4-29例：利用例：利用100、121和和144開(kāi)平方值計(jì)算開(kāi)平方值計(jì)算115解：解： 令令 ，利用三點(diǎn)，利用三點(diǎn)Lagrange公式公式xy 212021012101200201021)()()()()()(yxxxxxxxxyxxxxxxxxyxxxxxxxxy221100yyyy其中：其中：x0=100, y0=10, x1=121, y0=11, x2=144, y2=12, x=115，將這些信息代入上面的公式，有，將這些信息代入上面的公式，有7228.10115 同精確值比較，該結(jié)果有同精確值比較，該結(jié)果有4位有效數(shù)字。位有效數(shù)字。1

6、32022-4-293. Aitken（埃特金）（埃特金）逐步插值算法n 化三點(diǎn)插值為兩點(diǎn)插值：u 對(duì)于點(diǎn)對(duì)于點(diǎn) (x0, y0), (x1, y1)和(x0, y0), (x2, y2)u 插值公式插值公式u 以以(x1, y01), (x2, y02)作為節(jié)點(diǎn)構(gòu)造兩點(diǎn)插值公式：作為節(jié)點(diǎn)構(gòu)造兩點(diǎn)插值公式：1010010101yxxxxyxxxxy2020020202yxxxxyxxxxy021210121212yxxxxyxxxxy142022-4-29 Aitken逐步插值算法：x0 y0 x1 y1x2 y2x3 y3x4 y4xn yny01y02y03y04y0ny12y13y14y

7、1ny23y24y2ny34y3nyn-1,nn+1點(diǎn)插值點(diǎn)插值 n點(diǎn)插值點(diǎn)插值 n-1點(diǎn)插值點(diǎn)插值 1點(diǎn)插值點(diǎn)插值 152022-4-29例：用下表中第例：用下表中第1、2列的值求解列的值求解f(0.462)的值的值xdtttxfsin)(解：解： 利用所給數(shù)值及利用所給數(shù)值及Aitken公式，有公式，有 xi yi y0i y1i y2i456557.0sin)(xdtttxf162022-4-29Neville（內(nèi)維爾）逐步插值算法：x0 y0 x1 y1x2 y2x3 y3x4 y4xn yny01y12y23y34yn-1,ny02y13y24yn-2,ny03y14yn-3,ny0

8、4yn-4,ny0,nn+1點(diǎn)插值點(diǎn)插值 n點(diǎn)插值點(diǎn)插值 n-1點(diǎn)插值點(diǎn)插值 1點(diǎn)插值點(diǎn)插值 172022-4-29vAitken算法和Neville算法是逐步插值的兩種基本形式v共同特點(diǎn)：都是將高階插值逐步歸結(jié)為線性插值（最簡(jiǎn)單、最基本）的重復(fù)182022-4-29u*x*y求任一插值點(diǎn)求任一插值點(diǎn))(*ixx 處的插值處的插值.*y0 x1xnx0y1y這些點(diǎn)可視為由這些點(diǎn)可視為由y=f(x)產(chǎn)生，但產(chǎn)生，但f表表達(dá)式復(fù)雜，或根達(dá)式復(fù)雜，或根本無(wú)法提供本無(wú)法提供已知已知 n+1個(gè)點(diǎn)個(gè)點(diǎn), 1 , 0(),(niyxii其中其中ix互不相同，不妨設(shè)互不相同，不妨設(shè)),10bxxxan問(wèn)題的提

9、出問(wèn)題的提出 4. 插值逼近192022-4-290 x1xnx0y1y 構(gòu)造一個(gè)相對(duì)簡(jiǎn)單的函數(shù)構(gòu)造一個(gè)相對(duì)簡(jiǎn)單的函數(shù)),(xgy 通過(guò)全部點(diǎn)，即通過(guò)全部點(diǎn)，即), 1 , 0()(niyxgii再用再用)(xg計(jì)算插值，即計(jì)算插值，即).(*xgy u*x*y求解插值問(wèn)題的基本思路求解插值問(wèn)題的基本思路202022-4-29插值與逼近插值與逼近u 上述過(guò)程就是逼近過(guò)程，上述方法就稱(chēng)為逼近方法，即構(gòu)造一個(gè)簡(jiǎn)單函數(shù)構(gòu)造一個(gè)簡(jiǎn)單函數(shù)g(x)作為作為f(x)的近似的近似，然后通過(guò)處理，然后通過(guò)處理g(x)獲得關(guān)于獲得關(guān)于f(x)所要的結(jié)果所要的結(jié)果u 插值方法是逼近方法的一種u 如果要求逼近函數(shù)g(

10、x)與其所逼近的函數(shù)f(x)在若干節(jié)點(diǎn)上取相同的離散信息（函數(shù)值、導(dǎo)數(shù)值），這種逼近方法稱(chēng)為插值方法，逼近函數(shù)g(x)稱(chēng)為插值函數(shù) 212022-4-29u 如果限定插值函數(shù)為代數(shù)多項(xiàng)式pn(x)。這類(lèi)插值方法稱(chēng)為代數(shù)插值，相應(yīng)的插值函數(shù)稱(chēng)為插值多項(xiàng)式u 如果插值函數(shù)為分段多項(xiàng)式，就稱(chēng)為分段插值，如果為三角多項(xiàng)式，就稱(chēng)為三角插值u 本章只討論代數(shù)插值和分段插值 我們的問(wèn)題是如何確定我們的問(wèn)題是如何確定 ?.)(2210nnnxxxxp)(*xpyn 進(jìn)而求得進(jìn)而求得 222022-4-29事實(shí)上，方程組的解事實(shí)上，方程組的解0, 1, , n存在且唯一。解出存在且唯一。解出i (i=0, 1,

11、 2, , n)， pn(x)就可構(gòu)造出來(lái)了。但遺憾的是就可構(gòu)造出來(lái)了。但遺憾的是此此方程組是病態(tài)方程組，方程組是病態(tài)方程組，當(dāng)階數(shù)當(dāng)階數(shù)n越越高時(shí)，病態(tài)越重高時(shí)，病態(tài)越重。為此我們從另一途徑來(lái)尋求獲得為此我們從另一途徑來(lái)尋求獲得pn(x)常用的代數(shù)插值方法常用的代數(shù)插值方法 Taylor插值 Lagrange插值 Hermite插值232022-4-29Taylor插值插值 在給定點(diǎn)x0鄰近用Taylor展開(kāi)式 pn(x) 來(lái)逼近： nnnxxnxfxxxfxxxfxfxp)(!)(.)(2)()()()(00)(200000 nixfxpiin, 1 ,0 )()(0)(0)( 該多項(xiàng)式滿(mǎn)

12、足： Taylor插值的特點(diǎn)：插值的特點(diǎn)：原理簡(jiǎn)單，但要求插值函數(shù)原理簡(jiǎn)單，但要求插值函數(shù)p(x)與所逼與所逼近的函數(shù)近的函數(shù)f(x)在展開(kāi)點(diǎn)在展開(kāi)點(diǎn)x0處具有相同的直到處具有相同的直到n階的導(dǎo)數(shù)值階的導(dǎo)數(shù)值 242022-4-29kx1 kxky1 ky)(xfy )(1xpy Lagrange 插值插值線性插值(n=1)：假定給定區(qū)間xk,xk+1及端點(diǎn)的函數(shù)值111)()()(kkkkyxyxxp252022-4-29)()(111kkkkkkxxxxyyyxp)(點(diǎn)斜式點(diǎn)斜式11111)(kkkkkkkkyxxxxyxxxxxp)(兩點(diǎn)式兩點(diǎn)式令令,)(11kkkkxxxxxkkkkx

13、xxxx11)(上滿(mǎn)足條件上滿(mǎn)足條件及及在節(jié)點(diǎn)在節(jié)點(diǎn)1 kkxx. 1, 0; 0)(, 11111kkkkkkkkxxxxkx1 kx10)(xk)(1xk插值基函數(shù)插值基函數(shù)262022-4-29)()()()()()(11112kkkkkkxfxxfxxfxxp）（1 kx1 kx10)(xk)(1xkkx)(1xk基基函函數(shù)數(shù)的的圖圖形形同理，當(dāng)n=2時(shí)，即利用二次插值基函數(shù)立即得到二次插值多項(xiàng)式插值基函數(shù)滿(mǎn)足條件1, 1 0)( , 1)(kkjxxjkkk272022-4-29n 2時(shí)，插值多項(xiàng)式nkkknxfxxp0)()()(nkxxxxxnkjjjkjk, 1 ,0 )(0插

14、值基函數(shù)優(yōu)點(diǎn)優(yōu)點(diǎn): 結(jié)構(gòu)緊湊結(jié)構(gòu)緊湊, 理論分析方便理論分析方便 缺點(diǎn)缺點(diǎn): 改變一個(gè)節(jié)點(diǎn)則全改變一個(gè)節(jié)點(diǎn)則全部的插值基函數(shù)都改變，部的插值基函數(shù)都改變，即節(jié)點(diǎn)增加，基函數(shù)失效即節(jié)點(diǎn)增加，基函數(shù)失效 282022-4-29.352274. 0,36. 0,333487. 0,34. 0,314567. 0,32. 0221100yxyxyx得得)3367. 0(3367. 0sin1p)3367. 0(001010 xxxyyy330365. 00167. 002. 001892. 0314567. 0,333487. 034. 0sin314567. 032. 0sin，已給已給)3367.

15、 0sin(3522787. 036. 0sin計(jì)算計(jì)算值值，用線性插值及拋物插，用線性插值及拋物插例例由題意取由題意取解解用線性插值計(jì)算，取用線性插值計(jì)算，取 x0=0.32、x1=0.34292022-4-290201021)()(3367. 0sinyxxxxxxxx21202101210120)()()()(yxxxxxxxxyxxxxxxxx330374. 0)3367. 0(2 p 這個(gè)結(jié)果與六位有效數(shù)字的正弦函數(shù)表完全一樣，這個(gè)結(jié)果與六位有效數(shù)字的正弦函數(shù)表完全一樣，這說(shuō)明查表時(shí)用二次插值精度已相當(dāng)高了。這說(shuō)明查表時(shí)用二次插值精度已相當(dāng)高了。時(shí)，時(shí)，用拋物插值計(jì)算用拋物插值計(jì)算3

16、367. 0sin302022-4-29Hermite（埃爾米特）（埃爾米特） 插值插值 是Taylor插值與Lagrange插值的綜合與推廣。思想：在節(jié)點(diǎn)xi處插值函數(shù)pn(x)和要逼近的函數(shù)具有相同的函數(shù)值和導(dǎo)數(shù)值，這種插值方法稱(chēng)為Hermite插值 niyxpyxpiiniin, 1 , 0 )( ,)( 該多項(xiàng)式滿(mǎn)足： 保持插值曲線在節(jié)點(diǎn)處有切線（光滑），使保持插值曲線在節(jié)點(diǎn)處有切線（光滑），使插值函數(shù)和被插函數(shù)的密合程度更好插值函數(shù)和被插函數(shù)的密合程度更好 。 312022-4-29112002002)( , )( ,)(yxpyxpyxp 最簡(jiǎn)單的形式： 對(duì)于該問(wèn)題，有三種解決方法

17、：u待定系數(shù)法：待定系數(shù)法：解方程組解方程組 困難困難u余項(xiàng)校正法：余項(xiàng)校正法：用某個(gè)余項(xiàng)校正用某個(gè)余項(xiàng)校正p1(x)以獲得以獲得p2(x) 可行，但插值公式的次數(shù)不能高可行，但插值公式的次數(shù)不能高u基函數(shù)方法：基函數(shù)方法：將插值多項(xiàng)式的構(gòu)造化歸為求解將插值多項(xiàng)式的構(gòu)造化歸為求解幾幾 個(gè)特殊數(shù)據(jù)表的插值問(wèn)題個(gè)特殊數(shù)據(jù)表的插值問(wèn)題322022-4-29分別滿(mǎn)足分別滿(mǎn)足，設(shè)有兩組函數(shù)：設(shè)有兩組函數(shù)：)()(xxii), 1 , 0,(0)( , 1 , 0)( ), 1 , 0,(0)( , 1 , 0)( )2(njixijijxnjixijijxjiijjijiijji次多項(xiàng)式次多項(xiàng)式都是至多

18、都是至多12)( ),( ) 1 (nxxiiniiiiinyxyxxp012)()()(則則Hermite 插值多項(xiàng)式為插值多項(xiàng)式為：一般形式：332022-4-29,21)(21010100 xxxxxxxxx,)()(210100 xxxxxxx2010101121)(xxxxxxxxx201011)()(xxxxxxx特別：n=1時(shí)110011003)()()()()(yxyxyxyxxp342022-4-29 求過(guò)求過(guò)0、1兩點(diǎn)構(gòu)造一個(gè)三次插值多項(xiàng)式兩點(diǎn)構(gòu)造一個(gè)三次插值多項(xiàng)式，滿(mǎn)足條件：滿(mǎn)足條件： f(0)=1, f (0)=1/2 , f(1)=2, f (1) =1/2解解: :

19、 設(shè) p3(x)=0(x) y0 + 1(x) y1 +0(x) y 0 +1(x) y 0 同理可得同理可得: 1(x)=(3-2x)x2 0(x)=x(x-1)2 1(x)=x2(x-1)例例2221010100) 1)(21 (1010102121)(xxxxxxxxxxxxx352022-4-295. 分段插值 一般來(lái)說(shuō)，高次插值多項(xiàng)式的逼近效果并不好，從數(shù)值計(jì)算上可解釋為高次插值多項(xiàng)式的計(jì)算會(huì)帶來(lái)舍入誤差的增大，從而引起計(jì)算失真。因此，實(shí)踐上作插值時(shí)一般只用一次、二次最多用三次插值多項(xiàng)式。 Runge（龍格）（龍格）現(xiàn)象現(xiàn)象 那么如何提高插值精度呢？ 采用分段插值362022-4-2

20、9分段插值的含義分段插值的含義 選取分段多項(xiàng)式作為插值函數(shù)，即將插值函數(shù)逐段多項(xiàng)式化 將插值區(qū)間a, b 劃分為若干個(gè)子段xi , xi+1 在每個(gè)子段上構(gòu)造插值多項(xiàng)式 將每個(gè)子段上的插值多項(xiàng)式拼接在一起作為整個(gè)區(qū)間上的插值函數(shù) 若插值函數(shù)Sk(x)在分劃的每個(gè)子段上都是k次式，則稱(chēng)Sk(x)為具有分劃的分段k次式372022-4-29分段線性插值 都是線性函數(shù)都是線性函數(shù)在每個(gè)小區(qū)間上在每個(gè)小區(qū)間上)(),1,.,2 , 1 , 0(,)2(),.,2 , 1 , 0()() 1 (111xSnixxniyxSiiii則稱(chēng)S1(x)是f(x)在a ,b上的分段線性插值多項(xiàng)式。通過(guò)插值點(diǎn)用折線

21、連接起來(lái)逼近f(x)。設(shè)已知插值節(jié)點(diǎn) 上的函數(shù)值為nyyy,10bxxxan10構(gòu)造插值函數(shù)S1(x)，使其滿(mǎn)足：382022-4-29)( )(111111iiiiiiiiiixxxyxxxxyxxxxxS分段表達(dá)式分段表達(dá)式若采用若采用Lagrange插值多項(xiàng)式插值多項(xiàng)式)( )(11101iiiiiiiixxxyhxxyhxxxSxjxj-1xj+1x0 xnn越大，誤差越小392022-4-29設(shè)設(shè) （-1 x 1），），將將-1, 1 10等份等份，用分段線性插值近似計(jì)算用分段線性插值近似計(jì)算f(-0.96)。22511)(xxf 8 . 01) 1(2941. 0)8 . 0(1923. 02 . 01)8 . 0(2 . 08 . 0) 1()(1xxxxfxfxS解解：(1)插值節(jié)點(diǎn)為xi=-1+i/5 (i=0,1,10), h=1/5 因?yàn)?0.96-1,-0.8，取此區(qū)間為線性插值區(qū) 間，其上的插值函數(shù)為例例所以f(-0.96)=0.041597 S1(-0.96)=0.042532402022-4-29選取距節(jié)點(diǎn)選取距節(jié)點(diǎn)x最近的三個(gè)節(jié)點(diǎn)最近的三個(gè)節(jié)點(diǎn)xi-1、xi、x