第4章 福大科學(xué)工程與計(jì)算-插值法

科學(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)用。引言拉格朗日插值均差與牛頓插值公式埃爾米特插值分段低次插值三次樣條插值插值法求擬合這組數(shù)據(jù)的多項(xiàng)式能否存在一個(gè)性能優(yōu)良、便于計(jì)算的函數(shù)一、插值問(wèn)題------(1)這就是插值問(wèn)題,(1)式為插值條件,其插值函數(shù)的圖象如圖整體誤差的大小反映了插值函數(shù)的好壞為了使插值函數(shù)更方便在計(jì)算機(jī)上運(yùn)算,一般插值函數(shù)都使用代數(shù)多項(xiàng)式和有理函數(shù)。x0x1x2x3x4xP(x)

f(x)Lagrange插值多項(xiàng)式為了求得便于使用的簡(jiǎn)單的插值多項(xiàng)式P(x),我們先討論n=1的情形要求線性插值多項(xiàng)式L1(x),使它滿足：L1(x)的幾何意義就是通過(guò)這兩點(diǎn)的直線；n=2的情況，假定插值節(jié)點(diǎn)為考慮通過(guò)n+1個(gè)節(jié)點(diǎn)……？n

1希望找到li(x)，i=0,…,n

使得

li(xj)=ij

===niiinyxlxL0)()(li(x)每個(gè)li

有n

個(gè)根x0…

xi…xnLagrangePolynomial與有關(guān)，而與無(wú)關(guān)節(jié)點(diǎn)f然后令例1:解:且在例1中,如果只給出兩個(gè)節(jié)點(diǎn)169和225,也可以作插值多項(xiàng)式,即1次Lagrange插值多項(xiàng)式,有兩個(gè)插值基函數(shù),這種插值方法稱(chēng)為L(zhǎng)agrange線性插值,也可以在n+1個(gè)節(jié)點(diǎn)中取相鄰的兩個(gè)節(jié)點(diǎn)作線性插值例2.解:Lagrange插值基函數(shù)為L(zhǎng)agrange線性插值多項(xiàng)式為所以Lagrange插值多項(xiàng)式的缺點(diǎn)：插值基函數(shù)計(jì)算復(fù)雜高次插值的精度不一定高高次插值通常優(yōu)于低次插值但絕對(duì)不是次數(shù)越高就越好，嘿嘿……三、插值余項(xiàng)Remainder滿足不會(huì)完全成立因此,插值多項(xiàng)式存在著截?cái)嗾`差,那么我們?cè)鯓庸烙?jì)這個(gè)截?cái)嗾`差呢？令設(shè)其中近似函數(shù)誤差根據(jù)Rolle定理,再由Rolle定理,依此類(lèi)推由于因此所以定理2.Lagrange型余項(xiàng)余項(xiàng)表達(dá)式只有在f(x)的高階導(dǎo)數(shù)存在時(shí)才能應(yīng)用。設(shè)則例3:解:練習(xí)1：練習(xí)2：第4章插值和擬合均差與牛頓插值公式Lagrange插值多項(xiàng)式的缺點(diǎn)我們知道,Lagrange插值多項(xiàng)式的插值基函數(shù)為理論分析中很方便，但是當(dāng)插值節(jié)點(diǎn)增減時(shí)全部插值基函數(shù)就要隨之變化，整個(gè)公式也將發(fā)生變化，這在實(shí)際計(jì)算中是很不方便的；Lagrange插值雖然易算，但若要增加一個(gè)節(jié)點(diǎn)時(shí)，全部基函數(shù)li(x)都需重新算過(guò)。解決由線性代數(shù)的知識(shí)可知,任何一個(gè)n次多項(xiàng)式都可以表示成共n+1個(gè)多項(xiàng)式的線性組合那么，是否可以將這n+1個(gè)多項(xiàng)式作為插值基函數(shù)呢？顯然，多項(xiàng)式組線性無(wú)關(guān)，因此，可以作為插值基函數(shù)基函數(shù)有再繼續(xù)下去待定系數(shù)的形式將更復(fù)雜。。。。。。為此引入差商的概念差商(亦稱(chēng)均差)/*

divideddifference*/1階差商

/*the1stdivideddifferenceoffw.r.t.xi

andxj

*/2階差商定義2.11101010111010],,...,[],,...,[],,...,[],...,,[],...,[++--+++--=--=kkkkkkkkkkkxxxxxfxxxfxxxxxfxxxfxxf(k+1)階差商差商的計(jì)算方法(表格法):規(guī)定函數(shù)值為零階差商差商表差商具有如下性質(zhì):Warning:myheadisexploding…Whatisthepointofthisformula?差商的值與xi

的順序無(wú)關(guān)！Newton插值公式Newton插值公式及其余項(xiàng)例：已知x=1,4,9的平方根為1,2,3，利用牛頓基本差商公式求的近似值。解：從而得二階牛頓基本差商公式為因此計(jì)算得的近似值為kxkf(xk)一階差商二階差商三階差商四階差商0123412345147863301-1-1/3-2-3/2-1/61/24二、代數(shù)插值多項(xiàng)式的存在唯一性且滿足--------(2)--------(3)--------(4)上述方程組的系數(shù)行列式為n+1階范德蒙行列式由Cramer法則,線性方程組(4)有唯一解定理1.

則滿足插值條件的插值多項(xiàng)式存在且唯一.注：若不將多項(xiàng)式次數(shù)限制為n

，則插值多項(xiàng)式不唯一。例如也是一個(gè)插值多項(xiàng)式，其中可以是任意多項(xiàng)式。練習(xí)2.已知函數(shù)在點(diǎn)的函數(shù)值，求其三次插值多項(xiàng)式。解：其三次插值多項(xiàng)式即為函數(shù)本身：（3）已知100,121,144的平方根，計(jì)算115平方根近似值x100121144y101112§4.3埃爾米特插值/*HermiteInterpolation*/§3HermiteInterpolation

求Hermite多項(xiàng)式的基本步驟：寫(xiě)出相應(yīng)于條件的hi(x)、hi(x)的組合形式；對(duì)每一個(gè)hi(x)、hi(x)找出盡可能多的條件給出的根；根據(jù)多項(xiàng)式的總階數(shù)和根的個(gè)數(shù)寫(xiě)出表達(dá)式；根據(jù)尚未利用的條件解出表達(dá)式中的待定系數(shù)；最后完整寫(xiě)出H(x)。習(xí)題1:求不超過(guò)3次的多項(xiàng)式H(x),使它滿足插值條件習(xí)題2:求不超過(guò)2次的多項(xiàng)式H(x),使它滿足插值條件§4分段低次插值/*piecewisepolynomialapproximation*/RememberwhatIhavesaid?IncreasingthedegreeofinterpolatingpolynomialwillNOTguaranteeagoodresult,sincehigh-degreepolynomialsareoscillating.例：在[5,5]上考察的Ln(x)。取

-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)越大，稱(chēng)為Runge現(xiàn)象Ln(x)f(x)分段低次插值§4PiecewisePolynomialApproximation

分段線性插值

/*piecewiselinearinterpolation*/在每個(gè)區(qū)間上，用1階多項(xiàng)式

(直線)逼近f(x):記，易證：當(dāng)時(shí)，一致失去了原函數(shù)的光滑性。

分段Hermite插值

/*Hermitepiecewisepolynomials*/給定在上利用兩點(diǎn)的y及y’構(gòu)造3次Hermite函數(shù)導(dǎo)數(shù)一般不易得到。Howcanwemakeasmoothinterpolationwithoutaskingtoomuchfromf?Headache…三次樣條插值早期工程師制圖時(shí)，把富有彈性的細(xì)長(zhǎng)木條（所謂樣條）用壓鐵固定在樣點(diǎn)上，在其它地方讓它自由彎曲，然后畫(huà)下長(zhǎng)條的曲線，稱(chēng)為樣條曲線。它實(shí)際上是由分段三次曲線并接而成，在連接點(diǎn)即樣點(diǎn)上要求二階導(dǎo)數(shù)連續(xù)，從數(shù)學(xué)上加以概括就得到數(shù)學(xué)樣條這一概念。

三次樣條插值樣條本質(zhì)上是一段一段的三次多項(xiàng)式拼合而成的曲線在拼接處,不僅函數(shù)是連續(xù)的,且一階和二階導(dǎo)數(shù)也是連續(xù)的一、三次樣條插值函數(shù)定義1.------(1)注：三次樣條與分段Hermite插值的根本區(qū)別在于S(x)自身光滑，不需要知道f的導(dǎo)數(shù)值（除了在2個(gè)端點(diǎn)可能需要）；而Hermite插值依賴于f在所有插值點(diǎn)的導(dǎo)數(shù)值。f(x)H(x)S(x)要求出S(x)，則在每個(gè)小區(qū)間上要確定4個(gè)待定系數(shù)，共有n個(gè)小區(qū)間，所以應(yīng)確定4n個(gè)參數(shù)。共(n+1)+(3n-3)=4n-2個(gè)條件，因此還需要兩個(gè)條件才能確定S(x)可在區(qū)間端點(diǎn)a,b上各加一個(gè)條件（邊界條件），具體要根據(jù)實(shí)際問(wèn)題要求給定；已知兩端的一階導(dǎo)數(shù)值2.兩端的二階導(dǎo)數(shù)已知其特殊情況為3.當(dāng)f(x)是為周期的周期函數(shù)時(shí)，則要求S(x)也是周期函數(shù)，這時(shí)邊界條件應(yīng)滿足：這樣確定的樣條函數(shù)S(x)稱(chēng)為周期樣條函數(shù)；加上任何一類(lèi)邊界條件(至少兩個(gè))后一般使用第一、二類(lèi)邊界條件,常用第二類(lèi)邊界條件樣條插值函數(shù)的建立即或可直接利用分段三次Hermit插值，只要假定可得加以整理后可得------(10)由條件------(11)由于以上兩式相等,得基本方程組如果問(wèn)題要求滿足第一類(lèi)(一階)邊界條件:即------(12)基本方程組化為n-1階方程組將上式化為矩陣形式------(13)------(14)這是一個(gè)三對(duì)角方程組如果問(wèn)題要求滿足第二類(lèi)(二階自然)邊界條件:由(11)式,可知------(15)----(16)------(17)------(18)與基本方程組(12)聯(lián)合,并化為矩陣形式,得-----(19)(19)式與(14)一樣,都是三對(duì)角方程組,解是唯一的；例1.對(duì)于給定的節(jié)點(diǎn)及函數(shù)值解:由(12)式可得由(19)式得基本方程組將上述結(jié)果代入(10)式定理.

最后，介紹一個(gè)有用的結(jié)果小結(jié)曲線擬合當(dāng)函數(shù)只在有限點(diǎn)集上給定函數(shù)值，要在包含該點(diǎn)擊的區(qū)間上用公式給出函數(shù)的簡(jiǎn)單表達(dá)式，這些都涉及到在區(qū)間[a,b]上用簡(jiǎn)單函數(shù)逼近已知復(fù)雜函數(shù)的問(wèn)題，這就是函數(shù)逼近問(wèn)題。插值法就是函數(shù)逼近問(wèn)題的一種擬解決的問(wèn)題：計(jì)算復(fù)雜的函數(shù)值已知有限點(diǎn)集上的函數(shù)值，給出在包含該點(diǎn)集的區(qū)間上函數(shù)的簡(jiǎn)單表達(dá)式函數(shù)逼近——對(duì)函數(shù)類(lèi)A中給定的函數(shù)f(x)，記作要求在另一類(lèi)簡(jiǎn)單的便于計(jì)算的函數(shù)類(lèi)B中求函數(shù)使p(x)與f(x)的誤差在某種度量意義下最小。逼近問(wèn)題函數(shù)逼近曲線擬合實(shí)例：考察某種纖維的強(qiáng)度與其拉伸倍數(shù)的關(guān)系,下表是實(shí)際測(cè)定的24個(gè)纖維樣品的強(qiáng)度與相應(yīng)的拉伸倍數(shù)是記錄:纖維強(qiáng)度隨拉伸倍數(shù)增加而增加并且24個(gè)點(diǎn)大致分布在一條直線附近必須找到一種度量標(biāo)準(zhǔn)來(lái)衡量什么曲線最接近所有數(shù)據(jù)點(diǎn)(1)仍然是已知x1…xm

;y1…ym,求一個(gè)簡(jiǎn)單易算的近似函數(shù)P(x)

f(x)。但是①

m

很大；②

yi

本身是測(cè)量值，不準(zhǔn)確，即yi

f(xi)這時(shí)沒(méi)必要取P(xi)=yi,

而要使P(xi)yi

總體上盡可能小。使誤差在某種度量意義下最小常見(jiàn)做法：

使最小/*minimaxproblem*/

太復(fù)雜使最小不可導(dǎo)，求解困難使最小/*Least-Squaresmethod*/最小二乘法的基本概念一般使用稱(chēng)為平方誤差從而確定(1)中的待定系數(shù)注意(1)式是一條直線因此將問(wèn)題一般化仍然定義平方誤差我們選取的度量標(biāo)準(zhǔn)是---------(2)---------(3)法方程組由可知因此可假設(shè)因此求最小二乘解轉(zhuǎn)化為二次函數(shù)由多元函數(shù)取極值的必要條件得即---------(4)引入記號(hào)則由內(nèi)積的概念可知---------(5)---------(6)顯然內(nèi)積滿足交換律方程組(4)便可化為---------(7)將其表示成矩陣形式-----(8)并且其系數(shù)矩陣為對(duì)稱(chēng)陣所以法方程組的系數(shù)矩陣非奇異,即根據(jù)Cramer法則,法方程組有唯一解即是的最小值所以因此作為一種簡(jiǎn)單的情況,基函數(shù)之間的內(nèi)積為平方誤差例1.回到本節(jié)開(kāi)始的實(shí)例，從散點(diǎn)圖可以看出纖維強(qiáng)度和拉伸倍數(shù)之間近似與線性關(guān)系故可選取線性函數(shù)為擬合函數(shù)，其基函數(shù)為建立法方程組根據(jù)內(nèi)積公式，可得法方程組為解得平方誤差為擬合曲線與散點(diǎn)的關(guān)系如右圖:例2.求擬合下列數(shù)據(jù)的最小二乘解x=.24.65.951.241.732.012.232.522.772.99y=.23-.26-1.10-.45.27.10-.29.24.561解:從數(shù)據(jù)的散點(diǎn)圖可以看出因此假設(shè)擬合函數(shù)與基函數(shù)分別為6.7941-5.347563.2589-5.34755.1084-49.008663.2589-49.00861002.5

1.6163-2.382726.7728通過(guò)計(jì)算,得法方程組的系數(shù)矩陣及常數(shù)項(xiàng)矩陣為Go!用Gauss列主元消去法,得

-1.0410-1.26130.030735擬合的平方誤差為圖象如圖例3.在某化學(xué)反應(yīng)里,測(cè)得生成物濃度y%與時(shí)間t的數(shù)據(jù)如下，試建立y關(guān)于t的經(jīng)驗(yàn)公式x=1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16y=4.00,6.40,8.00,8.80,9.22,9.50,9.70,9.86,10.00,10.20,10.32,10.42,10.50,10.55,10.58,10.60解:具有圖示的圖形的曲線很多，本題特提供兩種形式例：xy(xi,yi),i=1,2,…,m方案一：設(shè)baxxxPy+=)(求a

和b

使得最小。=-+=miiiiybaxxba12)(),(jButhey,thesystemofequationsforaandbisnonlinear!Takeiteasy!Wejusthavetolinearizeit…線性化

/*linearization*/：令，則bXaY+就是個(gè)線性問(wèn)題將化為后易解a

和b。),(iiYX),(iiyx方案二：設(shè)xbeaxPy/)(-=(a>0,b>0)線性化：由可做變換xbay-lnlnbBaAxXyY-====,ln,1,lnBXAY+就是個(gè)線性問(wèn)題將化為后易解A

和B),(iiYX),(iiyx兩邊取對(duì)數(shù),得得即為擬合函數(shù)基函數(shù)為解法方程組得平方誤差為用最小二乘法得即無(wú)論從圖形還是從平方誤差考慮在本例中指數(shù)函數(shù)擬合比雙曲線擬合要好平方誤差為定義權(quán)函數(shù)：①

離散型/*discretetype*/根據(jù)一系列離散點(diǎn)擬合時(shí)，在每一誤差前乘一正數(shù)wi

，即誤差函數(shù)

，這個(gè)wi

就稱(chēng)作權(quán)