計(jì)算方法第四章插值法

第4章插值法§1插值問(wèn)題§2線性插值與二次插值§3代數(shù)多項(xiàng)式插值的存在唯一性§4代數(shù)多項(xiàng)式的余項(xiàng)§5拉格朗日插值多項(xiàng)式§6牛頓均差插值多項(xiàng)式§7牛頓前差和后差插值多項(xiàng)式§8三次樣條插值§9數(shù)值微分§10曲線擬合法?7=xi4916yi234479164320應(yīng)用背景造函數(shù)表：三角函數(shù)、對(duì)數(shù)預(yù)測(cè)：雞蛋價(jià)格、城市用水量數(shù)控加工：造船、飛機(jī)機(jī)翼骨架、服裝樣片、模具加工、刀具計(jì)算機(jī)輔助設(shè)計(jì)：潛水艇、汽車(chē)造型服裝樣片實(shí)際問(wèn)題中，f(x)多樣，復(fù)雜，通常只能觀測(cè)到一些離散數(shù)據(jù)；或者f(x)過(guò)于復(fù)雜而難以運(yùn)算。這時(shí)我們要用近似函數(shù)φ(x)來(lái)逼近f(x)。自然地，希望φ(x)通過(guò)所有的離散點(diǎn)。x0x1x2x3x4xφ(x)f(x)已知{xi，yi}，i=0,1,…,n是函數(shù)y=f(x)的離散點(diǎn)，φ(x)∈φ為y=f(x)的近似函數(shù)。滿足φ(xi)=yi，i=0,1,…,n稱這個(gè)問(wèn)題為曲線插值問(wèn)題。φ(x)為插值函數(shù)；xi,i=0,1,…,n為插值節(jié)點(diǎn)；f被插值函數(shù)；φ(xi)=yi插值條件或插值原則。(x)求§1插值問(wèn)題數(shù)學(xué)模型：已知{xi，yi}，求一條光滑曲線滿足φ(xi)=yi。理論問(wèn)題：1數(shù)學(xué)描述；2誤差估計(jì)；取前n+1項(xiàng)的部分和Pn(x)作為f(x)的近似式，也即：若僅限于求函數(shù)在x=x0的近似函數(shù)，一個(gè)熟知的辦法就是將f(x)在x=x0處展成泰勒級(jí)數(shù)，即多項(xiàng)式插值（待定系數(shù)法）多項(xiàng)式插值（待定系數(shù)法）代數(shù)多項(xiàng)式形式簡(jiǎn)單，便于計(jì)算，且在某些情況下與給定的函數(shù)有較好的逼近的特性1個(gè)點(diǎn)插值φ(x)=y0x0y0（，）xy§2線性插值與二次插值

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

φ(x)=P1(x)=ax+b

近似地代替f(x)。按照插值原則，有：因?yàn)閤0≠x1,所以a，b可唯一確定，且有

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

φ(x)=P2(x)=ax2+bx+c

近似地代替f(x)，并滿足插值原則

P2(xi)=yi，i=0，1，2，…x0，x1，x2互異，a，b，c可唯一地確定。二次函數(shù)P2(x)也唯一地被確定。§3代數(shù)多項(xiàng)式插值的存在唯一性對(duì)于一般的代數(shù)插值問(wèn)題，就是尋求一個(gè)n次的代數(shù)多項(xiàng)式：

Pn(x)=a0+a1x+a2x2+…+anxn

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

Pn(xi)=yi，i=0，1，…，n根據(jù)插值原則式，代數(shù)多項(xiàng)式中的各個(gè)系數(shù)a0，a1，…，an應(yīng)滿足下列n+1階線性方程組系數(shù)行列式為范德蒙特(VanderMonde)行列式由于插值基點(diǎn)xi(I=0，1，…，n)為互異,故

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

方程組有唯一的一組解a0，a1，…，an

Pn(x)存在且唯一。§4代數(shù)多項(xiàng)式的余項(xiàng)一般說(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)x0x1x2x3x4xφ(x)f(x)插值多項(xiàng)式Pn(x)的余項(xiàng)定理:

設(shè)Pn(x)是過(guò)點(diǎn)x0，x1，x2，…，xn的f(x)的n次插值多項(xiàng)式，f(x)

∈Cn+1[a,b]，其中[a，b]是包含點(diǎn)x0，x1，x2，…，xn的區(qū)間，則對(duì)任意給定的x[a，b]，總存在一點(diǎn)

（a，b）（依賴于x）使：

插值的截?cái)嗾`差其中： 證明見(jiàn)書(shū)P145

插值的絕對(duì)誤差限為:由上面定理有一下幾點(diǎn)結(jié)論:(1)插值多項(xiàng)式只與插值基點(diǎn)及基點(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)。

(3)當(dāng)點(diǎn)x位于x0，x1，…，xn的中部時(shí)，|ωn+1(x)|比較小，誤差小些，而位于兩端時(shí)，誤差要更大些。nkkiiknyxlyxP==?)()(i=0構(gòu)造li(x)為n次多項(xiàng)式，滿足：說(shuō)明：滿足插值條件φn(xi)=yi，i=0，1，…,n于是：§5拉格朗日插值多項(xiàng)式kiinknxlyxP=?)()(i=0li(xj)=j≠i1j=i0關(guān)鍵是:li(x)=？注意到li(xj)=0j≠i說(shuō)明li(x)中定有因子：(x–x0)(x–x1)…(x–xi-1)(x–xi+1)…(x–xn)即：xj，j≠i是li(x)的根再注意到li(xi)=1，說(shuō)明li(x)的分母中有因子(xi–x0)(xi–x1)…(xi–xi-1)(xi–xi+1)…(xi–xn)故有稱為L(zhǎng)agerange插值基但是將xi代入，此式不等于nixxxxxljijnijji,,1,0,)(0L=--P=1=當(dāng)n=1,Lagerange插值10100101)(yxxxxyxxxxxy--+--=x0x1y0y1xy010110)(,)(xxxxxlxxxxxl--=--=1022當(dāng)n=2時(shí)，Lagerange插值為：滿足插值條件：例：已知函數(shù)y=f(x)的觀測(cè)數(shù)據(jù)為x1234y0-5-63試求拉格朗日插值多項(xiàng)式。解：已知函數(shù)y=f(x)的觀測(cè)數(shù)據(jù)為x012y123試求拉格朗日插值多項(xiàng)式。解：例：解：圖4.3圖4.3想法：

Lagrange插值每增加一個(gè)節(jié)點(diǎn)，所有的系數(shù)必須重新計(jì)算。能否有一種方法，增加節(jié)點(diǎn)時(shí)，先前的計(jì)算仍然可以利用，只增加很少的工作量就能得到新的高次插值多項(xiàng)式。做法：§6牛頓均差插值多項(xiàng)式?將插值多項(xiàng)式Pn(x)表示成下列形式:依據(jù)條件，根據(jù)插值原則，可以依次確定系數(shù)a0，a1，…，an，例如：取x=x0，得取x=x1,得

為了得到計(jì)算系數(shù)ai的一般方法,下面引進(jìn)差商的概念.取x=x2,得二差商的定義

給定[a,b]中互不相同的點(diǎn)x0，x1，x2，…，以及f(x)在這些點(diǎn)處相應(yīng)的函數(shù)值f(x0)，f(x1)，f(x2)，…，用記號(hào)表示f(x)在x0及x1兩點(diǎn)的一階差商。x0，x1，x2三點(diǎn)的二階差商為：一般地，有了k-1階差商之后，可以定義f(x)在x0，x1，..，xk的k階差商：三Newton插值公式由差商定義,有

f(x)=f[x0]+(x-x0)f[x,x0]

f[x,x0]=f[x0,x1]+(x-x1)f[x,x0,x1]

f[x,x0,x1]=f[x0,x1,x2]+(x-x2)f[x,x0,x1,x2]………..

f[x,x0,…xn-1]=f[x0,…,xn]+(x-xn)f[x,x0,….,xn]將以上各式，由下而上逐步代入，得到

f(x)=f(x0)+(x-x0)f[x0,x1]+(x-x0)(x-x1)f[x0,x1,x2]+…+(x-x0)…(x-xn-1)f[x0,…,xn]+(x-x0)…(x-xn-1)(x-xn)f[x,x0,…xn](5)],,,,[))(())((],,,,[)())((],,[))((],[)()()(10110210110210101000nnnnnxxxxfxxxxxxxxxxxxfxxxxxxxxxfxxxxxxfxxxfxfLLLLL----+---++--+-+=--=Pn(x)稱為Newton插值公式=Rn(x)Newton插值余項(xiàng)0x牛頓差商表例3已知數(shù)據(jù)表，構(gòu)造f(x)的牛頓均差插值多項(xiàng)式。x1234y0-5-63

解：作均差表P3(x)=0+(-5)(x-1)+2(x-1)(x-2)+(x-1)(x-2)(x-3)=x3-4x2+3x

12356F(x)

0262090試求牛頓均差插值多項(xiàng)式。

例4已知數(shù)據(jù)表解:§7牛頓前差和后差插值多項(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有限差我們分別稱為一階前差、一階后差和一階中心差,又統(tǒng)稱為一階有限差。這里符號(hào)Δ、、δ分別表示前差、后差和中心差算子。由一階有限差算子的定義,用遞推方法可定義高階有限差。二階前、后差分別定義為依此類推,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)

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

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

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

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

則

xi=x0+ih

x-xi=(s-i)h,i=0,1,2,…,n

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

2.牛頓后差插值多項(xiàng)式若將n+1個(gè)插值基點(diǎn)依xn,xn-1,…,x0的次序排列,則牛頓均差插值多項(xiàng)式為

Pn(x)=f(xn)+f［xn,xn-1］(x-xn)+f［xn,x

n-1,…,x0］(x-xn)(x-xn-1)…(x-x1)

根據(jù)公式(4―33)易得用后差代替均差,可得牛頓后差插值多項(xiàng)式令

x=xn+th（t不一定是整數(shù)）則

xn-k=xn-khx-xn-k=(t+k)h,k=0,1,2,…,n于是牛頓后差插值多項(xiàng)式又可寫(xiě)成(4―37)或記為其余項(xiàng)為(4―38)這里

ωn+1(x)=t(t+1)(t+2)…(t+n)hn+1表4―5表4―6例5分別作出

f(x)=x2+x+1

的前差和后差表。解前差表見(jiàn)表4―7;后差表見(jiàn)表4―8。表4―7表4―8例6給出正弦函數(shù)sinx由x=0.4到0.7的值(h=0.1),試分別用牛頓前差和后差公式計(jì)算sin0.57891的近似值。解作差分表4―9。表4―９利用牛頓前差公式利用牛頓后差公式§8三次樣條插值

8.1三次樣條插值函數(shù)的定義設(shè)給定區(qū)間［a,b］上n+1個(gè)點(diǎn)

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

如果函數(shù)s(x)滿足:(1)在每一個(gè)子區(qū)間［xk,xk+1］(k=0,1,…,n-1)上,s(x)是一個(gè)不超過(guò)三次的多項(xiàng)式,且

s(xi)=f(xi),i=0,1,2,…,n(4―39)

(2)函數(shù)s(x)在［a,b］上具有直到二階的連續(xù)導(dǎo)數(shù),則稱s(x)是f(x)以x1,x2,…,xn-1為內(nèi)部基點(diǎn)的三次樣條插值函數(shù),并稱(xi,yi)(i=0,1,2,…,n)為樣條插值函數(shù)的樣點(diǎn)。

8.2三次樣條插值法按照三次樣條插值函數(shù)的定義,s(x)在每一個(gè)子區(qū)間［xk,xk+1］上是一個(gè)不超過(guò)三次的多項(xiàng)式,故s″(x)是線性函數(shù)。令

mk=s″(xk),k=0,1,2,…,n(4―40)

設(shè)x∈［xk,xk+1］,則過(guò)兩點(diǎn)(xk,mk)與(xk+1,mk+1)的直線所表示的線性函數(shù)為(4―41)其中

hk=xk+1-xk

對(duì)(4―41)式兩端連續(xù)求兩次積分得(4―42)(4―43)其中Ak、Bk為積分常數(shù)。根據(jù)插值原則由式(4―43)得到方程(4―44)從而解出Ak和Bk,即(4―45)(4―46)由式(4―43)可看出三次樣條插值函數(shù)s(x)僅與mk、mk+1有關(guān)系,因此只要求得各個(gè)mk,則各個(gè)子區(qū)間［xk,x

k+1］上的三次樣條函數(shù)也就確定了。下面介紹求mk的方法。當(dāng)x∈［xk-1,xk］時(shí),(4―47)式應(yīng)表示為當(dāng)x∈［xk,x

k+1］時(shí),(4―48)(4―49)根據(jù)三次樣條插值函數(shù)的定義,應(yīng)有整理后得到(4―50)那么于是(4―50)式可簡(jiǎn)寫(xiě)成(4―51)也即(4―52)

此是含有n+1個(gè)未知量m0,m1,…,mn的n-1個(gè)方程的方程組,我們可根據(jù)實(shí)際問(wèn)題的具體要求補(bǔ)充兩個(gè)附加條件,就可求出各個(gè)mk。在區(qū)間［a,b］的端點(diǎn)a和b(即x0和xn)處對(duì)樣條插值函數(shù)加以限制,稱為端點(diǎn)條件。常用的端點(diǎn)條件有以下幾種:①函數(shù)y=f(x)在兩端點(diǎn)x0及xn處的導(dǎo)數(shù)y′0和y′n為已知。此時(shí)要求由式(4―48)和(4―49)得到也即(4―53)其中(4―54)式(4―52)與式(4―53)兩個(gè)方程組聯(lián)立成

其幾何解釋為曲線在兩端點(diǎn)的斜率。②函數(shù)y=f(x)在兩端點(diǎn)x0,xn處的二階導(dǎo)數(shù)為零。此時(shí)要求其幾何解釋為曲線在兩端點(diǎn)的曲率為零。③函數(shù)y=f(x)是一個(gè)以b-a=xn-x0為周期的周期函數(shù)。此時(shí)

y0=yn

相應(yīng)也要求樣條插值函數(shù)s(x)也具有周期性,故在端點(diǎn)要求滿足條件由于hn=h0,mn=m0,yn=y0利用式(4―48)和式(4―49)可得到于是有(4―57)例7給出四個(gè)樣點(diǎn)(1,1)、(2,3)、(4,4)、(5,2),求其各個(gè)子區(qū)間上的樣條插值函數(shù)s(x)(設(shè)m0=m3=0),并求f(3)。解給定樣點(diǎn)的函數(shù)表為x1234y1342于是求mk的方程組為則關(guān)于m1,m2的方程組為解得在［1,2］上的樣條插值函數(shù)為在［2,4］上的樣條插值函數(shù)為在［4,5］上的樣條插值函數(shù)為并且§9數(shù)值微分

9.1用插值法求數(shù)值微分用插值多項(xiàng)式Pn(x)近似地表示函數(shù)f(x),即

f(x)≈Pn(x)

于是有

f(k)(x)≈P(k)n(x)

其余項(xiàng)相應(yīng)地為R(k)n(x)。設(shè)插值基點(diǎn)為等距分布,由牛頓前差插值多項(xiàng)式其中由于于是即因?yàn)槎?dāng)x=xi時(shí),s=i,此時(shí)(4―59)(4―60)特別當(dāng)x=x0時(shí),s=0,則(4―61)

1.兩點(diǎn)公式(n=1)于是在區(qū)間［x0,x2］上有(4―62)

2.三點(diǎn)公式(n=2)于是在區(qū)間［x0,x2］上有

9.2用三次樣條函數(shù)求數(shù)值微分設(shè)s(x)是f(x)在各區(qū)間［xk,xk+1］上的三次樣條插值函數(shù),則在區(qū)間［xk,xk+1

］上可通過(guò)三次樣條函數(shù)來(lái)求f(x)的數(shù)值微分。

1.一階數(shù)值微分公式(4―65)若只求基點(diǎn)xk(k=0,1,…,n-1)上的一階導(dǎo)數(shù)值,則(4―66)

2.二階數(shù)值微分公式特別,若只求基點(diǎn)上的二階導(dǎo)數(shù)值,則(4―67)

(4―68)§10曲線擬合法設(shè)一組觀測(cè)數(shù)據(jù)為xx0x1x2x3…xnyy0y1y2y3…yn能否找到一個(gè)簡(jiǎn)單易算的p(x)

，使得f(x)

p(x)已知f(x)

在某些點(diǎn)的函數(shù)值：xx0x1…xm

f(x)y0y1…ym

m

通常很大

yi

本身是測(cè)量值，不準(zhǔn)確，即yi

f(xi)不要求f(xi)通過(guò)所給的數(shù)據(jù)點(diǎn)，但能表述（xi，yi）的趨勢(shì)已知f(xi)的基本形式這時(shí)不要求p(xi)=yi,而只要

p(xi)

yi

總體上盡可能小

曲線擬合

使最小

使最小

p(xi)

yi

總體上盡可能小

常見(jiàn)做法不可導(dǎo)，求解困難，分析困難最小二乘法：目前最好的多項(xiàng)式曲線擬合算法設(shè)函數(shù)關(guān)系y=f(x)的一組觀測(cè)數(shù)據(jù)為(xi,yi)(i=0,1,2,…,n),欲求一個(gè)m(m＜n)次多項(xiàng)式

Pm(x)=α0+α1x+…+αmxm的平方和最小最小二乘法R稱為用Pm(x)擬合f(x)的總偏差根據(jù)極值理論，要使得R

達(dá)到極小，必有：稱此方程組為正則方程組。通過(guò)它可求出a0,a1,…,am。下面對(duì)m=2的情形作具體討論。

擬合函數(shù)基本形式為：

總偏差為：正則方程為：寫(xiě)成矩陣形式：例8設(shè)有一組數(shù)據(jù)表x1345678910y2781011111098試用二次