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

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

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

使得

li(xj)=ij

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

有n

個根x0…

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

divideddifference*/1階差商

/*the1stdivideddifferenceoffw.r.t.xi

andxj

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

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

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

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

求Hermite多項式的基本步驟：寫出相應于條件的hi(x)、hi(x)的組合形式；對每一個hi(x)、hi(x)找出盡可能多的條件給出的根；根據多項式的總階數和根的個數寫出表達式；根據尚未利用的條件解出表達式中的待定系數；最后完整寫出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現象Ln(x)f(x)分段低次插值§4PiecewisePolynomialApproximation

分段線性插值

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

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

分段Hermite插值

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

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

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

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

f(x)。但是①

m

很大；②

yi

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

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

而要使P(xi)yi

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

使最小/*minimaxproblem*/

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

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

-1.0410-1.26130.030735擬合的平方誤差為圖象如圖例3.在某化學反應里,測得生成物濃度y%與時間t的數據如下，試建立y關于t的經驗公式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兩邊取對數,得得即為擬合函數基函數為解法方程組得平方誤差為用最小二乘法得即無論從圖形還是從平方誤差考慮在本例中指數函數擬合比雙曲線擬合要好平方誤差為定義權函數：①

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

，即誤差函數

，這個wi

就稱作權