- 相關(guān)推薦
離散數(shù)學(xué)證明題
離散數(shù)學(xué)證明題離散數(shù)學(xué)證明題:鏈為分配格
證明設(shè)a,b均是鏈A的元素,因?yàn)殒溨腥我鈨蓚(gè)元素均可比較,即有a≤b或a≤b,如果a≤b,則a,b的最大下界是a,最小上界是b,如果b≤a,則a,b的最大下界是b,最小上界是a,故鏈一定是格,下面證明分配律成立即可,對(duì)A中任意元素a,b,c分下面兩種情況討論:
⑴b≤a或c≤a
⑵a≤b且a≤c
如果是第⑴種情況,則a∪(b∩c)=a=(a∪b)∩(a∪c)
如果是第⑵種情況,則a∪(b∩c)=b∩c=(a∪b)∩(a∪c)
無(wú)論那種情況分配律均成立,故A是分配格.
一.線性插值(一次插值)
已知函數(shù)f(x)在區(qū)間[xk ,xk+1 ]的端點(diǎn)上的函數(shù)值yk =f(xk ), yk+1 = f(xk+1 ),求一個(gè)一次函數(shù)y=P1 (x)使得yk =f(xk ),yk+1 =f(xk+1 ), 其幾何意義是已知平面上兩點(diǎn)(xk ,yk ),(xk+1 ,yk+1 ),求一條直線過(guò)該已知兩點(diǎn)。
1. 插值函數(shù)和插值基函數(shù)
由直線的點(diǎn)斜式公式可知:
把此式按照 yk 和yk+1 寫成兩項(xiàng):
記
并稱它們?yōu)橐淮尾逯祷瘮?shù)。該基函數(shù)的特點(diǎn)如下表:
從而
P1 (x) = yk lk (x) + yk+1 lk+1 (x)
此形式稱之為拉格朗日型插值多項(xiàng)式。其中, 插值基函數(shù)與yk 、yk+1 無(wú)關(guān),而由插值結(jié)點(diǎn)xk 、xk+1 所決定。一次插值多項(xiàng)式是插值基函數(shù)的線性組合, 相應(yīng)的組合系數(shù)是該點(diǎn)的函數(shù)值yk 、yk+1 .
例1: 已知lg10=1,lg20=1.3010, 利用插值一次多項(xiàng)式求lg12的近似值。
解: f(x)=lgx,f(10)=1,f(20)=1.3010, 設(shè)
x0 =10 ,x1 =20 ,y0 =1 ,y1 =1.3010
則插值基函數(shù)為:
于是, 拉格朗日型一次插值多項(xiàng)式為:
故 :
即lg12 由lg10 和lg20 兩個(gè)值的線性插值得到,且具有兩位有效數(shù)字(精確值lg12=1.0792).
二.二次插值多項(xiàng)式
已知函數(shù)y=f(x)在點(diǎn)xk-1 ,xk ,xk+1 上的函數(shù)值yk-1 =f(xk-1 ),yk =f(xk ), yk+1 =f(xk+1 ), 求一個(gè)次數(shù)不超過(guò)二次的多項(xiàng)式P2 (x), 使其滿足,
P2 (xk-1 )=yk-1 , P2 (xk )=yk , P2 (xk+1 )=yk+1 .
其幾何意義為:已知平面上的三個(gè)點(diǎn)
(xk-1 ,yk-1 ),(xk ,yk ),(xk+1 ,yk+1 ),
求一個(gè)二次拋物線, 使得該拋物線經(jīng)過(guò)這三點(diǎn)。
1.插值基本多項(xiàng)式
有三個(gè)插值結(jié)點(diǎn)xk-1 ,xk ,xk+1 構(gòu)造三個(gè)插值基本多項(xiàng)式,要求滿足:
(1) 基本多項(xiàng)式為二次多項(xiàng)式; (2) 它們的函數(shù)值滿足下表:
因?yàn)閘k-1 (xk )= 0,lk-1 (xk+1 )=0, 故有因子(x-xk )(x-xk+1 ), 而其已經(jīng)是一個(gè)二次多項(xiàng)式, 僅相差一個(gè)常數(shù)倍, 可設(shè)
lk-1 (x)=a(x-xk )(x-xk+1 ),
又因?yàn)?/p>
lk-1 (xk-1 )=1 ==> a(xk-1 -xk )(xk-1 -xk+1 )=1
得
從而
同理得
基本二次多項(xiàng)式見右上圖(點(diǎn)擊按鈕“顯示Li”)。
2. 拉格朗日型二次插值多項(xiàng)式
由前述, 拉格朗日型二次插值多項(xiàng)式:
P2 (x)=yk-1 lk-1 (x)+yk lk (x)+yk+1 lk+1 (x),P2 (x)
是三個(gè)二次插值多項(xiàng)式的線性組合,因而其是次數(shù)不超過(guò)二次的多項(xiàng)式,且滿足:
P2 (xi )=yi , (i=k-1,k,k+1) 。
例2 已知:
xi 10 15 20
yi=lgxi 1 1.1761 1.3010
利用此三值的二次插值多項(xiàng)式求lg12的近似值。
解:設(shè)x0 =10,x1 =15,x2 =20,則:
故:
所以
7利用三個(gè)點(diǎn)進(jìn)行拋物插值得到lg12的值,與精確值lg12=1.0792相比,具有3位有效數(shù)字,精度提高了。
三、拉格朗日型n次插值多項(xiàng)式
已知函數(shù)y=f(x)在n+1個(gè)不同的點(diǎn)x0 ,x1 ,…,x2 上的函數(shù)值分別為
y0 ,y1 ,…,yn ,求一個(gè)次數(shù)不超過(guò)n的多項(xiàng)式Pn (x),使其滿足:
Pn (xi )=yi , (i=0,1,…,n),
即n+1個(gè)不同的點(diǎn)可以唯一決定一個(gè)n次多項(xiàng)式。
1. 插值基函數(shù)
過(guò)n+1個(gè)不同的點(diǎn)分別決定n+1個(gè)n次插值基函數(shù)
l0 (x),l1 (x),…,ln (X)
每個(gè)插值基本多項(xiàng)式li (x)滿足:
(1) li (x)是n次多項(xiàng)式;
(2) li (xi )=1,而在其它n個(gè)li (xk )=0 ,(k≠i)。
由于li (xk )=0 ,(k≠i), 故有因子:
(x-x0 )…(x-xi-1 )(x-xi+1 )…(x-xn )
因其已經(jīng)是n次多項(xiàng)式,故而僅相差一個(gè)常數(shù)因子。令:
li (x)=a(x-x0 )…(x-xi-1 )(x-xi+1 )…(x-xn )
由li (xi )=1,可以定出a, 進(jìn)而得到:
2. n次拉格朗日型插值多項(xiàng)式Pn (x)
Pn (x)是n+1個(gè)n次插值基本多項(xiàng)式l0 (x),l1 (x),…,ln (X)的線性組合,相應(yīng)的組合系數(shù)是y0 ,y1 ,…,yn 。即:
Pn (x)=y0 l0 (x)+y1 l1 (x)+…+yn ln (x) ,
從而Pn (x)是一個(gè)次數(shù)不超過(guò)n的多項(xiàng)式,且滿足
Pn (xi )=yi , (i=0,1,2,…,n).
例3 求過(guò)點(diǎn)(2,0),(4,3),(6,5),(8,4),(10,1)的拉格朗日型插值多項(xiàng)式。
解 用4次插值多項(xiàng)式對(duì)5個(gè)點(diǎn)插值。
所以
四、拉格朗日插值多項(xiàng)式的截?cái)嗾`差
我們?cè)赱a,b]上用多項(xiàng)式Pn (x) 來(lái)近似代替函數(shù)f(x), 其截?cái)嗾`差記作
Rn (x)=f(x)-Pn (x)
當(dāng)x在插值結(jié)點(diǎn)xi 上時(shí)Rn (xi )=f(xi )-P n(xi )=0,下面來(lái)估計(jì)截?cái)嗾`差:
定理1:設(shè)函數(shù)y=f(x)的n階導(dǎo)數(shù)y(n) =f(n) (x)在[a,b]上連續(xù),
y(n+1) = f(n+1) (x)
在(a,b)上存在;插值結(jié)點(diǎn)為:
a≤x0
Pn (x)是n次拉格朗日插值多項(xiàng)式;則對(duì)任意x∈[a,b]有:
其中ξ∈(a,b), ξ依賴于x:ωn+1 (x)=(x-x0 )(x-x1 )…(x-xn )
證明:由插值多項(xiàng)式的要求:
Rn(xi )=f(xi )-Pn (xi )=0,(i=0,1,2,…,n);
設(shè)
Rn (x)=K(x)(x-x0 )(x-x1 )…(x-xn )=K(x)ωn+1 (x)
其中K(x)是待定系數(shù);固定x∈[a,b]且x≠xk ,k=0,1,2,…,n;作函數(shù)
H(t)=f(t)-Pn (t)-K(x)(t-x0 )(t-x1 )…(t-xn )
則 H(xk )=0,(k=0,1,2,…,n), 且H(x)=f(x)-Pn (x)-Rn(x)=0, 所以,
H(t)在[a,b]上有n+2個(gè)零點(diǎn),反復(fù)使用羅爾中值定理:存在ξ∈(a,b),
使; 因Pn (x)是n次多項(xiàng)式,故P(n+1) (ξ)=0, 而
ωn+1 (t)=(t-x0 )(t-x1 )…(t-xn )
是首項(xiàng)系數(shù)為1的n+1次多項(xiàng)式,故有
于是
H(n+1) (ξ)=f(n+1)(ξ)-(n+1)!K(x)
得:
所以
設(shè) , 則:
易知,線性插值的截?cái)嗾`差為:
二次插值的截?cái)嗾`差為:
下面來(lái)分析前面兩個(gè)例子(例1,例2)中計(jì)算lg12的截?cái)嗾`差:
在例1中,用lg10和lg20計(jì)算lg12,
P1(12)=1.0602,lg12=1.0792
e=|1.0792-1.0602|=0.0190;
估計(jì)誤差:f(x)=lgx,
,當(dāng)x∈[10,20]時(shí),
2
【離散數(shù)學(xué)證明題】相關(guān)文章:
幾何證明題04-29
離散數(shù)學(xué)論文04-28
離散數(shù)學(xué)數(shù)學(xué)論文11-05
初中幾何證明題的入門的論文04-27
淺談離散數(shù)學(xué)的學(xué)習(xí)心得04-25
高中數(shù)學(xué)證明題04-30
離散數(shù)學(xué)的實(shí)驗(yàn)教學(xué)探討04-30