第二講：插值法

第二章插值法

/*Chapter2Interpolation

*/1當(dāng)精確函數(shù)y=f(x)非常復(fù)雜或未知時(shí)，在一系列節(jié)點(diǎn)x0…xn

處測(cè)得函數(shù)值y0

=f(x0),…yn

=f(xn)，由此構(gòu)造一個(gè)簡(jiǎn)單易算的近似函數(shù)g(x)

f(x)，滿足條件g(xi)=f(xi)(i=0,…n)。這里的g(x)

稱(chēng)為f(x)的插值函數(shù)。最常用的插值函數(shù)是…?多項(xiàng)式x0x1x2x3x4xg(x)

f(x)§2.1多項(xiàng)式插值/*PolynomialInterpolation*/2§2.2拉格朗日多項(xiàng)式/*LagrangePolynomial*/niyxPiin,...,0,)(==求n

次多項(xiàng)式使得條件：無(wú)重合節(jié)點(diǎn)，即n=1已知x0

,x1

;

y0

,

y1

，求使得111001)(,)(yxPyxP==可見(jiàn)P1(x)是過(guò)(x0,y0

)和(x1,y1

)兩點(diǎn)的直線。)()(0010101xxxxyyyxP---+=101xxxx--010xxxx--=y0

+y1l0(x)l1(x)==10)(iiiyxl稱(chēng)為拉氏基函數(shù)

/*LagrangeBasis*/，滿足條件li(xj)=ij

/*KroneckerDelta*/線性插值3n=2已知x0

,x1

,

x2;

y0

,

y1,

y2

，滿足()y00,xf=拋物線插值，寫(xiě)出二次拉格朗日插值11)(yxf=,22)(yxf=多項(xiàng)式：==20)(iiiyxl)(xL2§2.2LagrangePolynomial4§2.2LagrangePolynomialn

1希望找到li(x)，i=0,…,n

使得

li(xj)=ij

；然后令==niiinyxlxP0)()(，則顯然有Pn(xi)=

yi

。li(x)每個(gè)li有n

個(gè)根x0…

xi…xn=-=---=njjijiniiixxCxxxxxxCxl00)())...()...(()(-==jijiiiixxCxl)(11)(LagrangePolynomial與有關(guān)，而與無(wú)關(guān)節(jié)點(diǎn)f5定理(唯一性)滿足的n

次插值多項(xiàng)式是唯一存在的。證明：反證：若不唯一，則除了Ln(x)外還有另一n

階多項(xiàng)式Pn(x)滿足Pn(xi)=yi

?？疾靹tQn

的階數(shù)n而Qn有個(gè)不同的根n+1x0…xn注：若不將多項(xiàng)式次數(shù)限制為n

，則插值多項(xiàng)式不唯一。例如也是一個(gè)插值多項(xiàng)式，其中可以是任意多項(xiàng)式?！?.2LagrangePolynomial6

插值余項(xiàng)/*Remainder*/設(shè)節(jié)點(diǎn)在[a,b]內(nèi)存在,考察截?cái)嗾`差，且f

滿足條件,RollesTheorem:若充分光滑，，則存在使得。推廣：若使得使得§2.2LagrangePolynomial7Rn(x)至少有個(gè)根n+1=-=niinxxxKxR0)()()(任意固定x

xi(i=0,…,n),考察=-=niixtxKtRnt0)()()()(j(t)有n+2

個(gè)不同的根x0…

xn

x!)1()()()1(+-+nxKRxnnx注意這里是對(duì)t求導(dǎo)=+--++!)1)(()()()1()1(nxKLfxnnxnxx!)1()()()1(+=+nfxKxnx§2.2LagrangePolynomial8注：

通常不能確定x

,而是估計(jì),x(a,b)

將作為誤差估計(jì)上限。當(dāng)

f(x)為任一個(gè)次數(shù)n

的多項(xiàng)式時(shí)，,可知，即插值多項(xiàng)式對(duì)于次數(shù)n的多項(xiàng)式是精確的?！?.2LagrangePolynomial注：

小的區(qū)間上插值有利于減少誤差；

依靠增多插值節(jié)點(diǎn)不一定能減少誤差；

多項(xiàng)式插值，外推誤差可能要比內(nèi)插誤差大。9例：已知分別利用sinx的1次、2次Lagrange插值計(jì)算sin50

并估計(jì)誤差。解：n=1分別利用x0,x1

以及x1,x2

計(jì)算利用這里而sin50=0.7660444…)185(50sin10pL0.77614外推

/*extrapolation*/

的實(shí)際誤差0.01001利用sin500.76008,內(nèi)插

/*interpolation*/

的實(shí)際誤差0.00596內(nèi)插通常優(yōu)于外推。選擇要計(jì)算的x

所在的區(qū)間的端點(diǎn)，插值效果較好?！?.2LagrangePolynomial10n=2)185(50sin20pL0.76543sin50=0.7660444…2次插值的實(shí)際誤差0.00061高次插值通常優(yōu)于低次插值但絕對(duì)不是次數(shù)越高就越好……§2.2LagrangePolynomial11Whenyoustartwritingtheprogram,youwillfindhoweasyitistocalculatetheLagrangepolynomial.Ohyeah?WhatifIfindthecurrentinterpolationnotaccurateenough?Thenyoumightwanttotakemoreinterpolatingpointsintoaccount.Right.ThenalltheLagrangebasis,li(x),willhavetobere-calculated.Excellentpoint!Wewillcometodiscussthisproblemnexttime.12§2.3牛頓插值/*Newton’sInterpolation*/Lagrange插值雖然易算，但若要增加一個(gè)節(jié)點(diǎn)時(shí)，全部基函數(shù)li(x)都需重新算過(guò)。的形式，希望每加一個(gè)節(jié)點(diǎn)時(shí)，將Ln(x)改寫(xiě)成只附加一項(xiàng)上去即可。????差商(亦稱(chēng)均差)

/*divideddifference*/1階差商

/*the1stdivideddifferenceoffw.r.t.xi

andxj

*/2階差商13§2.3Newton’sInterpolation11101010111010],,...,[],,...,[],,...,[],...,,[],...,[++--+++--=--=kkkkkkkkkkkxxxxxfxxxfxxxxxfxxxfxxf(k+1)階差商：事實(shí)上其中Warning:myheadisexploding…Whatisthepointofthisformula?差商的值與xi

的順序無(wú)關(guān)！P30均差的性質(zhì)14牛頓插值

/*Newton’sInterpolation*/12…………n11+(x

x0)2+……+(x

x0)…(x

xn1)n1Nn(x)--牛頓插值多項(xiàng)式Rn(x)ai=

f[x0,…,xi]§2.3Newton’sInterpolation15注：

由唯一性可知Nn(x)Ln(x)，只是算法不同，故其余項(xiàng)也相同，即實(shí)際計(jì)算過(guò)程為f(x0)f(x1)f(x2)…f(xn1)f(xn)f[x0,x1]f[x1,x2]…………f[xn1,xn]f[x0,x1,x2]…………f[xn2,xn1,xn]f[x0,…,xn]

f(xn+1)f[xn,xn+1]f[xn1,xn,xn+1]f[x1,…,xn+1]f[x0,…,xn+1]§2.3Newton’sInterpolation16§2.3Newton’sInterpolation例4(P32):給出f(x)的函數(shù)表，求4次牛頓插值多項(xiàng)式，并由此計(jì)算f(0.596)的近似值。N4(x)=0.41075+1.116(x-0.4)+0.28(x-0.4)(x-0.55)+0.19733(x-0.4)(x-0.55)(x-0.65)+0.03134(x-0.4)(x-0.55)(x-0.65)(x-0.8)f(0.596)≈N4(0.596)=0.63192R4(x)=f[x,x0,…,xn](x-0.4)(x-0.55)(x-0.65)(x-0.8)(x-0.9)

R4(0.596)？17Lagrange插值與Newton插值的本質(zhì)？18差分形式—等距節(jié)點(diǎn)公式

/*FormulaewithEqualSpacing*/向前差分iiifff-=+1ikikikikffff1111)(-+---==向后差分111----=ikikikfffi1iifff-=中心差分其中當(dāng)節(jié)點(diǎn)等距分布時(shí):§2.3Newton’sInterpolation19差分的重要性質(zhì)：

線性：例如若f(x)是m

次多項(xiàng)式，則是次多項(xiàng)式，而差分值可由函數(shù)值算出：=-+-=Dnjjknjknfjnf0)1(=-+--=njnjkjnknfjnf0)1(其中/*binomialcoefficients*/函數(shù)值可由差分值算出：kjnjknfjnfD=+=0kkkhkfxxf!],...,[00D=knkknnnhkfxxxf!],...,,[1=--kkkhff0)()(D=x由Rn

表達(dá)式§2.3Newton’sInterpolation20

牛頓公式牛頓前插公式/*Newton’sforward-differenceformula*/牛頓后插公式/*Newton’sbackward-differenceformula*/將節(jié)點(diǎn)順序倒置：設(shè)，則)()()(000xfkthtxNxNknknn=+==設(shè)，則)()1()()(0nknkknnnxfkthtxNxN--=+==注：一般當(dāng)x

靠近x0時(shí)用前插，靠近xn時(shí)用后插，故兩種公式亦稱(chēng)為表初公式和表末公式。§2.3Newton’sInterpolation21§2.4埃爾米特插值/*HermiteInterpolation*/不僅要求函數(shù)值重合，而且要求若干階導(dǎo)數(shù)也重合。即：要求插值函數(shù)

(x)

滿足

(xi)=f(xi),’(xi)=f’(xi),…,(mi)(xi)=f

(mi)(xi).注：

N

個(gè)條件可以確定次多項(xiàng)式。N

1要求在1個(gè)節(jié)點(diǎn)x0處直到m0

階導(dǎo)數(shù)都重合的插值多項(xiàng)式即為T(mén)aylor多項(xiàng)式其余項(xiàng)為一般只考慮f

與f’的值。22§2.4HermiteInterpolation例：設(shè)x0

x1x2,已知f(x0)、f(x1)、f(x2)

和f’(x1),求多項(xiàng)式P(x)

滿足P(xi)=f(xi)，i=0,1,2，且P’(x1)=f’(x1),并估計(jì)誤差。模仿Lagrange多項(xiàng)式的思想，設(shè)解：首先，P

的階數(shù)=3+=213)()()()()(=0iiixhx1f’xhxfxPh0(x)有根x1,x2，且h0’(x1)=0x1是重根。)()()(22100xxxxCxh--=又:h0(x0)=1C0h2(x)h1(x)有根x0,x2

))()(()(201xxxxBAxxh--+=由余下條件h1(x1)=1和

h1’(x1)=0可解。與h0(x)完全類(lèi)似。

(x)h1有根x0,x1,x2

h1))()(()(2101xxxxxxCx---=h1又:’(x1)=1C1

可解。其中hi(xj)=ij,hi’(x1)=0,

(xi)=0,

’(x1)=1h1h1與Lagrange分析完全類(lèi)似23一般地，已知x0

,…,xn

處有y0

,…,yn

和y0’

,…,yn’，求H2n+1(x)

滿足H2n+1(xi)=yi，H’2n+1(xi)=yi’。解：設(shè)+=ni)()()(=0iixhxhyixH2n+1n=0iyi’其中hi(xj)=ij,hi’(xj)=0,

(xj)=0,

’(xj)=ij

hihihi(x)有根x0

,…,xi,…,xn且都是2重根)()()(2xlBxAxhiiii+=由余下條件hi(xi)=1和

hi’(xi)=0可解Ai

和Bi

(x)hi有根x0

,…,xn,除了xi

外都是2重根hi)()(iili2(x)xxCx-=hi又:’(xi)=1Ci

=1hi)(x)(ili2(x)xx-=設(shè)則這樣的Hermite插值唯一

埃爾米特插值構(gòu)造基函數(shù)的方法§2.4HermiteInterpolation24Quiz:

給定xi=i+1,i=0,1,2,3,4,5.

下面哪個(gè)是h2(x)的圖像？x0--10.5123456yxy0---10.5123456斜率=1

求Hermite多項(xiàng)式的基本步驟：寫(xiě)出相應(yīng)于條件的hi(x)、hi(x)的組合形式；對(duì)每一個(gè)hi(x)、hi(x)找出盡可能多的條件給出的根；根據(jù)多項(xiàng)式的總階數(shù)和根的個(gè)數(shù)寫(xiě)出表達(dá)式；根據(jù)尚未利用的條件解出表達(dá)式中的待定系數(shù)；最后完整寫(xiě)出H(x)?！?.4HermiteInterpolation25§2.5分段低次插值/*piecewisepolynomialapproximation*/RememberwhatIhavesaid?IncreasingthedegreeofinterpolatingpolynomialwillNOTguaranteeagoodresult,sincehigh-degreepolynomialsareoscillating.例：在[5,5]上考察的Ln(x)。取

-5

-4

-3

-2

-1

0

1

2

3

4

5

-0.5

0

0.5

1

1.5

2

2.5

n

越大，端點(diǎn)附近抖動(dòng)越大，稱(chēng)為Runge現(xiàn)象Ln(x)f(x)分段低次插值26§2.5PiecewisePolynomialApproximation

分段線性插值

/*piecewiselinearinterpolation*/在每個(gè)區(qū)間上，用1次多項(xiàng)式

(直線)逼近f(x):記，易證：當(dāng)時(shí)，一致失去了原函數(shù)的光滑性。

分段三次Hermite插值

/*Hermitepiecewisepolynomials*/給定在上利用兩點(diǎn)的y及y’構(gòu)造3次Hermite函數(shù)導(dǎo)數(shù)一般不易得到。Howcanwemakeasmoothinterpolationwithoutaskingtoomuchfromf?Headache…27§2.6三次樣條插值

/*CubicSpline*/定義設(shè)。三次樣條函數(shù),

且在每個(gè)上為三次多項(xiàng)式

/*cubicpolynomial*/。若它同時(shí)還滿足，則稱(chēng)為f的三次樣條插值函數(shù)

/*cubicsplineinterpolant*/.注：三次樣條與分段Hermite插值的根本區(qū)別在于S(x)自身光滑，不需要知道f的導(dǎo)數(shù)值（除了在2個(gè)端點(diǎn)可能需要）；而Hermite插值依賴(lài)于f在所有插值點(diǎn)的導(dǎo)數(shù)值。f(x)H(x)S(x)28§2.6CubicSpline構(gòu)造三次樣條插值函數(shù)的三彎矩法

/*methodofbendingmoment*/在上，記](méi),[for)()(1][jjjxxxxSxS-=對(duì)每個(gè)j,此為3次多項(xiàng)式則S[j]”(x)為次多項(xiàng)式，需個(gè)點(diǎn)的值確定之。12設(shè)S[j]”(xj1)=Mj1，S[j]”(xj)=Mj

對(duì)應(yīng)力學(xué)中的梁彎矩，故名對(duì)于x

[xj1,

xj

]可得到S[j]”(x)=jjjjjjhxxMhxxM11---+-積分2次，可得S[j]’(x)和S[j](x)：jjjjjjjAhxxMhxxM+-+-----2)(2)(21121S[j]’(x)=jjjjjjjjBxAhxxMhxxM++-+---6)(6)(3131S[j](x)=利用已知S[j](xj1)=yj1S[j](xj)=yj

可解29jjjjjjjhMMhyyA611-----=jjjjjjjjjjjjhxxhMyhxxhMyBxA12211)6()6(-----+--=+下面解決Mj

：利用S’

在xj的連續(xù)性[xj1,

xj

]:

S[j]’(x)=jjjjjjjjjjjhMMxxfhxxMhxxM6],[2)(2)(112121------+-+--1111211216],[2)(2)(+++++++--+-+--jjjjjjjjjjjhMMxxfhxxMhxxM[xj,

xj+1]:

S[j+1]’(x)=利用S[j]’(xj)=S[j+1]’(xj)，合并關(guān)于Mj1、

Mj、Mj+1的同類(lèi)項(xiàng)，并記,,,整理后得到：11jjjjhhh+++=l1jj-=lm]),[],[(6111jjjjjjjxxfxxfhhg-++-+=211gMMMjjjjjj=+++-lm

j

1n1即：有個(gè)未知數(shù)，個(gè)方程。n1n+1還需2個(gè)邊界條件

/*boundaryconditions*/§2.6CubicSpline30

第1類(lèi)邊條件

/*clampedboundary*/：S’(a)=y0’，S’(b)=yn’[a,

x1

]:

S[1]’(x)=0011002102106],[2)(2)(hMMxxfhaxMhxxM--+-+--010010)],[(62gy0’xxfhMM=-=+nnnn-1n