第4章 福大科學工程與計算-插值法

科學和工程計算第4章插值法插值法插值法是一種古老的數(shù)學方法，早在一千多年前的隋唐時期定制歷法時就廣泛應用了二次插值。劉焯將等距節(jié)點的二次插值應用于天文計算。插值理論卻是在17世紀微積分產(chǎn)生后才逐步發(fā)展起來的，Newton插值公式理論是當時的重要成果。由于計算機的使用以及航空、造船、精密儀器的加工，插值法在理論和實踐上都得到進一步發(fā)展，獲得了廣泛的應用。引言拉格朗日插值均差與牛頓插值公式埃爾米特插值分段低次插值三次樣條插值插值法求擬合這組數(shù)據(jù)的多項式能否存在一個性能優(yōu)良、便于計算的函數(shù)一、插值問題------(1)這就是插值問題,(1)式為插值條件,其插值函數(shù)的圖象如圖整體誤差的大小反映了插值函數(shù)的好壞為了使插值函數(shù)更方便在計算機上運算,一般插值函數(shù)都使用代數(shù)多項式和有理函數(shù)。x0x1x2x3x4xP(x)

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

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

使得

li(xj)=ij

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

有n

個根x0…

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

divideddifference*/1階差商

/*the1stdivideddifferenceoffw.r.t.xi

andxj

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

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

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

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

求Hermite多項式的基本步驟：寫出相應于條件的hi(x)、hi(x)的組合形式；對每一個hi(x)、hi(x)找出盡可能多的條件給出的根；根據(jù)多項式的總階數(shù)和根的個數(shù)寫出表達式；根據(jù)尚未利用的條件解出表達式中的待定系數(shù)；最后完整寫出H(x)。習題1:求不超過3次的多項式H(x),使它滿足插值條件習題2:求不超過2次的多項式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

越大，端點附近抖動越大，稱為Runge現(xiàn)象Ln(x)f(x)分段低次插值§4PiecewisePolynomialApproximation

分段線性插值

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

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

分段Hermite插值

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

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

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

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

f(x)。但是①

m

很大；②

yi

本身是測量值，不準確，即yi

f(xi)這時沒必要取P(xi)=yi,

而要使P(xi)yi

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

使最小/*minimaxproblem*/

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

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

-1.0410-1.26130.030735擬合的平方誤差為圖象如圖例3.在某化學反應里,測得生成物濃度y%與時間t的數(shù)據(jù)如下，試建立y關(guān)于t的經(jīng)驗公式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方案一：設baxxxPy+=)(求a

和b

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

/*linearization*/：令，則bXaY+就是個線性問題將化為后易解a

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

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

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

，即誤差函數(shù)

，這個wi

就稱作權(quán)