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

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

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

/*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)處的近似值/*AlgebraicInterpolation*/插值類型代數(shù)插值：集合為多項(xiàng)式函數(shù)集x0x1x2x3x4xg(x)

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

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

的不超過n次的插值多項(xiàng)式是唯一存在的.截?cái)嗾`差插值余項(xiàng)設(shè)在區(qū)間[a,b]上連續(xù)，在區(qū)間[a,b]上存在,

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

t

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

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

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

將作為誤差估計(jì)上限?！?代數(shù)插值多項(xiàng)式的構(gòu)造方法一、拉格朗日多項(xiàng)式

/*LagrangePolynomial*/niyxPiin,...,0,)(==求n

次多項(xiàng)式使得條件：無重合節(jié)點(diǎn)，即n=1已知x0

,x1

;

y0

,

y1

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

,y0)和(x1,y1

)兩點(diǎn)的直線。)()(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)每個(gè)li(x)

有n

個(gè)根x0…

xi-1

、

xi+1…xn-==jijiiiixxCxl)(11)(LagrangePolynomial節(jié)點(diǎn)f若記例如也是一個(gè)插值多項(xiàng)式，其中可以是任意多項(xiàng)式。（2）Lagrange插值多項(xiàng)式結(jié)構(gòu)對(duì)稱，形式簡(jiǎn)單，常用于理論分析，因?yàn)楫?dāng)n較大時(shí)，計(jì)算復(fù)雜。（3）誤差估計(jì)注：（1）若不將多項(xiàng)式次數(shù)限制為n

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

給定xi=i+1,i=0,1,2,3,4,5.下面哪個(gè)是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

插值計(jì)算sin50

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

以及x1,x2

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

/*extrapolation*/

的實(shí)際誤差0.0101利用sin50

0.76008,內(nèi)插

/*interpolation*/

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

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

xi

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

/*Newton’sInterpolation*/Lagrange

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

都需重新算過。將Ln(x)改寫成的形式，希望每加一個(gè)節(jié)點(diǎn)時(shí)，只附加一項(xiàng)上去即可。????一、

差商(亦稱均差)

/*divideddifference*/1階差商

/*the1stdivideddifferenceoffw.r.t.xi

andxj

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

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

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

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

x0)2+……+(x

x0)…(x

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

f[x0,…,xi]3注：

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

實(shí)際計(jì)算過程為（建立差商表）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插值多項(xiàng)式解：構(gòu)造差商表三、差商性質(zhì)

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

/*forwarddifference*/向后差分

/*backwarddifference*/中心差分

/*centereddifference*/恒等算子

/*identicaloperator*/移位算子

/*shiftoperator*/

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

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