第二章：插值法

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

處測(cè)得函數(shù)值y0

=f(x0),…yn

=f(xn)，由此構(gòu)造一個(gè)簡(jiǎn)單易算的近似函數(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ù)是…?多項(xiàng)式：代數(shù)多項(xiàng)式最簡(jiǎn)單，計(jì)算其值只需用到加、減乘運(yùn)算，且積分和微分都很方便；所以常用它來近似表示表格函數(shù)(或復(fù)雜函數(shù)),這樣的插值方法叫做代數(shù)插值法，簡(jiǎn)稱插值法?！?拉格朗日多項(xiàng)式niyxPiin,...,0,)(==求n

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

,x1

;

y0

,

y1

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

)和(x1,y1

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

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

,x1

,x2;

y0

,

y1

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

,x1

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

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

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

+y1==10)(iiiyxl兩點(diǎn)式l0(x)l1(x)實(shí)質(zhì)上（）和（）即是滿足函數(shù)表的一次插值多項(xiàng)式,稱l0(x)和l1(x)為以x0,x1為節(jié)點(diǎn)的基本插值多項(xiàng)式，也稱為線性插值的插值基函數(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ù)來線性組合:這時(shí)，l0(x),l1(x),l2(x)都是二次多項(xiàng)式，且應(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)的特殊(基本)二次插值多項(xiàng)式;稱為二次插值基函數(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

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

其中0

是待定系數(shù)。又因?yàn)閘0(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)每個(gè)li有n

個(gè)根x0…

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

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

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

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

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

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

?？疾靹tQn

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

，則插值多項(xiàng)式不唯一。例如也是一個(gè)插值多項(xiàng)式，其中可以是任意多項(xiàng)式。設(shè)節(jié)點(diǎn)在[a,b]內(nèi)存在,考察截?cái)嗾`差，且f

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

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

個(gè)不同的根x0…

xn

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

1.4插值余項(xiàng)

(Remainder)注：

通常不能確定x

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

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

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

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

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

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

以及x1,x2

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

(extrapolation)

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

(interpolation)

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

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

例3

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

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

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

計(jì)算機(jī)上實(shí)現(xiàn)也很容易.也有一些缺點(diǎn)：

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

為克服上述兩個(gè)缺點(diǎn),

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

下面我們將看到,這是可能的。我們可以有具有“承襲性”的所謂牛頓公式。)()(0010101xxxxyyyxP---+=)(001010xxxxxxy---+=(())fff[x0,x1]二次牛頓插值多項(xiàng)式我們?cè)倏淳€性插值的點(diǎn)斜式:)(00xxy-+=f[x0,x1]常數(shù)(差商)由此啟發(fā)，我們希望二次插值也能類似地有有規(guī)律的組合表達(dá)式: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時(shí)0注:1.事實(shí)上,從上述可看出二次牛頓插值公式是用待定系數(shù)法求得的;2.它也可看作是三個(gè)特殊函數(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個(gè)節(jié)點(diǎn)的插值多項(xiàng)式，我們希望由上述類似的一組特殊函數(shù)：來線性組合為：

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

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

稱為函數(shù)f(x)關(guān)于點(diǎ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這個(gè)性質(zhì)可用歸納法證明.這個(gè)性質(zhì)也表明均差與節(jié)點(diǎn)的排列次序無關(guān),稱為均差的對(duì)稱性,即

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é)點(diǎn)x0,x1,…,xn[a,b],則n階均差與導(dǎo)數(shù)關(guān)系如下:這個(gè)公式可直接用羅爾定理證明.所以12…………n11+(x

x0)2+……+(x

x0)…(x

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

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

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

由唯一性可知Nn(x)Ln(x)，只是算法不同，故其余項(xiàng)也相同，即實(shí)際計(jì)算過程為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]均差計(jì)算可列均差表如下：

例1

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

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

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

(x)

滿足

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

(mi)(xi).注：

N

個(gè)條件可以確定階多項(xiàng)式。N

1要求在1個(gè)節(jié)點(diǎn)x0處直到m0

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

與f’的值。

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

為Hermite插值多項(xiàng)式。Kronecker（克羅內(nèi)克）符號(hào)柏林科學(xué)院院士，巴黎科學(xué)院通訊院士，倫敦皇家學(xué)會(huì)外籍會(huì)員。主張分析學(xué)應(yīng)奠基于算術(shù)，而算術(shù)的基礎(chǔ)是整數(shù)?？肆_內(nèi)克名言：“上帝創(chuàng)造了整數(shù)，其余都是人做的工作”令則其中又則由（1）（2）得所以其中則所以令則又由得所以例已知求三次多項(xiàng)式滿足解所以驗(yàn)證：練習(xí)：（P43（19））求四次多項(xiàng)式滿足令解：在點(diǎn)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

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

分段線性插值

在每個(gè)區(qū)間上，用1階多項(xiàng)式

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

分段Hermite插值

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