2022离散数学证明题_离散数学证明题答案.docx

《2022离散数学证明题_离散数学证明题答案.docx》由会员分享，可在线阅读，更多相关《2022离散数学证明题_离散数学证明题答案.docx（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2022离散数学证明题_离散数学证明题答案 离散数学证明题由我整理，希望给你工作、学习、生活带来便利，猜你可能喜爱“离散数学证明题答案”。 离散数学证明题 离散数学证明题:链为安排格 证明设a,b均是链A的元素，因为链中随意两个元素均可比较，即有ab或ab，假如ab，则a,b的最大下界是a,最小上界是b，假如ba，则a,b的最大下界是b,最小上界是a，故链肯定是格,下面证明安排律成马上可,对A中随意元素a,b,c分下面两种状况探讨: ba或ca ab且ac 假如是第种状况,则a(bc)=a=(ab)(ac) 假如是第种状况,则a(bc)=bc=(ab)(ac) 无论那种状况安排律均成立,故A是

2、安排格.一.线性插值(一次插值) 已知函数f(x)在区间的端点上的函数值yk=f(xk),yk+1=f(xk+1),求一个一次函数y=p1(x)使得yk=f(xk),yk+1=f(xk+1),其几何意义是已知平面上两点(xk,yk),(xk+1,yk+1),求一条直线过该已知两点。 1.插值函数和插值基函数 由直线的点斜式公式可知： 把此式根据yk和yk+1写成两项: 记 并称它们为一次插值基函数。该基函数的特点如下表： 从而 p1(x)=yklk(x)+yk+1lk+1(x) 此形式称之为拉格朗日型插值多项式。其中,插值基函数与yk、yk+1无关，而由插值结点xk、xk+1所确定。一次插值多

3、项式是插值基函数的线性组合,相应的组合系数是该点的函数值yk、yk+1. 例1:已知lg10=1,lg20=1.3010,利用插值一次多项式求lg12的近似值。 解:f(x)=lgx,f(10)=1,f(20)=1.3010,设 x0=10,x1=20,y0=1,y1=1.3010 则插值基函数为： 于是,拉格朗日型一次插值多项式为: 故: 即lg12由lg10和lg20两个值的线性插值得到,且具有两位有效数字(精确值lg12=1.0792).二.二次插值多项式 已知函数y=f(x)在点xk-1,xk,xk+1上的函数值yk-1=f(xk-1),yk=f(xk),yk+1=f(xk+1),求一

4、个次数不超过二次的多项式p2(x),使其满意, p2(xk-1)=yk-1,p2(xk)=yk,p2(xk+1)=yk+1. 其几何意义为:已知平面上的三个点 (xk-1,yk-1),(xk,yk),(xk+1,yk+1), 求一个二次抛物线,使得该抛物线经过这三点。 1.插值基本多项式 有三个插值结点xk-1,xk,xk+1构造三个插值基本多项式，要求满意： (1)基本多项式为二次多项式;(2)它们的函数值满意下表： 因为lk-1(xk)=0,lk-1(xk+1)=0,故有因子(x-xk)(x-xk+1),而其已经是一个二次多项式,仅相差一个常数倍,可设 lk-1(x)=a(x-xk)(x-

5、xk+1), 又因为 lk-1(xk-1)=1=a(xk-1-xk)(xk-1-xk+1)= 1得 从而 同理得 基本二次多项式见右上图(点击按钮“显示Li”)。 2.拉格朗日型二次插值多项式 由前述,拉格朗日型二次插值多项式: p2(x)=yk-1lk-1(x)+yklk(x)+yk+1lk+1(x),p2(x) 是三个二次插值多项式的线性组合,因而其是次数不超过二次的多项式,且满意: p2(xi)=yi,(i=k-1,k,k+1)。 例2已知： xi101520 yi=lgxi11.17611.3010 利用此三值的二次插值多项式求lg12的近似值。 解：设x0=10,x1=15,x2=2

6、0,则: 故: 所以 7利用三个点进行抛物插值得到lg12的值,与精确值lg12=1.0792相比,具有3位有效数字,精度提高了。 三、拉格朗日型n次插值多项式 已知函数y=f(x)在n+1个不同的点x0,x1,x2上的函数值分别为 y0,y1,yn,求一个次数不超过n的多项式pn(x),使其满意: pn(xi)=yi,(i=0,1,n), 即n+1个不同的点可以唯一确定一个n次多项式。 1.插值基函数 过n+1个不同的点分别确定n+1个n次插值基函数 l0(x),l1(x),ln(X) 每个插值基本多项式li(x)满意： (1)li(x)是n次多项式; (2)li(xi)=1,而在其它n个l

7、i(xk)=0,(ki)。 由于li(xk)=0,(ki),故有因子: (x-x0)(x-xi-1)(x-xi+1)(x-xn) 因其已经是n次多项式，故而仅相差一个常数因子。令: li(x)=a(x-x0)(x-xi-1)(x-xi+1)(x-xn) 由li(xi)=1,可以定出a,进而得到： 2.n次拉格朗日型插值多项式pn(x) pn(x)是n+1个n次插值基本多项式l0(x),l1(x),ln(X)的线性组合,相应的组合系数是y0,y1,yn。即: pn(x)=y0l0(x)+y1l1(x)+ynln(x), 从而pn(x)是一个次数不超过n的多项式,且满意 pn(xi)=yi,(i=

8、0,1,2,n).例3求过点(2,0),(4,3),(6,5),(8,4),(10,1)的拉格朗日型插值多项式。 解用4次插值多项式对5个点插值。 所以 四、拉格朗日插值多项式的截断误差 我们在上用多项式pn(x)来近似代替函数f(x),其截断误差记作 Rn(x)=f(x)-pn(x) 当x在插值结点xi上时Rn(xi)=f(xi)-pn(xi)=0,下面来估计截断误差： 定理1：设函数y=f(x)的n阶导数y(n)=f(n)(x)在上连续， y(n+1)=f(n+1)(x) 在(a,b)上存在;插值结点为: ax0 pn(x)是n次拉格朗日插值多项式;则对随意x有： 其中(a,b),依靠于x

9、：n+1(x)=(x-x0)(x-x1)(x-xn) 证明：由插值多项式的要求： Rn(xi)=f(xi)-pn(xi)=0，(i=0,1,2,n); 设 Rn(x)=K(x)(x-x0)(x-x1)(x-xn)=K(x)n+1(x) 其中K(x)是待定系数;固定x且xxk，k=0,1,2,n;作函数 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)在上有n+2个零点，反复运用罗尔中值定理:存在(a,b), 使;因pn(x)是n次多项式，故p(n+1)()=

10、0,而 n+1(t)=(t-x0)(t-x1)(t-xn) 是首项系数为1的n+1次多项式，故有 于是 H(n+1)()=f(n+1)()-(n+1)!K(x) 得： 所以 设,则： 易知，线性插值的截断误差为: 二次插值的截断误差为: 下面来分析前面两个例子(例1，例2)中计算lg12的截断误差： 在例1中，用lg10和lg20计算lg12, p1(12)=1.0602,lg12=1.0792 e=|1.0792-1.0602|=0.0190; 估计误差：f(x)=lgx, ,当x时, 2 离散数学证明题 证明题1.用等值演算法证明下列等值式：（1）(PQ)(PQ)(PQ)（2）(PQ)(P

11、Q)(PQ)(PQ)证明：（1）(PQ)(PQ)(QP)(PQ)(QP)(PQ)(QP. 电大离散数学证明题参考题 五、证明题1设G是一个n阶无向简洁图，n是大于等于3的奇数证明图G与它的补图G中的奇数度顶点个数相等 证明：设G=，=则E是由n阶无向完全图Kn的边删去E所得到的所以对于随意结点. 离散数学历年考试证明题 1、试证明集合等式A (BC)=(AB) (AC)证明：设S=A(BC)，T=(AB)(AC)，若xS，则xA且xBC，即 xA且xB 或 xA且xC，也即xAB 或 xAC ，即 xT，所以ST反之，若x. 离散数学证明题解题方法 离散数学是现代数学的一个重要分支，是计算机科

12、学中基础理论的核心课程。离散数学以探讨离散量的结构和相互间的关系为主要目标，其探讨对象一般地是有限个或可数个元素，因此他充. 离散数学 离散数学试题（A卷答案）一、（10分）（1）证明(PQ)(QR)(PR) （2）求(PQ)R的主析取范式与主合取范式，并写出其相应的成真赋值和成假赋值。 解：（1）因为(PQ)(QR)(PR) (PQ)(QR)(P. 本文来源：网络收集与整理，如有侵权，请联系作者删除，谢谢！第10页 共10页第 10 页 共 10 页第 10 页 共 10 页第 10 页 共 10 页第 10 页 共 10 页第 10 页 共 10 页第 10 页 共 10 页第 10 页 共 10 页第 10 页 共 10 页第 10 页 共 10 页第 10 页 共 10 页