數(shù)值分析 插值法

第2章插值法

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

§1插值問(wèn)題

設(shè)函數(shù)關(guān)系y=f(x)在區(qū)間［a,b］上給出一系列點(diǎn)的函數(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

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

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

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

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

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

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

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

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

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

近似地代替f(x),并滿(mǎn)足插值原則(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)就是我們要求的二次插值多項(xiàng)式。二次插值的幾何意義是用經(jīng)過(guò)三點(diǎn)A(x0,y0),B(x1,y1),C(x2,y2)的拋物線來(lái)近似地代替f(x),見(jiàn)圖2.2。圖2.2§3代數(shù)多項(xiàng)式插值的存在唯一性線性插值和二次插值都屬于代數(shù)多項(xiàng)式插值。對(duì)于一般的代數(shù)插值問(wèn)題,就是尋求一個(gè)不高于n次的代數(shù)多項(xiàng)式

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

使其在給定的n+1個(gè)互異的插值基點(diǎn)上滿(mǎn)足插值原則

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

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

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

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

則

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

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

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

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

Pn(x0)=y0

Pn(x1)=y1

…

Pn(xn)=yn

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

t=x,x0,x1,…,xn

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

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

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

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

(2)若f(x)為次數(shù)不超過(guò)n的多項(xiàng)式,那么以n+1個(gè)點(diǎn)為基點(diǎn)的插值多項(xiàng)式就一定是其本身,即Pn(x)≡f(x)。這是因?yàn)榇藭r(shí)Rn(x)=0。

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

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

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

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

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

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

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

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

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

6.1均差設(shè)函數(shù)y=f(x)在區(qū)間［xi,xj］上定義,則稱(chēng)(i≠j)為f(x)在區(qū)間［xi,xj］上的一階均差。一階均差的均差稱(chēng)為二階均差,記為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)關(guān)于xi的零階均差為函數(shù)值本身,即

f［xi］=f(xi)

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

(2-24)

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

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

f［x,x0,x1,…,xn］(n+1)!=f(n+1)(ξ)(2―27)其中ξ∈(a,b)。牛頓均差插值多項(xiàng)式的計(jì)算極為方便,且當(dāng)增加一個(gè)插值基點(diǎn)時(shí),只要在后面多計(jì)算一項(xiàng),Pn(x)的各項(xiàng)系數(shù)恰好是各階均差值。各階均差值可按均差表2―1計(jì)算。表2―1例3構(gòu)造例1中f(x)的牛頓均差插值多項(xiàng)式。解作均差表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試求牛頓均差插值多項(xiàng)式。解作均差表2―4。表2―4下面敘述均差的幾個(gè)重要性質(zhì):(1)k階均差f［x0,x1,…,xk］是函數(shù)值f(x0),f(x1),…,f(xk)的線性組合,即

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

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

f［x0,x1,…,xk］=0(4)設(shè)f(x)為x的n次多項(xiàng)式,則其一階均差f［x,x0］為x的n-1次多項(xiàng)式,二階均差f［x,x0,x1］為x的n-2次多項(xiàng)式,一般說(shuō)來(lái),k(k≤n)階均差f［x,x0,…,xk-1］為x的n-k次多項(xiàng)式。

(5)設(shè)f(x)可導(dǎo),則定義一般地

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

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

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

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

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

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

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

牛頓均差插值多項(xiàng)式的表達(dá)形式可以簡(jiǎn)化。為此先引進(jìn)有限差(差分)概念。

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

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

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

7.2牛頓前差和后差插值多項(xiàng)式

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

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

則

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

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

2.牛頓后差插值多項(xiàng)式