第二章：插值法

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

處測得函數值y0

=f(x0),…yn

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

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

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

f(x)根據實際需要，可以用各種不同的函數來近似原來的函數。最常用的插值函數是…?多項式：代數多項式最簡單，計算其值只需用到加、減乘運算，且積分和微分都很方便；所以常用它來近似表示表格函數(或復雜函數),這樣的插值方法叫做代數插值法，簡稱插值法?！?拉格朗日多項式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),將三點代入其表達式,即可得到三個方程式,從而聯立方程組解出系數a0,a1,a2即可:方程組的解是否存在?若存在解,是否唯一?!當x0

,x1

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

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

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

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

顯然有l(wèi)0(x)+l0(x)≡1.這里，l0(x)和l1(x)具有如下性質：l0(x0)=1,l0(x1)=0,l1(x0)=0,l1(x1)=1,由此啟發(fā)，我們希望二次插值也能由一些二次插值基函數來線性組合:這時，l0(x),l1(x),l2(x)都是二次多項式，且應滿足滿足(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)的特殊(基本)二次插值多項式;稱為二次插值基函數.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

是待定系數。又因為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)(

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

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

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

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

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

?？疾靹tQn

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

，則插值多項式不唯一。例如也是一個插值多項式，其中可以是任意多項式。設節(jié)點在[a,b]內存在,考察截斷誤差，且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求導=+--++!)1)(()()()1()1(nxKLfxnnxnxx!)1()()()1(+=+nfxKxnx

1.4插值余項

(Remainder)注：

通常不能確定x

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

將作為誤差估計上限。當

f(x)為任一個次數n

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

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

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

以及x1,x2

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

(extrapolation)

的實際誤差0.01001利用sin500.76008,內插

(interpolation)

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

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

例3

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

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

含義直觀,結構緊湊,在理論分析中非常方便;

計算機上實現也很容易.也有一些缺點：

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

為克服上述兩個缺點,

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

下面我們將看到,這是可能的。我們可以有具有“承襲性”的所謂牛頓公式。)()(0010101xxxxyyyxP---+=)(001010xxxxxxy---+=(())fff[x0,x1]二次牛頓插值多項式我們再看線性插值的點斜式:)(00xxy-+=f[x0,x1]常數(差商)由此啟發(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.事實上,從上述可看出二次牛頓插值公式是用待定系數法求得的;2.它也可看作是三個特殊函數的一種線性組合: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)即函數的線性組合,組合系數為本質上還是基函數法.更一般地，n+1個節(jié)點的插值多項式，我們希望由上述類似的一組特殊函數：來線性組合為：

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

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

稱為函數f(x)關于點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均差有如下的基本性質:

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

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

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

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由性質1o可得:

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

3o若f(x)在[a,b]上存在n階導數,且節(jié)點x0,x1,…,xn[a,b],則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),且次數不超過n,由唯一性定理它就是前述的Ln(x),其系數為

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

由唯一性可知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

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

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

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

(x)

滿足

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

(mi)(xi).注：

N

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

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

階導數都重合的插值多項式即為Taylor多項式其余項為一般只考慮f

與f’的值。

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

為Hermite插值多項式。Kronecker（克羅內克）符號柏林科學院院士，巴黎科學院通訊院士，倫敦皇家學會外籍會員。主張分析學應奠基于算術，而算術的基礎是整數?？肆_內克名言：“上帝創(chuàng)造了整數，其余都是人做的工作”令則其中又則由（1）（2）得所以其中則所以令則又由得所以例已知求三次多項式滿足解所以驗證：練習：（P43（19））求四次多項式滿足令解：在點0，1，2上做Lagrange插值函數則因此所以§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現象Ln(x)f(x)分段低次插值

分段線性插值

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

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

分段Hermite插值

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