計算方法第四章插值法

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

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

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

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

2.2二次插值二次插值又稱為拋物線插值,也是常用的代數(shù)多項式插值之一。設已知函數(shù)f(x)的三個互異插值基點x0，x1，x2的函數(shù)值分別為y0，y1，y2,見下表所示:xx0x1x2yy0y1y2（3點插值）現(xiàn)要構造一個二次函數(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)也唯一地被確定?！?代數(shù)多項式插值的存在唯一性對于一般的代數(shù)插值問題，就是尋求一個n次的代數(shù)多項式：

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

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

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

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

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

Pn(x)存在且唯一?！?代數(shù)多項式的余項一般說來,對插值區(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)x0x1x2x3x4xφ(x)f(x)插值多項式Pn(x)的余項定理:

設Pn(x)是過點x0，x1，x2，…，xn的f(x)的n次插值多項式，f(x)

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

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

插值的截斷誤差其中： 證明見書P145

插值的絕對誤差限為:由上面定理有一下幾點結論:(1)插值多項式只與插值基點及基點上的函數(shù)值有關，與函數(shù)f(x)沒有關系。但余項Rn(x)卻與f(x)聯(lián)系很緊。

(2)若f(x)即為次數(shù)不超過n的多項式，那么以n+1個點為基點的插值多項式就一定是其本身，即Pn

(x)≡f(x)。

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

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

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

給定[a,b]中互不相同的點x0，x1，x2，…，以及f(x)在這些點處相應的函數(shù)值f(x0)，f(x1)，f(x2)，…，用記號表示f(x)在x0及x1兩點的一階差商。x0，x1，x2三點的二階差商為：一般地，有了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插值余項0x牛頓差商表例3已知數(shù)據(jù)表，構造f(x)的牛頓均差插值多項式。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試求牛頓均差插值多項式。

例4已知數(shù)據(jù)表解:§7牛頓前差和后差插值多項式當插值基點x0,x1,…,xn分布等距時,也即

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

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

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

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

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

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

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

則

xi=x0+ih

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

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

2.牛頓后差插值多項式若將n+1個插值基點依xn,xn-1,…,x0的次序排列,則牛頓均差插值多項式為

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)易得用后差代替均差,可得牛頓后差插值多項式令

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

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

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

f(x)=x2+x+1

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

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

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

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

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

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

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

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

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

hk=xk+1-xk

對(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有關系,因此只要求得各個mk,則各個子區(qū)間［xk,x

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

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

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

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

y0=yn

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

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

f(x)≈Pn(x)

于是有

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

其余項相應地為R(k)n(x)。設插值基點為等距分布,由牛頓前差插值多項式其中由于于是即因為而當x=xi時,s=i,此時(4―59)(4―60)特別當x=x0時,s=0,則(4―61)

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

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

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

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

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

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

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

，使得f(x)

p(x)已知f(x)

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

f(x)y0y1…ym

m

通常很大

yi

本身是測量值，不準確，即yi

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

p(xi)

yi

總體上盡可能小

曲線擬合

使最小

使最小

p(xi)

yi

總體上盡可能小

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

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

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

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

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