數(shù)值分析 插值法

第2章插值法

簡介:插值法是函數(shù)逼近的重要方法之一，有著廣泛的應用。在生產(chǎn)和實驗中，函數(shù)f(x)或者其表達式不便于計算復雜或者無表達式而只有函數(shù)在給定點的函數(shù)值(或其導數(shù)值)，此時我們希望建立一個簡單的而便于計算的函數(shù)(x)，使其近似的代替f(x)，有很多種插值法,其中以拉格朗日(Lagrange)插值和牛頓(Newton)插值為代表的多項式插值最有特點,常用的插值還有Hermit插值,分段插值和樣條插值.

§1插值問題

設函數(shù)關系y=f(x)在區(qū)間［a,b］上給出一系列點的函數(shù)值

yi=f(xi),i=0,1,2,…,n(2―1)

或者給出一張函數(shù)表,如表2―1所示。表2―1xx0x1......xn

yy0y1.......yn這里

a≤x0＜x1＜x2＜…＜xn≤b

欲選擇一個函數(shù)φ(x),使得

φ(xi)=yi,i=0,1,2,…,n(2―2)

作為函數(shù)y=f(x)的近似表達式。應用：例如程控加工機械零件等。由于代數(shù)多項式具有形式簡單,便于計算,且在某些情況下與給定的函數(shù)有較好的逼近的特性,人們很早就用它去近似地表示復雜的函數(shù)或由表格給出的函數(shù)。

若僅限于求函數(shù)在x=x0附近的近似值,一個熟知的辦法就是將f(x)在x=x0處展成泰勒級數(shù),即取前n+1項的部分和Pn(x)作為f(x)的近似式,也即§2線性插值與二次插值

2.1線性插值線性插值是代數(shù)多項式插值的最簡單的形式。假設給定了函數(shù)f(x)在兩個互異點x0,x1的值,即xx0x1yy0y1現(xiàn)要用一線性函數(shù)

φ(x)=P1(x)=ax+b(2―3)

近似地代替f(x)。按照插值原則,式(2―2)應有因為x0≠x1,所以a,b可唯一確定,且有代入式(4―3)得(2―4)圖4.1因為P1(x)就是經(jīng)過兩點A(x0,y0),B(x1,y1)的直線方程,所以線性插值的幾何意義為用經(jīng)過兩點A(x0,y0),B(x1,y1)的直線近似地代替曲線y=f(x),見圖4.1。(2―5)

2.2二次插值二次插值又稱為拋物線插值,也是常用的代數(shù)多項式插值之一。設已知函數(shù)f(x)的三個互異插值基點x0,x1,x2的函數(shù)值分別為y0,y1,y2,見下表所示:xxox1x2yy0y1y2現(xiàn)要構造一個二次函數(shù)

φ(x)=P2(x)=ax2+bx+c(2―6)

近似地代替f(x),并滿足插值原則(4―2)P2(xi)=yi,i=0,1,2,…(2―7)

由(2―7)式得(2―8)由于方程組(2―8)中x0,x1,x2互異,則因此,a,b,c可唯一地確定。這樣二次函數(shù)P2(x)也唯一地被確定。P2(x)就是我們要求的二次插值多項式。二次插值的幾何意義是用經(jīng)過三點A(x0,y0),B(x1,y1),C(x2,y2)的拋物線來近似地代替f(x),見圖2.2。圖2.2§3代數(shù)多項式插值的存在唯一性線性插值和二次插值都屬于代數(shù)多項式插值。對于一般的代數(shù)插值問題,就是尋求一個不高于n次的代數(shù)多項式

Pn(x)=a0+a1x+a2x2+…+anxn(2―9)

使其在給定的n+1個互異的插值基點上滿足插值原則

Pn(xi)=yi,i=0,1,…,n(2―10)這樣的多項式是否存在并且唯一呢?回答是肯定的。根據(jù)插值原則式(2―10),代數(shù)多項式(2―9)中的各個系數(shù)a0,a1,…,an應滿足下列n+1階線性方程組其中未知量a0,a1,…,an的系數(shù)行列式為范德蒙特(VanderMonde)行列式由于插值基點xi(i=0,1,…,n)為互異,故

V(x0,x1,…,xn)≠0

因此,方程組(2―11)有唯一的一組解a0,a1,…,an,于是Pn(x)存在且唯一。§4代數(shù)多項式的余項代數(shù)多項式Pn(x)僅為已知函數(shù)f(x)的一種近似表達式,用它來代替f(x)進行計算總會帶來誤差。一般說來,對插值區(qū)間［a,b］上插值基點xi(i=0,1,2,…,n)以外的點,Pn(x)≠f(x)。若令

Rn(x)=f(x)-Pn(x)

則

f(x)=Pn(x)+Rn(x)我們稱Rn(x)為插值多項式Pn(x)的余項。顯然有

Rn(xi)=0,i=0,1,2,…,n

下面給出插值多項式Pn(x)余項的表達式。定理設函數(shù)f(x)在區(qū)間［a,b］上具有n+1階導數(shù),

Pn(x)為次數(shù)不高于n的多項式,且

Pn(x0)=y0

Pn(x1)=y1

…

Pn(xn)=yn

則對插值區(qū)間上的任何x,都存在ξ∈(a,b),使得這里(2―12)(2―13)證當x=xi時,式(2―12)顯然成立。當x∈(a,b)但不等于任一個插值基點時,作輔助函數(shù)上式右端第一項f(t)有n+1階導數(shù),第二項是次數(shù)不高于n的多項式,當x取某一定值時,第三項是變量t的n+1次多項式,因此F(t)有n+1階導數(shù)。又在區(qū)間［a,b］上,F(t)有n+2個零點

t=x,x0,x1,…,xn

應用洛爾(Rolle)定理,在(a,b)內(nèi)至少有ξ0,ξ1,…,ξn使得

F′(ξi)=0,i=0,1,2,…,n

如此反復應用洛爾定理,可知在(a,b)內(nèi)至少存在一點ξ使得

F(n+1)(ξ)=0于是可得到公式(2―12)。利用公式(2―12)可以給出用多項式Pn(x)近似代替f(x)的誤差估計。這里還得說明幾點:(1)插值多項式本身只與插值基點及f(x)在這些基點上的函數(shù)值有關,而與函數(shù)f(x)并沒有關系。但余項Rn(x)卻與f(x)聯(lián)系很緊。即

(2)若f(x)為次數(shù)不超過n的多項式,那么以n+1個點為基點的插值多項式就一定是其本身,即Pn(x)≡f(x)。這是因為此時Rn(x)=0。

(3)從余項Rn(x)中的ω(n+1)(x)知,當點x位于x0,x1,…,xn的中部時,|ωn+1(x)|比較小,精度要高一些,而位于兩端時,精度要差一些;若x位于x0,x1,…,xn的外部,一般稱為外插(或外推),此時精度一般不理想,使用時必須注意。

§5拉格朗日插值多項式我們根據(jù)插值原則將Pn(x)表示成下列形式,即這里(2―14)(2―15)

(2―14)式的Pn(x)是n+1個n次多項式li(x)(i=0,1,2,…,n)的線性組合,因而Pn(x)的次數(shù)不高于n。我們稱形如多項式(2―14)的Pn(x)為拉格朗日插值多項式。Pn(x)還可以寫成下列較簡單的形式:顯然(2―17)特別當n=1時,即得到y(tǒng)=f(x)的線性插值多項式(2―5):或(4―4)式:當n=2時,即得到y(tǒng)=f(x)的二次插值多項式例1已知函數(shù)y=f(x)的觀測數(shù)據(jù)為x1234y0-5-63試求拉格朗日插值多項式。解例2已知函數(shù)y=f(x)的觀測數(shù)據(jù)為x012y123試求拉格朗日插值多項式。解這是二次項系數(shù)為0的二次多項式。從幾何上看,這三點(0,1)、(1,2)、(2,3)在一條直線上。此例說明Pn(x)的次數(shù)可以小于n。拉格朗日插值多項式的計算框圖見圖2.3。圖2.3圖2.3優(yōu)點:Lagrange基函數(shù)容易構造,結(jié)構緊湊,便于理論研究.缺點:當增加或減少插值結(jié)點時,基函數(shù)需要重新構造,不便于實際的計算使用評價

§6牛頓均差(差商)插值多項式

拉格朗日插值多項式形式對稱,計算較方便,但由于li(x)依賴于全部基點,若算出所有l(wèi)i(x)后又需要增加基點,則必須重新計算。為了克服這個缺點,我們引進牛頓均差插值多項式。將插值多項式Pn(x)表示成下列形式:

Pn(x)=a0+a1(x-x0)+…+an(x-x0)(x-x1)…(x-xn-1)(2―18)

這里的插值基點為x0,x1,x2,…,xn,相應的函數(shù)值為y0,y1,…,yn。若根據(jù)插值原則

Pn(xi)=yi,i=0,1,2,…,n

則可逐次求出系數(shù)a0,a1,…,an。但這種確定系數(shù)的方法一般比較復雜。我們將利用均差概念導出牛頓均差插值多項式。

6.1均差設函數(shù)y=f(x)在區(qū)間［xi,xj］上定義,則稱(i≠j)為f(x)在區(qū)間［xi,xj］上的一階均差。一階均差的均差稱為二階均差,記為f［xi,xj,xk］。已知k階均差f［xi,x

i+1,…,xi+k］,f［xi+1,xi+2,…,xi+k+1］,則定義k+1階均差為并規(guī)定f(x)關于xi的零階均差為函數(shù)值本身,即

f［xi］=f(xi)

6.2牛頓均差插值多項式現(xiàn)在利用均差來推導牛頓均差插值多項式。由均差定義(2―20)將式(2―２０)中的第二式代入第一式的右端便得到線性牛頓均差插值公式(2―21)這里為線性插值多項式為其余項.將式(2―20)中的第三式代入式(2―21),又得到二次牛頓均差插值多項式(4―22)這里是二次插值多項式為其余項。仿此,每增加一個插值基點,只要將(2―20)中高階均差代入前一個公式,…,最后可得到(2―23)這里

(2-24)

(2-25)稱(2―24)式為牛頓均差插值多項式,(2―25)式為牛頓均差插值多項式的余項。將式(2―24)與(2―18)比較,顯然有

ak=f［x0,x1,…,xk］,k=0,1,2,…,n(2―26)根據(jù)插值多項式的存在唯一性,將牛頓均差插值公式與拉格朗日插值公式比較這樣得到均差與導數(shù)間的關系為

f［x,x0,x1,…,xn］(n+1)!=f(n+1)(ξ)(2―27)其中ξ∈(a,b)。牛頓均差插值多項式的計算極為方便,且當增加一個插值基點時,只要在后面多計算一項,Pn(x)的各項系數(shù)恰好是各階均差值。各階均差值可按均差表2―1計算。表2―1例3構造例1中f(x)的牛頓均差插值多項式。解作均差表2―2。表2―2

P3(x)=0+(-5)(x-1)+2(x-1)(x-2)+(x-1)(x-2)(x-3)=x3-4x2+3

例4已知數(shù)據(jù)表4―3。表2―3x

12356F(x)

0262090試求牛頓均差插值多項式。解作均差表2―4。表2―4下面敘述均差的幾個重要性質(zhì):(1)k階均差f［x0,x1,…,xk］是函數(shù)值f(x0),f(x1),…,f(xk)的線性組合,即

(2)均差f［x0,x1,…,xk］為x0,x1,…,xk的對稱函數(shù)。也就是設i0,i1,…,ik為0,1,2,…,k的任一種排列,則恒有

f［x0,x1,…,xk］=f［xi0,xi1,…,xik］(2―29)(3)設f(x)為x的n次多項式,則當k＞n時

f［x0,x1,…,xk］=0(4)設f(x)為x的n次多項式,則其一階均差f［x,x0］為x的n-1次多項式,二階均差f［x,x0,x1］為x的n-2次多項式,一般說來,k(k≤n)階均差f［x,x0,…,xk-1］為x的n-k次多項式。

(5)設f(x)可導,則定義一般地

f′(x,x0,x1,…,xn)=f(x,x,x0,x1,…,xn)(2―30)

性質(zhì)(1)、(2)、(3)、(4)證明都比較簡單,我們僅給出性質(zhì)(1)、(2)、(3)的證明,性質(zhì)(4)留給讀者證。證對于性質(zhì)(1),利用數(shù)學歸納法性質(zhì)(1)成立。假設k=m時成立,要證明k=m+1也成立。因為所以,性質(zhì)(1)成立。由性質(zhì)(1)可得可見改變基點的排列次序,實質(zhì)上僅是改變求和次序,其值不變。因此性質(zhì)(2)成立。最后證明性質(zhì)(3)。因為f(x)為x的n次多項式,以互異點x0,x1,…,xk為基點的牛頓均差插值多項式為

Pk(x)=f(x0)+f［x0,x1］(x-x0)+…+f(x0,x1,…,xk)(x-x0)(x-x1)…(x-xk-1)=f(x)

這說明多項式Pk(x)中的最高次應該是。故當k＞n時,Pk(x)中xk的系數(shù)f［x0,x1,…,xk］應為零。性質(zhì)(3)得證。拉格朗日插值與牛頓插值的比較

(1)與均是n次多項式,且均滿足插值條件:

由插值多項式的唯一性,,因而,兩個公式的余項是相等的,即則可知n階差商與導數(shù)的關系如下：（2）當插值多項式從n-1次增加到n次時,拉格朗日型插值必須重新計算所有的基本插值多項式;而對于牛頓型插值,只需用表格再計算一個n階差商,然后加上一項即可。（3）牛頓型插值余項公式對是由離散點給出或?qū)?shù)不存在時均適用?！?牛頓前差和后差插值多項式當插值基點x0,x1,…,xn分布等距時,也即

h=xk+1-xk,k=0,1,2,…,n-1

牛頓均差插值多項式的表達形式可以簡化。為此先引進有限差(差分)概念。

7.1差分我們分別稱為一階前差、一階后差和一階中心差,又統(tǒng)稱為一階差分。這里符號Δ、▽、δ分別表示前差、后差和中心差算子。由一階有限差算子的定義,用遞推方法可定義高階有限差。二階前、后差分別定義為依此類推,n階前差定義為n階后差定義為并規(guī)定零階前、后差為同樣可定義n階中心差根據(jù)有限差的定義,可得到它的幾個簡單性質(zhì):=(1)若函數(shù)f(x)為m次多項式,則m-k次多項式,0≤k≤mk＞m（即常數(shù)的有限差為零）(4―31)

(3)均差與前、后差的關系可表示為(2―32)(2―33)式(4―32)和(4―33)可用歸納法證明。

(2)各階差分之間有如下關系

7.2牛頓前差和后差插值多項式

1.牛頓前差插值多項式在牛頓均差插值多項式(2―24)中,按式(2―32)將均差換成前差,即得到牛頓前差插值多項式(2―34)令

x=x0+sh(s未必是整數(shù))

則

xi=x0+ihx-xi=(s-i)h,i=0,1,2,…,n

這樣牛頓前差插值多項式可改寫成(2―35)且其余項為

2.牛頓后差插值多項式