三次樣條插值算法詳解ppt課件

三次樣條插值,鑒于高次插值不收斂又不穩(wěn)定的特點(diǎn)，低次插值既具有收斂性又具有穩(wěn)定性，因此低次值更具有實(shí)用價(jià)值，但是低次插值的光滑性較差，比如分段線性插值多項(xiàng)式在插值區(qū)間中僅具有連續(xù)性，在插值節(jié)點(diǎn)處有棱角，一階導(dǎo)數(shù)不存在；分段三次Hermite插值多項(xiàng)式在插值區(qū)間中僅具有一階導(dǎo)數(shù)即一階光滑性但不具備二階光滑性，不能滿足某些實(shí)際應(yīng)用比如汽車(chē)、輪船、飛機(jī)等的外形中流線形設(shè)計(jì)。樣條是在二十世紀(jì)初期經(jīng)常用于圖樣設(shè)計(jì)的一種富有彈性的細(xì)長(zhǎng)條，多個(gè)樣條互相彎曲連接后沿其邊緣畫(huà)出的曲線就是三次樣條曲線。后來(lái)數(shù)學(xué)上對(duì)其進(jìn)行了抽象，定義了m次樣條函數(shù)，并成為數(shù)值逼近的重要研究分枝，進(jìn)一步擴(kuò)大了樣條函數(shù)的應(yīng)用范圍。,1,樣條函數(shù)的定義,定義4.1設(shè)區(qū)間a,b上給定一個(gè)節(jié)點(diǎn)劃分a=x0x1xn-1xn=b如果存在正整數(shù)k使得a,b上的分段函數(shù)s(x)滿足如下兩條：(1)在a,b上有直到k-1階連續(xù)導(dǎo)數(shù)。(2)在每個(gè)小區(qū)間xi,xi+1上是次數(shù)不大于k的多項(xiàng)式。則稱分段函數(shù)s(x)是以(2.6)為節(jié)點(diǎn)集的k次樣條函數(shù)。,2,三次樣條插值函數(shù)的定義,并且關(guān)于這個(gè)節(jié)點(diǎn)集的三次樣條函數(shù)s(x)滿足插值條件：,則稱這個(gè)三次樣條函數(shù)s(x)為三次樣條插值函數(shù)。,3,三次樣條插值函數(shù)的邊界條件,插值條件：,連續(xù)性條件：,一階導(dǎo)數(shù)連續(xù)條件：,二階導(dǎo)數(shù)連續(xù)條件：,4,（1）因?yàn)閟(x)在每個(gè)小區(qū)間上是一個(gè)次小于三次的多項(xiàng)式，故有四個(gè)未知系數(shù)；（2）因?yàn)閟(x)有n分段，從而共有4n個(gè)未知系數(shù)?。?）但插值條件與樣條條件僅給出4n-2個(gè)條件，無(wú)法定出4n個(gè)未知系數(shù)，還差2個(gè)條件！這2個(gè)條件我們用邊界條件給出！,5,通常我們對(duì)插值多項(xiàng)式在兩端點(diǎn)的狀態(tài)加以要求也就是所謂的邊界條件:,第一邊界條件：由區(qū)間端點(diǎn)處的一階導(dǎo)數(shù)給出即,6,第二邊界條件：由區(qū)間端點(diǎn)處的二階導(dǎo)數(shù)給出即,特殊情況為自然邊界條件：由區(qū)間端點(diǎn)處的二階導(dǎo)數(shù)恒為0給出即,7,這樣三次樣條插值問(wèn)題就分成三類！其實(shí)不止這三類!,第三類又稱周期邊界條件：由區(qū)間端點(diǎn)處的函數(shù)值或?qū)?shù)值滿足周期條件給出,8,樣條函數(shù)的例子,容易驗(yàn)證：,是滿足如下數(shù)據(jù)的第一類邊界樣條插值問(wèn)題解：,9,樣條函數(shù)的例子,10,通常有三轉(zhuǎn)角法、三彎矩法、B樣條基函數(shù)法。,三次樣條插值函數(shù)的求法,這三種方法的基本思想是類似的，都是通過(guò)待定某些參數(shù)來(lái)確定插值函數(shù)，但肯定不是待定4n個(gè)參數(shù)。而是利用已知條件將待定參數(shù)減小到最少。,比如：待定一階導(dǎo)數(shù)、待定二階導(dǎo)數(shù)、采用基函數(shù)方法來(lái)確定插值函數(shù)。,11,三轉(zhuǎn)角法:待定一階數(shù),為了確定三次樣條插值函數(shù)的表達(dá)式S(x)，我們采用待定系數(shù)法來(lái)求解，我們待定什么系數(shù)呢？,考慮到帶一階導(dǎo)數(shù)的分段三次Hermite插值多項(xiàng)式,12,我們采用待定一階導(dǎo)數(shù)的方法即設(shè),因?yàn)榉侄稳蜨ermite插值多項(xiàng)式已經(jīng)至少是一階連續(xù)可導(dǎo)了，為了讓它成為三次樣條函數(shù)只需確定節(jié)點(diǎn)處的一階導(dǎo)數(shù)使這些節(jié)點(diǎn)處的二階導(dǎo)數(shù)連續(xù)即可！,13,14,由于在內(nèi)部節(jié)點(diǎn)處二階導(dǎo)數(shù)連續(xù)條件：,整理化簡(jiǎn)后得：,15,稱為三轉(zhuǎn)角法基本方程組,以上推導(dǎo)還沒(méi)有考慮邊界條件！針對(duì)不同類型的三次樣條問(wèn)題，就可以導(dǎo)出不同的方程組！,16,第一類三次樣條插值問(wèn)題方程組,基本方程組化為n-1階方程組,由于已知：,化為矩陣形式,17,這是一個(gè)嚴(yán)格對(duì)角占優(yōu)的三對(duì)角方程組，用追趕法可以求解！,18,第二類三次樣條插值問(wèn)題的方程組,由于已知：,故得：,19,稍加整理得,聯(lián)合基本方程組得一個(gè)n+1階三對(duì)角方程組，化成矩陣形式為：仍然是嚴(yán)格對(duì)角占優(yōu),20,第三類樣條插值問(wèn)題的方程組,立即可得下式：,由于：,21,其中：,聯(lián)合基本方程得一個(gè)廣義三對(duì)角或周期三對(duì)角方程組：,這個(gè)方程組的系數(shù)矩陣仍然是嚴(yán)格對(duì)角占優(yōu)陣！,22,求解這些不同類型的樣條插值問(wèn)題的方程組，我們可得所要待定的一階導(dǎo)數(shù)：,稱為三次樣條插值問(wèn)題三轉(zhuǎn)角公式！,再代入S(x)的每一段表達(dá)式，就求得三次樣條函數(shù)的表達(dá)式!,23,例1.對(duì)于給定的節(jié)點(diǎn)及函數(shù)值,解:,這是自然邊界條件下的樣條問(wèn)題。,24,我們可以將上述計(jì)算列于表中：,25,由些得如下方程組：,利用三轉(zhuǎn)角公式：,26,同樣可以求得第三段表達(dá)式！,27,28,29,三彎矩法:待定二階導(dǎo)數(shù),選擇二階導(dǎo)數(shù)作為待定參數(shù):,由于三次樣條S(x)是三次多項(xiàng)式,故它的二階導(dǎo)數(shù)是一次多項(xiàng)式,從而,思考:(1)的原因?,30,31,從而推導(dǎo)出了三次樣條S(x)在第k個(gè)小區(qū)間xk,xk+1上的表達(dá)式為:,它的系數(shù)都是用二階導(dǎo)數(shù)與函數(shù)值表示!,32,對(duì)所有中間節(jié)點(diǎn)xk,k=1,2,n-1,左邊小區(qū)間與右邊小區(qū)間上的三次多項(xiàng)式的一階導(dǎo)數(shù)應(yīng)當(dāng)連續(xù)!,確定二階導(dǎo)數(shù),33,三彎矩法基本方程,注意到這個(gè)基本方程只包括了n-1個(gè)方程!但卻有n個(gè)二階導(dǎo)數(shù)需要待定,這是一個(gè)欠定方程組,還需要根據(jù)邊界條件再確定兩個(gè)方程!,34,曲率調(diào)整樣條,這種樣條的邊界條件是已知兩端點(diǎn)的二階導(dǎo)數(shù)值!,這樣從三彎矩基本方程可以導(dǎo)數(shù)確定其它n-2個(gè)待定參數(shù)的方程組:,35,自然樣條,這種樣條的邊界條件是:已知兩端點(diǎn)的二階導(dǎo)數(shù)值為0!,這樣從三彎矩基本方程可以導(dǎo)數(shù)確定其它n-2個(gè)待定參數(shù)的方程組:,36,固支樣條,這種樣條的邊界條件是:已知兩端點(diǎn)的一階導(dǎo)數(shù)值!,根據(jù)前面推導(dǎo)過(guò)程中得到的樣條函數(shù)S(x)的一階導(dǎo)數(shù)的表達(dá)式(2.11),得方程,37,固支樣條,這樣從三彎矩基本方程可以導(dǎo)數(shù)確定n個(gè)待定參數(shù)的方程組:,38,非扭結(jié)樣條,這種樣條的邊界條件是:要求樣條S(x)在開(kāi)始的兩個(gè)小區(qū)間x0,x1,x1,x2上的三階導(dǎo)數(shù)相同,在最后兩個(gè)小區(qū)間xn-2,xn-1,xn-1,xn上的三階導(dǎo)數(shù)相同.,對(duì)表達(dá)式(2.9)再求一次導(dǎo)數(shù)得方程,39,非扭結(jié)樣條,再由三彎矩基本方程,可得,40,周期樣條,這種樣條的邊界條件是:要求樣條S(x)及其導(dǎo)數(shù)是以區(qū)間長(zhǎng)度xn-x0為周期的函數(shù)即,這些條件可以確定如下兩個(gè)方程:,41,再由三彎矩基本方程,可得,周期樣條,42,在Matlab中數(shù)據(jù)點(diǎn)稱之為斷點(diǎn)。如果三次樣條插值沒(méi)有邊界條件，最常用的方法，就是采用非扭結(jié)（not-a-knot）條件。這個(gè)條件強(qiáng)迫第1個(gè)和第2個(gè)三次多項(xiàng)式的三階導(dǎo)數(shù)相等，對(duì)最后一個(gè)和倒數(shù)第2個(gè)三次多項(xiàng)式也做同樣地處理。Matlab中三次樣條插值也有現(xiàn)成的函數(shù)：y=interp1(x0,y0,x,spline)；y=spline(x0,y0,x)；pp=csape(x0,y0,conds),pp=csape(x0,y0,conds,valconds)，y=ppval(pp,x)。其中x0,y0是已知數(shù)據(jù)點(diǎn)，x是插值點(diǎn)，y是插值點(diǎn)的函數(shù)值。對(duì)于三次樣條插值，我們提倡使用函數(shù)csape，csape的返回值是pp形式，要求插值點(diǎn)的近似函數(shù)值，必須調(diào)用函數(shù)ppval。,MATLAB中三次樣條函數(shù)法實(shí)現(xiàn),43,pp=csape(x0,y0,conds,valconds)conds指定插值的邊界條件，其值可為：complete邊界為一階導(dǎo)數(shù)，一階導(dǎo)數(shù)的值在valconds參數(shù)中給出。not-a-knot非扭結(jié)條件periodic周期條件second邊界為二階導(dǎo)數(shù)，二階導(dǎo)數(shù)的值在valconds參數(shù)中給出，若忽略valconds參數(shù)，二階導(dǎo)數(shù)的缺省值為0,0。,MATLAB中三次樣條函數(shù)法實(shí)現(xiàn),44,例2：第一邊界條件的例題,clear;x=1,2,4,5;y=1,3,4,2;pp=csape(x,y,complete,17/8,-19/8);pp.coefs,MATLAB代碼,45,第一邊界條件的例題,pp=form:ppbreaks:1245coefs:3x4doublepieces:3order:4dim:1pp.coefs-0.125002.12501.0000-0.1250-0.37501.75003.00000.3750-1.1250-1.25004.0000,分段多項(xiàng)式結(jié)構(gòu)與系數(shù)矩陣,46,如下代碼求解上述樣條問(wèn)題：,例3：自然邊界條件例題,47,x=-4-3-2-101234;y=00.151.122.362.361.460.490.060;pp=csape(x,y,second);xx=-4:0.01:4;yy=ppval(pp,xx);holdon;plot(x,y,ok);plot(xx,yy,k-);holdoff;,MATLAB程序,48,pp=form:ppbreaks:-4-3-2-101234coefs:8x4doublepieces:8order:4dim:1,分段多項(xiàng)式結(jié)構(gòu)：,49,pp.coefs=0.180856038291610.00000000000000-0.030856038291610-0.084280191458030.542568114874820.511712076583210.15000000000000-0.393735272459500.289727540500741.344007731958761.120000000000000.14922128129602-0.891478276877760.742256995581742.360000000000000.13685014727540-0.44381443298969-0.593035714285712.360000000000000.13337812960236-0.03326399116348-1.070114138438881.46000000000000-0.060362665684830.36687039764359-0.736507731958760.49000000000000-0.061927466863030.18578240058910-0.183854933726070.06000000000000,分段多項(xiàng)式的系數(shù)矩陣：,50,圖像,51,例4：對(duì)如下Runge現(xiàn)象中的函數(shù)，求用n分點(diǎn)作節(jié)點(diǎn)的三次樣條插值多項(xiàng)式s3(x)的圖象。,取n=5,10,15,20等，將區(qū)間等分成n份，取分點(diǎn)作為插值節(jié)點(diǎn)，利用matlab函數(shù)csape()作出它的三次樣條插值函數(shù)，并作出這些插值函數(shù)與被插函數(shù)的圖像。,但由于插值節(jié)點(diǎn)數(shù)目較多，故不列出插值函數(shù)的表達(dá)式，只畫(huà)出它們的圖象與被插函數(shù)的圖象的復(fù)合，從這些圖象可以看出，隨著節(jié)點(diǎn)數(shù)目的增多，樣條插值函數(shù)圖象越來(lái)越符合被插函數(shù)，因此避免Runge現(xiàn)象，也就是說(shuō)三次樣條插值函數(shù)具有收斂性。,52,53,54,55,56