數(shù)值分析-課件第4章

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

第四章多項式插值與函數(shù)逼近問題背景§1插值問題

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

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

f(x)幾何意義：有理插值：集合為有理分式函數(shù)集/*Rational*/三角插值：集合為三角函數(shù)集/*Trigonometric*/代數(shù)插值的存在唯一性設(shè)即代入插值條件：方程組的系數(shù)矩陣是Vandermonde矩陣

方程組存在唯一解，因此滿足插值條件(*)

的不超過n次的插值多項式是唯一存在的.截斷誤差插值余項設(shè)在區(qū)間[a,b]上連續(xù)，在區(qū)間[a,b]上存在,

是滿足插值條件（*）的不超過n次的插值多項式，則對存在，滿足其中。且當(dāng)在區(qū)間[a,b]有上界時，有代數(shù)插值的插值余項/*Remainder*/注意這里是對

t

求導(dǎo)證明：設(shè)結(jié)論顯然成立時構(gòu)造輔助函數(shù)則有個互異零點、由羅爾(Roll)定理在區(qū)間（a,b）上至少有n+1個互異零點在區(qū)間（a,b）上至少有n個互異零點以此類推，反復(fù)利用Roll定理在區(qū)間（a,b）上至少有1個零點而注：（1）插值誤差與節(jié)點和之間的距離有關(guān)；

（2）如果本身為多項式，其插值函數(shù)為本身。

（3）通常不能確定,而是估計,x(a,b)

將作為誤差估計上限?！?代數(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與有關(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若記例如也是一個插值多項式，其中可以是任意多項式。（2）Lagrange插值多項式結(jié)構(gòu)對稱，形式簡單，常用于理論分析，因為當(dāng)n較大時，計算復(fù)雜。（3）誤差估計注：（1）若不將多項式次數(shù)限制為n

，則插值多項式不唯一。（4）當(dāng)插值節(jié)點增加時，拉氏基函數(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例1：已知分別利用sinx的1次、2次Lagrange

插值計算sin50

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

以及x1,x2

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

/*extrapolation*/

的實際誤差0.0101利用sin50

0.76008,內(nèi)插

/*interpolation*/

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

在區(qū)間的內(nèi)部，插值效果較好。高次插值通常優(yōu)于低次插值n=2)185(50sin20pL0.76543sin50=0.7660444…2次插值的實際誤差0.00061但絕對不是次數(shù)越高就越好，嘿嘿……反插值問題已知定義于區(qū)間上的單調(diào)連續(xù)函數(shù)在個互異節(jié)點處的函數(shù)值，若函數(shù)值已知，如何求？即求因此可以看作如下插值問題：已知定義于區(qū)間上的連續(xù)函數(shù)在個互異節(jié)點處的函數(shù)值，求函數(shù)值

xi

1.01.41.82.0yi=f(xi)-2.0-0.80.41.2例2：已知單調(diào)連續(xù)函數(shù)在如下采樣點的函數(shù)值：求方程在[1，2]內(nèi)根的近似值。解：§2牛頓插值

/*Newton’sInterpolation*/Lagrange

插值雖然易算，但若要增加一個節(jié)點時，全部基函數(shù)li(x)

都需重新算過。將Ln(x)改寫成的形式，希望每加一個節(jié)點時，只附加一項上去即可。????一、

差商(亦稱均差)

/*divideddifference*/1階差商

/*the1stdivideddifferenceoffw.r.t.xi

andxj

*/2階差商11101010111010],,...,[],,...,[],,...,[],...,,[],...,[++--+++--=--=kkkkkkkkkkkxxxxxfxxxfxxxxxfxxxfxxf(K+1)階差商：事實上其中差商的值與xi

的順序無關(guān)！二、牛頓插值

/*Newton’sInterpolation*/已知定義于區(qū)間上的連續(xù)函數(shù)在個互異節(jié)點處的函數(shù)值n次Lagrange

插值多項式可表示為：其中12…………n+11+(x

x0)2+……+(x

x0)…(x

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

f[x0,…,xi]3注：

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

實際計算過程為（建立差商表）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]f(x0)f(x1)f(x2)…f(xn1)f(xn)x0x1x2…xn1xn例3：已知函數(shù)的函數(shù)表：

xi12345yi=f(xi)14786寫出4次Newton插值多項式解：構(gòu)造差商表三、差商性質(zhì)

/*Propertyofdivideddifference*/性質(zhì)1即其中證明：數(shù)學(xué)歸納法n=1n=2同理歸納，結(jié)論成立性質(zhì)2差商具有對稱性，即的值與節(jié)點的順序無關(guān)。由性質(zhì)1易知性質(zhì)3如果的k階差商是的m次多項式，則的k+1階差商是的m-1次多項式。證明：上式右端的分子是的m次多項式，記為則為m-1次多項式故結(jié)論成立。性質(zhì)4證明：設(shè)以為節(jié)點的n次Newton插值多項式為則四、等距節(jié)點插值公式/*InterpolationFormulaewithEqualSpacing*/當(dāng)節(jié)點等距分布時:稱為在點處的階向前差分稱為在點處的階向后差分稱為在點處的階中心差分向前差分

/*forwarddifference*/向后差分

/*backwarddifference*/中心差分

/*centereddifference*/恒等算子

/*identicaloperator*/移位算子

/*shiftoperator*/

差分性質(zhì)（/*Propertyofdifference*/

）性質(zhì)1其中證明：數(shù)學(xué)歸納法m=1m=j即對任意整數(shù)m成立性質(zhì)2其中存在證明：性質(zhì)3其中數(shù)學(xué)歸納法（自己證）性質(zhì)4（補(bǔ)充）