數(shù)值分析插值法

數(shù)值分析插值法第一頁，共九十一頁，2022年，8月28日x0x1x2x3x4xP(x)

f(x)f(x)

y=f(x)≈P(x),使得P(xi)=f(xi)=yi(i=0,1,...,n)其它點P(x)

f(x)=y第二頁，共九十一頁，2022年，8月28日2.1.1插值問題設(shè)y=f(x)是區(qū)間[a,b]

上的一個實函數(shù),xi(i=0,1,...,n)是[a,b]上n+1個互異實數(shù),已知y=f(x)在xi的值yi=f(xi)(i=0,1,...,n),求一個次數(shù)不超過n的多項式Pn(x)使其滿足Pn(xi)=yi(i=0,1,...,n)

(5-1)這就是多項式插值問題.2.1引言第三頁，共九十一頁，2022年，8月28日其中Pn(x)稱為f(x)的n次插值多項式,f(x)稱為被插函數(shù),xi(i=0,1,...,n)稱為插值節(jié)點,(xi,yi)(i=0,1,…,n)稱為插值點,[a,b]稱為插值區(qū)間,式(5-1)稱為插值條件。從幾何意義來看,上述問題就是要求一條多項式曲線y=Pn(x),使它通過已知的n+1個點(xi,yi)(i=0,1,…,n),并用Pn(x)近似表示f(x).第四頁，共九十一頁，2022年，8月28日即P(x)=a0+a1x+a2x2+...+anxn其中ai為實數(shù)，就稱P(x)為插值多項式，相應(yīng)的插值法稱為多項式插值，若P(x)為分段的多項式，就稱為分段插值，若P(x)為三角多項式,就稱為三角插值，本章只討論插值多項式與分段插值。本章主要研究如何求出插值多項式，分段插值函數(shù)，樣條插值函數(shù)；討論插值多項式P(x)的存在唯一性、收斂些及誤差估計等。第五頁，共九十一頁，2022年，8月28日定理1

設(shè)節(jié)點xi(i=0,1,…,n)互異,則滿足插值條件

Pn(xi)=yi(i=0,1,...,n)的次數(shù)不超過n的多項式存在且唯一.證設(shè)所求的插值多項式為Pn(x)=a0+a1x+a2x2+...+anxn(5-2)則由插值條件式Pn(xi)=yi(i=0,1,...,n)可得關(guān)于系數(shù)a0,a1,…,an的線性代數(shù)方程組2.1.2插值多項式的存在性和唯一性第六頁，共九十一頁，2022年，8月28日此方程組有n+1個方程,n+1個未知數(shù),其系數(shù)行列式是范德蒙(Vandermonde)行列式：（5-3）由克萊姆法則知方程組(5-3)的解存在唯一.證畢。第七頁，共九十一頁，2022年，8月28日考慮最簡單、最基本的插值問題.求n次插值多項式li(x)(i=0,1,…,n),使其滿足插值條件2.2.1基函數(shù)可知,除xi點外,其余都是li(x)的零點,故可設(shè)Lagrange法1736-1813

2.2拉格朗日插值第八頁，共九十一頁，2022年，8月28日其中A為常數(shù),由li(xi)=1可得稱之為拉格朗日基函數(shù),都是n次多項式。第九頁，共九十一頁，2022年，8月28日

n=1時的一次基函數(shù)為:y1O

xy1Ox第十頁，共九十一頁，2022年，8月28日即已知函數(shù)f(x)在點x0和x1點的函數(shù)值y0=f(x0)，y1=f(x1).求線性函數(shù)

L(x)=a0+a1x使?jié)M足條件：L(x0)=y0,L(x1)=y1.此為兩點線性插值問題第十一頁，共九十一頁，2022年，8月28日或用直線的兩點式表示為：插值基函數(shù)的特點：

x0x1l010l1011x0x1l0l1記第十二頁，共九十一頁，2022年，8月28日n=2時的二次基函數(shù)為:第十三頁，共九十一頁，2022年，8月28日可知其滿足2.2.2拉格朗日插值多項式利用拉格朗日基函數(shù)li(x),構(gòu)造次數(shù)不超過n的多項式稱為拉格朗日插值多項式,再由插值多項式的唯一性,得特別地,當(dāng)n=1時又叫線性插值,其幾何意義為過兩點的直線.當(dāng)n=2時又叫拋物（線）插值,其幾何意義為過三點的拋物線.第十四頁，共九十一頁，2022年，8月28日注意:(1)對于插值節(jié)點,只要求它們互異,與大小次序無關(guān);

以xi(i=0,1,…,n)為插值節(jié)點,函數(shù)f(x)1作插值多項式,由插值多項式的唯一性即得基函數(shù)的一個性質(zhì)(2)插值基函數(shù)li(x)僅由插值節(jié)點xi(i=0,1,…,n)確定,與被插函數(shù)f(x)無關(guān);(3)插值基函數(shù)li(x)的順序與插值節(jié)點xi(i=0,1,…,n)的順序一致.第十五頁，共九十一頁，2022年，8月28日這是因為若取(x)=xk

(k=0,1,…,n),由插值多項式的唯一性有特別當(dāng)k=0時,就得到第十六頁，共九十一頁，2022年，8月28日所以例1

已知用線性插值(即一次插值多項式)求的近似值?；瘮?shù)分別為:解插值多項式為()第十七頁，共九十一頁，2022年，8月28日例2求過點(-1,-2),(1,0),(3,-6),(4,3)的拋物線插值(即三次插值多項式).解以以為節(jié)點的基函數(shù)分別為:第十八頁，共九十一頁，2022年，8月28日則拉格朗日的三次插值多項式為第十九頁，共九十一頁，2022年，8月28日截斷誤差Rn(x)=f(x)-Ln(x)也稱為n次Lagrange插值多項式的余項。以下為拉格朗日余項定理。

定理2設(shè)f(x)在區(qū)間[a,b]上存在n+1階導(dǎo)數(shù),xi∈[a,b](i=0,1,…,n)為n+1個互異節(jié)點,則對任何x∈[a,b],有2.2.3插值余項且與x有關(guān))第二十頁，共九十一頁，2022年，8月28日證由插值條件和n+1(x)的定義,當(dāng)x=xk時,式子顯然成立,并且有n+1(xk)=0(

k=0,1,…,n),這表明x0

,

x1,

…,xn都是函數(shù)n+1(x)的零點,從而n+1(x)可表示為其中K(x)是待定函數(shù)。對于任意固定的x[a,b],xxk

,構(gòu)造自變量t的輔助函數(shù)第二十一頁，共九十一頁，2022年，8月28日由式n+1(xk)=0和式Ln(xk)=yk(k=0,1,…,n),以及可知：x0

,

x1,

,xn和x是(t)在區(qū)間[a,b]上的n+2個互異零點,因此根據(jù)羅爾(Rolle)定理,至少存在一點=(x)(a,b),使

即所以第二十二頁，共九十一頁，2022年，8月28日一般來說,外推比內(nèi)插效果差,在估計誤差時下列不等式很有用。第二十三頁，共九十一頁，2022年，8月28日的拋物插值多項式,且計算f(3)的近似值并估計誤差。例3設(shè)解插值多項式為第二十四頁，共九十一頁，2022年，8月28日因為故于是另見書p29的例1.第二十五頁，共九十一頁，2022年，8月28日用二次插值計算ln11.25的近似值,并估計誤差.例4

給定函數(shù)表x10111213lnx2.3025852.3978952.4849072.564949解

取節(jié)點x0=10,x1=11,x2=12,作二次插值有l(wèi)n11.25L2(11.25)第二十六頁，共九十一頁，2022年，8月28日在區(qū)間[10,12]上lnx的三階導(dǎo)數(shù)的上限M3=0.002,可得誤差估計式實際上,ln11.25=2.420368,|R2(11.25)|=0.000058.第二十七頁，共九十一頁，2022年，8月28日2.3.1均差及其基本性質(zhì)定義1稱為f(x)在x0、x1點的一階均差.一階均差的均差(差商)稱為函數(shù)f(x)在x0、x1、x2點的二階均差.英1642-17272.3均差與牛頓插值公式第二十八頁，共九十一頁，2022年，8月28日一般地，n-1階均差的均差

稱為f(x)在x0,x1,…,xn點的n階均差。差商的計算步驟與結(jié)果可列成均差表，如下

一般f(xi)稱為f(x)在xi點的零階均差，記作f[xi]。第二十九頁，共九十一頁，2022年，8月28日xk函數(shù)值一階均差二階均差三階均差...

x0x1

x2

x3...

f(x0)

f(x1)f(x2)f(x3)...

f[x0,x1]

f[x1,x2]

f[x2,x3]

...

f[x0,x1,x2]

f[x1,x2,x3]

...

f[x0,x1,x2,x3]

......表5-1（均差表）第三十頁，共九十一頁，2022年，8月28日給出節(jié)點x0,x1,…,xn和函數(shù)值(x0),(x1),…,(xn),可按如下的差商表順序逐次計算各階差商值.xi?(xi)一階差商二階差商三階差商…n階差商x0x1x2x3xn?(x0)?(x1)?(x2)?(x3)?(xn)?[x0,x1]?[x1,x2]?[x2,x3]?[xn-1,xn]?[x0,x1,x2]?[x1,x2,x3]?[xn-2,xn-1,xn]?[x0,x1,x2,x3]?[xn-3,xn-2,x2,x3]………………?[x0,x1,…,xn]第三十一頁，共九十一頁，2022年，8月28日這一性質(zhì)可以用數(shù)學(xué)歸納法證明，它表明均差與節(jié)點的排列次序無關(guān)，即

f[x0,x1,x2,...,xn]=f[x1,x0,x2,...,xn]=…=f[x1,x2,...,xn,

x0

]性質(zhì)1均差可以表示為函數(shù)值的線性組合，即稱之為均差的對稱性（也稱為對稱性質(zhì)）。第三十二頁，共九十一頁，2022年，8月28日性質(zhì)2由性質(zhì)1立刻得到或第三十三頁，共九十一頁，2022年，8月28日性質(zhì)3

n次多項式f(x)的k階差商,當(dāng)kn時是一個n-k次多項式;當(dāng)k>n時恒等于0.性質(zhì)4若f(x)在[a,b]上存在n階導(dǎo)數(shù),且節(jié)點x0,x1,…,xn∈[a,b],則至少存在一點[a,b]滿足下式例1

f(x)=－6x8+7x5－10,求f[1,2,…,9]及f[1,2,…,10].

解

f(8)(x)=－6·8!,f[1,2,…,9]=-6,

f(9)(x)=0,f[1,2,…,10]=0.第三十四頁，共九十一頁，2022年，8月28日2.3.2牛頓插值多項式設(shè)x是[a，b]上一點，由一階均差定義得同理，由二階均差定義如此繼續(xù)下去，可得一系列等式得得第三十五頁，共九十一頁，2022年，8月28日依次把后式代入前式，最后得第三十六頁，共九十一頁，2022年，8月28日其中第三十七頁，共九十一頁，2022年，8月28日可見,Nn(x)為次數(shù)不超過n的多項式,且易知Rn(xi)=0即Nn(xi)=yi,(i=0,1,…,n)滿足插值條件,故其為插值問題的解,Nn(x)稱為牛頓插值多項式。

Rn(x)稱為牛頓型插值余項。第三十八頁，共九十一頁，2022年，8月28日由插值多項式的唯一性知，它與拉格朗日插值多項式是等價的,即Ln(x)Nn(x)且有如下遞推形式和余項公式由此即得性質(zhì)4。且第三十九頁，共九十一頁，2022年，8月28日xkf(xk)一階均差二階均差三階均差四階均差0.400.550.650.800.900.410750.578150.696750.888111.026521.11601.18601.27571.38410.28000.35880.43360.19700.21370.0344例1已知f(x)=shx的數(shù)表,求二次牛頓插值多項式,并由此計算f(0.596)的近似值。解由上表可得過前三點的二次牛頓插值多項式為第四十頁，共九十一頁，2022年，8月28日又可得過前四點的三次牛頓插值多項式故可得N3(x)的截斷誤差第四十一頁，共九十一頁，2022年，8月28日設(shè)函數(shù)y=f(x)在等距節(jié)點xi=x0+ih(i=0,1,…,n)上的函數(shù)值為fi=f(xi)(h為步長)定義2

fi=fi+1-fi

和fi=fi-fi-1分別稱為函數(shù)f(x)在點xi處的一階向前差分和一階向后差分。一般地,f(x)在點xi處的m階向前差分和m階向后差分分別為mfi=

m-1fi+1-

m-1fi

和mfi=

m-1fi-

m-1fi-12.4差分與等距節(jié)點插值2.4.1差分及其性質(zhì)第四十二頁，共九十一頁，2022年，8月28日函數(shù)值一階差分二階差分三階差分四階差分...

f(x0)

f(x1)f(x2)f(x3)f(x4)...

f0

(f1)

f1

(f2)

f2

(f3)f3

(f4)...

2f0

(2f2)

2f1

(2f3)2f2

(2f4)...

3f0

(3f3)

3f1

(3f4)...4f0

(4f4)......構(gòu)造差分表5-2第四十三頁，共九十一頁，2022年，8月28日容易證明，差分有如下基本性質(zhì)性質(zhì)1各階差分均可用函數(shù)值表示.即且有等式nfi=nfi+n.第四十四頁，共九十一頁，2022年，8月28日性質(zhì)3均差與差分的關(guān)系式為性質(zhì)2函數(shù)值均可用各階差分表示.即且有差分與微商的關(guān)系式為差分的其它性質(zhì)參看本章p59習(xí)題8，9，10，11.第四十五頁，共九十一頁，2022年，8月28日代入牛頓插值公式,可得稱為牛頓向前插值公式，其余項為插值節(jié)點為xi=x0+ih(i=0,1,…,n),如果要計算x0附近點x處的函數(shù)值f(x),可令x=x0+th

(0tn)2.4.2等距節(jié)點差值公式第四十六頁，共九十一頁，2022年，8月28日類似地,若計算xn附近的函數(shù)值f(x),可令x=xn+th(-

n

t0)

，可得牛頓向后插值公式及其余項第四十七頁，共九十一頁，2022年，8月28日例2設(shè)y=f(x)=ex,xi=1,1.5,2,2.5,3,用三次插值多項式求f(1.2)及f(2.8)的近似值.解相應(yīng)的函數(shù)值及差分表如下:xif(xi)一階差分二階差分三階差分四階差分11.522.532.71828

4.481697.2890612.1824920.08554

1.76341

2.90347

4.793437.90305

1.14396

1.886063.10962

0.74210

1.223560.48146第四十八頁，共九十一頁，2022年，8月28日求f(1.2)用牛頓前插公式,且由1.2=1+0.5t,得t=0.4xif(xi)一階差分二階差分三階差分四階差分11.522.532.71828

4.481697.2890612.1824920.08554

1.76341

2.90347

4.793437.90305

1.14396

1.886063.10962

0.74210

1.223560.48146第四十九頁，共九十一頁，2022年，8月28日求f(2.8)用牛頓后插公式,且由2.8=3+0.5t,得t=-0.4xif(xi)一階差分二階差分三階差分四階差分11.522.532.71828

4.481697.2890612.1824920.08554

1.76341

2.90347

4.793437.90305

1.14396

1.886063.10962

0.74210

1.223560.48146求f(1.8)呢?第五十頁，共九十一頁，2022年，8月28日2.5.1三次埃爾米特插值多項式設(shè)y=f(x)是區(qū)間[a,b]上的實函數(shù),x0,x1是[a,b]上相異兩點,且x0＜x1,y=f(x)在xi上的函數(shù)值和一階導(dǎo)數(shù)值分別為yi=f(xi)(i=0,1)和mi=f(xi)(i=0,1),求三次多項式H3(x),使其滿足：H3(x)稱為三次埃爾米特插值多項式。法1822-19012.5埃爾米特(Hermite)插值第五十一頁，共九十一頁，2022年，8月28日構(gòu)造三次埃爾米特插值多項式如下:定理3滿足條件式的三次埃爾米特插值多項式存在且唯一。

條件函數(shù)函數(shù)值導(dǎo)數(shù)值x0x1x0x10(x)10001(x)01000(x)00101(x)0001第五十二頁，共九十一頁，2022年，8月28日由可將它寫成第五十三頁，共九十一頁，2022年，8月28日第五十四頁，共九十一頁，2022年，8月28日即插值點的Lagrange一次基函數(shù).第五十五頁，共九十一頁，2022年，8月28日可得滿足條件的三次埃爾米特插值多項式為第五十六頁，共九十一頁，2022年，8月28日定理4設(shè)f(x)在包含x0、x1的區(qū)間[a,b]內(nèi)存在四階導(dǎo)數(shù)，則當(dāng)x∈[a,b]時有余項設(shè)則當(dāng)x∈(x0,x1)時,余項有如下估計式（誤差限）2.5.2誤差估計且與x有關(guān))第五十七頁，共九十一頁，2022年，8月28日例2已知f(x)=x1/2及其一階導(dǎo)數(shù)的數(shù)據(jù)見下表,用埃爾米特插值公式計算1251/2的近似值,并估計其截斷誤差.x121144f(x)1112f'(x)1/221/24解第五十八頁，共九十一頁，2022年，8月28日得由可求得第五十九頁，共九十一頁，2022年，8月28日2.6分段低次插值先看下面的例子

對?(x)=(1+25x2)-1,在區(qū)間[-1,1]上取等距節(jié)點

xi=-1+ih,i=0,1,…,10,h=0.2,作?(x)關(guān)于節(jié)點

xi(i=0,1,…,10)的10次插值多項式L10(x),如圖所示第六十頁，共九十一頁，2022年，8月28日xyo1-10.511.5y=L10(x)這個現(xiàn)象被稱為Runge現(xiàn)象.表明高次插值的不穩(wěn)定性.實際上,很少采用高于7次的插值多項式.第六十一頁，共九十一頁，2022年，8月28日2.6.1分段線性插值求一個分段函數(shù)P(x),使其滿足:

P(xi)=yi(i=0,1,...,n);在每個子區(qū)間[xi，xi+1]上是線性函數(shù).稱滿足上述條件的函數(shù)P(x)為分段線性插值函數(shù).第六十二頁，共九十一頁，2022年，8月28日分別作線性插值得,在每個子區(qū)間[xi，xi+1]已知或第六十三頁，共九十一頁，2022年，8月28日由線性插值的誤差即得分段線性插值在區(qū)間[xi,xi+1]上的余項估計式為因此,在插值區(qū)間[a,b]上有余項第六十四頁，共九十一頁，2022年，8月28日2.6.2分段拋物線插值(2)在每個子區(qū)間[xi-1,xi+1]上，L(x)是次數(shù)不超過2的多項式.稱滿足上述條件的函數(shù)L(x)為分段拋物線插值函數(shù).

L(xi)=yi(i=0,1,...,n);對求一個分段函數(shù)L(x),使其滿足:即將區(qū)間[a,b]分為小區(qū)間[xi-1,xi+1](i=1,2,…,n)第六十五頁，共九十一頁，2022年，8月28日2.6.3分段三次Hermite插值已知求一個分段函數(shù)H(x),使其滿足:(2)在每個子區(qū)間[xi,xi+1]上，H(x)是次數(shù)不超過3的多項式.稱滿足上述條件的函數(shù)H(x)為分段三次Hermite插值函數(shù).第六十六頁，共九十一頁，2022年，8月28日或[xi，xi+1]上得在每個子區(qū)間由第六十七頁，共九十一頁，2022年，8月28日分段三次埃爾米特插值在區(qū)間[xi,xi+1]上的余項估計式為因此，在插值區(qū)間[a,b]上有余項第六十八頁，共九十一頁，2022年，8月28日例3構(gòu)造函數(shù)f(x)=lnx在1≤x≤10上的數(shù)表,應(yīng)如何選取步長h,才能使利用數(shù)表進(jìn)行分段插值時誤差不超過0.5×10-4。解欲使即進(jìn)行分段線性插值時，應(yīng)取h≤2×10-2，誤差不超過0.5×10-4。第六十九頁，共九十一頁，2022年，8月28日欲使即進(jìn)行分段三次埃爾米特插值時,應(yīng)取誤差不超過0.5×10-4。第七十頁，共九十一頁，2022年，8月28日2.7.1問題的提出定義給定區(qū)間[a,b]的一個劃分a=x0<x1<…<xn=b，yi=f(xi)(i=0,1,…,n),如果函數(shù)S(x)滿足：

S(xi)=yi(i=0,1,…,n);在每個小區(qū)間[xi,xi+1](i=0,1,...,n-1)上是次數(shù)不超過3的多項式;(3)在每個內(nèi)節(jié)點xi(i=1,2,...,n-1)上具有二階連續(xù)導(dǎo)數(shù),則稱S(x)為關(guān)于上述劃分的一個三次多項式樣條函數(shù)，簡稱三次樣條。2.7三次樣條插值第七十一頁，共九十一頁，2022年，8月28日S(x)在每個小區(qū)間[xi,xi+1]上是一個