第二章：插值法

描述事物之間的數(shù)量關(guān)系：函數(shù)。有兩種情況：一是表格形式——一組離散的數(shù)據(jù)來表示函數(shù)關(guān)系；另一種是函數(shù)雖然有明顯的表達式，但很復(fù)雜，不便于研究和使用。從實際需要出發(fā)：對于計算結(jié)果允許有一定的誤差，可以把函數(shù)關(guān)系用一個簡單的便于計算和處理的近似表達式來代替，從而使問題得到簡化。一般地，構(gòu)造某種簡單函數(shù)代替原來函數(shù)。插值法就是一種基本方法§0引言第二章插值（Interpolation）法(1)(2)(2)在x為特殊時,是好計算的,則(2)可轉(zhuǎn)化為(1)當(dāng)精確函數(shù)y=f(x)非常復(fù)雜或未知時，在一系列節(jié)點x0…xn

處測得函數(shù)值y0

=f(x0),…yn

=f(xn)，由此構(gòu)造一個簡單易算的近似函數(shù)g(x)

f(x)，滿足條件g(xi)=f(xi)(i=0,…n)。這里的g(x)

稱為f(x)的插值函數(shù)。x0x1x2x3x4xg(x)

f(x)根據(jù)實際需要，可以用各種不同的函數(shù)來近似原來的函數(shù)。最常用的插值函數(shù)是…?多項式：代數(shù)多項式最簡單，計算其值只需用到加、減乘運算，且積分和微分都很方便；所以常用它來近似表示表格函數(shù)(或復(fù)雜函數(shù)),這樣的插值方法叫做代數(shù)插值法，簡稱插值法。§1拉格朗日多項式niyxPiin,...,0,)(==求n

次多項式使得條件：無重合節(jié)點，即n=1已知x0

,x1

;

y0

,

y1

，求使得111001)(,)(yxPyxP==可見P1(x)是過(x0,y0

)和(x1,y1

)兩點的直線。)(1xP101xxxx--010xxxx--=y0

+y11.1線性插值兩點式)()(0010101xxxxyyyxP---+=點斜式)(001010xxxxxxy---+=(())ff1.2二次插值n=2已知x0

,x1

,x2;

y0

,

y1

,y2,求使得002,)(yxP112)(yxP==222)(yxP=,為求P2(x),將三點代入其表達式,即可得到三個方程式,從而聯(lián)立方程組解出系數(shù)a0,a1,a2即可:方程組的解是否存在?若存在解,是否唯一?!當(dāng)x0

,x1

,x2互異時,方程組的解存在且唯一.注：顯然有,求n次插值時,由n+1個點可有n+1個方程,聯(lián)立方程組即可求出插值多項式的n+1個系數(shù).

然而,方程組的求解也并不是一件容易的事。1.2.1待定系數(shù)法

對于線性插值的兩種形式解進行適當(dāng)?shù)姆治?從中尋求規(guī)律而得到啟發(fā),就有了所謂的拉格朗日插值法(公式)和牛頓插值(公式).我們先來看看如何得到二次拉格朗日插值公式（和牛頓插值公式（為討論方便，留待后述））.首先,線性插值的兩點式可看作是兩個特殊的一次式的一種線性組合.101xxxx--010xxxx--)(1xP=y0

+y1==10)(iiiyxl兩點式l0(x)l1(x)實質(zhì)上（）和（）即是滿足函數(shù)表的一次插值多項式,稱l0(x)和l1(x)為以x0,x1為節(jié)點的基本插值多項式，也稱為線性插值的插值基函數(shù)。于是，線性插值即是用基函數(shù)的線性組合來構(gòu)造的.1.2.2基函數(shù)法稱為拉氏基函數(shù)，滿足li(xj)=ij

顯然有l(wèi)0(x)+l0(x)≡1.這里，l0(x)和l1(x)具有如下性質(zhì)：l0(x0)=1,l0(x1)=0,l1(x0)=0,l1(x1)=1,由此啟發(fā)，我們希望二次插值也能由一些二次插值基函數(shù)來線性組合:這時，l0(x),l1(x),l2(x)都是二次多項式，且應(yīng)滿足滿足(2.1)式的

li(x)是否存在?若存在，具有什么形式呢?（2.1）同理可得

l1(x)＝1(x－x0)(x－x2),

l2(x)＝2(x－x0)(x－x1),1＝(x1－x0)(x1－x2)12＝(x2－x0)(x2－x1)1此即二次拉格朗日插值公式,其中,l0(x),l1(x),l2(x)是滿足(2.1)的特殊(基本)二次插值多項式;稱為二次插值基函數(shù).P2(x)=y0+y1+y2(x-x0)(x-x2)(x1-x0)(x1-x2)(x-x1)(x-x2)(x0-x1)(x0-x2)(x-x0)(x-x1)(x2-x0)(x2-x1)先考慮l0(x)。因l0(x)是以x1,x2

為零點的二次多項式,所以它可寫成l0(x)＝0(x－x1)(x－x2),

其中0

是待定系數(shù)。又因為l0(x0)=1，所以0(x0－x1)(x0－x2)＝1，則可有0＝(x0－x1)(x0－x2)1

l0(x)＝0(x－x1)(x－x2),

n

1希望找到li(x)，i=0,…,n

使得

li(xj)=ij

；然后令==niiinyxlxP0)()(，則顯然有Pn(xi)=

yi

。li(x)每個li有n

個根x0…

xi…xn=-=---=njjijiniiixxCxxxxxxCxl00)())...()...(()(-==jijiiiixxCxl)(11)(

拉格朗日多項式與有關(guān)，而與無關(guān)節(jié)點f1.3n

次插值定理(唯一性)滿足的n

階插值多項式是唯一存在的。證明：(存在性可利用Vandermonde

行列式論證)反證：若不唯一，則除了Ln(x)外還有另一n

階多項式Pn(x)滿足Pn(xi)=yi

?？疾靹tQn

的階數(shù)n而Qn有個不同的根n+1x0…xn注：若不將多項式次數(shù)限制為n

，則插值多項式不唯一。例如也是一個插值多項式，其中可以是任意多項式。設(shè)節(jié)點在[a,b]內(nèi)存在,考察截斷誤差，且f

滿足條件,Rolle’sTheorem:若充分光滑，，則存在使得。推廣：若使得使得存在使得Rn(x)至少有個根n+1=-=niinxxxKxR0)()()(任意固定x

xi(i=0,…,n),考察=-=niixtxKtRnt0)()()()(j(t)有n+2

個不同的根x0…

xn

x!)1()()()1(+-+nxKRxnnx注意這里是對t求導(dǎo)=+--++!)1)(()()()1()1(nxKLfxnnxnxx!)1()()()1(+=+nfxKxnx

1.4插值余項

(Remainder)注：

通常不能確定x

,而是估計,x(a,b)

將作為誤差估計上限。當(dāng)

f(x)為任一個次數(shù)n

的多項式時，,可知，即插值多項式對于次數(shù)n的多項式是精確的。例1

求經(jīng)過A(0,1)，B(1,2)，C(2,3)三個插值點的插值多項式.解：三個插值節(jié)點及對應(yīng)的函數(shù)值為由拋物插值公式得例2：已知分別利用sinx的1次、2次Lagrange插值計算sin50

并估計誤差。解：n=1分別利用x0,x1

以及x1,x2

計算利用這里而sin50=0.7660444…)185(50sin10pL0.77614外推

(extrapolation)

的實際誤差0.01001利用sin500.76008,內(nèi)插

(interpolation)

的實際誤差0.00596內(nèi)插通常優(yōu)于外推。選擇要計算的x

所在的區(qū)間的端點，插值效果較好。n=2)185(50sin20pL0.76543sin50=0.7660444…2次插值的實際誤差0.00061高次插值通常優(yōu)于低次插值但絕對不是次數(shù)越高就越好，嘿嘿……

例3

考慮下述的插值法問題：求二次多項式P(x)，滿足P(x0)=y0,其中是已給的數(shù)據(jù)并給出使這一問題的解存在且唯一的條件.解：設(shè)則由已知條件有即所以故原問題的唯一可解性就歸結(jié)為上述方程組的唯一可解性而后者唯一可解的充要條件為這就是P（x）存在且唯一的條件。

Lagrange插值公式(利用插值基函數(shù)很容易得到):

含義直觀,結(jié)構(gòu)緊湊,在理論分析中非常方便;

計算機上實現(xiàn)也很容易.也有一些缺點：

一是計算量大，這是顯然的；另外，還有一個更嚴(yán)重的缺點，當(dāng)插值節(jié)點增加時，全部插值基函數(shù)均要隨之變化，整個計算工作必須從頭開始：不僅原來的每一項都要改變，還要增加一項計算。

為克服上述兩個缺點,

努力：把插值多項式變形為便于計算的形式。希望：計算改變的過程中,盡可能能利用已有的計算結(jié)果.

下面我們將看到,這是可能的。我們可以有具有“承襲性”的所謂牛頓公式。)()(0010101xxxxyyyxP---+=)(001010xxxxxxy---+=(())fff[x0,x1]二次牛頓插值多項式我們再看線性插值的點斜式:)(00xxy-+=f[x0,x1]常數(shù)(差商)由此啟發(fā)，我們希望二次插值也能類似地有有規(guī)律的組合表達式:P2(x)=0+1(x-x0)+2(x-x0)(x-x1)利用P2(x0)=y0有:0=y0,利用P2(x1)=y1有:1=0101xxxx--(())ff=f[x0,x1],利用P2(x2)=y2有:2=f[x0,x1]

(x2-x0)(x2-x1)

(x2-x0)(x2-x1)0xx2-(())ff

(x2-x0)-f[x0,x2]f[x0,x1]

x2-x1

=-=f[x0,x1,x2];P2(x)=f(x0)

+(x-x0)+(x-x0)(x-x1)

f[x0,x1]

f[x0,x1,x2]f[x0,x2]

x=x0時0注:1.事實上,從上述可看出二次牛頓插值公式是用待定系數(shù)法求得的;2.它也可看作是三個特殊函數(shù)的一種線性組合:P2(x)=f(x0)

+(x-x0)+(x-x0)(x-x1)

f[x0,x1]

f[x0,x1,x2]

f[x0,x1],

f[x0,x1,x2]f(x0),

1,(x-x0),(x-x0)(x-x1)即函數(shù)的線性組合,組合系數(shù)為本質(zhì)上還是基函數(shù)法.更一般地，n+1個節(jié)點的插值多項式，我們希望由上述類似的一組特殊函數(shù)：來線性組合為：

1,(x-x0),(x-x0)(x-x1)，……，(x-x0)(x-x1)…(x-xn)那么其組合系數(shù)是什么樣的呢？怎么求呢？我們同樣可用待定系數(shù)法.容易發(fā)現(xiàn),計算a0,a1,a2,…,an

是很有規(guī)律的.一、均差及其性質(zhì)§2牛頓插值當(dāng)x=x0時，Pn(x0)=a0=f0.當(dāng)x=x1時，Pn(x1)=a0+a1(x1-x0)=f1,推得a1=f1-f0x1-x0當(dāng)x=x2時，Pn(x2)=a0+a1(x2-x0)+a2(x2-x0)(x2-x1)=f2,推得f1-f0x1-x0-f1-f0x1-x0a2=x2-x1依次遞推可得到a3,…,an.為寫出系數(shù)ak的一般表達式,先引進如下均差定義.定義2

稱為函數(shù)f(x)關(guān)于點x0,xk的一階均差.稱為f(x)的二階均差.一般地,稱為f(x)的k階均差(差商).

f[x0,xk]=f(xk)-f(x0)xk-x0

f[x0,x1,xk]=f[x0,xk]-f[x0,x1]xk-x1

f[x0,x1,…,xk]=f[x0,…,xk-2,xk]-f[x0,x1,…,xk-1]xk-xk-1均差有如下的基本性質(zhì):

1ok階均差可表示為函數(shù)值f(x0),f(x1),…,f(xk)的線性組合,即

f[x0,x1,…,xk]=f(xj)(xj-xj+1)…(xj-xk)…(xj-xj+1)(xj-x0)∑

kj=0這個性質(zhì)可用歸納法證明.這個性質(zhì)也表明均差與節(jié)點的排列次序無關(guān),稱為均差的對稱性,即

f[x0,x1,…,xk]=f[x1,x0,x2,…,xk]=…=f[x1,…,xk,x0]

f[x0,x1,…,xk]=f[x1,…,xk-1,xk]-f[x0,x1,…,xk-1]xk-x02o由性質(zhì)1o可得:

f[x0,x1,…,xk]=f(n)(ξ)n!

3o若f(x)在[a,b]上存在n階導(dǎo)數(shù),且節(jié)點x0,x1,…,xn[a,b],則n階均差與導(dǎo)數(shù)關(guān)系如下:這個公式可直接用羅爾定理證明.所以12…………n11+(x

x0)2+……+(x

x0)…(x

xn1)n1Nn(x)Rn(x)ai=

f[x0,…,xi]二、牛頓插值公式Rn(x)Nn(x)ωn+1(x)多項式Nn(x)顯然滿足插值條件,即Nn(xj)=f(xj),(j=1,…,n),且次數(shù)不超過n,由唯一性定理它就是前述的Ln(x),其系數(shù)為

Nn(x)稱為牛頓均差插值多項式,它比拉格朗日插值多項式計算量省,且便于程序設(shè)計.注：

由唯一性可知Nn(x)Ln(x)，只是算法不同，故其余項也相同，即實際計算過程為f(x0)f(x1)f(x2)…f(xn1)f(xn)f[x0,x1]f[x1,x2]…………f[xn1,xn]f[x0,x1,x2]…………f[xn2,xn1,xn]f[x0,…,xn]

f(xn+1)f[xn,xn+1]f[xn1,xn,xn+1]f[x1,…,xn+1]f[x0,…,xn+1]均差計算可列均差表如下：

例1

依據(jù)如下函數(shù)值表建立不超過3次的拉格朗日插值多項式及牛頓插值多項式Nn(x),并驗證插值多項式的唯一性.

解:(1)拉格朗日插值多項式Ln(x).插值基函數(shù)xk0124f(xk)19233拉格朗日插值多項式為:xkf(xk)

一階均差二階均差三階均差0119822314343-10-8(2)牛頓插值多項式Nn(x).建立如下差商表牛頓插值多項式為:(3)唯一性驗證.通過比較牛頓插值多項式和拉格朗日插值多項式,知:Nn(x)=Ln(x)這一事實與插值多項式的唯一性一致.2已知等距節(jié)點三、Newton等距插值1、差分定義簡記為簡記為簡記為向前差分向后差分中心差分前差算子后差算子高階向前差分高階向后差分如2、高階差分又如3、前差與后差的關(guān)系一般有再定義前移算子不變算子后移算子則有因此4差商與差分的關(guān)系m階向前差商與m階向前差分的關(guān)系查看全部m階向后差商與m階向后差分的關(guān)系又所以5、差分的計算6、等距節(jié)點的Newton插值已知等距節(jié)點得令由Newton插值公式其中參照即前插公式同理可得后插公式（P27)§3厄爾米特插值不僅要求函數(shù)值重合，而且要求若干階導(dǎo)數(shù)也重合。即：要求插值函數(shù)

(x)

滿足

(xi)=f(xi),’(xi)=f’(xi),…,(mi)(xi)=f

(mi)(xi).注：

N

個條件可以確定階多項式。N

1要求在1個節(jié)點x0處直到m0

階導(dǎo)數(shù)都重合的插值多項式即為Taylor多項式其余項為一般只考慮f

與f’的值。

當(dāng)較大時用待定系數(shù)法求是困難的令為次多項式且滿足其中且滿足令為次多項式所以

為Hermite插值多項式。Kronecker（克羅內(nèi)克）符號柏林科學(xué)院院士，巴黎科學(xué)院通訊院士，倫敦皇家學(xué)會外籍會員。主張分析學(xué)應(yīng)奠基于算術(shù)，而算術(shù)的基礎(chǔ)是整數(shù)?？肆_內(nèi)克名言：“上帝創(chuàng)造了整數(shù)，其余都是人做的工作”令則其中又則由（1）（2）得所以其中則所以令則又由得所以例已知求三次多項式滿足解所以驗證：練習(xí)：（P43（19））求四次多項式滿足令解：在點0，1，2上做Lagrange插值函數(shù)則因此所以§4分段低次插值RememberwhatIhavesaid?IncreasingthedegreeofinterpolatingpolynomialwillNOTguaranteeagoodresult,sincehigh-degreepolynomialsareoscillating.例：在[5,5]上考察的Ln(x)。取

-5

-4

-3

-2

-1

0

1

2

3

4

5

-0.5

0

0.5

1

1.5

2

2.5

n

越大，端點附近抖動越大，稱為Runge現(xiàn)象Ln(x)f(x)分段低次插值

分段線性插值

在每個區(qū)間上，用1階多項式

(直線)逼近f(x):記，易證：當(dāng)時，一致失去了原函數(shù)的光滑性。

分段Hermite插值

/*Hermitepiecewisepolynomials*/給定在上利用兩點的y及y’構(gòu)造3次Hermite函數(shù)導(dǎo)數(shù)一般不易得到。Howcanwemakeasmoothinterpolationwithoutaskingtoomuchfromf?Headache…2、分段線性插值設(shè)函數(shù)在節(jié)點：上的函數(shù)值為：記步