【计算机科学导论-基于计算思维的思想与方法（第4版） 课件 ch08】问题求解的近似计算

计算机科学导论基于计算思维的思想与方法问题求解的近似计算第八章新工科建设之路·计算机类系列教材01定积分的近似计算定积分的近似计算01一、近似计算方法根据定积分定义推算出求解定积分近似值表达式定积分的近似计算01一、近似计算方法1.矩形积分法定积分的近似计算01一、近似计算方法1.矩形积分法定积分的近似计算01一、近似计算方法1.矩形积分法定积分的近似计算01一、近似计算方法2.梯形积分法梯形积分法是把曲边梯形分成若千个小窄曲边梯形，每个小窄曲边梯形面积用小直边梯形面积来近似代替，然后将每个直边梯形面积相加，从而得到定积分的近似值，其几何图形如图8-2所示。定积分的近似计算01一、近似计算方法3.抛物线积分法虽然梯形积分法比矩形积分法的误差小，但还是不够精确。如果每段改用与凸起相接近的二次曲线来近似，这就是抛物线积分法，也称为辛普森(Simpson)方法，如图8-3所示。定积分的近似计算01二、计算求解方法1.编程求解方法这里仍以定积分的近似计算为例，讨论利用计算机实现矩形积分法中右端点求和法的实现方法。基本算法步骤如下。定积分的近似计算01二、计算求解方法2.工具软件方法Matlab全称为MatrixLaboratory(矩阵试验室)，是当今最受控制系统设计和仿真领域青睐的工具软件，可用于数值计算、数据建模、数字仿真、数据处理、工程与科学绘图等，为众多科学领域提供了全面的解决方案，代表了当今国际科学计算软件的先进水平；Maple是目前世界上最通用的数学和工程计算软件之一，在数学和科学领域享有盛誉，有“数学家的软件”之称；Mathematica是世界上通用计算系统中最强大的系统，拥有强大的数值计算和符号运算能力，在科技和其他领域产生了深刻的影响。这里简要介绍运用Matlab求定积分计算的基本方法。02有限元方法有限元方法021.有限元方法的理论基础有限元方法是一种用于求解微分方程组数值解的数值技术。有限元方法是基于数值计算发展起来的一种近似数值方法，用来解决力学、数学中的带有特定边界条件的偏微分方程问题，而这些偏微分方程是工程实践中常见的固体力学和流体力学问题的基础。一、有限元方法的基本概念有限元方法022.有限元方法的解题思想有限元方法基于变分原理，它将求解域看成是由许多称为有限元的小的互联子域组成的，并且对每一单元假定一个合适而简单的近似解，然后推导求解这个域总的满足条件(如结构的平衡条件)，从而得到原问题的解。一、有限元方法的基本概念有限元方法021.局部与整体的计算思维有限元方法的关键思想是离散化，它完美体现了局部与整体的哲学思想，若要解决整体问题，必须先研究局部问题。把复杂的结构看成由有限个单元组成的整体，化整为零、集零为整是有限元方法的基本思想，这种思想为我们处理复杂工程问题提供了一种基本思路。二、有限元方法的计算思维有限元方法022.单元与组合体的计算思维有限元方法将连续方程的求解域离散为有限个由单元组成的组合体，以此组合体来模拟和逼近原求解域。由于各单元本身具有不同的几何形状，并且各单元间可以按照各种不同的联结方式组合，所以这个组合体可以模拟几何形状复杂的求解域，并且原问题单元划分越细，单元数越多，求解的逼近程度越高。二、有限元方法的计算思维03随机事件及其概率随机事件及其概率03一、随机事件我们把对一个客观事物进行的“试验”“调查”或“观测”统称为“试验”。一个试验知道可能产生的所有结果，而且这个试验在相同条件下可以重复进行，这样的试验称为“随机试验”。“随机试验”产生的结果称为“随机事件”，一般用A，B，C…表示。1.什么是随机事件随机事件及其概率03一、随机事件随机事件具有如下3个重要特征：(1)具有重复性：可以在相同条件下，反复进行多次试验；(2)没有确定性：在一次试验(观察)中，随机事件可能发生或不发生，结果具有偶然性；(3)统计规律性：在大量重复试验(观察)中，随机事件的发生具有某种统计规律性。2.随机事件的特征随机事件及其概率03一、随机事件随机事件的关系是指事件A与事件B的包含、相等、互斥、互逆这4个方面的相互关系。3.随机事件的关系对于同一个样本空间S的任意两个事件A和B，并具有以下3种运算关系：(1)并(或和)；(2)积(或交)；(3)差(或减)。4.随机事件的运算随机事件及其概率03二、随机概率1.概率的统计定义为了揭示概率统计规律，我们希望寻求一种合适的数来表示事件发生的可能性的大小。通过大量反复试验，随机事件具有以下两个重要特征。(1)在一次试验中，随机事件的发生具有偶然性。(2)在大量反复试验中，随机事件的发生具有统计规律性。随机事件及其概率03二、随机概率2.概率的性质随机事件及其概率03二、随机概率3.古典概型古典概型在数学上可表示为：根据古典概型的特点，可以定义任一随机事件的概率。随机事件及其概率03三、随机变量1.随机变量的定义随机事件及其概率03三、随机变量2.离散型随机变量随机事件及其概率03三、随机变量3.连续型随机变量04蒙特卡罗方法蒙特卡罗方法04一、蒙特卡罗方法的概念1.求解思想蒙特卡罗方法是以概率统计理论为指导的一类非常重要的数值计算方法，所以在解决实际问题时的模拟方法主要有两部分：一是用蒙特卡罗方法模拟某一过程，产生满足该随机过程概率分布的随机变量；二是用统计方法估计模型的数字特征，从而得到实际问题的数值解。蒙特卡罗方法04一、蒙特卡罗方法的概念2.求解方法蒙特卡罗方法与传统的确定性算法解决问题的思路截然不同，是基于概率论及数理统计来解决计算问题的方法，是一种应用随机数进行仿真试验的方法，在具体实现上常采用以下两种方法。(1)模拟随机过程(2)获取概率统计蒙特卡罗方法04二、蒙特卡罗方法求定积分1.蒙特卡罗积分蒙特卡罗方法04二、蒙特卡罗方法求定积分2.数值积分法的选择4种数值积分计算公式。05圆周率的近似计算圆周率的近似计算05一、圆周率的计算史1.试验法时期圆是最简单、最基本的曲边图形，其量度问题在几何学中占有相当重要的位置。今天数学上的许多成果，得益于人类对于几何形状的认识与探测过程中，实现了从“直”到“曲”，从“有限”到“无限”这一历史性的跨越。此后，经过历代数学家的相继探索，推算出的圆周率数值日益精确。圆周率的近似计算05一、圆周率的计算史2.几何法时期魏晋时期，中国古代数学家刘徽利用算筹，采用称为“割圆术(CyclotomicMethou)”的计算方法，在刘徽之后200年的南北朝时期，我国古代天文学家、数学家祖冲之利用刘徽的“割圆术”，继续分割，内接多边形的周长还会增加。在全凭手工计算的古代，能取得如此精确的计算，是人类在几何学的处理方法和思想观念上突破和跨越了从“直”到“曲”，从“有限”到“无限”的结果。圆周率的近似计算05一、圆周率的计算史3.分析法时期圆周率的近似计算05一、圆周率的计算史4.计算机法时期1946年，世界上第一台电子计算机ENIAC诞生，并得到飞速发展，从此开启了现代科学的新时代，人工计算圆周率的历史从此结束。人们用计算机求解圆周率的值，即使在普通的微机上，求得上万位的圆周率的值也是轻而易举的事。只要提供足够多的机时，就可以将圆周率的值计算到任意多位。圆周率的近似计算05二、研究计算圆周率的意义1.检验计算机系统的性能利用圆周率π的求解检验计算机硬件和软件的性能是一项具有重要意义的工作。例如，在486Dx/100微机上计算5万位π值，大约需要6小时，运行中任何一个微小的机器故障都将导致错误的结果。因而，这对于计算机的运行速度以及运行的可靠、稳定性都是一个很好的检验手段。由此可以看出，高精度π值计算可作为检验和比较计算机性能的一个标准计算。圆周率的近似计算05二、研究计算圆周率的意义2.研究圆周率的值随机分布性质关于圆周率的各位小数的随机分布的性质，目前还主要依赖于统计分析，计算的位数越多，统计分析的结果就越可靠。用圆周率的小数位计算的效果最好。有两个致命弱点：周期不够长，分布不够均匀。这对于一般的应用影响不大，但对某些重要的科学计算将会产生不能容忍的误差，因此，在必要时用圆周率或由圆周率生成的其他数作为随机数似乎更为理想。06仿生学算法仿生学算法06一、遗传算法的基本方法1.遗传算法流程遗传算法流程包括编码生成初始种群、个体、适应度、选择、交叉和变异，如图8-9所示。仿生学算法06一、遗传算法的基本方法2.遗传算法编码遗传算法不能直接处理问题的参数，必须把参数转换成遗传空间的、由基因按一定结构组成的染色体或个体。这一转换操作被称为编码(Code)或者问题的表示(Representation)。在遗传算法中的编码有位串编码和符号编码两种方式。仿生学算法06二、群体智能优化算法概念1.蚁群优化算法概念蚁群优化算法是一种随机通用试探法，属于分布式智能模拟算法，可用于求解各种不同的组合优化问题。有人根据蚁群优化算法求解144个城市的最短回路问题，求得解的结果同其他方法求得的解一样精确，由此说明蚁群优化算法是求解组合优化的可行算法。仿生学算法06二、群体智能优化算法概念2.粒子群优化算法概念粒子群优化算法(ParticleSwarmOptimization，PSO)也称为粒子群算法、微粒群优化算法，粒子群优化算法是通过模拟鸟群觅食行为而发展起来的一种基于群体协作的随机搜索算法，基本思想是模拟鸟群的捕食行为，即一群鸟在随机搜索食物，在这个区域里只有一块食物，但所有的鸟都不知道食物在哪里，但是它们知道当前的位置离食物还有多远，那么找到食物的最优策略是什么呢?显然，最简单有效的就是搜寻目前离食物最近的鸟的周围区域。因此，研究该算法的意义在于利用位置和速度的变化，模拟鸟群迁移中个体行为和群体行为之间的相互影响。仿生学算法06二、群体智能优化算法概念3.