四章-多項式插值與數(shù)值逼近課件

第四章多項式插值與函數(shù)逼近/*Polynomial

Interpolationand

ApproximationofFunctions*/本章主要內(nèi)容：1、Lagrange插值方法2、Newton插值方法3、Hermite插值方法4、三次樣條插值方法5、函數(shù)逼近:最佳平方逼近和最佳一致逼近第四章多項式插值與函數(shù)逼近本章主要內(nèi)容：1

實際問題中經(jīng)常要涉及到函數(shù)值的計算問題： （1）如果函數(shù)表達(dá)式本身比較復(fù)雜，且需要多次重復(fù)計算時，計算量會很大；（2）有的函數(shù)甚至沒有表達(dá)式，只是一種表格函數(shù)，而我們需要的函數(shù)值可能不在該表格中。對于這兩種情況，我們都需要尋找一個計算方便且表達(dá)簡單的函數(shù)來近似代替，這就是數(shù)值逼近問題。

問題背景問題背景2§1插值問題

/*InterpolationProblem*/（插值的定義）已知定義于區(qū)間上的實值函數(shù)在個互異節(jié)點

處的函數(shù)值，若函數(shù)集合中的函數(shù)滿足則稱為在函數(shù)集合中關(guān)于節(jié)點的一個插值函數(shù)，并稱為被插值函數(shù),[a,b]為插值區(qū)間，為插值節(jié)點，（*）式為插值條件。設(shè)外插法：內(nèi)插法：用計算被插值函數(shù)在點處的近似值用計算被插值函數(shù)在點處的近似值§1插值問題/*Interpolation3插值類型代數(shù)插值：集合為多項式函數(shù)集x0x1x2x3x4xg(x)

f(x)幾何意義：有理插值：集合為有理分式函數(shù)集三角插值：集合為三角函數(shù)集插值類型代數(shù)插值：集合為多項式函數(shù)集x0x1x2x3x4代數(shù)插值的存在唯一性設(shè)即代入插值條件：代數(shù)插值的存在唯一性設(shè)即代入插值條件：5方程組的系數(shù)矩陣是Vandermonde矩陣方程組存在唯一解，因此滿足插值條件(*)的不超過n次的插值多項式是唯一存在的.方程組的系數(shù)矩陣是Vandermonde矩陣方程組6截斷誤差插值余項設(shè)在區(qū)間[a,b]上連續(xù)，在區(qū)間[a,b]上存在,是滿足插值條件（*）的不超過n次的插值多項式，則對存在，滿足其中。且當(dāng)在區(qū)間[a,b]有上界時，有代數(shù)插值的插值余項/*Remainder*/截斷誤差插值余項設(shè)在區(qū)間[a,b]上連續(xù)，7§2代數(shù)插值多項式的構(gòu)造方法一、拉格朗日多項式

/*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§2代數(shù)插值多項式的構(gòu)造方法一、拉格朗日多項式/*8與有關(guān)，而與無關(guān)n

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

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

yi

。li(x)每個li(x)

有n個根x0…

xi-1

、

xi+1…xn-==jijiiiixxCxl)(11)(LagrangePolynomial節(jié)點f與有關(guān)，而與無關(guān)n1希望找9例如也是一個插值多項式，其中可以是任意多項式。（2）Lagrange插值多項式結(jié)構(gòu)對稱，形式簡單.（3）誤差估計注：（1）若不將多項式次數(shù)限制為n

，則插值多項式不唯一。（4）當(dāng)插值節(jié)點增加時，拉氏基函數(shù)需要重新計算，

n較大時，計算量非常大,故常用于理論分析。例如10二、

牛頓插值

/*Newton’sInterpolation*/Lagrange

插值雖然易算，但若要增加一個節(jié)點時，全部基函數(shù)li(x)都需重新算過。將Ln(x)改寫成的形式，希望每加一個節(jié)點，只附加一項上去即可。????差商(亦稱均差)

/*divideddifference*/1階差商

/*the1stdivideddifferenceoffw.r.t.xi

andxj

*/2階差商二、牛頓插值/*Newton’sInterpola1111101010111010],,...,[],,...,[],,...,[],...,,[],...,[++--+++--=--=kkkkkkkkkkkxxxxxfxxxfxxxxxfxxxfxxf(K+1)階差商：事實上其中差商的值與xi的順序無關(guān)！11101010111010],,...,[],,...,[1212…………n+11+(x

x0)2+……+(x

x0)…(x

xn1)n+1Nn(x)Rn(x)ai=

f[x0,…,xi]312…………n+11+(xx0)2+…13注：

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

實際計算過程為（建立差商表）f[x0,x1]f[x1,x2]…………f[xn1,xn]f[x0,x1,x2]……f[xn2,xn1,xn]f[x0,…,xn]

xn+1

f(xn+1)f[xn,xn+1]f[xn1,xn,xn+1]f[x1,…,xn+1]f[x0,…,xn+1]f(x0)f(x1)f(x2)…f(xn1)f(xn)x0x1x2…xn1xn注：由唯一性可知Nn(x)Ln(x)，只是算法14例3：已知函數(shù)的函數(shù)表：

xi12345yi=f(xi)14786寫出4次Newton插值多項式解：構(gòu)造差商表例3：已知函數(shù)的函數(shù)表：15§4分段插值

/*piecewiseInterpolation*/一、高次插值評述1、從插值余項角度分析為了提高插值精度，一般來說應(yīng)該增加插值節(jié)點的個數(shù)，這從插值余項的表達(dá)式也可以看出，但不能簡單地這樣認(rèn)為，原因有三個：插值余項與節(jié)點的分布有關(guān)；余項公式成立的前提條件是有足夠階連續(xù)導(dǎo)數(shù)（即函數(shù)足夠光滑），但隨著節(jié)點個數(shù)的增加，這個條件一般很難成立；隨著節(jié)點個數(shù)的增加，可能會增大。隨著節(jié)點個數(shù)增加到某個值，誤差反而會增加?！?分段插值/*piecewiseInterpo16注意下面圖中曲線的變化情況！例3：在[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)注意下面圖中例3：在[5,5]上考察17§5三次樣條插值/*CubicSplineInterpolation*/

許多實際工程技術(shù)中一般對精度要求非常高，（1）要求近似曲線在節(jié)點連續(xù)；（2）要求近似曲線在節(jié)點處導(dǎo)數(shù)連續(xù)，即充分光滑。

分段插值不能保證節(jié)點的光滑性，而Hermite插值需要知道節(jié)點處的導(dǎo)數(shù)值，實際中無法確定。

問題背景§5三次樣條插值/*CubicSplineInt18一、三次樣條函數(shù)的力學(xué)背景

在工程技術(shù)和數(shù)學(xué)應(yīng)用中經(jīng)常遇到這樣一類數(shù)據(jù)處理問題：在平面上給定了一組有序的離散點列，要求用一條光滑曲線把這些點按次序連接起來。........壓鐵彈性木條.數(shù)據(jù)點形象地稱之為樣條曲線一、三次樣條函數(shù)的力學(xué)背景在工程技術(shù)和數(shù)學(xué)應(yīng)用中經(jīng)常19

在力學(xué)上，通常均勻細(xì)木條可以看作彈性細(xì)梁，壓鐵看作是作用在梁上的集中載荷，“樣條曲線”就模擬為彈性細(xì)梁在外加集中載荷作用下的彎曲變形曲線。設(shè)細(xì)梁剛度系數(shù)為，彎矩為，樣條曲線的曲率為由力學(xué)知識：當(dāng)時（即“小撓度”的情況）上述微分方程簡化為：是線性函數(shù)因此，“樣條曲線”可近似認(rèn)為是三次多項式在力學(xué)上，通常均勻細(xì)木條可以看作彈性細(xì)梁，壓鐵看作是20二、三次樣條函數(shù)定義及求法設(shè)在區(qū)間上給定一個分割，定義在上的函數(shù)如果滿足下列條件：(1)在每個小區(qū)間內(nèi)是三次多項式(2)在整個區(qū)間上，為二階連續(xù)可導(dǎo)函數(shù)，即在每個節(jié)點處則稱為三次樣條函數(shù)二、三次樣條函數(shù)定義及求法設(shè)在區(qū)間上給21假設(shè)現(xiàn)在已知函數(shù)在節(jié)點處的函數(shù)值：如果三次樣條函數(shù)滿足則稱為插值于的三次樣條函數(shù)，簡稱三次樣條插值函數(shù)。如何求的三次樣條插值函數(shù):4n個未知數(shù)3n-1個條件假設(shè)現(xiàn)在已知函數(shù)在節(jié)點處的函數(shù)值：如果三次樣條函數(shù)22線性插值函數(shù)1、M連續(xù)方程與的表達(dá)式記因為在每一個子區(qū)間上都是線性函數(shù)

兩邊積分兩邊再積分一次？線性插值函數(shù)1、M連續(xù)方程與的表達(dá)式記因為23由其中代入插值條件：由其中代入插值條件：24寫成方程組的形式：上述方程組稱為的M連續(xù)方程n-1個方程n+1個未知數(shù)三彎矩方程寫成方程組的形式：上述方程組稱為的M連續(xù)方程n25M、m連續(xù)方程的求解：需要補(bǔ)充附加條件3、邊界條件/*boundaryconditions*/已知端點的斜率：已知端點的二階導(dǎo)數(shù)：設(shè)是以為周期的周期函數(shù)，對附加周期性條件：

即要求三次樣條插值函數(shù)在端點處函數(shù)值、一階導(dǎo)數(shù)值和二階導(dǎo)數(shù)值相同。M、m連續(xù)方程的求解：需要補(bǔ)充附加條件3、邊界條件/*bou26M連續(xù)方程在各類邊界條件下的求解方法對于第一類邊界條件由得M連續(xù)方程在各類邊界條件下的求解方法對于第一類邊界條件由得27從而得到方程組（三對角）：可用追趕法求解從而得到方程組（三對角）：可用追趕法求解28注：三次樣條與分段Hermite插值的根本區(qū)別在于S(x)自身光滑，不需要知道f的導(dǎo)數(shù)值（除了在2個端點處的函數(shù)值）；而Hermite插值依賴于f在許多插值節(jié)點的導(dǎo)數(shù)值。f(x)H(x)S(x)注：三次樣條與分段Hermite插值的根本區(qū)別在于S(x29四章-多項式插值與數(shù)值逼近課件30性質(zhì)3（誤差估計）設(shè)函數(shù)，是區(qū)間的一個分割，是關(guān)于的帶有Ⅰ型(斜率邊界)或Ⅱ型(二階導(dǎo)數(shù)邊界)邊界條件的插值函數(shù)，則有誤差估計其中

是分割比，并且系數(shù)與是最優(yōu)估計。

性質(zhì)說明：三次樣條插值函數(shù)本身連同它的一、二、三階導(dǎo)數(shù)分別收斂到及其相應(yīng)導(dǎo)數(shù)，具有強(qiáng)收斂性。性質(zhì)3（誤差估計）設(shè)函數(shù)，是31第四章多項式插值與函數(shù)逼近/*Polynomial

Interpolationand

ApproximationofFunctions*/本章主要內(nèi)容：1、Lagrange插值方法2、Newton插值方法3、Hermite插值方法4、三次樣條插值方法5、函數(shù)逼近:最佳平方逼近和最佳一致逼近第四章多項式插值與函數(shù)逼近本章主要內(nèi)容：32

實際問題中經(jīng)常要涉及到函數(shù)值的計算問題： （1）如果函數(shù)表達(dá)式本身比較復(fù)雜，且需要多次重復(fù)計算時，計算量會很大；（2）有的函數(shù)甚至沒有表達(dá)式，只是一種表格函數(shù)，而我們需要的函數(shù)值可能不在該表格中。對于這兩種情況，我們都需要尋找一個計算方便且表達(dá)簡單的函數(shù)來近似代替，這就是數(shù)值逼近問題。

問題背景問題背景33§1插值問題

/*InterpolationProblem*/（插值的定義）已知定義于區(qū)間上的實值函數(shù)在個互異節(jié)點

處的函數(shù)值，若函數(shù)集合中的函數(shù)滿足則稱為在函數(shù)集合中關(guān)于節(jié)點的一個插值函數(shù)，并稱為被插值函數(shù),[a,b]為插值區(qū)間，為插值節(jié)點，（*）式為插值條件。設(shè)外插法：內(nèi)插法：用計算被插值函數(shù)在點處的近似值用計算被插值函數(shù)在點處的近似值§1插值問題/*Interpolation34插值類型代數(shù)插值：集合為多項式函數(shù)集x0x1x2x3x4xg(x)

f(x)幾何意義：有理插值：集合為有理分式函數(shù)集三角插值：集合為三角函數(shù)集插值類型代數(shù)插值：集合為多項式函數(shù)集x0x1x2x3x35代數(shù)插值的存在唯一性設(shè)即代入插值條件：代數(shù)插值的存在唯一性設(shè)即代入插值條件：36方程組的系數(shù)矩陣是Vandermonde矩陣方程組存在唯一解，因此滿足插值條件(*)的不超過n次的插值多項式是唯一存在的.方程組的系數(shù)矩陣是Vandermonde矩陣方程組37截斷誤差插值余項設(shè)在區(qū)間[a,b]上連續(xù)，在區(qū)間[a,b]上存在,是滿足插值條件（*）的不超過n次的插值多項式，則對存在，滿足其中。且當(dāng)在區(qū)間[a,b]有上界時，有代數(shù)插值的插值余項/*Remainder*/截斷誤差插值余項設(shè)在區(qū)間[a,b]上連續(xù)，38§2代數(shù)插值多項式的構(gòu)造方法一、拉格朗日多項式

/*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§2代數(shù)插值多項式的構(gòu)造方法一、拉格朗日多項式/*39與有關(guān)，而與無關(guān)n

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

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

yi

。li(x)每個li(x)

有n個根x0…

xi-1

、

xi+1…xn-==jijiiiixxCxl)(11)(LagrangePolynomial節(jié)點f與有關(guān)，而與無關(guān)n1希望找40例如也是一個插值多項式，其中可以是任意多項式。（2）Lagrange插值多項式結(jié)構(gòu)對稱，形式簡單.（3）誤差估計注：（1）若不將多項式次數(shù)限制為n

，則插值多項式不唯一。（4）當(dāng)插值節(jié)點增加時，拉氏基函數(shù)需要重新計算，

n較大時，計算量非常大,故常用于理論分析。例如41二、

牛頓插值

/*Newton’sInterpolation*/Lagrange

插值雖然易算，但若要增加一個節(jié)點時，全部基函數(shù)li(x)都需重新算過。將Ln(x)改寫成的形式，希望每加一個節(jié)點，只附加一項上去即可。????差商(亦稱均差)

/*divideddifference*/1階差商

/*the1stdivideddifferenceoffw.r.t.xi

andxj

*/2階差商二、牛頓插值/*Newton’sInterpola4211101010111010],,...,[],,...,[],,...,[],...,,[],...,[++--+++--=--=kkkkkkkkkkkxxxxxfxxxfxxxxxfxxxfxxf(K+1)階差商：事實上其中差商的值與xi的順序無關(guān)！11101010111010],,...,[],,...,[4312…………n+11+(x

x0)2+……+(x

x0)…(x

xn1)n+1Nn(x)Rn(x)ai=

f[x0,…,xi]312…………n+11+(xx0)2+…44注：

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

實際計算過程為（建立差商表）f[x0,x1]f[x1,x2]…………f[xn1,xn]f[x0,x1,x2]……f[xn2,xn1,xn]f[x0,…,xn]

xn+1

f(xn+1)f[xn,xn+1]f[xn1,xn,xn+1]f[x1,…,xn+1]f[x0,…,xn+1]f(x0)f(x1)f(x2)…f(xn1)f(xn)x0x1x2…xn1xn注：由唯一性可知Nn(x)Ln(x)，只是算法45例3：已知函數(shù)的函數(shù)表：

xi12345yi=f(xi)14786寫出4次Newton插值多項式解：構(gòu)造差商表例3：已知函數(shù)的函數(shù)表：46§4分段插值

/*piecewiseInterpolation*/一、高次插值評述1、從插值余項角度分析為了提高插值精度，一般來說應(yīng)該增加插值節(jié)點的個數(shù)，這從插值余項的表達(dá)式也可以看出，但不能簡單地這樣認(rèn)為，原因有三個：插值余項與節(jié)點的分布有關(guān)；余項公式成立的前提條件是有足夠階連續(xù)導(dǎo)數(shù)（即函數(shù)足夠光滑），但隨著節(jié)點個數(shù)的增加，這個條件一般很難成立；隨著節(jié)點個數(shù)的增加，可能會增大。隨著節(jié)點個數(shù)增加到某個值，誤差反而會增加?！?分段插值/*piecewiseInterpo47注意下面圖中曲線的變化情況！例3：在[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)注意下面圖中例3：在[5,5]上考察48§5三次樣條插值/*CubicSplineInterpolation*/

許多實際工程技術(shù)中一般對精度要求非常高，（1）要求近似曲線在節(jié)點連續(xù)；（2）要求近似曲線在節(jié)點處導(dǎo)數(shù)連續(xù)，即充分光滑。

分段插值不能保證節(jié)點的光滑性，而Hermite插值需要知道節(jié)點處的導(dǎo)數(shù)值，實際中無法確定。

問題背景§5三次樣條插值/*CubicSplineInt49一、三次樣條函數(shù)的力學(xué)背景

在工程技術(shù)和數(shù)學(xué)應(yīng)用中經(jīng)常遇到這樣一類數(shù)據(jù)處理問題：在平面上給定了一組有序的離散點列，要求用一條光滑曲線把這些點按次序連接起來。........壓鐵彈性木條.數(shù)據(jù)點形象地稱之為樣條曲線一、三次樣條函數(shù)的力學(xué)背景在工程技術(shù)和數(shù)學(xué)應(yīng)用中經(jīng)常50

在力學(xué)上，通常均勻細(xì)木條可以看作彈性細(xì)梁，壓鐵看作是作用在梁上的集中載荷，“樣條曲線”就模擬為彈性細(xì)梁在外加集中載荷作用下的彎曲變形曲線。設(shè)細(xì)梁剛度系數(shù)為，彎矩為，樣條曲線的曲率為由力學(xué)知識：當(dāng)時（即“小撓度”的情況）上述微分方程簡化為：是線性函數(shù)因此，“樣條曲線”可近似認(rèn)為是三次多項式在力學(xué)上，通常均勻細(xì)木條可以看作彈性細(xì)梁，壓鐵看作是51二、三次樣條函數(shù)定義及求法設(shè)在區(qū)間上給定一個分割，定義在上的函數(shù)如果滿足