計(jì)算方法 數(shù)值分析 第五章考點(diǎn)總結(jié)CH.5

1、第六章 數(shù)值逼近問題（I）插值及其數(shù)值計(jì)算§1 插值的基本概念插值方法是數(shù)值分析中一個(gè)很古老的分支，它有著悠久的歷史。插值理論和方法也是現(xiàn)代數(shù)值分析中最基本的內(nèi)容之一，它在數(shù)值積分，曲線曲面擬合，求微分方程數(shù)值解等方面有著廣泛的應(yīng)用。在工程技術(shù)與科學(xué)研究中，有時(shí)對(duì)一個(gè)函數(shù)只知道它在某些點(diǎn)上的數(shù)值，為了進(jìn)一步研究其性質(zhì)，需要用其他函數(shù)去近似代替它，這時(shí)就可以用插值方法。有時(shí)候，雖然函數(shù)有解析表達(dá)式，但形式過于復(fù)雜，為了便于處理，先在某些點(diǎn)上取值作表格函數(shù)，再通過插值建立易于處理的新函數(shù)，這也是插值理論的一個(gè)應(yīng)用。先介紹一般的插值概念。設(shè)，。已知它在個(gè)互異的點(diǎn)，處的函數(shù)值，即：， ，1，

2、n求解插值問題就是從函數(shù)類中求使， ，1，n （1.1）這里的稱為被插函數(shù)，稱為插值區(qū)間，1，n，稱為插值節(jié)點(diǎn)，（1.1）式稱為插值條件，而和分別為插值函數(shù)和插值函數(shù)類。通常選定的插值函數(shù)類是有限維線性空間，它可看成是某一組基張成的線性空間：對(duì)，有使得于是確定函數(shù)歸結(jié)為確定數(shù)列。從理論上看，插值問題包含以下內(nèi)容：（1）確定的基，一般地說基不唯一，選擇合適的基可以簡(jiǎn)化問題的解法；（2）討論滿足（1.1）的的存在性，求法及唯一性；（3）尋找插值問題的截?cái)嗾`差，即余項(xiàng)：的表達(dá)式與估計(jì)。§2 多項(xiàng)式插值本節(jié)選取常用的多項(xiàng)式函數(shù)類作插值函數(shù)類。多項(xiàng)式函數(shù)屬于解析函數(shù)類，形式簡(jiǎn)單，計(jì)算方便，其導(dǎo)

3、數(shù)與不定積分易于求出。下面把不超過n次的多項(xiàng)式函數(shù)類記為2.1 Lagrange插值設(shè)已知，在相異節(jié)點(diǎn)，上的函數(shù)值，1，n，取=，下面求的插值函數(shù)。設(shè)，插值的基本問題是，尋求如上的，使得，1，n.該問題等價(jià)于求解下列線性方程組：上述線性方程組的系數(shù)矩陣為：A的行列式為（稱為Vandermonde 行列式）根據(jù)線性代數(shù)的知識(shí)知道注意到諸互不相同，從而，上述線性方程組存在唯一解。這說明滿足條件（1.1）的插值多項(xiàng)式是存在的，而且還是唯一的。定理2.1 設(shè)， 為上的n+1個(gè)相異的節(jié)點(diǎn)，i=0，1，n，則滿足，i=0，1，n的是存在并且唯一的。從定理2.1的證明可看到，要求插值多項(xiàng)式p(x),可以通過

4、求解一個(gè)線性方程組得到。但這樣做不但計(jì)算復(fù)雜，且難于得到p(x)的簡(jiǎn)單表達(dá)式。為了求得便于使用的簡(jiǎn)單的插值多項(xiàng)式p(x)，可以如§1所述，選擇的適當(dāng)?shù)幕?。先?gòu)造n次插值基函數(shù) ，i=0，1，n使， ，1，n， （2.1）由當(dāng)時(shí)，可知： ，1，n （2.2）其中是待定常數(shù)，它可由定出：；，1，n。代入（2.2）得： i=0，1，n再作易知，即為所求的插值函數(shù)。這種具有性質(zhì)的基稱為對(duì)偶基，以后我們還會(huì)多次構(gòu)造針對(duì)不同問題的對(duì)偶基。記 ，則， i=0，1，n，例2.1 已知，節(jié)點(diǎn)為，求解 ，。2.2 插值多項(xiàng)式的插值余項(xiàng)現(xiàn)在考慮用近似所產(chǎn)生的誤差，即插值余項(xiàng)當(dāng)在上n+1階可導(dǎo)時(shí)，可以把化為

5、便于估計(jì)的形式，先設(shè)，i=0，1，n，作輔助函數(shù)，其中滿足： （2.3）當(dāng)x不為插值節(jié)點(diǎn)時(shí)，這樣的是存在的。于是，是的n+2個(gè)相異的零點(diǎn)，依次對(duì)，應(yīng)用Rolle定理可知存在使0=從而代入（2.3）式得：，若x等于某一，則，故任取上式也成立。于是得出：定理2.2（多項(xiàng)式插值的余項(xiàng)） 設(shè)在上n+1階可導(dǎo)，則存在使注：由上式可知，當(dāng)時(shí)，特別當(dāng)時(shí)，可得： （2.4）例2.2 考察四位常用對(duì)數(shù)表作線性插值的誤差。解 設(shè)，0.4343。設(shè)x位于和之間：1，則，記表距，得=當(dāng)h=0.01時(shí)， （2.5）再考慮舍入誤差，設(shè)， i=0，1其中是表值，是舍入誤差，則：，i=0，1 （2.6）把以，i=0，1構(gòu)造的

6、線性插值分別記為，注意到，i=0，1在上非負(fù)及（2.5），（2.6）式，則線性插值的舍入誤差=可見舍入誤差比截?cái)嗾`差大一個(gè)量級(jí)。此時(shí)整個(gè)誤差不超過2.3 Newton插值Lagrange插值公式的缺點(diǎn)是，當(dāng)插值節(jié)點(diǎn)的個(gè)數(shù)有所變動(dòng)時(shí)（例如為了提高精度，有時(shí)需要增加節(jié)點(diǎn)個(gè)數(shù)），Lagrange插值基函數(shù)，i=0，1，n就要隨之發(fā)生變化，從而整個(gè)公式的結(jié)構(gòu)也要發(fā)生變化，這在計(jì)算實(shí)踐中是不方便的。為了克服上述缺點(diǎn)，在這一節(jié)中我們引入Newton插值公式。顯然，n+1個(gè)節(jié)點(diǎn)，上的n次插值多項(xiàng)式也可以寫成下列形式：令表示n個(gè)節(jié)點(diǎn)，上的n-1次插值多項(xiàng)式，由于， i=0，1，n-1所以此處c為常數(shù)，由條件，

7、可以定出又因 引進(jìn)記號(hào) （2.8）得與之間的關(guān)系式：同理繼續(xù)下去，最終得到 （2.9）公式（2.9）就是Newton型插值公式。系數(shù)由（2.8）式確定。Newton插值公式的系數(shù)很不好記，因此有必要另找方法確定它們，為此我們引進(jìn)差商的概念，并指出Newton插值公式中各系數(shù)，i=0，1，n即是的i階差商。設(shè)已知不同的自變量上的函數(shù)值，i=0，1，n，稱，為的一階差商（式均差）。一階差商的一階差商叫做的二階差商。一般說來，我們稱n-1階差商的一階差商為函數(shù)的n階差商。用數(shù)學(xué)歸納法易證明n階差商可由（2.8）式的右端表出。使用前面的記號(hào)也可將它寫成為了作數(shù)值計(jì)算常利用形式如下的差商表x一階差商二階

8、差商三階差商插值公式（2.9）中的系數(shù)就是上表中帶下劃線的項(xiàng)。因此當(dāng)已知，i=0，1，n時(shí)，利用差商表可以很容易地算出的各階差商的值，而不必去記憶公式（2.8）。因?yàn)樵趎+1個(gè)不同的點(diǎn)，上取給定值的次數(shù)不超過n的多項(xiàng)式是唯一的，所以次數(shù)相同的Newton插值多項(xiàng)式與Lagrange插值多項(xiàng)式是恒等的，它們的差異僅是書寫形式不同而已，但是這種差異卻為計(jì)算實(shí)踐帶來了很大的方便，實(shí)際上，對(duì)于Newton插值公式來說，當(dāng)需要增加一個(gè)插值點(diǎn)時(shí)，只需要在原插值多項(xiàng)式的后面再添加一個(gè)新項(xiàng)就可以了。2.6 Hermite插值為了理論和應(yīng)用上的需要，有時(shí)不但要求插值函數(shù)p(x)在節(jié)點(diǎn)處的函數(shù)值與被插值函數(shù)f(x

9、)相同，而且要求在節(jié)點(diǎn)處的導(dǎo)數(shù)值也相等，這就導(dǎo)致了下面的Hermite插值。給定 f(x) 在n1 個(gè)互異的節(jié)點(diǎn)處的函數(shù)值及導(dǎo)數(shù)值，i=0，1，n， 要求一個(gè)次數(shù)不超過2n1次的多項(xiàng)式 滿足， i=0，1，n， （219）我們從構(gòu)造Lagrange插值多項(xiàng)式的方法得到啟發(fā)，設(shè)法構(gòu)造Hermite插值問題的對(duì)偶基。即構(gòu)造兩組次數(shù)都是2n1次的多項(xiàng)式 i=0，1，n 使其滿足： i，j=0，1，n （220）則滿足插值條件（2.19）的2n1次多項(xiàng)式就是 （221）由（220）知是的二重零點(diǎn)，因此可設(shè)其中a，b為待定常數(shù)， j=0，1，n是2.1節(jié)中定義的n次Lagrange插值基函數(shù)，于是只要選

10、擇常數(shù)a，b滿足整理有解上述方程得：類似于上述做法，令：同理可求得將a,b,c,d代入（2.21）并整理可得定理2.4 Hermite插值問題（2.19）的解是存在且唯一的。證明 存在性上面已證。為證唯一性，假設(shè)有另一也滿足條件（2.19），令：，易知是的二重零點(diǎn)，于是，次數(shù)不超過2n1的多項(xiàng)式有2n2 個(gè)零點(diǎn)，必從而。Hermite插值函數(shù)的誤差與Lagrange插值的誤差估計(jì)十分類似，有如下定理，讀者可仿照定理2.2自己證明。定理2.5 （Hermite插值的余項(xiàng)） 設(shè)在上2n+2階可導(dǎo)，x和諸皆位于區(qū)間內(nèi)，則存在使 2.7 Newton-Hermite插值公式本節(jié)討論一類具有重節(jié)點(diǎn)的多項(xiàng)

11、式插值方法，即Newton-Hermite插值方法。因?yàn)榇祟惒逯祮栴}要求在節(jié)點(diǎn)處滿足任意給定的導(dǎo)數(shù)條件，所以也常被稱為切觸插值問題。設(shè) （2.22），為事先指定的實(shí)數(shù)，其中為正整數(shù) （2.23）我們要構(gòu)造一個(gè)次數(shù)不高于n的多項(xiàng)式，使， （2.24）下面我們用類似于Newton插值的方法來解這個(gè)問題。第一步：根據(jù)（2.22），（2.24）式寫出數(shù)列 （2.25）（2.25）中，連續(xù)寫次，再將（2.25）中的數(shù)據(jù)重新順序編號(hào)，得到 （2.26）（2.26）稱為有重節(jié)點(diǎn)的插值節(jié)點(diǎn)組。第二步：對(duì)于節(jié)點(diǎn)組（2.26）和插值條件（2.24），用2.3節(jié)中同樣的方法作出差商表。這里對(duì)重節(jié)點(diǎn)的差商作補(bǔ)充規(guī)定：

12、第三步：寫出形如（2.10）的，就是所要求的Newton-Hermite插值多項(xiàng)式例2.5 設(shè)節(jié)點(diǎn)為，設(shè)求，使， ，。解 重寫節(jié)點(diǎn)組并作差商表：x一階差商二階差商三階差商四階差商五階差商-3-3 -3 02 02 1 111 0 即為所求之插值多項(xiàng)式。§3 分段線性插值討論了Lagrange插值法以后，自然會(huì)問：當(dāng)插值節(jié)點(diǎn)無(wú)限加密時(shí)，必在上收斂于嗎？即使對(duì)于性質(zhì)很好的函數(shù)，答案也是否定的。Runge指出，無(wú)窮次可微函數(shù)在上用等距節(jié)點(diǎn)插值時(shí)，在區(qū)間兩端會(huì)產(chǎn)生劇烈振蕩的現(xiàn)象。圖3.1給出了與的示意圖。可以證明：在等距節(jié)點(diǎn)下當(dāng)時(shí)，收斂于。而>時(shí)不收斂。圖3.1因此在實(shí)際實(shí)用中，往往不

13、采用高次插值多項(xiàng)式，而改用分段的低次插值多項(xiàng)式去近似函數(shù)。由于分段的低次插值多項(xiàng)式對(duì)函數(shù)通常有較好的逼近性態(tài)，因而近年來有著十分廣泛的應(yīng)用。其中突出的如樣條函數(shù)。本段先介紹分段線性插值。設(shè)，已知它在節(jié)點(diǎn)上的函數(shù)值，i=0，1，n。試求，使（1），i=0，1，n；（2）在，i=0，1，n上是一次多項(xiàng)式。滿足上述條件的稱之為在上以為節(jié)點(diǎn)的分段線性插值多項(xiàng)式。滿足所述條件的是存在的，只要把在，i=0，1，n-1上的線性插值多項(xiàng)式逐段拼接起來就得出了。，i=0，1，n1；對(duì)于分段線性插值多項(xiàng)式我們也可以構(gòu)造型的基，只要令： j=1，2，n-1 顯然有 i,j=0，1，n。因此可表示為記，i=0，1，n

14、-1，。對(duì)于時(shí)趨向于的收斂問題，有定理3.1 （分段線性插值收斂的充分條件）若在上連續(xù)，則當(dāng)時(shí)，在上一致收斂于。證 由的連續(xù)性，i=0，1，n-1，使和分別取得在上的最大值和最小值，于是，再由在上的一致連續(xù)性，0，0使，時(shí)，有。于是當(dāng)h時(shí)，使 證畢。由定理3.1 可知，剛才我們討論的Runge函數(shù)，它在等距節(jié)點(diǎn)組上的n次插值多項(xiàng)式不收斂，而其在同一節(jié)點(diǎn)組上的分段線性插值多項(xiàng)式一致收斂于。§4 三次樣條插值雖然分段線性插值較好地解決了收斂問題，但是在內(nèi)節(jié)點(diǎn)上通常是不可導(dǎo)的。而在實(shí)際應(yīng)用中，如高速飛行器的機(jī)翼設(shè)計(jì)、船體放樣等，需要分段插值函數(shù)有二階可導(dǎo)性。為此，下面討論三次樣條插值。4.

15、1 三次樣條函數(shù)樣條（Spline）本來是在船體放樣繪制光滑曲線時(shí)用的一種細(xì)木條。用壓鐵把細(xì)木條固定在一些已知點(diǎn)上，細(xì)木條就形成一條相當(dāng)光滑的曲線。數(shù)學(xué)上的樣條函數(shù)是從這個(gè)物理模型中抽象出來的，其中常用的三次樣條函數(shù)的定義如下：對(duì)函數(shù)，與上的一組節(jié)點(diǎn)：若（1）在，i=0，1，n-1上都是三次多項(xiàng)式，（2）在上有二階連續(xù)導(dǎo)函數(shù)，則稱為上以為節(jié)點(diǎn)的三次樣條函數(shù)。若再要求：（3）， i=0，1，n則稱為上以為節(jié)點(diǎn)的的插值三次樣條函數(shù)。4.2 三次樣條插值的計(jì)算設(shè)給定一區(qū)間，且任意給定一組常數(shù)，要求構(gòu)造一個(gè)插值三次樣條函數(shù)，使得如下插值條件得以滿足：，j=0，1，n （4.1）今以表示，j=0，1，n

16、 。由于為分段3次多項(xiàng)式，所以在區(qū)間上為一線性函數(shù)。因而它可由過與兩點(diǎn)的線性插值函數(shù) （） （4.2）所決定，其中。為了最后求出在上的表達(dá)式，只須對(duì)（4.2）式積分兩次，并定出積分常數(shù)就夠了。當(dāng)時(shí)， （4.3） （4.4）由（4.3）可知，為求，關(guān)鍵是設(shè)法確定各個(gè)，j=0，1，n。而為了求得各個(gè)，必須引用樣條節(jié)點(diǎn)處的光滑連接條件 （4.5）按（4.4）有由（4.5）可得連續(xù)性方程 j=1，n1 （4.6）它給出了n+1個(gè)未知數(shù)，j=0，1，n的n-1個(gè)方程式，按它尚不足以唯一確定。還須補(bǔ)充兩個(gè)“邊界條件”，這有下述幾種情況：（1）假定。于是按照前面公式，可得方程： （47）（2）假定，相當(dāng)于直

17、接給出， .無(wú)論（1）或（2），均可概括為 （4.8）引入記號(hào)，j=1，2，n-1 （4.9）則（4.6）可改寫為 j=1，2，n-1 （4.10）所以由（4.8），（4.10）確定的線性方程組為 = （4.11）其中，j=0，1，n-1表示（4.11）的右端項(xiàng)。如果滿足條件 j=0，1，2. （4.12）則稱之為以b-a為周期的三次周期樣條函數(shù)。顯然，對(duì)于3次周期樣條函數(shù)，應(yīng)該要求（4.10）對(duì)j=n的情況也成立，如果再注意到的性質(zhì)，而把（4.10）中的換成，則相應(yīng)于3次周期樣條函數(shù)的方程組為 = （4.13）其中線性代數(shù)方程組（4.11）?？捎米汾s法來求解，而方程組（4.13）則可把先作為

18、參數(shù)，求解其中n-1個(gè)方程中的n-1個(gè)未知數(shù)，（其解依賴于），然后代入最后一個(gè)方程以求出，同時(shí)，也隨之確定了。4.3 誤差界與收斂性三次樣條函數(shù)的收斂性與誤差估計(jì)比較復(fù)雜，這里不加證明地給出一個(gè)主要結(jié)果。定理4.1 設(shè)，為滿足第一類或第二類邊界條件的三次插值樣條函數(shù)，令，則有估計(jì)式其中這個(gè)定理不但給出了三次樣條插值函數(shù)S(x)的誤差估計(jì)，且指出了當(dāng)時(shí)，S(x) 及其一階導(dǎo)數(shù)S(x) 和二階導(dǎo)數(shù)S(x) 均分別一致收斂于f(x)，f(x)，f(x).B-樣條函數(shù)空間上面導(dǎo)出的三次樣條插值函數(shù)分別在每個(gè)子區(qū)間上有一表達(dá)式，這在應(yīng)用上和理論分析中都很不方便，如果利用基函數(shù)表示往往更為方便。設(shè)給定一組節(jié)點(diǎn) （5.1）又設(shè)分段函數(shù)滿足條件：1于每個(gè)區(qū)間，j=0，N上，是一個(gè)次數(shù)不超過n的實(shí)系數(shù)代數(shù)多項(xiàng)式；2于上具有直到n-1階的連續(xù)