离散数学证明题

《离散数学证明题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、离散数学证明题离散数学证明题离散数学证明题:链为分配格证明设a,b均是链A的元素，因为链中任意两个元素均可比较，即有aWb或aWb,如果aWb,则a,b的最大下界是a,最小上界是b,如果bWa,则a,b的最大下界是b,最小上界是a,故链一定是格，下面证明分配律成立即可，对A中任意元素a,b,c分下面两种情况讨论：(1)bWa或cWa(2)aWb且aWc如果是第⑴种情况，则aU=a=Pl如果是第⑵种情况，则au=bnc=n无论那种情况分配律均成立，故A是分配格.一.线性插值已知函数f在区间［xk,xk+1］的端点上的函数值yk=f,yk+l=f,求一个一次函数y=Pl使得yk=f,yk+l=f

2、,其几何意义是已知平面上两点,，求一条直线过该已知两点。1.插值函数和插值基函数由直线的点斜式公式可知：把此式按照yk和yk+1写成两项：记并称它们为一次插值基函数。该基函数的特点如下表:从而Pl=yklk+yk+llk+1此形式称之为拉格朗日型插值多项式。其中，插值基函数与yk、yk+1无关，而由插值结点xk>xk+1所决定。一次插值多项式是插值基函数的线性组合，相应的组合系数是该点的函数值yk、yk+1.例1:已知lglO=l,lg2O,利用插值一次多项式求lgl2的近似值。解:f=lgx,f=l,f=,设xO=10,xl=20,y0=l,yl=则插值基函数为：于是，拉格朗日型一次插值多

3、项式为：故：即lg12由lglO和lg20两个值的线性插值得到，且具有两位有效数字.一.二次插值多项式已知函数y=f在点xk-1,xk,xk+1上的函数值yk-l=f,yk=f,yk+匸f,求一个次数不超过二次的多项式P2,使其满足，P2=yk-1,P2=yk,P2=yk+1.其几何意义为：已知平面上的三个点,,,求一个二次抛物线,使得该抛物线经过这三点。1.插值基本多项式有三个插值结点xk-1,xk,xk+1构造三个插值基本多项式，要求满足：基本多项式为二次多项式;它们的函数值满足下表：因为lk-l=O,lk-l=O,故有因子，而其已经是一个二次多项式，仅相差一个常数倍，可设lk~l=a,

4、又因为lk~l=l==>a=l得从而同理得基本二次多项式见右上图。2.拉格朗日型二次插值多项式由前述，拉格朗日型二次插值多项式：P2=yk-llk-l+yklk+yk+llk+1,P2是三个二次插值多项式的线性组合，因而其是次数不超过二次的多项式，且满足：P2=yi,o例2已知：xil01520yi=lgxil利用此三值的二次插值多项式求1gl2的近似值。解：设x0=10,x1=15,x2=20，则:故：所以7利用三个点进行抛物插值得到吨12的值，与精确值崩12二相比,具有3位有效数字,精度提高了。三、拉格朗日型n次插值多项式已知函数y二f在n+1个不同的点x0,xl,…,x2上的函数值分别

5、为y0,yl,…,yn,求一个次数不超过n的多项式Pn,使其满足：Pn=yi,,即n+1个不同的点可以唯一决定一个n次多项式。1.插值基函数过n+1个不同的点分别决定n+1个n次插值基函数10,11,In每个插值基本多项式li满足：li是n次多项式；1i=l,而在其它n个li=0,o由于li=0,,故有因子：因其已经是n次多项式，故而仅相差一个常数因子。令：li=a由li=l,可以定出a,进而得到：1.n次拉格朗日型插值多项式PnPn是n+1个n次插值基本多项式10,11,—,In的线性组合，相应的组合系数是y0,yl,…，yn。即：Pn二y010+ylll+・・・+ynln,从而Pn是一个

6、次数不超过n的多项式,且满足Pn=yi,.例3求过点,，,,的拉格朗日型插值多项式。解用4次插值多项式对5个点插值。所以四、拉格朗日插值多项式的截断误差我们在［a,b］上用多项式Pn来近似代替函数f,其截断误差记作Rn=f-Pn当x在插值结点xi上时Rn=f-Pn=0,下面来估计截断误差：定理1：设函数y=f的n阶导数y=f在［a,b］上连续,y=f在上存在;插值结点为：aWxOPn是n次拉格朗日插值多项式；则对任意xE[a,b]有：其中2已§依赖于X:con+l=••-证明：由插值多项式的要求：Rn二f-Pn二0,;设Rn二K…二Ksn+l其中K是待定系数；固定xe[a,b]且xHxk,k

7、=0,1,2,…,n;作函数H二f-Pn-K…则H=0,,且H二f-Pn-Rn二0,所以,H在[a,b]上有n+2个零点，反复使用罗尔中值定理:存在Ee,使；因Pn是n次多项式，故P=0,而3n+1二••・是首项系数为1的n+1次多项式，故有于是H二f-!K得：所以设,则：易知，线性插值的截断误差为：二次插值的截断误差为下面来分析前面两个例子中计算魄12的截断误差:在例1中，用lglO和lg20计〔1gl2,