第四章-插值法及曲線擬合

1第四章插值與曲線擬合§1引言§2拉格朗日插值多項式§3牛頓插值多項式§4分段低次插值§5

最小二乘擬合2§1引言1.

1插值問題的提法在生產(chǎn)和科研中出現(xiàn)的函數(shù)是多種多樣的。常遇到這種情況：在某個實際問題中，雖然可以斷定所考慮的函數(shù)在區(qū)間上存在且連續(xù)，但卻難以找到它的解析表達式，只能通過實驗和觀測得到在有限個點上的函數(shù)值（即一張函數(shù)表）。顯然，要利用這張函數(shù)表來分析函數(shù)的性態(tài)、甚至直接求出其3它一些點上的函數(shù)值是非常困難的。在有些情況下，雖然可以寫出函數(shù)的解析表達式，但由于結(jié)構(gòu)相當(dāng)復(fù)雜，使用起來很不方便。面對這些情況，總希望根據(jù)所得函數(shù)表（或結(jié)構(gòu)復(fù)雜的解析表達式），構(gòu)造某個簡單函數(shù)P(x)作為的近似。

插值法是解決此類問題的一種比較古老的、然而卻是目前常用的方法，它不僅直接廣泛地應(yīng)用于生產(chǎn)實際和科學(xué)研究中，而且也是進一步學(xué)習(xí)數(shù)值計算方法的基礎(chǔ)。4定義設(shè)函數(shù)y=f(x)在區(qū)間[a,b]上連續(xù)，且在n+1個不同的點上分別取值，在一個性質(zhì)優(yōu)良、便于計算的函數(shù)類φ

中，求一簡單函數(shù)p(x)，使

而在其它點上，作為f(x)的近似。稱區(qū)間為插值區(qū)間，點為插值節(jié)點，稱（1.1）為f(x)的插值條件，稱函數(shù)類φ

為插值函數(shù)類，稱p(x)為函數(shù)在(1.1)5節(jié)點處的插值函數(shù)。求插值函數(shù)p(x)的方法稱為插值法。插值函數(shù)類φ的取法不同，所求得的插值函數(shù)p(x)逼近f(x)的效果就不同它的選擇取決于使用上的需要。常用的有代數(shù)多項式、三角多項式和有理函數(shù)等。當(dāng)選用代數(shù)多項式作為插值函數(shù)時，相應(yīng)的插值問題就稱為多項式插值。在多項式插值中，最常見、最基本的問題是：求一次數(shù)不超過n的代數(shù)多項式6

(1.2)使其中為實數(shù)。滿足插值條件(1.3)的多項式(1.2)，稱為函數(shù)f(x)

在節(jié)點處的n次插值值多項式。

n次插值多項式的幾何意義：過曲線y=f(x)上的n+1個點作一條n次代數(shù)曲線，作為曲線y=f(x)的近似，如圖2-1。

(1.3)78

1.2插值多項式存在唯一性由插值條件（1.3）知，插值多項式的系數(shù)滿足線性方程組

（1.4）由線性代數(shù)知，線性方程組的系數(shù)行列式（記為V）是n+1階范德蒙（Vandermonde）行列式，且9

因是區(qū)間上的不同點，上式右端乘積中的每一個因子，于是，方程組（1.4）的解存在且唯一。故有下面的結(jié)論：定理1

若節(jié)點互不相同，則滿足插值條件（1.3）的n次插值多項式（1.2）存在且唯一。

10§2拉格朗日插值多項式在上一節(jié)里，我們不僅指出了插值多項式的存在唯一性，而且也提供了它的一種求法，即通過解線性方程組（1.4）來確定其系數(shù)，但是，這種作法的計算工作量大，不便于實際應(yīng)用，下面介紹幾種簡便的求法。

2.1插值基函數(shù)先考慮一下簡單的插值問題：對節(jié)點中任一點

,作一n次多項式

,使它在該點上取值為1,而在其余點

上取值為零,即

（2.1）（2.1）表明n個點

都是n次多項式的零點，故可設(shè)11其中

為待定系數(shù)，由條件

可得故

(2.2)對應(yīng)于每一節(jié)點，都能求出一個滿足插值條件（2.1）的n次插值多項式（2.2），這樣，由（2.2）式可以求出n+1個n次插插多項式

。容易看出，這組多項式僅與節(jié)點的取法有關(guān)，稱它們?yōu)樵趎+1個節(jié)點上的n次基本插值多項式或n次插值基函數(shù)。12

2.2拉格朗日插值多項式利用插值基函數(shù)立即可以寫出滿足插值條件（1.3）的n次插值多項式

（2.3）事實上，由于每個插值基函數(shù)

都是n次多項式，故其線性組合（2.3）必是不高于n次的多項式，同時，根據(jù)條件（2.1）容易驗證多項式（2.3）在節(jié)點

處的值為

，因此，它就是待求的n次插值多項式。形如(2.3)的插值多項式稱為拉格朗日插值多項式，記為

（2.4)13

作為的特例，令n=1，由（2.4）即得兩點插值公式即這是一個線性函數(shù)，用線性函數(shù)

近似代替函數(shù)，在幾何上就是通過曲線

上兩點

作一直線

近似代替曲線(見圖2-2)，故兩點插值又名線性插值。

若令n=2，由（2.4）又可得常用的三點插值公式

（2.5）

（2.6）（2.7）))(())(())(())(())(())(()(1202102210120120102102xxxxxxxxyxxxxxxxxyxxxxxxxxyxL----+----+----=14這是一個二次函數(shù)，用二次函數(shù)近似代替函數(shù)，在幾何上就是通過曲線上的三點，作一拋物線近似地代替曲線（圖2-3），故三點插值(二次插值)。例1

已知分別用線性插值和拋物插值求的值。x0y圖2-215解

因為115在100和121之間，故取節(jié)點x0=100，x1=121相應(yīng)地有

y0=10，y1=11，于是，由線性插值公式（2.5）可得故用線性插值求得的近似值為圖2-3yx016仿上，用拋物插值公式（2.7）所求得的近似值為將所得結(jié)果與的精確值10.7238…相比較，可以看出拋物插值的精確度較好。為了便于上機計算，我們常將拉格朗日插值多項式（2.4）改寫成公式（2.8）的對稱形式可用二重循環(huán)來完成值的計算，先通過內(nèi)循環(huán)，即先固定k，令j從0到，累乘求得

（2.8）17

然后再通過外循環(huán)，即令k從0到n，累加得出插值結(jié)果。

2.3插值余項在插值區(qū)間[a,b]上用插值多項式近似代替，除了在插值節(jié)點xi上沒有誤差外，在其它點上一般是存在有誤差的。若記則

就是用近似代替時所產(chǎn)生的截斷誤差，稱為插值多項式的余項。

18

的n次插值多項式，則對于任何，有其中且依賴于。

（2.9）關(guān)于誤差有如下定理2中的估計式。定理2

設(shè)在區(qū)間上有直到n+1階導(dǎo)數(shù)，為區(qū)間上n+1個互異的節(jié)點，為滿足條件:19例2

在例1中分別用線性插值和拋物插值計算了的近似值，試估計它們的截斷誤差。解

用線性插值求的近似值，其截斷誤差由插值余項公式（2.9）知

現(xiàn)在x0=100，x1=121，x=115，故20

當(dāng)用拋物插值求

的近似值時，其截斷誤差為

將代入，即得

§3牛頓插值多項式由線性代數(shù)可知，任何一個不高于n次的多項式，都可表示成函數(shù)的線性組合，即可將滿足插值條件的n次多項式寫成形式其中為待定系數(shù)。這種形式的插值多項式稱為牛頓﹙Newton﹚插值多項式，我們把它記成Νn﹙x﹚,即

（3.1)21

22

因此，牛頓插值多項式是插值多項式的另一種表示形式,與拉格朗日插值多項式相比較，不僅克服了“增加一個節(jié)點時整個計算機工作必須重新開始”﹙見例1﹚的缺點，而且可以節(jié)省乘﹑除法運算次數(shù)。同時，在牛頓插值多項式中用到的差分與差商等概念，又與數(shù)值計算的其它方面有著密切的關(guān)系.3.1向前差分與牛頓插值公式設(shè)函數(shù)?﹙x﹚在等距節(jié)點處的函數(shù)值為已知，其中h是正常數(shù)，稱為步長，稱兩個相鄰點和處函數(shù)值之差為函數(shù)?﹙x﹚在點處以h為步長的一階向前差分﹙簡稱一階差分﹚，記作，即于是，函數(shù)?﹙x﹚在各節(jié)點處的一階差分依次為

又稱一階差分的差分為二階差分。23一般地，定義函數(shù)?﹙x﹚在點處的m階差分為

為了便于計算與應(yīng)用，通常采用表格形式計算差分，如表2-1所示。表2-124

在等距節(jié)點情況下，可以利用差分表示牛頓插值多項式﹙3.1﹚

的系數(shù)，并將所得公式加以簡化。事實上，由插值條件

立即可得

再由插值條件可得由插值條件可得

一般地，由插值條件可得

25

于是，滿足插值條件的插值多項式為

令,并注意到，則可簡化為

這個用向前差分表示的插值多項式，稱為牛頓向前插值公式，簡稱前插公式。它適用于計算表頭附近的函數(shù)值。由插值余項公式﹙2.9﹚，可得前插公式的余項為：﹙3﹒2﹚26

（3.3)例4

從給定的正弦函數(shù)表﹙表2-2左邊兩列﹚出發(fā)計算,并估計截斷誤差。表2—20.10.20.30.40.50.60.295520.198670.099830.479430.389420.564640.098840.096850.093900.090010.08521-0.00389-0.00295-0.00094-0.00096-0.00480-0.00091-0.0019927解

因為0.12介于0.1與0.2之間，故取，此時。為求,構(gòu)造差分表2—2。表中長方形框中各數(shù)依次為在處的函數(shù)值和各階差分。若用線性插值求sin﹙0.12﹚的近似值，則由前插公式﹙3.2﹚立即可得用二次插值得用三次插值得：28

因很接近，且由差分表2—2可以看出，三階差分接近于常數(shù)（即接近于零），故取作為的近似值，此時由余項公式（3.3）可知其截斷誤差

3.2向后差分與牛頓向后插值公式在等距節(jié)點下，除了向前差分外，還可引入向后差分和中心差分，其定義和記號分別如下：在點處以h為步長的一階向后差分和m階向后差分分別為29

在點處以為步長的一階中心差分和m階中心差分分別為其中

各階向后差分與中心差分的計算，可通過構(gòu)造向后差分表與中心差分表來完成?參見表2－２?。利用向后差分，可簡化牛頓插值多項式（３.1），導(dǎo)出與牛頓前插公式?3.2?類似的公式，即，若將節(jié)點的排列次序看作，那么?３.1)可寫成

30根據(jù)插值條件,可得到一個用向后差分表示的插值多項式其中t<0，插枝多項式(3.4)稱為牛頓向后插值公式，簡稱后插公式。它適用于計算表尾附近的函數(shù)值。由插值余項公式（２.9），可寫出后插公式的余項(3.4)31(3.5)例５已知函數(shù)表同例４，計算，并估算截斷誤差。解因為０.58位于表尾附近，故用后插公式（3.4）計算sin(0.58)的近似值。一般地為了計算函數(shù)在處的各階向后差分，應(yīng)構(gòu)造向后差分表。但由向前差分與向后差分的定義可以看出，對同一函數(shù)表來說，構(gòu)造出來的向后差分表與向前差分表在數(shù)據(jù)上完全相同。因此，表２-２用“——”線標出的各數(shù)依次給出了在處的函數(shù)值和向后差分值。因三階向后差分接近于常數(shù)，故用三次插值進行計算，且，于是由后插公式（3.4）得32

因為在整個計算中，只用到四個點上的函數(shù)值，故由余項公式（３.5）知其截斷誤差333.3差商與牛頓基本插值多項式當(dāng)插值節(jié)點非等距分布時，就不能引入差分來簡化牛頓插值多項式，此時可用差商這個新概念來解決。設(shè)函數(shù)在一串互異的點上的值依次為

。我們稱函數(shù)值之差與自變量之差的比值為函數(shù)關(guān)于點的一階差商，記作例如

34稱一階差商的差商為函數(shù)關(guān)于點的二階差商（簡稱二階差商），記作，例如一般地，可通過函數(shù)的m-1階差商定義的m階差商如下：35

差商計算也可采用表格形式（稱為差商表），如表2—3所示，表2—3

一階差商二階差商三階差商36差商具有下列重要性質(zhì)（證明略）：（1）

函數(shù)的m階差商可由函數(shù)值的線性組合表示，且（2）差商具有對稱性，即任意調(diào)換節(jié)點的次序，不影響差商的值。例如（３）當(dāng)在包含節(jié)點的某個區(qū)間上存在時，在之間必有一點使37（４）在等距節(jié)點情況下，可同時引入階差分與差商，且有下面關(guān)系：引入差商的概念后，可利用差商表示牛頓插值多項式（３.1）的系數(shù)。事實上，從插值條件出發(fā)，可以象確定前插公式中的系數(shù)那樣，逐步地確定（３.1）中的系數(shù)故滿足插值條件的n次插值多項式為38

（3.6）（3.6）稱為牛頓基本插值多項式，常用來計算非等距節(jié)點上的函數(shù)值。例６試用牛頓基本插值多項式按例１要求重新計算的近似值。解先構(gòu)造差商表。由上表可以看出牛頓基本插值多項式(3.6)中各系數(shù)依次為一階商差二階商差10012111100.0434780.047619-0.0000941441239

故用線性插值所得的近似值為用拋物插值所求得的近似值為

所得結(jié)果與例1相一致。比較例1和例6的計算過程可以看出，與拉格朗日插值多項式相比較，牛頓插值多項式的優(yōu)點是明顯的。由插值多項式的存在唯一性定理知，滿足同一組插值條件的拉格朗日插值多項式（2.4）與牛頓基本插值多項式（3.6）是同一多項式。因此，余項公式（2.9）也適用于牛頓插值。但是在實際計算中，有時也用差商表示的余項公式40

（3.7）來估計截斷誤差（證明略）。注意：上式中的n+1階商差與的值有關(guān)，故不能準確地計算出的精確值，只能對它作一種估計。例，當(dāng)四階差商變化不大時，可用近似代替。

分段線性插值Runge現(xiàn)象給定函數(shù)取等距插值節(jié)點建立10次插值多項式43

-101xy

1y=1/(1+25x2)y=L5(x)圖2-5y=L10(x)分段線性插值

分段線性插值就是通過插值節(jié)點用折線段連接起來逼近f(x)。

設(shè)f(x)在n+1個節(jié)點上的函數(shù)值為,在每個小區(qū)間(k=0,1,…，n）上作線性插值，得在幾何上就是用折線替代曲線,如右圖所示若用插值基函數(shù)表示,則在a,b上

其中顯然，是分段線性連續(xù)函數(shù)，且

稱S(x)為f(x)的分段線性插值函數(shù)。由線性插值的余項估計式知,f(x)在每個子段上有誤差估計式其中例5.19已知f(x)在四個節(jié)點上的函數(shù)值如下表所示

304560901求f(x)在區(qū)間30,90上的分段連續(xù)線性插值函數(shù)S(x)

解將插值區(qū)間30,90分成連續(xù)的三個小區(qū)間

30,45,45,60,60,90則S(x)在區(qū)間30,45上的線性插值為

S(x)在區(qū)間45,60上的線性插值為

S(x)在區(qū)間60,90上的線性插值為將各小區(qū)間的線性插值函數(shù)連接在一起，得

三次Hermite插值問題:已知函數(shù)f(x)在兩個節(jié)點x0,x1上的函數(shù)值分別為y0,y1

及一階導(dǎo)數(shù)值分別為m0,m1構(gòu)造一個插值函數(shù)H3(x)，使?jié)M足條件

1°H3(x)是次數(shù)3的多項式

2°H3(x0)=y0,H3(x1)=y1,H'3(x0)=m0

H'3(x1)=m1

稱這類插值問題為三次Hermite插值問題.首先求做三次多項式h0(x),h1(x),h0(x),h1(x),使其滿足

h0(x0)=1,h0(x1)=0,h'0(x0)=0,h'0(x1)=0h1(x0)=0,h1(x1)=1,h'1(x0)=0,h'1(x1)=0

h0(x0)=0,h0(x1)=0,h'0(x0)=1,h'0(x1)=0

h1(x0)=0,h1(x1)=0,h'1(x0)=0,h'1(x1)=1設(shè)

由h0(x0)=1，得a=1,再由h'0(x0)=0，得，于是同理有設(shè)

由h'0(x0)=1，得a=1,于是同理有顯然H3(x)=y0h0(x)+y1h1(x)+m0h0(x)+m1h1(x)其中三次Hermite插值多項式的余項定理3

設(shè)H3(x)

是以x0,x1為插值節(jié)點的三次Hermite插值多項式，若f(x)C3[a,b]，f(4)(x)在(a,b)上存在，其中

[a,b]是包含(x0,x1)的任一區(qū)間，則對任意給定的x[a,b]

，總存在一點(a,b)（依賴于x）使

曲線擬合的最小二乘法

如果已知函數(shù)f(x)在若干點xi(i=1,2,…,n)處的值yi,便可根據(jù)插值原理來建立插值多項式作為f(x)的近似。但在科學(xué)實驗和生產(chǎn)實踐中，往往會遇到這樣一種情況，即節(jié)點上的函數(shù)值并不是很精確的，這些函數(shù)值是由實驗或觀測得到的數(shù)據(jù)，不可避免地帶有測量誤差，如果要求所得的近似函數(shù)曲線精確無誤地通過所有的點(xi,yi),就會使曲線保留著一切測試誤差。當(dāng)個別數(shù)據(jù)的誤差較大時,插值效果顯然是不理想的。此外,由實驗或觀測提供的數(shù)據(jù)個數(shù)往往很多,如果用插值法,勢必得到次數(shù)較高的插值多項式，這樣計算起來很煩瑣。為此,我們希望從給定的數(shù)據(jù)(xi,yi)出發(fā),構(gòu)造一個近似函數(shù),不要求函數(shù)完全通過所有的數(shù)據(jù)點，只要求所得的近似曲線能反映數(shù)據(jù)的基本趨勢，如圖5-7所示。圖5-7曲線擬合示意圖

換句話說:求一條曲線,使數(shù)據(jù)點均在離此曲線的上方或下方不遠處,所求的曲線稱為擬合曲線,它既能反映數(shù)據(jù)的總體分布,又不至于出現(xiàn)局部較大的波動,更能反映被逼近函數(shù)的特性,使求得的逼近函數(shù)與已知函數(shù)從總體上來說其偏差按某種方法度量達到最小,這就是曲線擬合。

與函數(shù)插值問題不同,曲線擬合不要求曲線通過所有已知點,而是要求得到的近似函數(shù)能反映數(shù)據(jù)的基本關(guān)系。在某種意義上,曲線擬合更有實用價值。在對給出的實驗(或觀測)數(shù)據(jù)作曲線擬合時,怎樣才算擬合得最好呢？一般希望各實驗(或觀測)數(shù)據(jù)與擬合曲線的偏差的平方和最小,這就是最小二乘原理。

兩種逼近概念:

插值:在節(jié)點處函數(shù)值相同.

擬合:在數(shù)據(jù)點處誤差平方和最小函數(shù)插值是插值函數(shù)P(x)與被插函數(shù)f(x)在節(jié)處函數(shù)值相同,即而曲線擬合函數(shù)不要求嚴格地通過所有數(shù)據(jù)點,也就是說擬合函數(shù)在xi處的偏差(亦稱殘差）

不都嚴格地等于零。但是,為了使近似曲線能盡量反映所給數(shù)據(jù)點的變化趨勢,要求按某種度量標準最小。若記向量,即要求向量某種范數(shù)最小,如的1-范數(shù)或∞-范數(shù)即或

最小。為了便于計算、分析與應(yīng)用，通常要求的2-范數(shù)即為最小。這種要求誤差（偏差）平方和最小的擬合稱為曲線擬合的最小二乘法。

（1）直線擬合設(shè)已知數(shù)據(jù)點,分布大致為一條直線。作擬合直線,該直線不是通過所有的數(shù)據(jù)點,而是使偏差平方和為最小，其中每組數(shù)據(jù)與擬合曲線的偏差為根據(jù)最小二乘原理，應(yīng)取和使有極小值，故和應(yīng)滿足下列條件：即得如下正規(guī)方程組

(5.45)例設(shè)有某實驗數(shù)據(jù)如下：12341.361.371.952.2814.09416.84418.47520.963

用最小二乘法求以上數(shù)據(jù)的擬合函數(shù)解:把表中所給數(shù)據(jù)畫在坐標紙上,將會看到數(shù)據(jù)點的分布可以用一條直線來近似地描述,設(shè)所求的

擬合直線為記x1=1.36,x2=1.37,x3=1.95x4=2.28,y1=14.094,y2=16