數(shù)值計(jì)算_第5章插值

1、第5章  插  值5.1引言在實(shí)際問題中，有時(shí)只能給出函數(shù)在平面上的一些離散點(diǎn)的值，而不能給出的具體解析表達(dá)式，或者的表達(dá)式過于復(fù)雜而難于運(yùn)算。這時(shí)我們需要用近似函數(shù)來逼近函數(shù)，在數(shù)學(xué)上常用的函數(shù)逼近的方法有：· 插值。 · 一致逼近。 · 均方逼近或稱最小乘法。 什么是插值？簡單地說，用給定的未知函數(shù)的若干函數(shù)值的點(diǎn)構(gòu)造的近似函數(shù)要求與在給定點(diǎn)的函數(shù)值相等，則稱函數(shù)為插值函數(shù)。例如：在服裝店訂做風(fēng)衣時(shí)，選擇好風(fēng)衣的樣式后，服裝師量出并記下你的胸圍、衣長和袖長等幾個(gè)尺寸，這幾個(gè)尺寸就是風(fēng)衣函數(shù)的插值點(diǎn)數(shù)值，在衣料上畫出的裁剪線就是服裝師構(gòu)造的插

2、值函數(shù)，裁剪水平的差別就在于量準(zhǔn)插值點(diǎn)和構(gòu)造合乎身材的插值函數(shù)。定義5.1 為定義在區(qū)間上的函數(shù)，為上個(gè)互不相同的點(diǎn)，為給定的某一函數(shù)類。若上有函數(shù)，滿足則稱為關(guān)于節(jié)點(diǎn)在上的插值函數(shù)；稱點(diǎn)為插值節(jié)點(diǎn)；稱，為插值型值點(diǎn)，簡稱型值點(diǎn)或插點(diǎn)；稱為被插函數(shù)。這樣，對函數(shù)在區(qū)間上的各種計(jì)算，就用對插值函數(shù)的計(jì)算取而代之。構(gòu)造插值函數(shù)需要關(guān)心下列問題：· 插值函數(shù)是否存在？ · 插值函數(shù)是否唯一？ · 如何表示插值函數(shù)？ 如何估計(jì)被插函數(shù)與插值函數(shù)的誤差？5.2拉格朗日（Lagrange）插值可對插值函數(shù)選擇多種不同的函數(shù)類型，由于代數(shù)多項(xiàng)式具有簡單和一些良好的特性，例如，多

3、項(xiàng)式是無窮光滑的，容易計(jì)算它的導(dǎo)數(shù)和積分，故常選用代數(shù)多項(xiàng)式作為插值函數(shù)。5.2.1 線性插值問題5.1 給定兩個(gè)插值點(diǎn)其中，怎樣做通過這兩點(diǎn)的一次插值函數(shù)？過兩點(diǎn)作一條直線，這條直線就是通過這兩點(diǎn)的一次多項(xiàng)式插值函數(shù)，簡稱線性插值。如圖5.1所示。圖5.1 線性插值函數(shù)在初等數(shù)學(xué)中，可用兩點(diǎn)式、點(diǎn)斜式或截距式構(gòu)造通過兩點(diǎn)的一條直線。下面先用待定系數(shù)法構(gòu)造插值直線。設(shè)直線方程為，將分別代入直線方程得：當(dāng)時(shí)，因，所以方程組有解，而且解是唯一的。這也表明，平面上兩個(gè)點(diǎn)，有且僅有一條直線通過。用待定系數(shù)法構(gòu)造插值多項(xiàng)式的方法簡單直觀，容易看到解的存在性和惟一性，但要解一個(gè)方程組才能得到插值函數(shù)的系數(shù)

4、，因工作量較大和不便向高階推廣，故這種構(gòu)造方法通常不宜采用。當(dāng)時(shí)，若用兩點(diǎn)式表示這條直線，則有：                    （5.1）這種形式稱為拉格朗日插值多項(xiàng)式。，稱為插值基函數(shù)，計(jì)算，的值，易見                

5、60;    （5.2）在拉格朗日插值多項(xiàng)式中可將看做兩條直線，的疊加，并可看到兩個(gè)插值點(diǎn)的作用和地位都是平等的。拉格朗日插值多項(xiàng)式型式免除了解方程組的計(jì)算，易于向高次插值多項(xiàng)式型式推廣。線性插值誤差定理5.1 記為以為插值點(diǎn)的插值函數(shù)，。這里，設(shè) 一階連續(xù)可導(dǎo)， 在上存在，則對任意給定的，至少存在一點(diǎn) ，使     （5.3）證明 令，因是的根，所以可設(shè)對任何一個(gè)固定的點(diǎn)，引進(jìn)輔助函數(shù)：則。由定義可得，這樣至少有3個(gè)零點(diǎn)，不失一般性，假定，分別在和上應(yīng)用洛爾定理，可知在每個(gè)區(qū)間至少存在一個(gè)零點(diǎn)，不妨記為和，即和，

6、對在上應(yīng)用洛爾定理，得到在上至少有一個(gè)零點(diǎn)，?，F(xiàn)在對求二次導(dǎo)數(shù)，其中的線性函數(shù))，故有代入，得        所以          即                  5.2.2 二次插值問題5.2 給定三個(gè)插值點(diǎn) ，,其中互不相等，怎樣構(gòu)造函數(shù)的二次的（

7、拋物線）插值多項(xiàng)式？平面上的三個(gè)點(diǎn)能確定一條次曲線，如圖5.2所示。圖5.2 三個(gè)插值點(diǎn)的二次插值仿造線性插值的拉格朗日插值，即用插值基函數(shù)的方法構(gòu)造插值多項(xiàng)式。設(shè) 每個(gè)基函數(shù)是一個(gè)二次函數(shù)，對來說，要求是它的零點(diǎn)，因此可設(shè)同理，也相對應(yīng)的形式，得將代入，得同理將代入得到和的值，以及和的表達(dá)式。  也容易驗(yàn)證：插值基函數(shù)仍然滿足：二次插值函數(shù)誤差：上式證明完全類似于線性插值誤差的證明，故省略。插值作為函數(shù)逼近方法，常用來作函數(shù)的近似計(jì)算。當(dāng)計(jì)算點(diǎn)落在插值點(diǎn)區(qū)間之內(nèi)時(shí)叫做內(nèi)插，否則叫做外插。內(nèi)插的效果一般優(yōu)于外插。例5.1 給定。構(gòu)造線性插值函數(shù)并用插值函數(shù)計(jì)算和解：構(gòu)造線性

8、插值函數(shù)：分別將代入上式，得，準(zhǔn)確值，準(zhǔn)確值例5.2 給定。構(gòu)造二次插值函數(shù)并計(jì)算。解：，準(zhǔn)確值例5.3 要制做三角函數(shù)的函數(shù) 值表，已知表值有四位小數(shù)，要求用線性插值引起的截?cái)嗾`差不超過表值的舍入誤差，試決定其最大允許步長。解：設(shè)最大允許步長5.2.3 次拉格朗日插值多項(xiàng)式問題5.3 給定平面上兩個(gè)互不相同的插值點(diǎn) ，有且僅有一條通過這兩點(diǎn)的直線；給定平面上三個(gè)互不相同的插值點(diǎn)，有且僅有一條通過這三個(gè)點(diǎn)的二次曲線；給定平面上個(gè)互不相同的插值點(diǎn)，互不相同是指互不相等，是否有且僅有一條不高于次的插值多項(xiàng)式曲線，如果曲線存在，那么如何簡單地作出這條次插值多項(xiàng)式曲線？分析：次多項(xiàng)式，它完全

9、由個(gè)系數(shù)決定。若曲線通過給定平面上個(gè)互不相同的插值點(diǎn)，則應(yīng)滿足，事實(shí)上一個(gè)插值點(diǎn)就是一個(gè)插值條件。將依次代入中得到線性方程組：           （5.4）方程組的系數(shù)行列式是范德蒙（Vandermonde）行列式：當(dāng)互異時(shí)，所以方程組（5.4）的解存在且惟一。即問題5.3的解存在而且惟一。通過求解（5.4）得到插值多項(xiàng)式 ，因其計(jì)算量太大而不可取，仿照線性以及二次插值多項(xiàng)式的拉格朗日形式，我們可構(gòu)造次拉格朗日插值多項(xiàng)式。對于個(gè)互不相同的插值節(jié)點(diǎn)，由次插值多項(xiàng)式的惟一性，可對每個(gè)插值節(jié)點(diǎn)作出相

10、應(yīng)的次插值基函數(shù)。要求是，的零點(diǎn)，因此可設(shè)由將代入，得到（5.5）作其組合：                           （5.6）那么不高于次且滿足，故就是關(guān)于插值點(diǎn)的插值多項(xiàng)式，這種插值形式稱為拉格朗日插值多項(xiàng)式。稱為關(guān)于節(jié)點(diǎn)的拉格朗日基函數(shù)。例5.4 給出下列插值節(jié)點(diǎn)數(shù)據(jù)，做三次拉格朗日插值多項(xiàng)式，并計(jì)算（0.6）。-2.0

11、00.001.002.0017.001.002.0017.00解：拉格朗日插值基函數(shù)為：三次拉格朗日插值多項(xiàng)式：       n次插值多項(xiàng)式的誤差定理5.2 設(shè)是上過的次插值多項(xiàng)式，互不相等，當(dāng)時(shí)，則插值多項(xiàng)式的誤差：  其中(5.7)證明*：記。由于，因而是的根，于是可設(shè)下面的目標(biāo)是算出，為此引入變量為的函數(shù)：  （5.8）令，得令，由定義即至少有個(gè)零點(diǎn)，由于，由洛爾定理，在相鄰的兩個(gè)零點(diǎn)之間至少有一個(gè)零點(diǎn)，即至少有個(gè)零點(diǎn)。同理再對應(yīng)用洛爾定理，即至少有個(gè)零點(diǎn)，反復(fù)應(yīng)用洛爾定理得到至少有一個(gè)零

12、點(diǎn)。另一方面，對求階導(dǎo)數(shù)，有令，有    得到 （5.9）由于的零點(diǎn)與的零點(diǎn)有關(guān)，因而為的函數(shù)。若|可表示為                    （5.10）由（5.9）式可以看到，當(dāng) 是不高于次的多項(xiàng)式時(shí)，即。對于函數(shù)，關(guān)于節(jié)點(diǎn)的拉格朗日插值多項(xiàng)式就是其本身，故拉格朗日基函數(shù)滿足令，得到。定理5.2給出了當(dāng)被插函數(shù)充分光滑時(shí)的插值誤差或稱插值余項(xiàng)表達(dá)式，但是，在實(shí)

13、際計(jì)算中，并不知道的具體表示，難以得到的形式或較精確的界限，因此也難以得到界。在實(shí)際計(jì)算中，可對誤差運(yùn)用下面的事后估計(jì)方法。給出個(gè)插值節(jié)點(diǎn)，任選其中的個(gè)插值節(jié)點(diǎn)，不妨取，構(gòu)造一個(gè)次插值多項(xiàng)式，記為。在個(gè)插值節(jié)點(diǎn)中另選個(gè)插值點(diǎn)，不妨取，構(gòu)造一個(gè)次插值多項(xiàng)式，記為。由定理2可得到  （5.11） （5.12）設(shè)在插值區(qū)間內(nèi)連續(xù)而且變化不大，有，則從而可得到         （5.13）       （5.14）拉格朗日插

14、值多項(xiàng)式的算法下面用偽碼描述拉格朗日插值多項(xiàng)式的算法。1：輸入：插值節(jié)點(diǎn)控制數(shù)，插值點(diǎn)序列，要計(jì)算的函數(shù)點(diǎn)，及變量 。2：FOR  i ：=0，1，n    /i控制拉格朗日基函數(shù)序列tmp：=1；2.1 FOR j：=0，1，i-1，i+1，n  /對于給定，計(jì)算拉格朗日基函數(shù)  ；         / tmp表示拉格朗日基函數(shù) 2.2      3：輸出的計(jì)算結(jié)果。5.4埃特金逐步插值法我們已經(jīng)知道，拉

15、格朗日插值多項(xiàng)式的余項(xiàng)為 其中但在實(shí)際插值過程中，由于 一般無法計(jì)算，因而實(shí)際的誤差也就無法得知。那么，如何根據(jù)所要求的精度來選取插值點(diǎn)的多少呢？這就是埃特金（Aitken）逐步插值所要解決的問題。首先介紹一個(gè)誤差的事后估計(jì)法。設(shè)為通過點(diǎn)的次插值多項(xiàng)式；為通過點(diǎn)的次插值多項(xiàng)式。這兩個(gè)次插值多項(xiàng)式都通過，其中前者還通過，而后者還通過，即它們所通過的插值線結(jié)點(diǎn)有個(gè)是共同的，只有一個(gè)是不同的。若插值多項(xiàng)式用表示，則其中第一個(gè)下標(biāo)表示插值多項(xiàng)式通過個(gè)插值結(jié)點(diǎn);第二個(gè)下標(biāo)表示還通過的插值結(jié)點(diǎn)?，F(xiàn)在考慮插值多項(xiàng)式與，由于它們所通過的插值結(jié)點(diǎn)中有一個(gè)不同的，因此其余項(xiàng)也不同。設(shè)它們的余項(xiàng)分別為&#

16、160;其中與雖然不等，但由于在插值區(qū)間內(nèi)這兩個(gè)插值多項(xiàng)式所通過的插值結(jié)點(diǎn)大部分相同，只有一個(gè)不同，所以這兩個(gè)階導(dǎo)數(shù)相差不多（假設(shè)與離得很近），可以近似看作相等，即    由此可以得到這兩個(gè)插值多項(xiàng)式的余項(xiàng)比為     從上式中解出得        即       由上式可以看出，次插值多項(xiàng)式的誤差可以由具有個(gè)相同的結(jié)點(diǎn)與一個(gè)不同結(jié)點(diǎn)的兩個(gè)次插值多項(xiàng)式的差來

17、估計(jì)。并且還可以看出，如果將這個(gè)誤差加上，則可以得到更精確的的近似值?？梢宰C明，這更精確的插值多項(xiàng)式為次插值多項(xiàng)式，即由上式可以看出，兩個(gè)次插值多項(xiàng)式與經(jīng)過線性組合后，便得到次插值多項(xiàng)式 。這種方法稱為埃特金逐步線性插值。它的優(yōu)點(diǎn)在于可根據(jù)精度的要求逐步提高插值的階，在插值過程中，由于都是線性運(yùn)算，因而計(jì)算也方便。其計(jì)算格式如圖5.3所示。圖5.3 埃特金逐步線性插值的計(jì)算格式例5.8  設(shè)函數(shù)已知求的近似值。解：根據(jù)埃特金逐步線性插值的計(jì)算格式，其計(jì)算結(jié)果如表5.2所示。表5.2Kxkf(xk)P0,k(x)P1,k(x)P2,k(x)P3,k(x)012340.30.40.50.

18、60.70.298540.396460.493110.588130.68122 0.4571950.4561340.4549000.453502  0.4565370.4564840.456432   0.4565570.456557    0.456557由表5.2可知，若取，則    所以有    此時(shí),實(shí)際上已用不著計(jì)算了。若取，則所以有此時(shí)，以后的值也不必計(jì)算了。埃特金逐步線性插值的算法輸入：插值結(jié)點(diǎn)；插值點(diǎn)

19、及精度要求。輸出：插值點(diǎn)處的函數(shù)值。在上述算法中，分別表示。當(dāng)某相鄰兩個(gè) 之差的絕對值小于時(shí)，插值過程就停止。如果所有的插值結(jié)點(diǎn)都已用完，但還未滿足精度要求，插值過程也停止。5.5  埃爾米特（Hermite）插值在構(gòu)造插值時(shí)，如果不僅要求插值多項(xiàng)式節(jié)點(diǎn)的函數(shù)值與被插函數(shù)的函數(shù)值相同，還要求在節(jié)點(diǎn)處的插值函數(shù)與被插函數(shù)的一階導(dǎo)數(shù)的值也相同，這樣的插值稱為埃爾米特插值或稱密切插值。常用埃爾米特插值描述如下：設(shè)具有一階連續(xù)導(dǎo)數(shù)，以及插值點(diǎn)，若有至多為次的多項(xiàng)式函數(shù)滿足則稱為關(guān)于節(jié)點(diǎn)的埃爾米特插值多項(xiàng)式。問題5.7：給定；怎樣構(gòu)造給定兩個(gè)節(jié)點(diǎn)的函數(shù)值和一階導(dǎo)數(shù)值的埃爾米特插值多項(xiàng)

20、式？分析：用4個(gè)條件，至多可確定三次多項(xiàng)式。設(shè)滿足插值條件的三次埃爾米特插值多項(xiàng)式為：將插值條件代入得到線性方程組：因?yàn)榉匠探M的系數(shù)行列式所以方程組有解，可惟一解出，即關(guān)于節(jié)點(diǎn)的埃爾米特插值多項(xiàng)式存在惟一。類似于拉格朗日插值多項(xiàng)式樣構(gòu)造手法，也可通過插值基函數(shù)作出。設(shè)    要    可設(shè) 同理要 有    要    有    要    有    由上述要求，對來說，

21、至多為三次多項(xiàng)式，是它的二重根，可設(shè)     （5.20）利用 解出 同理可得  由 ，可設(shè)。由，算出。所以                    （5.21）同理綜上所述，得到以為節(jié)點(diǎn)的埃爾米特插值為 （5.22）容易證明，當(dāng)時(shí)插值誤差為      （5.23）如果要

22、構(gòu)造關(guān)于個(gè)節(jié)點(diǎn)的米特插值多項(xiàng)式，手法與構(gòu)造兩個(gè)節(jié)點(diǎn)的方法類似。這里分別為不高于次插值多項(xiàng)式，分別滿足  及  由此可得到             （5.24）這里為關(guān)于節(jié)點(diǎn)的拉格朗日基函數(shù)。容易證明，當(dāng)時(shí)，誤差為：（5.25）例5.8 給定，求埃爾米特插值多項(xiàng)式，并計(jì)算。解：顯然本題不必計(jì)算。 利用構(gòu)造基函數(shù)方法做插值多項(xiàng)式被廣泛地應(yīng)用在不同的插值條件中。例5.9 給定構(gòu)造二次插值多項(xiàng)式函數(shù)。解：設(shè)這里均為不高于二次的多項(xiàng)式，它們分別滿

23、足                于是可表示為由，得由，得所以， 所以 同理由所以所以用牛頓差商插值也能構(gòu)造埃爾米特插值。對給定的插值點(diǎn)的函數(shù)值和一階導(dǎo)數(shù)值定義序列即計(jì)算一階差商時(shí)：由和，取即構(gòu)造差商表中用代替其余差商計(jì)算公式不變，得到差商型埃爾米特插值公式：      （5.26）其中，。例5.10 用下列數(shù)據(jù)構(gòu)造埃爾米特插值多項(xiàng)式，并計(jì)算f（1.36）。1.21.41.60.60.91.10.

24、50.70.6解：計(jì)算差商。1.21.21.41.41.61.60.60.60.90.91.11.10.51.50.71.00.6  5-41.5-2   -4513  -17.5    145 -76.25     -553.125例5.11 求 使 及 插值多項(xiàng)式及其余項(xiàng)表達(dá)式。解：這里給出了四個(gè)條件故可構(gòu)造三次插值多項(xiàng)式,可用Newton均差插值，令顯然它滿足條件，為待定參數(shù)。由可得解得：于是就可得到插值多項(xiàng)式。它的余項(xiàng)為在與之間，而。5.

25、6  分段插值5.6.1 龍格（Runge）現(xiàn)象在構(gòu)造插值多項(xiàng)式時(shí)，根據(jù)誤差表達(dá)式（5.9），你是否認(rèn)為多取插值點(diǎn)總比少取插值點(diǎn)的效果好呢？答案是不一定。如果被插函數(shù)是高次多項(xiàng)式，那么多取插值點(diǎn)比少取插值點(diǎn)效果好；但對有些函數(shù)來說，有時(shí)點(diǎn)取的越多，效果越不近人意。請看下面的例子。給定函數(shù)，。構(gòu)造10次插值多項(xiàng)式。對作等距分割，取，構(gòu)造，10次插值多項(xiàng)式如圖5.4所示。從圖中可以看到，在零點(diǎn)附近，對的逼近效果較好，在=0.90，0.70，0.70，0.90時(shí)誤差較大。圖 5.4 和下面列出和的幾個(gè)插值點(diǎn)的數(shù)值：0.900.700.500.301.578720.47060.075470.

26、226200.137930.253760.307690.23535這個(gè)例子是由龍格（C.Runge）提出的，也稱插值多項(xiàng)式在插值區(qū)間發(fā)生劇烈振蕩的現(xiàn)象為龍格現(xiàn)象。龍格現(xiàn)象揭示了插值多項(xiàng)式的缺陷。它說明高次多項(xiàng)式的插值效果并不一定優(yōu)于低次多項(xiàng)式的插值效果。在插值過程中，誤差由截?cái)嗾`差和舍入誤差組成。式（5.9）給出的是截?cái)嗾`差，它是插值函數(shù)與原函數(shù)的誤差。另外由節(jié)點(diǎn)計(jì)算產(chǎn)生的舍入誤差，在插值計(jì)算過程中可能被擴(kuò)散或放大，這就是插值的穩(wěn)定性問題。而高次多項(xiàng)式的穩(wěn)定性一般比較差，這從另一角度說明了高次插值多項(xiàng)式的缺陷。5.6.2 分段線性插值既然增加插值點(diǎn)并不能提高插值函數(shù)的逼近效果，那么采用分段插值

27、的效果又如何呢？若對給定區(qū)間作分割，在每個(gè)小區(qū)間上作以為節(jié)點(diǎn)的線性插值，記這個(gè)插值函數(shù)為，則（5.27）把每個(gè)小區(qū)間的線性插值函數(shù)連接起來，就得到了以剖分（節(jié)點(diǎn)）的分段線性函數(shù)。在上為一個(gè)不高于一次的多項(xiàng)式，事實(shí)上是平面上以點(diǎn)為折點(diǎn)的折線。由線性插值誤差公式，當(dāng)時(shí)有  （5.28）因而       其中。于是，當(dāng)區(qū)間分割加密，時(shí)，分段線性插值收斂于。事實(shí)上，只要連續(xù)，分段線性插值序列就能收斂于。分段線性插值算法簡單，只要區(qū)間充分小，就能保證它的誤差要求。它的一個(gè)顯著優(yōu)點(diǎn)是它的局部性質(zhì)，如果修改了某節(jié)點(diǎn)的值，僅在相鄰

28、的兩個(gè)區(qū)間受到影響。分段線性插值的缺點(diǎn)是在插值節(jié)點(diǎn)處不光滑。圖5.5 給出分段線性插值 （虛線表示）和的圖形，可以看到分段線性插值的效果明顯好于整體的拉格朗日插值的效果。圖5.5 分段線性插值和例5.12 對下列數(shù)據(jù)作分段線性插值，并計(jì)算（1.2 ），（3.3 ）。3123912121612解：  1.21，2  (1.2 ) =× 5 +×1=2.0667 3.33，9 (3.3 ) =× 6 +× 12 = 6.35.7  三次樣條函數(shù)在制造船體和汽車外形等工藝中傳統(tǒng)的設(shè)計(jì)方法是，首先由設(shè)計(jì)人員按外形要求，給出

29、外形曲線的一組離散點(diǎn)值，施工人員準(zhǔn)備好有彈性的樣條（一般用竹條或有彈性的鋼條）和壓鐵，將壓鐵放在點(diǎn)的位置上，調(diào)整竹條的形狀，使其自然光滑，這時(shí)竹條表示一條插值曲線，我們稱為樣條函數(shù)。從數(shù)學(xué)上看，這一條近似于分段的三次多項(xiàng)式，在節(jié)點(diǎn)處具有一階和二階連續(xù)微商。樣條函數(shù)的主要優(yōu)點(diǎn)是它的光滑程度較高，保證了插值函數(shù)二階導(dǎo)數(shù)的連續(xù)性，對于三階導(dǎo)數(shù)的間斷，人類的眼睛已難以辨認(rèn)了。樣條函數(shù)是一種隱式格式，最后需要解一個(gè)方程組，它的工作量大于多項(xiàng)式拉格朗日型式或牛頓型式等顯式插值方法。定義 給定區(qū)間上個(gè)節(jié)點(diǎn)和這些點(diǎn)上的函數(shù)值，。若滿足；在每個(gè)小區(qū)間上至多是一個(gè)三次多項(xiàng)式；在上有連續(xù)的二階導(dǎo)數(shù)，則稱為關(guān)于剖分的

30、三次樣條插值函數(shù)，稱為樣條節(jié)點(diǎn)。要在每個(gè)子區(qū)間上構(gòu)造三次多項(xiàng)式 ，共需要個(gè)條件，由插值條件，提供了個(gè)條件；用每個(gè)內(nèi)點(diǎn)的關(guān)系建立條件又得到個(gè)條件；再附加兩個(gè)邊界條件，即可惟一確定樣條函數(shù)了。用待定系數(shù)法確定了構(gòu)造樣條函數(shù)的存在性和惟一性。在具體構(gòu)造樣條函數(shù)時(shí)一般都不使用計(jì)算量大的待定系數(shù)法。下面給出構(gòu)造三次樣插值的關(guān)系式和關(guān)系式的方法。5.7.1 三次樣條插值的M關(guān)系式引入記號(hào)。用節(jié)點(diǎn)處二階導(dǎo)數(shù)表示樣條插值函數(shù)時(shí)稱為大關(guān)系式，用一階導(dǎo)數(shù)表示樣條插值函數(shù)時(shí)稱為小關(guān)系式。問題5.8 給定插值點(diǎn)，怎樣構(gòu)造用二階導(dǎo)數(shù)表示的樣條插值函數(shù)，即怎樣構(gòu)造關(guān)系式？假設(shè)。由于在上為線性函數(shù)，故在上做的分段

31、線性插值函數(shù)： 令 ，得到       （5.29）對積分兩次有 （5.30）將代入式（5.27）可解出故在上有（5.31）在每個(gè)小區(qū)間上具有不同的表達(dá)式，但由于在整個(gè)區(qū)間上是二階光滑的，故有列出每一個(gè)關(guān)系式，再經(jīng)計(jì)算得：         （5.32）其中：              由式（5.32

32、）得到個(gè)未知數(shù)的個(gè)方程組?，F(xiàn)補(bǔ)充兩個(gè)邊界條件，使方程組只有惟一解。下面分三種情況討論邊界條件。（1）給定的值時(shí)，稱為自然邊界條件），此時(shí)階方程組有個(gè)未知量，即 （5.33）（2）給定的值，它們分別代入在中的表達(dá)式，得到另外兩個(gè)方程：于是需要解階的方程組：    （5.34）（3）被插函數(shù)以為基本周期時(shí)，即，即；即。此時(shí)化為個(gè)變量、個(gè)方程的方程組。樣條插值構(gòu)造的關(guān)系式是對角占優(yōu)的三對角帶狀矩陣，可用第3章中的追趕法求解。例5.13 給出離散數(shù)值表：1.11.21.41.50.40000.80001.65001.8000取，構(gòu)造三次樣條插值的關(guān)系式，并計(jì)算f

33、（1.25）。解：由題中的數(shù)值，計(jì)算得    由的邊界條件，得解得。因此，三次樣條插值的分段表達(dá)式為特別地，。詳細(xì)的程序和算例請看5.8節(jié)。5.7.2 三次樣條插值的m關(guān)系式問題5.9 給定插值點(diǎn)，怎樣構(gòu)造用節(jié)點(diǎn)處一階導(dǎo)數(shù)表示的樣條插值函數(shù)，即怎樣構(gòu)造關(guān)系式？對給定的插值點(diǎn)，先假定已知，在每個(gè)小區(qū)間上做埃爾米特插值，那么在整個(gè)上是分段的埃爾米特插值，在上的表達(dá)式為通過得到方程組其中：再附加兩個(gè)邊界條件，即可解出的值。附加的邊界條件情況同關(guān)系式中的討論類似，不再詳述。對作樣條插值，插值效果見圖5.6。可以看到樣條插值效果優(yōu)于分段插值效果。圖5.6 樣條插值圖示5.8

34、程序示例程序5.1給定，構(gòu)造牛頓插值多項(xiàng)式互不相同。算法描述輸入值，及（；記；計(jì)算差商其中對給定的，由計(jì)算的值；輸出。程序源碼/   purpose：（x_i，y_i）的牛頓插值多項(xiàng)式  /# include stdio.h# define MAX_N 20              / 定義（x_i，y_i）的最大維數(shù)typedef struct tagPOINT     &

35、#160;    / 點(diǎn)的結(jié)構(gòu) double x；  double y； POINT；int main ( ) int n； int i，j；   POINT points MAX_N + 1；double diff MAX_N + 1；   double x，tmp，newton = 0；   printf (“ nInput n value：”)； / 輸入被插值點(diǎn)的數(shù)目   scanf (“% d”，&n)；if (nMAX_N )

36、  printf (“The input n is larger then MAX_N，please redefine the MAX_N. n”)；  return 1；if (n= 0) printf (“Please input a number between 1 and % d. n”，MAX_N )； return 1；         / 輸入被插值點(diǎn)（x_i，y_i）printf (“Now input the（x_i，y_i），i=0，% d: n”，n)；

37、for (i=0；i= n；i+)    scanf (“% lf % lf”，&pointsi.x, &pointsi.y)；printf (“Now input the x value：”)；       / 輸入計(jì)算牛頓插值多項(xiàng)式的x值scanf (“%lf”，& x)；for (i=0；i= n；i+)  diff i = points i.y；for (i=1；i= n；i+)    for ( j = n；j=i；j-) 

38、;  diff j = ( diff jdiff j-1) / (points j. x points j-1-i.x)；                          / 計(jì)算f (x_0，x_n)的差商tmp = 1；newton = diff 0；for (i=0；i= n；i + +)  tmp = tmp * (x

39、-pointsi.x)；  newton = newton + tmp * diff i+1；printf (“newton (% f ) = %f n”，x，newton)；  / 輸出return 0；計(jì)算實(shí)例給定sin11°= 0.190809，sin12°= 0.207912，sin13°= 0.224951，構(gòu)造牛頓插值函數(shù)并計(jì)算sin11°30。程序輸入輸出input n value：2Now input the（x_i，y_i），i=0，2：11 0.190809 12 0.207912 13 0.224951Now I

40、nput the x value：11.5newton (11.500000) = 0.199369程序5.2給定插值點(diǎn)和二階導(dǎo)數(shù)的端點(diǎn)值，用關(guān)系式構(gòu)造三次樣條插值多項(xiàng)式，求在給定點(diǎn)處的值。算法描述1輸入值，及，要計(jì)算的函數(shù)點(diǎn)；2for i =1 to n1計(jì)算，其中；3求解方程組 對給定的，由4計(jì)算出的值；5輸出。程序源碼/ purpose：給定，值的三次樣條插值多項(xiàng)式  /# include <stdio.h># define MAX_N 20         

41、;    / 定義(x_i，y_i)的最大的維數(shù)typedef struct tagPOINT         / 點(diǎn)的結(jié)構(gòu) double x；double y； POINT；int main ( ) int n；  int i，k；POINT pointsMAX_N +1；double hMAX_N +1，bMAX_N +1，cMAX_N +1，dMAX_N +1，MMAX_N +1；double uMAX_N +1，vMAX_N +1，yMAX_N +1；double x

42、，p，q，S；printf (“ nInput n value：”)；       / 輸入插值點(diǎn)的數(shù)目scanf (“% d”，&n)；if (nMAX_N) printf (“The input n is larger than MAX_N, please redefine the MAX_N. n”)；return 1；if (n0)  printf (“Please input a number between 1 and % d. n”，MAX_N)；return 1   / 輸入插值點(diǎn)

43、(x_i，y_i)，M0值和Mn值printf (“Now input the (x_i，y_i)，i=0，% d： n”，n)；for (i=0；in；i+)  scanf (“% lf % lf ”，&pointsi.y)；printf (“Now input the M0 value：”)；scanf (“% lf ”，&M0)；printf (“Now input the Mn value：”)；scanf (“%lf ”，&Mn)；printf (“Now input the x value：”)；     /

44、輸入計(jì)算三次樣條插值函數(shù)的x值scanf (“%lf”，&x)；if (xpointsn. x | | xpoints0.x printf (“Please input a number between % f and % f. n”，points0.x，points0.x)；return 1；/ 計(jì)算M關(guān)系式中各參數(shù)的值h0=points1.xpoints0.x；for (i=1；i；i+ )hi=pointsi+1.xpointsi.x；bi=hi/(hi+hi1；ci=1bi；di=6*(pointsi+1.ypointsi.y)/hi(pointsi.ypointsi1.y)/

45、hi1)/(hi+hi1)；/ 用追趕法計(jì)算Mi，i=1，n1d1= c1*M0；dn1=bn1*Mn；bn1=0；c1=0；v0=0；for ( i=1；in；i+) ui=2ci*vi1； vi=bi/ui； yi= (dici*yi1)/ui；for (i=1；in；i+) Mni=ynivni* Mn-i+1；/ 計(jì)算三次樣條插值函數(shù)在x處的值k=0；while (x= pointsk.x) k+；k=k1p=pointsk+1.xx;q=xpointsk.x；S=(p* p* p* Mk +q* q* q* Mk+1) / (6* hk)+( p* points

46、k.y+q* pointsk+1.y) / hkhk*(p* Mk +q* Mk+q* Mk+1)/6；printf (“S(%f ) = % f n”，x，S)；/ 輸出getchar ( )；return 0；計(jì)算實(shí)例給定離散點(diǎn)（1.1，0.4），（1.2，0.8），（1.4，1.65），（1.5，1.8），用關(guān)系式構(gòu)造三次樣條插值多項(xiàng)式，計(jì)算。程序輸入輸出Input n value：3Now input the (x_i，y_i)，i=0，3：1.1 0.4 1.2 0.8 1.4 1.65 1.5 1.8Now Input the M0 value：0Now Input the Mn

47、value：0Now Input the x value：1.25S (1.25000) = 1.0335945.3牛頓（Newton）插值拉格朗日插值多項(xiàng)式的優(yōu)點(diǎn)是格式整齊和規(guī)范，它的缺點(diǎn)是計(jì)算量大且沒有承襲性質(zhì)，當(dāng)需要增加插值節(jié)點(diǎn)時(shí)，不得不重新計(jì)算所有插值基函數(shù)。本節(jié)給出具有承襲性質(zhì)的牛頓插值多項(xiàng)式，并首先介紹在牛頓插值中需要用到的差商計(jì)算。5.3.1 差商及其計(jì)算一階差商稱函數(shù)值的差與自變量的差之比值為關(guān)于點(diǎn)的一階差商，并記為，即而稱為關(guān)于點(diǎn)的二階差商。函數(shù)關(guān)于的零階差商即為函數(shù)在的函數(shù)值，。階差商設(shè)點(diǎn)互不相同，關(guān)于的階差商為 差商有很多性質(zhì)，我們僅列舉其中的兩條。性質(zhì)1：階差

48、商是由函數(shù)值的線性組合而成。用歸納法可以證明這一性質(zhì)。例如：性質(zhì)2：若為的任一排列，則該性質(zhì)表明差商的值只與節(jié)點(diǎn)有關(guān)而與節(jié)點(diǎn)的順序無關(guān)，即差商對節(jié)點(diǎn)具有對稱性，這一性質(zhì)由性質(zhì)1可直接推出。差商的計(jì)算按照差商定義，用兩個(gè)階差商的值計(jì)算階差商，通常用差商表的形式計(jì)算和存放（見表5.1）。由于差商對節(jié)點(diǎn)具有對稱性，可以任意選擇兩個(gè)差商的值計(jì)算階差商。例如：表5.1 差商表ixif(xi)一階差商二階差商三階差商n階差商0123nx0x1x2x3xnf(x0)f(x1)f(x2)f(x3)f(xn) fx0，x1fx1，x2fx2，x3fxn-1，xn  fx0，x1，x2fx1，x2，x3fxn-2，xn-1，xn   fx0，x1，x2，x3fxn-3，xn     fx0，x1，xn例5.5 計(jì)算（2，17），（0，1），（1，2），（2，19）的一至三階差商。ixif(xi)fxi-1，xifxi-2，xi-1，xifxi-3，xi-2，xi-1，xi0123-2012171219