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

Interpolationand

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

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

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

/*InterpolationProblem*/（插值的定義）已知定義于區間上的實值函數在個互異節點

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

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

/*LagrangePolynomial*/niyxPiin,...,0,)(==求n次多項式使得條件：無重合節點，即n=1已知x0

,x1

;

y0

,

y1

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

,y0)和(x1,y1

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

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

/*LagrangeBasis*/，滿足條件li(xj)=ij§2代數插值多項式的構造方法一、拉格朗日多項式/*8與有關，而與無關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節點f與有關，而與無關n1希望找9例如也是一個插值多項式，其中可以是任意多項式。（2）Lagrange插值多項式結構對稱，形式簡單.（3）誤差估計注：（1）若不將多項式次數限制為n

，則插值多項式不唯一。（4）當插值節點增加時，拉氏基函數需要重新計算，

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

牛頓插值

/*Newton’sInterpolation*/Lagrange

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

/*divideddifference*/1階差商

/*the1stdivideddifferenceoffw.r.t.xi

andxj

*/2階差商二、牛頓插值/*Newton’sInterpola1111101010111010],,...,[],,...,[],,...,[],...,,[],...,[++--+++--=--=kkkkkkkkkkkxxxxxfxxxfxxxxxfxxxfxxf(K+1)階差商：事實上其中差商的值與xi的順序無關！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：已知函數的函數表：

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

/*piecewiseInterpolation*/一、高次插值評述1、從插值余項角度分析為了提高插值精度，一般來說應該增加插值節點的個數，這從插值余項的表達式也可以看出，但不能簡單地這樣認為，原因有三個：插值余項與節點的分布有關；余項公式成立的前提條件是有足夠階連續導數（即函數足夠光滑），但隨著節點個數的增加，這個條件一般很難成立；隨著節點個數的增加，可能會增大。隨著節點個數增加到某個值，誤差反而會增加?！?分段插值/*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現象Ln(x)

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

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

分段插值不能保證節點的光滑性，而Hermite插值需要知道節點處的導數值，實際中無法確定。

問題背景§5三次樣條插值/*CubicSplineInt18一、三次樣條函數的力學背景

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

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

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

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

是分割比，并且系數與是最優估計。

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

Interpolationand

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

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

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

/*InterpolationProblem*/（插值的定義）已知定義于區間上的實值函數在個互異節點

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

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

/*LagrangePolynomial*/niyxPiin,...,0,)(==求n次多項式使得條件：無重合節點，即n=1已知x0

,x1

;

y0

,

y1

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

,y0)和(x1,y1

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

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

/*LagrangeBasis*/，滿足條件li(xj)=ij§2代數插值多項式的構造方法一、拉格朗日多項式/*39與有關，而與無關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節點f與有關，而與無關n1希望找40例如也是一個插值多項式，其中可以是任意多項式。（2）Lagrange插值多項式結構對稱，形式簡單.（3）誤差估計注：（1）若不將多項式次數限制為n

，則插值多項式不唯一。（4）當插值節點增加時，拉氏基函數需要重新計算，

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

牛頓插值

/*Newton’sInterpolation*/Lagrange

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

/*divideddifference*/1階差商

/*the1stdivideddifferenceoffw.r.t.xi

andxj

*/2階差商二、牛頓插值/*Newton’sInterpola4211101010111010],,...,[],,...,[],,...,[],...,,[],...,[++--+++--=--=kkkkkkkkkkkxxxxxfxxxfxxxxxfxxxfxxf(K+1)階差商：事實上其中差商的值與xi的順序無關！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：已知函數的函數表：

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

/*piecewiseInterpolation*/一、高次插值評述1、從插值余項角度分析為了提高插值精度，一般來說應該增加插值節點的個數，這從插值余項的表達式也可以看出，但不能簡單地這樣認為，原因有三個：插值余項與節點的分布有關；余項公式成立的前提條件是有足夠階連續導數（即函數足夠光滑），但隨著節點個數的增加，這個條件一般很難成立；隨著節點個數的增加，可能會增大。隨著節點個數增加到某個值，誤差反而會增加?！?分段插值/*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現象Ln(x)

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

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

分段插值不能保證節點的光滑性，而Hermite插值需要知道節點處的導數值，實際中無法確定。

問題背景§5三次樣條插值/*CubicSplineInt49一、三次樣條函數的力學背景

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

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