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

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

Interpolationand

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

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

問(wèn)題背景問(wèn)題背景2§1插值問(wèn)題

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

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

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

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

,x1

;

y0

,

y1

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

,y0)和(x1,y1

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

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

/*LagrangeBasis*/，滿足條件li(xj)=ij§2代數(shù)插值多項(xiàng)式的構(gòu)造方法一、拉格朗日多項(xiàng)式/*8與有關(guān)，而與無(wú)關(guān)n

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

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

yi

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

有n個(gè)根x0…

xi-1

、

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

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

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

牛頓插值

/*Newton’sInterpolation*/Lagrange

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

/*divideddifference*/1階差商

/*the1stdivideddifferenceoffw.r.t.xi

andxj

*/2階差商二、牛頓插值/*Newton’sInterpola1111101010111010],,...,[],,...,[],,...,[],...,,[],...,[++--+++--=--=kkkkkkkkkkkxxxxxfxxxfxxxxxfxxxfxxf(K+1)階差商：事實(shí)上其中差商的值與xi的順序無(wú)關(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)，只是算法不同，故其余項(xiàng)也相同，即

實(shí)際計(jì)算過(guò)程為（建立差商表）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插值多項(xiàng)式解：構(gòu)造差商表例3：已知函數(shù)的函數(shù)表：15§4分段插值

/*piecewiseInterpolation*/一、高次插值評(píng)述1、從插值余項(xiàng)角度分析為了提高插值精度，一般來(lái)說(shuō)應(yīng)該增加插值節(jié)點(diǎn)的個(gè)數(shù)，這從插值余項(xiàng)的表達(dá)式也可以看出，但不能簡(jiǎn)單地這樣認(rèn)為，原因有三個(gè)：插值余項(xiàng)與節(jié)點(diǎn)的分布有關(guān)；余項(xiàng)公式成立的前提條件是有足夠階連續(xù)導(dǎo)數(shù)（即函數(shù)足夠光滑），但隨著節(jié)點(diǎn)個(gè)數(shù)的增加，這個(gè)條件一般很難成立；隨著節(jié)點(diǎn)個(gè)數(shù)的增加，可能會(huì)增大。隨著節(jié)點(diǎn)個(gè)數(shù)增加到某個(gè)值，誤差反而會(huì)增加?！?分段插值/*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

越大，端點(diǎn)附近誤差越大，稱為Runge現(xiàn)象Ln(x)

f(x)注意下面圖中例3：在[5,5]上考察17§5三次樣條插值/*CubicSplineInterpolation*/

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

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

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

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

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

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

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

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

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

Interpolationand

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

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

問(wèn)題背景問(wèn)題背景33§1插值問(wèn)題

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

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

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

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

,x1

;

y0

,

y1

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

,y0)和(x1,y1

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

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

/*LagrangeBasis*/，滿足條件li(xj)=ij§2代數(shù)插值多項(xiàng)式的構(gòu)造方法一、拉格朗日多項(xiàng)式/*39與有關(guān)，而與無(wú)關(guān)n

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

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

yi

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

有n個(gè)根x0…

xi-1

、

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

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

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

牛頓插值

/*Newton’sInterpolation*/Lagrange

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

/*divideddifference*/1階差商

/*the1stdivideddifferenceoffw.r.t.xi

andxj

*/2階差商二、牛頓插值/*Newton’sInterpola4211101010111010],,...,[],,...,[],,...,[],...,,[],...,[++--+++--=--=kkkkkkkkkkkxxxxxfxxxfxxxxxfxxxfxxf(K+1)階差商：事實(shí)上其中差商的值與xi的順序無(wú)關(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)，只是算法不同，故其余項(xiàng)也相同，即

實(shí)際計(jì)算過(guò)程為（建立差商表）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插值多項(xiàng)式解：構(gòu)造差商表例3：已知函數(shù)的函數(shù)表：46§4分段插值

/*piecewiseInterpolation*/一、高次插值評(píng)述1、從插值余項(xiàng)角度分析為了提高插值精度，一般來(lái)說(shuō)應(yīng)該增加插值節(jié)點(diǎn)的個(gè)數(shù)，這從插值余項(xiàng)的表達(dá)式也可以看出，但不能簡(jiǎn)單地這樣認(rèn)為，原因有三個(gè)：插值余項(xiàng)與節(jié)點(diǎn)的分布有關(guān)；余項(xiàng)公式成立的前提條件是有足夠階連續(xù)導(dǎo)數(shù)（即函數(shù)足夠光滑），但隨著節(jié)點(diǎn)個(gè)數(shù)的增加，這個(gè)條件一般很難成立；隨著節(jié)點(diǎn)個(gè)數(shù)的增加，可能會(huì)增大。隨著節(jié)點(diǎn)個(gè)數(shù)增加到某個(gè)值，誤差反而會(huì)增加?！?分段插值/*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

越大，端點(diǎn)附近誤差越大，稱為Runge現(xiàn)象Ln(x)

f(x)注意下面圖中例3：在[5,5]上考察48§5三次樣條插值/*CubicSplineInterpolation*/

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

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

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

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

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