数学建模课件算法基础.ppt
《数学建模课件算法基础.ppt》由会员分享,可在线阅读,更多相关《数学建模课件算法基础.ppt(65页珍藏版)》请在三一文库上搜索。
1、第八章 算法基础,西北工业大学 应用数学系 聂玉峰,算法概念,数学建模竞赛的过程 算法的概念 算法的分类 算法的评价,1.1 建模竞赛的过程,实际上是命题人(某个领域的专家)提出实际问题 参赛人首先读题,分析问题,依照自己的理解准确阐述问题; 辨析问题中的主要矛盾和次要矛盾,并在合理假设的条件下,运用各种数学理论、工具和方法,建立起问题中不同量之间的约束关系,进而得到完备的数学模型; 在研究模型解的存在性与惟一性 如何求其解 利用解对模型的正确性进行评价。,1.2 算法的概念,当数学模型的分析解得不到时,使用计算机进行求解。我们不会做的计算机肯定不会做,只有当我们会做,但因为数据计算量太大时,
2、把自己的求解过程(算法)编写成程序,计算机将其编译、运行得到计算结果。 所谓(串行)算法就是求解一个问题类的无二义性的有穷过程,这里过程明确无歧义的描述由有限操作(算术运算、逻辑运算、字符运算、读写操作等)及有限操作对象合成的按一定顺序执行的有限序列。 原始的可以变化的有限操作对象就是有限输入数据,它所有可能允许的变化构成求解的问题类。,1.3 算法的分类,对给定的输入数据,算法运行后得到的数据结果也是有限的,这样可以把算法看成有限输入数据和有限输出结果之间的对应关系。 将以浮点算术运算为主的算法称为数值型算法,如线性方程组的求解,数值积分的计算,微分方程初边值问题的求解等。其它算法称为非数值
3、型算法,如排序问题,匹配查找问题等。,1.4 算法的评价,算法在保证可靠的大前提下再评价其优劣才是有价值的。 数值型算法的可靠性 算法的收敛性、稳定性、误差估计等 算法必须在有限的时间内得到计算结果,如果某问题类的一个求解过程是无限长,需要将其截断得到求解算法,并产生截断误差。 算法的收敛性就是研究当运行时间趋于无限长时,算法的解是否趋于真实解,即截断误差是否趋于零。 非数值型算法的可靠性更为强调对于整体问题类算法计算结果的正确性。,算法的评价(2),评价一个可靠算法的优劣,应该考虑其时间复杂度(计算机运行时间)、空间复杂度(占据计算机存储空间的多少)以及逻辑复杂度(影响程序开发的周期以及维护
4、)。,2数值型算法的收敛阶,迭代是构造数值问题算法的基本思想之一,迭代的结果是得到问题解的一个近似序列. 如果对于问题类中任一问题,迭代次数k趋于无穷大时序列极限存在,并且就是该问题的准确解,则称该迭代算法收敛到问题的解。,2.1 数列收敛阶的定义,2.2 举例,2.3 2阶收敛举例,2.4 算法的收敛阶,类似地,如果收敛的数列是由迭代算法产生的,定义数列的收敛阶为算法的收敛阶。不过需要注意,算法是对问题类的算法,不是针对一个特定问题的,这样算法的收敛阶应该是由该算法生成的序列都具有的共同特征。,2.5 时间花费与收敛速度,对于不同的算法,若每一迭代步的时间花费相当,从收敛阶的定义可以知道,收
5、敛阶高的算法花费较少的时间;对于同阶的算法,渐近常数小者花费较少的时间。,2.6 向量序列的极限,2.7 范数概念,2.8 常用向量范数,2.9 等价性定理、收敛速度,2.10 常用的矩阵范数,3 误差及数值算法的稳定性,误差的产生 模型建立时因舍去次要矛盾会产生模型误差; 模型中包含一些参数是通过仪表观测得到的,产生观测误差; 算法必须在有限步内执行结束,这样需要将无穷过程截断为有限过程,产生截断误差; 在用计算机实现数值算法的过程中,由于计算机表示浮点数采用的是固定有限字长,因而仅能够区分有限个信息,准确表示在某个有限范围内的某些有理数,不能准确表示数学中的所有实数,这样在计算机中表示的原
6、始输入数据、中间计算数据、以及最终输出结果必然产生误差,称此类误差为舍入误差。 得到的计算结果是这些误差综合影响下的数据。,3.2 浮点数系,浮点数系是计算机常用的实数表示系统,一个浮点数的表示由正负号、有限小数形式的尾数、以及确定小数点位置的阶码三部分组成. 设在某一浮点系统中, 尾数占t位二进制数(未计算尾数的符号位), 阶数占s位二进制数(未计算阶数的符号位), 实数的浮点表示共需要ts2位的二进制数位.,3.3 溢出,3.4 单精度数,单精度实数用32位的二进制数据表示浮点数的这三个信息, 其中数值符号和阶码符号各占1位, 尾数占t=23位, 阶码数值占s7位. 这样,除零外, 单精度
7、实数的量级不大于1038不小于1038. 当输入、输出或中间计算过程中出现量级大于1038的数据时, 因单精度实数无法正确表示该数据, 将导致程序的非正常停止, 称此现象为上溢(Overflow). 而当出现量级小于10-38的非零数据时, 一般计算机将该数置为零, 精度损失, 称此现象为下溢(Underflow). 当数据有可能出现上溢或下溢时, 可通过乘积因子变换数据, 使之正常表示. 67位有效数字,3.5 初值误差,由于误差传播研究困难,经常研究某种假设下误差的传播规律。如初值误差传播是在每一步都准确计算的假设下,即不考虑截断误差和由运算进一步引入的舍入误差,研究误差传播规律。,3.6
8、 数值稳定性,舍入误差分析是非常繁杂困难的, 而舍入误差不可避免, 运算量又相当大, 为此, 人们提出了“数值稳定性“这一概念对舍入误差是否影响产生可靠的结果进行定性分析. 一个算法, 如果在运算过程中舍入误差在一定条件下能够得到控制, 或者舍入误差的增长不影响产生可靠的结果, 则称该算法是数值稳定的, 否则称其为数值不稳定.,3.7 数值稳定举例,不稳定算法结果,I1-I10近似值分别如下: 0.0883920 0.0580400 0.0431333 0.0343333 0.0283333 0.0250000 0.0178571 0.0357143 -0.0674603 0.4373016,
9、算法2,Matlab 算出的精确解,稳定性不同于显著性,对算法的稳定性分析,其实就是给原始数据一个小扰动,分析计算结果变化的程度,若很大则算法不稳定,若可以接受,则算法稳定. 这里需要指出,算法的稳定性不同于建立模型过程中因素的显著性分析.,数值型算法设计注意事项,对于一个数值型算法除了其正确性(如收敛性)外,研究其效率(如收敛速度)、鲁棒性(如稳定性)是很重要的,同时程序设计或实现时如下几个问题也不可忽视: 1)减少计算次数以缩短计算时间,2)避免相近数相减,避免相近数相减举例,3)尽可能避免大数吃小数,其它,4)避免很小的数做分母,防止溢出出现; 5)正确使用实数相等的比较,5 数值型算法
10、构造的常用基本思想,掌握数值型算法构造的基本思想将会有利于提出针对具体问题的有效快速算法,关于迭代的解释,在这个过程中,首先我们用到了逼近的思想,将一个常量(方程的一个根)看成变量的极限,这个变量的每一个值是常量的近似值,不过它愈来愈近似的好. 当然你也可以看出这个过程其实也用到了两个思想:动与静的思想,极限的思想. 其次也用到了问题转换的思想,将函数的零点(方程的根)转换为另一个函数的不动点. 最后借助不动点问题产生迭代序列,即使用迭代的思想产生逼近序列.,线性方程组,5.2 直与曲的思想,该法除了使用逼近的思想外,还用到了以直代曲的思想,用一系列的直线近似曲线,这些直线是曲线的一系列切线,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数学 建模 课件 算法 基础
链接地址:https://www.31doc.com/p-2156568.html