三次樣條插值算法詳解.ppt

1、b,1,三次樣條插值,鑒于高次插值不收斂又不穩(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)用范

2、圍。,b,2,樣條函數(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ù)。,b,3,三次樣條插值函數(shù)的定義,并且關(guān)于這個(gè)節(jié)點(diǎn)集的三次樣條函數(shù)s(x)滿足插值條件：,則稱這個(gè)三次樣條函數(shù)s(x)為三次樣條插值函數(shù)。,b,4,三次樣條插值函數(shù)的邊界條件,插值條件：,連續(xù)性條件：,一階導(dǎo)數(shù)連續(xù)條件：,二階導(dǎo)數(shù)連續(xù)條件：,b,5,（1）因?yàn)閟(x)在每個(gè)

3、小區(qū)間上是一個(gè)次小于三次的多項(xiàng)式，故有四個(gè)未知系數(shù)； （2）因?yàn)閟(x)有n分段，從而共有4n個(gè)未知系數(shù)！ （3）但插值條件與樣條條件僅給出4n-2個(gè)條件，無(wú)法定出4n個(gè)未知系數(shù)，還差2個(gè)條件！這2個(gè)條件我們用邊界條件給出！,b,6,通常我們對(duì)插值多項(xiàng)式在兩端點(diǎn)的狀態(tài)加以要求也就是 所謂的邊界條件:,第一邊界條件：由區(qū)間端點(diǎn)處的一階導(dǎo)數(shù)給出即,b,7,第二邊界條件：由區(qū)間端點(diǎn)處的二階導(dǎo)數(shù)給出即,特殊情況為自然邊界條件： 由區(qū)間端點(diǎn)處的二階導(dǎo)數(shù)恒為0給出即,b,8,這樣三次樣條插值問(wèn)題就分成三類！其實(shí)不止這三類!,第三類又稱周期邊界條件： 由區(qū)間端點(diǎn)處的函數(shù)值或?qū)?shù)值滿足周期條件給出,b,9,樣

4、條函數(shù)的例子,容易驗(yàn)證：,是滿足如下數(shù)據(jù)的第一類邊界樣條插值問(wèn)題解：,b,10,樣條函數(shù)的例子,b,11,通常有三轉(zhuǎn)角法、三彎矩法、B樣條基函數(shù)法。,三次樣條插值函數(shù)的求法,這三種方法的基本思想是類似的，都是通過(guò)待定某些參數(shù)來(lái)確定插值函數(shù)，但肯定不是待定4n個(gè)參數(shù)。而是利用已知條件將待定參數(shù)減小到最少。,比如：待定一階導(dǎo)數(shù)、待定二階導(dǎo)數(shù)、采用基函數(shù)方法來(lái)確定插值函數(shù)。,b,12,三轉(zhuǎn)角法:待定一階數(shù),為了確定三次樣條插值函數(shù)的表達(dá)式 S(x)， 我們采用待定系數(shù)法來(lái)求解，我們待定什么系數(shù)呢？,考慮到帶一階導(dǎo)數(shù)的分段三次Hermite插值多項(xiàng)式,b,13,我們采用待定一階導(dǎo)數(shù)的方法即設(shè),因?yàn)榉侄?/p>

5、三次Hermite插值多項(xiàng)式已經(jīng)至少是一階連續(xù)可導(dǎo)了，為了讓它成為三次樣條函數(shù)只需確定節(jié)點(diǎn)處的一階導(dǎo)數(shù)使這些節(jié)點(diǎn)處的二階導(dǎo)數(shù)連續(xù)即可！,b,14,b,15,由于在內(nèi)部節(jié)點(diǎn)處二階導(dǎo)數(shù)連續(xù)條件：,整理化簡(jiǎn)后得：,b,16,稱為三轉(zhuǎn)角法基本方程組,以上推導(dǎo)還沒(méi)有考慮邊界條件！針對(duì)不同類型的三次樣條問(wèn)題，就可以導(dǎo)出不同的方程組！,b,17,第一類三次樣條插值問(wèn)題方程組,基本方程組化為n-1階方程組,由于已知：,化為矩陣形式,b,18,這是一個(gè)嚴(yán)格對(duì)角占優(yōu)的三對(duì)角方程組， 用追趕法可以求解！,b,19,第二類三次樣條插值問(wèn)題的方程組,由于已知：,故得：,b,20,稍加整理得,聯(lián)合基本方程組得一個(gè)n+1階

6、三對(duì)角方程組， 化成矩陣形式為：仍然是嚴(yán)格對(duì)角占優(yōu),b,21,第三類樣條插值問(wèn)題的方程組,立即可得下式：,由于：,b,22,其中：,聯(lián)合基本方程得一個(gè)廣義三對(duì)角或周期三對(duì)角方程組：,這個(gè)方程組的系數(shù)矩陣仍然是嚴(yán)格對(duì)角占優(yōu)陣！,b,23,求解這些不同類型的樣條插值問(wèn)題的方程組，我們可得 所要待定的一階導(dǎo)數(shù)：,稱為三次樣條插值問(wèn)題三轉(zhuǎn)角公式！,再代入S(x)的每一段表達(dá)式，就求得三次樣條函數(shù)的表達(dá)式!,b,24,例1. 對(duì)于給定的節(jié)點(diǎn)及函數(shù)值,解:,這是自然邊界條件下的樣條問(wèn)題。,b,25,我們可以將上述計(jì)算列于表中：,b,26,由些得如下方程組：,利用三轉(zhuǎn)角公式：,b,27,同樣可以求得第三段表

7、達(dá)式！,b,28,b,29,b,30,三彎矩法:待定二階導(dǎo)數(shù),選擇二階導(dǎo)數(shù)作為待定參數(shù):,由于三次樣條S(x)是三次多項(xiàng)式,故它的二階導(dǎo)數(shù)是一次多項(xiàng)式,從而,思考:(1)的原因?,b,31,b,32,從而推導(dǎo)出了三次樣條S(x)在第k個(gè)小區(qū)間xk,xk+1上的表達(dá)式為:,它的系數(shù)都是用二階導(dǎo)數(shù)與函數(shù)值表示!,b,33,對(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ù),b,34,三彎矩法基本方程,注意到這個(gè)基本方程只包括了n-1個(gè)方程!但卻有n個(gè)二階導(dǎo)數(shù)需要待定,這是一個(gè)欠定方程組,還需要根據(jù)邊界條件再確定兩個(gè)方程!,b,35,曲率調(diào)

8、整樣條,這種樣條的邊界條件是已知兩端點(diǎn)的二階導(dǎo)數(shù)值!,這樣從三彎矩基本方程可以導(dǎo)數(shù)確定其它n-2個(gè)待定參數(shù)的方程組:,b,36,自然樣條,這種樣條的邊界條件是:已知兩端點(diǎn)的二階導(dǎo)數(shù)值為0!,這樣從三彎矩基本方程可以導(dǎo)數(shù)確定其它n-2個(gè)待定參數(shù)的方程組:,b,37,固支樣條,這種樣條的邊界條件是:已知兩端點(diǎn)的一階導(dǎo)數(shù)值!,根據(jù)前面推導(dǎo)過(guò)程中得到的樣條函數(shù)S(x)的一階導(dǎo)數(shù)的表達(dá)式(2.11),得方程,b,38,固支樣條,這樣從三彎矩基本方程可以導(dǎo)數(shù)確定n個(gè)待定參數(shù)的方程組:,b,39,非扭結(jié)樣條,這種樣條的邊界條件是:要求樣條S(x)在開(kāi)始的兩個(gè)小區(qū)間x0,x1,x1,x2上的三階導(dǎo)數(shù)相同,在最

9、后兩個(gè)小區(qū)間xn-2,xn-1,xn-1,xn上的三階導(dǎo)數(shù)相同.,對(duì)表達(dá)式(2.9)再求一次導(dǎo)數(shù)得方程,b,40,非扭結(jié)樣條,再由三彎矩基本方程,可得,b,41,周期樣條,這種樣條的邊界條件是:要求樣條S(x)及其導(dǎo)數(shù)是以區(qū)間長(zhǎng)度xn-x0為周期的函數(shù)即,這些條件可以確定如下兩個(gè)方程:,b,42,再由三彎矩基本方程,可得,周期樣條,b,43,在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)

10、成的函數(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),b,44,pp=csape(x0,y0,conds,valconds) conds指定插值的邊界條件，其值可為： complete 邊

11、界為一階導(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),b,45,例2：第一邊界條件的例題,clear; x=1,2,4,5; y=1,3,4,2; pp=csape(x,y,complete,17/8,-19/8); pp.coefs,MATLAB代碼,b,46,第一邊界條件的例題,pp = form: pp breaks: 1 2 4 5 coefs: 3x4 do

12、uble pieces: 3 order: 4 dim: 1 pp.coefs -0.1250 0 2.1250 1.0000 -0.1250 -0.3750 1.7500 3.0000 0.3750 -1.1250 -1.2500 4.0000,分段多項(xiàng)式結(jié)構(gòu)與系數(shù)矩陣,b,47,如下代碼求解上述樣條問(wèn)題：,例3：自然邊界條件例題,b,48,x=-4 -3 -2 -1 0 1 2 3 4; y=0 0.15 1.12 2.36 2.36 1.46 0.49 0.06 0; pp=csape(x,y,second); xx=-4:0.01:4; yy=ppval(pp,xx); hold on

13、; plot(x,y,ok); plot(xx,yy,k-); hold off;,MATLAB程序,b,49,pp = form: pp breaks: -4 -3 -2 -1 0 1 2 3 4 coefs: 8x4 double pieces: 8 order: 4 dim: 1,分段多項(xiàng)式結(jié)構(gòu)：,b,50,pp.coefs= 0.18085603829161 0.00000000000000 -0.03085603829161 0 -0.08428019145803 0.54256811487482 0.51171207658321 0.15000000000000 -0.393735

14、27245950 0.28972754050074 1.34400773195876 1.12000000000000 0.14922128129602 -0.89147827687776 0.74225699558174 2.36000000000000 0.13685014727540 -0.44381443298969 -0.59303571428571 2.36000000000000 0.13337812960236 -0.03326399116348 -1.07011413843888 1.46000000000000 -0.06036266568483 0.36687039764

15、359 -0.73650773195876 0.49000000000000 -0.06192746686303 0.18578240058910 -0.18385493372607 0.06000000000000,分段多項(xiàng)式的系數(shù)矩陣：,b,51,圖像,b,52,例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ù)具有收斂性。,b,53,b,54,b,