數(shù)值分析第二章-插值總結(jié)課件

第二章插值方法/*Interpolation*/Interpolation_introduction§1

問題提出—函數(shù)逼近

/*problemformulation-----functionapproximation*/用第二章插值方法/*Interpolation*/InInterpolation_introduction函數(shù)逼近的方法有很多，例如Taylor級數(shù)，F(xiàn)ourier級數(shù)，有限元方法、邊界元方法，小波分析等，大學(xué)科叫逼近論。本書討論連續(xù)函數(shù)的逼近，主要介紹插值法(chapter2)和最佳一直逼近、最小平方逼近離散數(shù)據(jù)擬合(chapter3)Interpolation_introduction函數(shù)逼近Interpolation_introduction插值節(jié)點插值條件---插值問題多項式插值是數(shù)值分析的基本工具，常用來計算被插函數(shù)的近似函數(shù)值，零、極點，導(dǎo)數(shù)、積分（第四章數(shù)值積分和數(shù)值微分），解微分方程（第五章）、積分方程插值Interpolation_introduction插值節(jié)點多項式插值----polynomialinterpolationProblemI.

給定y=f(x)的函數(shù)表,xi[a,b]niyxPiin,...,0,)(==求次數(shù)不超過n

的多項式使得條件：無重合節(jié)點，即InterpolationintervalInterpolationconditionInterpolationpolynomialInterpolationpointsInterpolationpolynomial

(2.1)(2.2)多項式插值----polynomialinterpolatx0x1x2x3x4xPn(x)

f(x)多項式插值的幾何意義Interpolationpolynomial

求x0x1x2x3x4xPn(x)f(x)多項式插值的幾插值多項式的唯一性

提問：ProblemI中的Pn(x)是否存在？若存在，是否唯一？如何求？Interpolationpolynomial

插值多項式的唯一性提問：ProblemI中的PInterpolationpolynomial

如何求？解線性方程組（2.3）----待定系數(shù)法Interpolationpolynomial如何求？解Interpolationpolynomial

Interpolationpolynomial§2拉格朗日多項式/*LagrangePolynomial*/niyxPiin,...,0,)(==求n

次多項式使得條件：無重合節(jié)點，即n=1已知x0,x1;

y0,

y1

，求使得111001)(,)(yxPyxP==可見P1(x)是過(x0,y0)和

(x1,y1)

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

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

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

/*KroneckerDelta*/§2LagrangePolynomial§2拉格朗日多項式/*LagrangePolynn

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

使得

li(xj)=ij

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

。li(x)每個li有n

個根x0…

xi…xn==jiC0=-njijxx)(---inxxixxxxC0))...()...((ixl)(-=jijxixiC)(1=iixl1)(LagrangePolynomial與節(jié)點有關(guān)，而與f無關(guān)==niinxlxP0)()(yi基函數(shù)法（n=1情形的推廣）§2LagrangePolynomialn1希望找到li(x)，i=0,…,n使得定理(唯一性)滿足的n

階插值多項式是唯一存在的。證明：(前面已利用Vandermonde

行列式論證)反證：若不唯一，則除了Ln(x)外還有另一n

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

?？疾靹tQn

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

，則插值多項式不唯一。例如也是一個插值多項式，其中可以是任意多項式?！?LagrangePolynomial定理(唯一性)滿足

插值余項

/*Remainder*/設(shè)節(jié)點在[a,b]內(nèi)存在,考察截斷誤差，且f

滿足條件,Rolle’sTheorem:若充分光滑，，則存在使得。推廣：若使得使得存在使得Rn(x)至少有個根n+1=-=niinxxxKxR0)()()(任意固定xxi(i=0,…,n),考察=-=niixtxKtRnt0)()()()(j(x)有n+2

個不同的根x0…

xn

x!)1()()()1(+-+nxKRxnnx注意這里是對t求導(dǎo)=+--++!)1)(()()()1()1(nxKLfxnnxnxx!)1()()()1(+=+nfxKxnx§2LagrangePolynomial插值余項/*Remainder*/設(shè)節(jié)點在[a,§1LagrangePolynomial注：

通常不能確定x

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

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

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

的多項式時，,可知，即插值多項式對于次數(shù)n的多項式是精確的。Quiz:

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

下面哪個是l2(x)的圖像？

y

0

-

-

-

1

0.5

-0.5

1

2

3

4

5

6

x

y

0

-

-

-

1

0.5

-0.5

1

2

3

4

5

6

x

y

0

-

-

-

1

0.5

-0.5

1

2

3

4

5

6

x

ABC§1LagrangePolynomial注：通常不§1LagrangePolynomial例：已知分別利用sinx的1次、2次Lagrange插值計算sin50

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

以及x1,x2

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

/*extrapolation*/

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

/*interpolation*/

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

所在的區(qū)間的端點，插值效果較好?！?LagrangePolynomial例：已知分別利§1LagrangePolynomialn=2)185(50sin20pL0.76543sin50=0.7660444…2次插值的實際誤差0.00061高次插值通常優(yōu)于低次插值但絕對不是次數(shù)越高就越好，嘿嘿……§1LagrangePolynomialn=2)1Whenyoustartwritingtheprogram,youwillfindhoweasyitistocalculatetheLagrangepolynomial.Ohyeah?WhatifIfindthecurrentinterpolationnotaccurateenough?Thenyoumightwanttotakemoreinterpolatingpointsintoaccount.Right.ThenalltheLagrangebasis,li(x),willhavetobere-calculated.Excellentpoint!Wewillcometodiscussthisproblemnexttime.Whenyoustart§3逐次線性插值

/*LagrangePolynomial*/§3逐次線性插值/*LagrangePolyno數(shù)值分析第二章-插值總結(jié)課件實際上，是對兩個低次插值的線性插值，這種通過低次插值再作線性插值生成高次插值的方法稱為逐次線性插值。

Aitken法(按下表計算)線性插值基函數(shù)實際上，是對兩個低次插值的線性插值，這種通過低次插值再作線性增加如果精度不構(gòu)，增加節(jié)點x4,同時表中增加一行，三角形斜邊上即為所要求的各次插值多項式。k1k0k2k3k4增加如果精度不構(gòu)，增加節(jié)點x4,同時表中增加一行，三角形斜邊

Neville法(按下表計算)增加如果精度不構(gòu)，增加節(jié)點x4,同時表中增加一行，三角形斜邊上即為所要求的各次插值多項式。k1k0k1k1k1HW:用類似于前面的方法構(gòu)造Neville計算公式Neville法(按下表計算)增加如果精度不構(gòu)，增加節(jié)點注：Atkin方法和Neville方法與Lagrange公式相比，當(dāng)需要增加節(jié)點時，很容易由低次插值構(gòu)造高次插值，而Lagrange插值公式中，每個基函數(shù)都需要作適當(dāng)變化。誤差估計：由插值多項式的存在唯一性知，仍有但這里可采用一種更簡便的方法。當(dāng)f(n+1)(x)在插值區(qū)間變化不大時，設(shè)f(n+1)(x)L，則有注：Atkin方法和Neville方法與Lagrange公式可認(rèn)為滿足精度要求。根據(jù)前面的計算結(jié)果估計當(dāng)前的誤差：事后誤差估計（實用），前面給出的誤差估計（事先誤差估計）不實用HW:p.58-59#1-8可認(rèn)為§4牛頓插值/*Newton’sInterpolation*/Lagrange插值雖然易算，但若要增加一個節(jié)點時，全部基函數(shù)li(x)都需重新算過。公式不具有繼承性，不利于編程。將Ln(x)改寫成的形式，希望每加一個節(jié)點時，只附加一項上去即可。????

差商(亦稱均差)

/*divideddifference*/1階差商

/*the1stdivideddifferenceoffw.r.t.xi

andxj

*/2階差商f(x0)1階差商的幾何意義：弦截線的斜率§4Newton’sInterpolation§4牛頓插值/*Newton’sInterpol§4Newton’sInterpolation11101010111010],,...,[],,...,[],,...,[],...,,[],...,[++--+++--=--=kkkkkkkkkkkxxxxxfxxxfxxxxxfxxxfxxf(k+1)階差商：事實上其中Warning:myheadisexploding…Whatisthepointofthisformula?差商的值與xi

的順序無關(guān)！§4Newton’sInterpolation11101.線性：2.差商可以表示為函數(shù)值的線性組合：3.

對稱性：由2知，差商的值與節(jié)點的順序無關(guān)！4.

差商的另一種定義：由2，3及均差定義可得§4Newton’sInterpolation1.線性：2.差商可以表示為函數(shù)值的線性組合：3.對稱性：6.5.

差商與導(dǎo)數(shù)的關(guān)系：f(x)Ck[a,b],則[a,b],s.t.HW:證明差商的性質(zhì)2，4§4Newton’sInterpolation6.5.差商與導(dǎo)數(shù)的關(guān)系：f(x)Ck[a,b],則§4Newton’sInterpolation牛頓插值

/*Newton’sInterpolation*/…………Nn(x)—n次多項式，滿足：Nn(xi)=f(xi)Rn(x)—插值余項，滿足Rn(xi)=0，i=0,…,n

ai=

f[x0,…,xi](1)(2)(n)(n)(n-1)…(2)(1)§4Newton’sInterpolation牛頓§4Newton’sInterpolation注：

由唯一性可知Nn(x)Ln(x)，只是算法不同，表達(dá)形式不同，故其余項也相同，即

實際計算過程為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]增加如果精度不構(gòu)，增加節(jié)點xn+1,同時表中增加一行，三角形斜邊上即為所要求的各次項系數(shù)?！?Newton’sInterpolation注：數(shù)值分析第二章-插值總結(jié)課件§4Newton’sInterpolation

等距節(jié)點公式

/*FormulaewithEqualSpacing*/向前差分

/*forwarddifference*/iiifff-=+1ikikikikffff1111)(-+---==向后差分

/*backwarddifference*/111----=ikikikfffi1iifff-=中心差分

/*centereddifference*/其中當(dāng)節(jié)點等距分布時:fi=f(xi)§4Newton’sInterpolation等距

差分計算可通過構(gòu)造差分表得到增加差分計算可通過構(gòu)造差分表得到增加數(shù)值分析第二章-插值總結(jié)課件

差分的重要性質(zhì)：

線性：例如

各階差分可用函數(shù)值表示：其中/*binomialcoefficients*/§4Newton’sInterpolation

函數(shù)值可用各階差分表示：差分的重要性質(zhì)：線性：例如各階差分可用函數(shù)值表

差商與差分的關(guān)系：

若f(x)是n

次多項式，則是次多項式，而差商與差分的關(guān)系：若f(x)是n次多項式，則

差分與導(dǎo)數(shù)的關(guān)系(由差分與差商、差商與導(dǎo)數(shù)的關(guān)系得）：差分與導(dǎo)數(shù)的關(guān)系(由差分與差商、差商與導(dǎo)數(shù)的關(guān)系得）：§4Newton’sInterpolation等距節(jié)點牛頓公式

牛頓前差公式/*Newton’sforward-differenceformula*/§4Newton’sInterpolation等距節(jié)點注：一般當(dāng)x

靠近x0時用前插，靠近xn時用后插，故兩種公式亦稱為表初公式和表末公式。

牛頓后差公式/*Newton’sforward-differenceformula*/HW:p.59#9-16注：一般當(dāng)x靠近x0時用前插，靠近xn時用后插，§5厄米插值/*HermiteInterpolation*/§5厄米插值/*HermiteInterpola不僅要求函數(shù)值重合，而且要求若干階導(dǎo)數(shù)也重合。即：要求插值函數(shù)

(x)

滿足

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

(mi)(xi).注：

N

個條件可以確定

階多項式。N

1要求在1個節(jié)點x0處直到m0

階導(dǎo)數(shù)都重合的插值多項式即為Taylor多項式其余項為一般只考慮f

與f'的值。厄米插值不僅要求函數(shù)值重合，而且要求若干階導(dǎo)數(shù)也重合。注：N個§3HermiteInterpolation例：設(shè)x0

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

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

滿足P(xi)=f(xi)，i=0,1,2，且P’(x1)=f’(x1),并估計誤差。模仿Lagrange多項式的思想，設(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)完全類似。

(x)h1有根x0,x1,x2

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

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

(xi)=0,

’(x1)=1h1h1與Lagrange分析完全類似§3HermiteInterpolation例：設(shè)x§3HermiteInterpolation一般地，已知x0

,…,xn

處有y0

,…,

yn

和y0’

,…,yn’

，求H2n+1(x)

滿足H2n+1(xi)=yi，H’2n+1(xi)=yi’?！?HermiteInterpolation一般地，已數(shù)值分析第二章-插值總結(jié)課件解：設(shè)+=ni)()()(=0iixxyixH2n+1n=0iyi’其中

i(xj)=ij,i’(xj)=0,

(xj)=0,

’(xj)=ij

ii(x)有根x0

,…,xi,…,xn且都是2重根由余下條件i

(xi)=1和

i’(xi)=0可解Ai

和Bi

(x)i有根x0

,…,xn,除了xi

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

=1i)(x)(ili2(x)xx-=設(shè)則這樣的Hermite插值唯一i)()()(2xlBxAxiii+=i解：設(shè)+=ni)()()(=0iixxyixH2n+1數(shù)值分析第二章-插值總結(jié)課件數(shù)值分析第二章-插值總結(jié)課件數(shù)值分析第二章-插值總結(jié)課件類似的，類似的，Th.設(shè)f(x)C2n+2[a,b],則[a,b],s.t.滿足下面插值條件Th.設(shè)f(x)C2n+2[a,b],則[a數(shù)值分析第二章-插值總結(jié)課件數(shù)值分析第二章-插值總結(jié)課件數(shù)值分析第二章-插值總結(jié)課件數(shù)值分析第二章-插值總結(jié)課件數(shù)值分析第二章-插值總結(jié)課件§3HermiteInterpolationQuiz:

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

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

求Hermite多項式的基本步驟：寫出相應(yīng)于條件的i(x)、i(x)的組合形式；對每一個i(x)、i(x)找出盡可能多的條件給出的根；根據(jù)多項式的總階數(shù)和根的個數(shù)寫出表達(dá)式；根據(jù)尚未利用的條件解出表達(dá)式中的待定系數(shù)；最后完整寫出H2n+1(x)。HW:p.59#17-19注：待定系數(shù)法仍適用，但插值節(jié)點多時比較麻煩?！?HermiteInterpolationQuiz:§4分段低次插值/*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

越大，端點附近抖動越大，稱為Runge現(xiàn)象Ln(x)f(x)分段低次插值§4分段低次插值/*piecewisepolyn§4PiecewisePolynomialApproximation

分段線性插值

/*piecewiselinearinterpolation*/在每個區(qū)間上，用1階多項式

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

分段Hermite插值

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

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

,

且在每個上為三次多項式

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

/*cubicsplineinterpolant*/.注：三次樣條與分段Hermite插值的根本區(qū)別在于S(x)自身光滑，不需要知道f的導(dǎo)數(shù)值（除了在2個端點可能需要）；而Hermite插值依賴于f在所有插值點的導(dǎo)數(shù)值。f(x)H(x)S(x)§5三次樣條/*CubicSpline*/定§5CubicSpline

構(gòu)造三次樣條插值函數(shù)的三彎矩法

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

對應(yīng)力學(xué)中的梁彎矩，故名對于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)=yj1

S[j](xj)=yj

可解§5CubicSpline構(gòu)造三次樣條插值函數(shù)的§5CubicSplinejjjjjjjhMMhyyA611-----=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的同類項，并記,,,整理后得到：11jjjjhhh+++=l1jj-=lm]),[],[(6111jjjjjjjxxfxxfhhg-++-+=211gMMMjjjjjj=+++-lm

j

1n1即：有個未知數(shù)，

個方程。n1n+1還需2個邊界條件

/*boundaryconditions*/§5CubicSplinejjjjjjjhMMhyy§5CubicSpline

第1類邊條件

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

,

x1

]:

S[1]’(x)=1011012112106],[2)(2)(hMMxxfhaxMhxxM--+-+--010110)],[(62gy0’xxfhMM=-=+nnnnnngxxfyn’hMM=-=+--]),[(6211類似地利用[xn1,

b

]上的

S[n]’(x)

第2類邊條件：S”(a)=y0”

=

M0，S”(b)=yn”

=

Mn這時：特別地，M0=

Mn=0

稱為自由邊界

/*freeboundary*/，對應(yīng)的樣條函數(shù)稱為自然樣條

/*NaturalSpline*/。

第3類邊條件/*periodicboundary*/

：當(dāng)f

為周期函數(shù)時，

yn

=y0

，

S’(a+)=S’(b)

M0=

Mn§5CubicSpline第1類邊條件/*c§5CubicSpline注：另有三轉(zhuǎn)角法(p.49-53)得到樣條函數(shù)，即設(shè)S[j]’(xj)=mj，則易知[xj1,

xj

]上的S[j](x)就是Hermite函數(shù)。再利用S”的連續(xù)性，可導(dǎo)出關(guān)于mj的方程組，加上邊界條件即可解。CubicSpline由boundaryconditions唯一確定。收斂性：若，且，則一致S(x)

f(x)即:提高精度只須增加節(jié)點,而無須提高樣條階數(shù)。穩(wěn)定性：只要邊條件保證|0|,|0|,|n|,|n|<2，則方程組系數(shù)陣為SDD陣，保證數(shù)值穩(wěn)定。HW:p.59-60,#19-25§5CubicSpline注：另有三轉(zhuǎn)角法(p.4§5CubicSpline

SketchoftheAlgorithm:CubicSpline①

計算j,j,gj;

②

計算Mj(追趕法等);③

找到x

所在區(qū)間(即找到相應(yīng)的j);④

由該區(qū)間上的S[j](x)算出f(x)的近似值。插值法小結(jié)Lagrange:給出y0…

yn，選基函數(shù)li(x)，其次數(shù)為

節(jié)點數(shù)–1。

NewtonLn(x)，只是形式不同；節(jié)點等距或漸增節(jié)點時方便處理。

Hermite：給出yi及yi’，選i(x)及

i(x)

。Spline：分段低次,自身光滑,f的導(dǎo)數(shù)只在邊界給出?！?CubicSplineSke§6快速傅立葉變換

/*FastFourierTransform*/問題的背景/*background*/傅立葉變換

——函數(shù)展開為三角級數(shù)設(shè)f(x)周期為2，在[0,2]上展開為三角級數(shù)，其中Cj

為復(fù)系數(shù)，，則實際計算時要取級數(shù)的前N項，并要求在區(qū)間的N

個等分點上與f(x)重合。即：給定[0,2]上N個等分點上的函數(shù)值，令滿足插值條件。N個未知數(shù)N個方程DiscreteFourierTransformInverseofDFT總之要進(jìn)行形如的計算，其中已知，§6快速傅立葉變換/*FastFourierT§6FastFourierTransform

FastFourierTransform快速計算(j=0,1,…,N1)，其中直接計算需復(fù)數(shù)乘法次N2

降到N·logN由于W的周期性WqN+s=Ws,Wkj實際上只有這

個不同的值。若N

為偶數(shù)，則Wkj只有個不同值。10...-NWWN

N/2先合并同類項，再做乘法。I’mgonnaneedsomemagichere…§6FastFourierTransformFa§6FastFourierTransform例：N=23=8,計算，j=0,1,2,3,4,5,6,7技巧：將k,j

先記為二進(jìn)制數(shù)

/*binarynumbers*/=++==++=)(222)(222012001122012001122jjjjjjjkkkkkkkkjW)222()222(001122001122++++=kkkjjjW)()222()222(012010213212031422kkkjkkkjkkkjW++++++=)()0()00(012001102kkkjkkjkjW++=23次乘法全部計算需要238次乘法一般地：取N=2p

，每個Cj

用2p

次乘法，共用2Nlog2N

次乘法。利用，還可以進(jìn)一步化簡到N(p1)/2

次乘法。HW:p.138#1§6FastFourierTransform例：N第二章插值方法/*Interpolation*/Interpolation_introduction§1

問題提出—函數(shù)逼近

/*problemformulation-----functionapproximation*/用第二章插值方法/*Interpolation*/InInterpolation_introduction函數(shù)逼近的方法有很多，例如Taylor級數(shù)，F(xiàn)ourier級數(shù)，有限元方法、邊界元方法，小波分析等，大學(xué)科叫逼近論。本書討論連續(xù)函數(shù)的逼近，主要介紹插值法(chapter2)和最佳一直逼近、最小平方逼近離散數(shù)據(jù)擬合(chapter3)Interpolation_introduction函數(shù)逼近Interpolation_introduction插值節(jié)點插值條件---插值問題多項式插值是數(shù)值分析的基本工具，常用來計算被插函數(shù)的近似函數(shù)值，零、極點，導(dǎo)數(shù)、積分（第四章數(shù)值積分和數(shù)值微分），解微分方程（第五章）、積分方程插值Interpolation_introduction插值節(jié)點多項式插值----polynomialinterpolationProblemI.

給定y=f(x)的函數(shù)表,xi[a,b]niyxPiin,...,0,)(==求次數(shù)不超過n

的多項式使得條件：無重合節(jié)點，即InterpolationintervalInterpolationconditionInterpolationpolynomialInterpolationpointsInterpolationpolynomial

(2.1)(2.2)多項式插值----polynomialinterpolatx0x1x2x3x4xPn(x)

f(x)多項式插值的幾何意義Interpolationpolynomial

求x0x1x2x3x4xPn(x)f(x)多項式插值的幾插值多項式的唯一性

提問：ProblemI中的Pn(x)是否存在？若存在，是否唯一？如何求？Interpolationpolynomial

插值多項式的唯一性提問：ProblemI中的PInterpolationpolynomial

如何求？解線性方程組（2.3）----待定系數(shù)法Interpolationpolynomial如何求？解Interpolationpolynomial

Interpolationpolynomial§2拉格朗日多項式/*LagrangePolynomial*/niyxPiin,...,0,)(==求n

次多項式使得條件：無重合節(jié)點，即n=1已知x0,x1;

y0,

y1

，求使得111001)(,)(yxPyxP==可見P1(x)是過(x0,y0)和

(x1,y1)

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

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

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

/*KroneckerDelta*/§2LagrangePolynomial§2拉格朗日多項式/*LagrangePolynn

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

使得

li(xj)=ij

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

。li(x)每個li有n

個根x0…

xi…xn==jiC0=-njijxx)(---inxxixxxxC0))...()...((ixl)(-=jijxixiC)(1=iixl1)(LagrangePolynomial與節(jié)點有關(guān)，而與f無關(guān)==niinxlxP0)()(yi基函數(shù)法（n=1情形的推廣）§2LagrangePolynomialn1希望找到li(x)，i=0,…,n使得定理(唯一性)滿足的n

階插值多項式是唯一存在的。證明：(前面已利用Vandermonde

行列式論證)反證：若不唯一，則除了Ln(x)外還有另一n

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

?？疾靹tQn

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

，則插值多項式不唯一。例如也是一個插值多項式，其中可以是任意多項式?！?LagrangePolynomial定理(唯一性)滿足

插值余項

/*Remainder*/設(shè)節(jié)點在[a,b]內(nèi)存在,考察截斷誤差，且f

滿足條件,Rolle’sTheorem:若充分光滑，，則存在使得。推廣：若使得使得存在使得Rn(x)至少有個根n+1=-=niinxxxKxR0)()()(任意固定xxi(i=0,…,n),考察=-=niixtxKtRnt0)()()()(j(x)有n+2

個不同的根x0…

xn

x!)1()()()1(+-+nxKRxnnx注意這里是對t求導(dǎo)=+--++!)1)(()()()1()1(nxKLfxnnxnxx!)1()()()1(+=+nfxKxnx§2LagrangePolynomial插值余項/*Remainder*/設(shè)節(jié)點在[a,§1LagrangePolynomial注：

通常不能確定x

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

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

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

的多項式時，,可知，即插值多項式對于次數(shù)n的多項式是精確的。Quiz:

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

下面哪個是l2(x)的圖像？

y

0

-

-

-

1

0.5

-0.5

1

2

3

4

5

6

x

y

0

-

-

-

1

0.5

-0.5

1

2

3

4

5

6

x

y

0

-

-

-

1

0.5

-0.5

1

2

3

4

5

6

x

ABC§1LagrangePolynomial注：通常不§1LagrangePolynomial例：已知分別利用sinx的1次、2次Lagrange插值計算sin50

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

以及x1,x2

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

/*extrapolation*/

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

/*interpolation*/

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

所在的區(qū)間的端點，插值效果較好。§1LagrangePolynomial例：已知分別利§1LagrangePolynomialn=2)185(50sin20pL0.76543sin50=0.7660444…2次插值的實際誤差0.00061高次插值通常優(yōu)于低次插值但絕對不是次數(shù)越高就越好，嘿嘿……§1LagrangePolynomialn=2)1Whenyoustartwritingtheprogram,youwillfindhoweasyitistocalculatetheLagrangepolynomial.Ohyeah?WhatifIfindthecurrentinterpolationnotaccurateenough?Thenyoumightwanttotakemoreinterpolatingpointsintoaccount.Right.ThenalltheLagrangebasis,li(x),willhavetobere-calculated.Excellentpoint!Wewillcometodiscussthisproblemnexttime.Whenyoustart§3逐次線性插值

/*LagrangePolynomial*/§3逐次線性插值/*LagrangePolyno數(shù)值分析第二章-插值總結(jié)課件實際上，是對兩個低次插值的線性插值，這種通過低次插值再作線性插值生成高次插值的方法稱為逐次線性插值。

Aitken法(按下表計算)線性插值基函數(shù)實際上，是對兩個低次插值的線性插值，這種通過低次插值再作線性增加如果精度不構(gòu)，增加節(jié)點x4,同時表中增加一行，三角形斜邊上即為所要求的各次插值多項式。k1k0k2k3k4增加如果精度不構(gòu)，增加節(jié)點x4,同時表中增加一行，三角形斜邊

Neville法(按下表計算)增加如果精度不構(gòu)，增加節(jié)點x4,同時表中增加一行，三角形斜邊上即為所要求的各次插值多項式。k1k0k1k1k1HW:用類似于前面的方法構(gòu)造Neville計算公式Neville法(按下表計算)增加如果精度不構(gòu)，增加節(jié)點注：Atkin方法和Neville方法與Lagrange公式相比，當(dāng)需要增加節(jié)點時，很容易由低次插值構(gòu)造高次插值，而Lagrange插值公式中，每個基函數(shù)都需要作適當(dāng)變化。誤差估計：由插值多項式的存在唯一性知，仍有但這里可采用一種更簡便的方法。當(dāng)f(n+1)(x)在插值區(qū)間變化不大時，設(shè)f(n+1)(x)L，則有注：Atkin方法和Neville方法與Lagrange公式可認(rèn)為滿足精度要求。根據(jù)前面的計算結(jié)果估計當(dāng)前的誤差：事后誤差估計（實用），前面給出的誤差估計（事先誤差估計）不實用HW:p.58-59#1-8可認(rèn)為§4牛頓插值/*Newton’sInterpolation*/Lagrange插值雖然易算，但若要增加一個節(jié)點時，全部基函數(shù)li(x)都需重新算過。公式不具有繼承性，不利于編程。將Ln(x)改寫成的形式，希望每加一個節(jié)點時，只附加一項上去即可。????

差商(亦稱均差)

/*divideddifference*/1階差商

/*the1stdivideddifferenceoffw.r.t.xi

andxj

*/2階差商f(x0)1階差商的幾何意義：弦截線的斜率§4Newton’sInterpolation§4牛頓插值/*Newton’sInterpol§4Newton’sInterpolation11101010111010],,...,[],,...,[],,...,[],...,,[],...,[++--+++--=--=kkkkkkkkkkkxxxxxfxxxfxxxxxfxxxfxxf(k+1)階差商：事實上其中Warning:myheadisexploding…Whatisthepointofthisformula?差商的值與xi

的順序無關(guān)！§4Newton’sInterpolation11101.線性：2.差商可以表示為函數(shù)值的線性組合：3.

對稱性：由2知，差商的值與節(jié)點的順序無關(guān)！4.

差商的另一種定義：由2，3及均差定義可得§4Newton’sInterpolation1.線性：2.差商可以表示為函數(shù)值的線性組合：3.對稱性：6.5.

差商與導(dǎo)數(shù)的關(guān)系：f(x)Ck[a,b],則[a,b],s.t.HW:證明差商的性質(zhì)2，4§4Newton’sInterpolation6.5.差商與導(dǎo)數(shù)的關(guān)系：f(x)Ck[a,b],則§4Newton’sInterpolation牛頓插值

/*Newton’sInterpolation*/…………Nn(x)—n次多項式，滿足：Nn(xi)=f(xi)Rn(x)—插值余項，滿足Rn(xi)=0，i=0,…,n

ai=

f[x0,…,xi](1)(2)(n)(n)(n-1)…(2)(1)§4Newton’sInterpolation牛頓§4Newton’sInterpolation注：

由唯一性可知Nn(x)Ln(x)，只是算法不同，表達(dá)形式不同，故其余項也相同，即

實際計算過程為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]增加如果精度不構(gòu)，增加節(jié)點xn+1,同時表中增加一行，三角形斜邊上即為所要求的各次項系數(shù)。§4Newton’sInterpolation注：數(shù)值分析第二章-插值總結(jié)課件§4Newton’sInterpolation

等距節(jié)點公式

/*FormulaewithEqualSpacing*/向前差分

/*forwarddifference*/iiifff-=+1ikikikikffff1111)(-+---==向后差分

/*backwarddifference*/111----=ikikikfffi1iifff-=中心差分

/*centereddifference*/其中當(dāng)節(jié)點等距分布時:fi=f(xi)§4Newton’sInterpolation等距

差分計算可通過構(gòu)造差分表得到增加差分計算可通過構(gòu)造差分表得到增加數(shù)值分析第二章-插值總結(jié)課件

差分的重要性質(zhì)：

線性：例如

各階差分可用函數(shù)值表示：其中/*binomialcoefficients*/§4Newton’sInterpolation

函數(shù)值可用各階差分表示：差分的重要性質(zhì)：線性：例如各階差分可用函數(shù)值表

差商與差分的關(guān)系：

若f(x)是n

次多項式，則是次多項式，而差商與差分的關(guān)系：若f(x)是n次多項式，則

差分與導(dǎo)數(shù)的關(guān)系(由差分與差商、差商與導(dǎo)數(shù)的關(guān)系得）：差分與導(dǎo)數(shù)的關(guān)系(由差分與差商、差商與導(dǎo)數(shù)的關(guān)系得）：§4Newton’sInterpolation等距節(jié)點牛頓公式

牛頓前差公式/*Newton’sforward-differenceformula*/§4Newton’sInterpolation等距節(jié)點注：一般當(dāng)x

靠近x0時用前插，靠近xn時用后插，故兩種公式亦稱為表初公式和表末公式。

牛頓后差公式/*Newton’sforward-differenceformula*/HW:p.59#9-16注：一般當(dāng)x靠近x0時用前插，靠近xn時用后插，§5厄米插值/*HermiteInterpolation*/§5厄米插值/*HermiteInterpola不僅要求函數(shù)值重合，而且要求若干階導(dǎo)數(shù)也重合。即：要求插值函數(shù)

(x)

滿足

(xi)=f