数学建模课件算法基础

《数学建模课件算法基础》由会员分享，可在线阅读，更多相关《数学建模课件算法基础（65页珍藏版）》请在金锄头文库上搜索。

1、第八章 算法基础 西北工业大学 应用数学系 聂玉峰1.算法概念l数学建模竞赛的过程l算法的概念l算法的分类l算法的评价1.1 建模竞赛的过程l实际上是命题人（某个领域的专家）提出实际问题l参赛人首先读题，分析问题，依照自己的理解准确阐述 问题；l辨析问题中的主要矛盾和次要矛盾，并在合理假设的条 件下，运用各种数学理论、工具和方法，建立起问题中 不同量之间的约束关系，进而得到完备的数学模型；l在研究模型解的存在性与惟一性l如何求其解 l利用解对模型的正确性进行评价。1.2 算法的概念l当数学模型的分析解得不到时，使用计算机进行求解。 我们不会做的计算机肯定不会做，只有当我们会做，但 因为数据计算

2、量太大时，把自己的求解过程（算法）编 写成程序，计算机将其编译、运行得到计算结果。l 所谓（串行）算法就是求解一个问题类的无二义性的有 穷过程，这里过程明确无歧义的描述由有限操作（算术 运算、逻辑运算、字符运算、读写操作等）及有限操作 对象合成的按一定顺序执行的有限序列。 l原始的可以变化的有限操作对象就是有限输入数据，它 所有可能允许的变化构成求解的问题类。1.3 算法的分类l对给定的输入数据，算法运行后得到的数据结果 也是有限的，这样可以把算法看成有限输入数据 和有限输出结果之间的对应关系。 l 将以浮点算术运算为主的算法称为数值型算法 ，如线性方程组的求解，数值积分的计算，微分 方程初边

3、值问题的求解等。其它算法称为非数值 型算法，如排序问题，匹配查找问题等。 1.4 算法的评价l算法在保证可靠的大前提下再评价其优劣才是有价值的 。l数值型算法的可靠性算法的收敛性、稳定性、误差估计等算法必须在有限的时间内得到计算结果，如果某问题类的一个 求解过程是无限长，需要将其截断得到求解算法，并产生截断 误差。算法的收敛性就是研究当运行时间趋于无限长时，算法的解是 否趋于真实解，即截断误差是否趋于零。l非数值型算法的可靠性更为强调对于整体问题类算法计 算结果的正确性。算法的评价（2）l评价一个可靠算法的优劣，应该考虑其时间复杂 度（计算机运行时间）、空间复杂度（占据计算 机存储空间的多少）

4、以及逻辑复杂度（影响程序 开发的周期以及维护）。 2数值型算法的收敛阶 l迭代是构造数值问题算法的基本思想之一，迭代 的结果是得到问题解的一个近似序列. l如果对于问题类中任一问题，迭代次数k趋于无 穷大时序列极限存在，并且就是该问题的准确解 ，则称该迭代算法收敛到问题的解。 2.1 数列收敛阶的定义2.2 举例2.3 2阶收敛举例2.4 算法的收敛阶l类似地，如果收敛的数列是由迭代算法产生的， 定义数列的收敛阶为算法的收敛阶。不过需要注 意，算法是对问题类的算法，不是针对一个特定 问题的，这样算法的收敛阶应该是由该算法生成 的序列都具有的共同特征。 2.5 时间花费与收敛速度l对于不同的算法

5、，若每一迭代步的时间花费相当 ，从收敛阶的定义可以知道，收敛阶高的算法花 费较少的时间；对于同阶的算法，渐近常数小者 花费较少的时间。 2.6 向量序列的极限2.7 范数概念2.8 常用向量范数2.9 等价性定理、收敛速度2.10 常用的矩阵范数3 误差及数值算法的稳定性l误差的产生模型建立时因舍去次要矛盾会产生模型误差；模型中包含一些参数是通过仪表观测得到的，产生观测误差；算法必须在有限步内执行结束，这样需要将无穷过程截断为有 限过程，产生截断误差；在用计算机实现数值算法的过程中，由于计算机表示浮点数采 用的是固定有限字长，因而仅能够区分有限个信息，准确表示 在某个有限范围内的某些有理数，不

6、能准确表示数学中的所有 实数，这样在计算机中表示的原始输入数据、中间计算数据、 以及最终输出结果必然产生误差，称此类误差为舍入误差。l 得到的计算结果是这些误差综合影响下的数据。3.2 浮点数系l浮点数系是计算机常用的实数表示系统，一个浮 点数的表示由正负号、有限小数形式的尾数、以 及确定小数点位置的阶码三部分组成. l设在某一浮点系统中, 尾数占t位二进制数(未计 算尾数的符号位), 阶数占s位二进制数(未计算阶 数的符号位), 实数的浮点表示共需要ts2位 的二进制数位. 3.3 溢出3.4 单精度数l单精度实数用32位的二进制数据表示浮点数的这三个信 息, 其中数值符号和阶码符号各占1位

7、, 尾数占t=23位, 阶 码数值占s7位. 这样，除零外, 单精度实数的量级不大 于1038不小于1038. l当输入、输出或中间计算过程中出现量级大于1038的数 据时, 因单精度实数无法正确表示该数据, 将导致程序的 非正常停止, 称此现象为上溢(Overflow). l而当出现量级小于10-38的非零数据时, 一般计算机将该 数置为零, 精度损失, 称此现象为下溢(Underflow). l当数据有可能出现上溢或下溢时, 可通过乘积因子变换 数据, 使之正常表示. 67位有效数字3.5 初值误差l由于误差传播研究困难，经常研究某种假设下误 差的传播规律。如初值误差传播是在每一步都准 确

8、计算的假设下，即不考虑截断误差和由运算进 一步引入的舍入误差，研究误差传播规律。 3.6 数值稳定性l舍入误差分析是非常繁杂困难的, 而舍入误差不 可避免, 运算量又相当大, 为此, 人们提出了“数值 稳定性“这一概念对舍入误差是否影响产生可靠 的结果进行定性分析.l一个算法, 如果在运算过程中舍入误差在一定条 件下能够得到控制, 或者舍入误差的增长不影响 产生可靠的结果, 则称该算法是数值稳定的, 否 则称其为数值不稳定.3.7 数值稳定举例不稳定算法结果I1-I10近似值分别如下： 0.0883920 0.0580400 0.0431333 0.0343333 0.0283333 0.02

9、50000 0.0178571 0.0357143 -0.0674603 0.4373016 算法2Matlab 算出的精确解稳定性不同于显著性l 对算法的稳定性分析，其实就是给原始数据一 个小扰动，分析计算结果变化的程度,若很大则 算法不稳定，若可以接受，则算法稳定. 这里需 要指出，算法的稳定性不同于建立模型过程中因 素的显著性分析. 4数值型算法设计注意事项 对于一个数值型算法除了其正确性（如收敛性）外， 研究其效率（如收敛速度）、鲁棒性（如稳定性）是 很重要的，同时程序设计或实现时如下几个问题也不 可忽视： 1）减少计算次数以缩短计算时间 2）避免相近数相减避免相近数相减举例 3）尽可

10、能避免大数吃小数 其它l4）避免很小的数做分母，防止溢出出现；l5）正确使用实数相等的比较5 数值型算法构造的常用基本思想 掌握数值型算法构造的基本思想将会有利于提 出针对具体问题的有效快速算法 关于迭代的解释在这个过程中，首先我们用到了逼近的思想，将 一个常量（方程的一个根）看成变量的极限，这 个变量的每一个值是常量的近似值，不过它愈来 愈近似的好. 当然你也可以看出这个过程其实也 用到了两个思想：动与静的思想，极限的思想. 其次也用到了问题转换的思想，将函数的零点（ 方程的根）转换为另一个函数的不动点. 最后借 助不动点问题产生迭代序列，即使用迭代的思想 产生逼近序列. 线性方程组5.2

11、直与曲的思想 该法除了使用逼 近的思想外，还 用到了以直代曲 的思想，用一系 列的直线近似曲 线，这些直线是 曲线的一系列切 线，特点是切点 越来越和方程的 一个根接近 举例5.3 分段处理的思想 5.4 修正的思想 l修正的思想在常微 分方程数值解中使 用非常之多，它属 于预估校正类算 法 5.5 组合的思想 l对精度较低的解近似 进行组合，以期望得 到近似精度高的解近 似. 一个典型的例子是 龙贝格求积算法. 进一步说明l在这一组公式中，每一个式子的第二式就是用精 度较低的两个近似通过组合得到精度较高的近似 . 这个组合的推出，由每一个公式的第一个式子 可以看出是用了修正的思想，修正量是对

12、分后改 进量的一个分数倍数. 它还用了以直代曲的思想 、化整为零的思想，以得到复化梯形法计算公式 ， 5.6 自适应的思想 l自适应在算法构造中是非常重要的思想，它在构 造算法时也同时兼顾了局部特征. 以计算积分为 例，当使用复化梯形公式时，我们总希望函数值 变化较大的地方使用较多的节点，即使用较小的 步长，变化平坦的地方，步长较大一些，用较少 的节点. 显然用等步长的梯形公式效率就低，因 为它忽视了函数变化的快慢，即局部特征. 6算法的评价 l 同一问题可用不同算法解决，在分析了算法的 可靠性之后，就需要对其效率进行分析，算法分 析的目的在于选择合适的算法和改进算法. 一个 算法的效率评价主

13、要从时间复杂度和空间复杂度 来考虑. 6.1 时间复杂度1）时间频度算法执行所开销的时间，从理论上是很难算出来的，而 上机运行测试可以得到时间花费的准确结果. 但我们不 可能也没有必要对每个算法都上机测试，只需知道哪个 算法花费的时间多，哪个算法花费的时间少就可以了. 并且一个算法花费的时间与算法中语句的执行次数成正 比例，哪个算法中语句执行次数多，它花费时间就多. 一个算法中的语句执行次数称为算法时间频度，记为 T(n)，其中 n是问题的规模，它是算法执行时所需存储 空间的度量. 符号T(n)表示算法的语句频度是问题规模 的函数，它是算法需要完成多少工作的度量.2）时间复杂度在时间频度中，当

14、问题规模n不断变化时，时 间频度T(n)也会不断变化. 为研究它变化时呈现 的规律性，引入时间复杂度的概念.算法的时间频度是问题规模n的某个函数T(n) ，若有某个辅助函数g(n)， 使得当n趋近于无穷 大时，T(n)/g(n)的极限值为不等于零的常数，则 称f(n)是T(n)的同数量级函数，记作T(n)=O(g(n) ，称O(g(n) 为算法的渐进时间复杂度，简称时 间复杂度. 举例时间复杂度的渐进常数之比说明l在算法中，若语句执行次数为一个常数，与求解规模没 关系，则时间复杂度为O(1). 即算法的执行时间不随着 问题规模n的增加而增长，即使算法中有上千条语句， 其执行时间也不过是一个较大

15、的常数，此类算法的时间 复杂度是O(1). l例子表明，在时间频度不相同时，时间复杂度也有可能 相同. l在算法分析时，往往对算法的时间复杂度和渐近时间复 杂度不予区分，而经常是将渐近时间复杂度 T(n)=O(g(n)简称为时间复杂度，其中函数g(n)一般选为 算法中频度最大的语句频度. 常见的不同时间复杂度的效率按数量级递增排列的时间复杂度 有：常数阶O(1)，线性阶O(n)， 线性对数阶O(nlogn)，平方阶 O(n2),立方阶O(n3)，指数阶O(2n) 和 n!. 随着问题规模n的不断增大 ，上述时间复杂度不断增大，算 法的执行效率越低 比较图1比较图2比较图3比较图4给定数据规模n

16、，执行给定时间复杂度的算法耗时比 较n102030 log10n 0.000 001 0秒 0.000 001 3 秒0.000 001 5 秒 n0.000 01秒0.000 02秒0.000 03秒 n20.000 1秒0.000 4秒0.000 9秒 n30.001秒0.008秒0.027秒 n50.1秒3.2秒24.3秒 2n0.001秒1.0秒17.9分 3n0.059秒58分6.5年 n!3.6秒771.5世纪8.4E16世纪给定数据规模n，执行给定时间复杂度的算法耗时比 较n405060 log10n 0.000 001 6秒 0.000 001 7 秒0.000 001 8 秒 n0.000 04秒0.000 05秒0.000 06秒 n20.001 6秒0.002 5秒0.003 6秒 n30.064秒0.125秒0.216秒 n51.7分5.2分13.0分 2n12.7天35.7年366世纪