数学建模课件算法基础.ppt

第八章 算法基础 西北工业大学 应用数学系 聂玉峰 1.算法概念 l数学建模竞赛的过程 l算法的概念 l算法的分类 l算法的评价 1.1 建模竞赛的过程 l实际上是命题人（某个领域的专家）提出实际问题 l参赛人首先读题，分析问题，依照自己的理解准确阐述 问题； l辨析问题中的主要矛盾和次要矛盾，并在合理假设的条 件下，运用各种数学理论、工具和方法，建立起问题中 不同量之间的约束关系，进而得到完备的数学模型； l在研究模型解的存在性与惟一性 l如何求其解 l利用解对模型的正确性进行评价。 1.2 算法的概念 l当数学模型的分析解得不到时，使用计算机进行求解。 我们不会做的计算机肯定不会做，只有当我们会做，但 因为数据计算量太大时，把自己的求解过程（算法）编 写成程序，计算机将其编译、运行得到计算结果。 l 所谓（串行）算法就是求解一个问题类的无二义性的有 穷过程，这里过程明确无歧义的描述由有限操作（算术 运算、逻辑运算、字符运算、读写操作等）及有限操作 对象合成的按一定顺序执行的有限序列。 l原始的可以变化的有限操作对象就是有限输入数据，它 所有可能允许的变化构成求解的问题类。 1.3 算法的分类 l对给定的输入数据，算法运行后得到的数据结果 也是有限的，这样可以把算法看成有限输入数据 和有限输出结果之间的对应关系。 l 将以浮点算术运算为主的算法称为数值型算法 ，如线性方程组的求解，数值积分的计算，微分 方程初边值问题的求解等。其它算法称为非数值 型算法，如排序问题，匹配查找问题等。 1.4 算法的评价 l算法在保证可靠的大前提下再评价其优劣才是有价值的 。 l数值型算法的可靠性 算法的收敛性、稳定性、误差估计等 算法必须在有限的时间内得到计算结果，如果某问题类的一个 求解过程是无限长，需要将其截断得到求解算法，并产生截断 误差。 算法的收敛性就是研究当运行时间趋于无限长时，算法的解是 否趋于真实解，即截断误差是否趋于零。 l非数值型算法的可靠性更为强调对于整体问题类算法计 算结果的正确性。 算法的评价（2） l评价一个可靠算法的优劣，应该考虑其时间复杂 度（计算机运行时间）、空间复杂度（占据计算 机存储空间的多少）以及逻辑复杂度（影响程序 开发的周期以及维护）。 2数值型算法的收敛阶 l迭代是构造数值问题算法的基本思想之一，迭代 的结果是得到问题解的一个近似序列. l如果对于问题类中任一问题，迭代次数k趋于无 穷大时序列极限存在，并且就是该问题的准确解 ，则称该迭代算法收敛到问题的解。 2.1 数列收敛阶的定义 2.2 举例 2.3 2阶收敛举例 2.4 算法的收敛阶 l类似地，如果收敛的数列是由迭代算法产生的， 定义数列的收敛阶为算法的收敛阶。不过需要注 意，算法是对问题类的算法，不是针对一个特定 问题的，这样算法的收敛阶应该是由该算法生成 的序列都具有的共同特征。 2.5 时间花费与收敛速度 l对于不同的算法，若每一迭代步的时间花费相当 ，从收敛阶的定义可以知道，收敛阶高的算法花 费较少的时间；对于同阶的算法，渐近常数小者 花费较少的时间。 2.6 向量序列的极限 2.7 范数概念 2.8 常用向量范数 2.9 等价性定理、收敛速度 2.10 常用的矩阵范数 3 误差及数值算法的稳定性 l误差的产生 模型建立时因舍去次要矛盾会产生模型误差； 模型中包含一些参数是通过仪表观测得到的，产生观测误差； 算法必须在有限步内执行结束，这样需要将无穷过程截断为有 限过程，产生截断误差； 在用计算机实现数值算法的过程中，由于计算机表示浮点数采 用的是固定有限字长，因而仅能够区分有限个信息，准确表示 在某个有限范围内的某些有理数，不能准确表示数学中的所有 实数，这样在计算机中表示的原始输入数据、中间计算数据、 以及最终输出结果必然产生误差，称此类误差为舍入误差。 l 得到的计算结果是这些误差综合影响下的数据。 3.2 浮点数系 l浮点数系是计算机常用的实数表示系统，一个浮 点数的表示由正负号、有限小数形式的尾数、以 及确定小数点位置的阶码三部分组成. l设在某一浮点系统中, 尾数占t位二进制数(未计 算尾数的符号位), 阶数占s位二进制数(未计算阶 数的符号位), 实数的浮点表示共需要ts2位 的二进制数位. 3.3 溢出 3.4 单精度数 l单精度实数用32位的二进制数据表示浮点数的这三个信 息, 其中数值符号和阶码符号各占1位, 尾数占t=23位, 阶 码数值占s7位. 这样，除零外, 单精度实数的量级不大 于1038不小于1038. l当输入、输出或中间计算过程中出现量级大于1038的数 据时, 因单精度实数无法正确表示该数据, 将导致程序的 非正常停止, 称此现象为上溢(Overflow). l而当出现量级小于10-38的非零数据时, 一般计算机将该 数置为零, 精度损失, 称此现象为下溢(Underflow). l当数据有可能出现上溢或下溢时, 可通过乘积因子变换 数据, 使之正常表示. 67位有效数字 3.5 初值误差 l由于误差传播研究困难，经常研究某种假设下误 差的传播规律。如初值误差传播是在每一步都准 确计算的假设下，即不考虑截断误差和由运算进 一步引入的舍入误差，研究误差传播规律。 3.6 数值稳定性 l舍入误差分析是非常繁杂困难的, 而舍入误差不 可避免, 运算量又相当大, 为此, 人们提出了“数值 稳定性“这一概念对舍入误差是否影响产生可靠 的结果进行定性分析. l一个算法, 如果在运算过程中舍入误差在一定条 件下能够得到控制, 或者舍入误差的增长不影响 产生可靠的结果, 则称该算法是数值稳定的, 否 则称其为数值不稳定. 3.7 数值稳定举例 不稳定算法结果 I1-I10近似值分别如下： 0.0883920 0.0580400 0.0431333 0.0343333 0.0283333 0.0250000 0.0178571 0.0357143 -0.0674603 0.4373016 算法2 Matlab 算出的精确解 稳定性不同于显著性 l 对算法的稳定性分析，其实就是给原始数据一 个小扰动，分析计算结果变化的程度,若很大则 算法不稳定，若可以接受，则算法稳定. 这里需 要指出，算法的稳定性不同于建立模型过程中因 素的显著性分析. 4数值型算法设计注意事项 对于一个数值型算法除了其正确性（如收敛性）外， 研究其效率（如收敛速度）、鲁棒性（如稳定性）是 很重要的，同时程序设计或实现时如下几个问题也不 可忽视： 1）减少计算次数以缩短计算时间 2）避免相近数相减 避免相近数相减举例 3）尽可能避免大数吃小数 其它 l4）避免很小的数做分母，防止溢出出现； l5）正确使用实数相等的比较 5 数值型算法构造的常用基本思想 掌握数值型算法构造的基本思想将会有利于提 出针对具体问题的有效快速算法 关于迭代的解释 在这个过程中，首先我们用到了逼近的思想，将 一个常量（方程的一个根）看成变量的极限，这 个变量的每一个值是常量的近似值，不过它愈来 愈近似的好. 当然你也可以看出这个过程其实也 用到了两个思想：动与静的思想，极限的思想. 其次也用到了问题转换的思想，将函数的零点（ 方程的根）转换为另一个函数的不动点. 最后借 助不动点问题产生迭代序列，即使用迭代的思想 产生逼近序列. 线性方程组 5.2 直与曲的思想 该法除了使用逼 近的思想外，还 用到了以直代曲 的思想，用一系 列的直线近似曲 线，这些直线是 曲线的一系列切 线，特点是切点 越来越和方程的 一个根接近 举例 5.3 分段处理的思想 5.4 修正的思想 l修正的思想在常微 分方程数值解中使 用非常之多，它属 于预估校正类算 法 5.5 组合的思想 l对精度较低的解近似 进行组合，以期望得 到近似精度高的解近 似. 一个典型的例子是 龙贝格求积算法. 进一步说明 l在这一组公式中，每一个式子的第二式就是用精 度较低的两个近似通过组合得到精度较高的近似 . 这个组合的推出，由每一个公式的第一个式子 可以看出是用了修正的思想，修正量是对分后改 进量的一个分数倍数. 它还用了以直代曲的思想 、化整为零的思想，以得到复化梯形法计算公式 ， 5.6 自适应的思想 l自适应在算法构造中是非常重要的思想，它在构 造算法时也同时兼顾了局部特征. 以计算积分为 例，当使用复化梯形公式时，我们总希望函数值 变化较大的地方使用较多的节点，即使用较小的 步长，变化平坦的地方，步长较大一些，用较少 的节点. 显然用等步长的梯形公式效率就低，因 为它忽视了函数变化的快慢，即局部特征. 6算法的评价 l 同一问题可用不同算法解决，在分析了算法的 可靠性之后，就需要对其效率进行分析，算法分 析的目的在于选择合适的算法和改进算法. 一个 算法的效率评价主要从时间复杂度和空间复杂度 来考虑. 6.1 时间复杂度 1）时间频度 算法执行所开销的时间，从理论上是很难算出来的，而 上机运行测试可以得到时间花费的准确结果. 但我们不 可能也没有必要对每个算法都上机测试，只需知道哪个 算法花费的时间多，哪个算法花费的时间少就可以了. 并且一个算法花费的时间与算法中语句的执行次数成正 比例，哪个算法中语句执行次数多，它花费时间就多. 一个算法中的语句执行次数称为算法时间频度，记为 T(n)，其中 n是问题的规模，它是算法执行时所需存储 空间的度量. 符号T(n)表示算法的语句频度是问题规模 的函数，它是算法需要完成多少工作的度量. 2）时间复杂度 在时间频度中，当问题规模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的增加而增长，即使算法中有上千条语句， 其执行时间也不过是一个较大的常数，此类算法的时间 复杂度是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，执行给定时间复杂度的算法耗时比 较 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世纪 3n3 855世纪2E8世纪1.3E13世纪 n!2.6E32世纪9.6E48世纪2.6E66世纪 6.2 问题的规模 l时间复杂度是问题规模n的函数. 我们将标识问题类中不 同问题大小的参数定义为问题的规模. 如计算两个向量 的点乘积，那么一个向量的分量个数n就是它的规模参 数；计算两个矩阵的乘法，矩阵的行数和列数就是该问 题的规模；如若计算方阵的乘法，它的行数或者列数就 是该问题规模；求解一个线性方程组，线形方程组的阶 数就是其规模；对一组数进行排序，这一组数的个数就 是其规模，等等. l问题的规模不同于求解一个问题的算法的空间复杂度， 算法的空间复杂度涉及到除原始数据外所需要额外增加 的存储空间. 原始数据量是问题规模的单调增加函数 6.3 时间复杂度分析 l考虑算法的渐进时间复杂度，即随着问题规模的增大时 间频度的变化趋势，通常时间耗费是问题规模的单调增 加函数，因而算法中的一些与问题规模无关的语句执行 时间可以不予考虑，因为该语句的频度是O(1). 由于编 译系统对循环语句中循环次数的控制在编译时已经计算 好，所以时间复杂性分析时可以不予考虑. l当对渐进常数的大小不关心，仅考虑其渐进阶数时，只 需分析循环中某一个语句的执行频度. 这也从另一个侧 面说明数量级分析并不是算法分析的全部内容，它仅考 虑了数量级最高项的级，忽略其系数，更忽略了低阶项. 例1 计算两个向量点乘积的算法 l问题规模为n，全部统计 时算法复杂度为O(n+1) ，忽略循环外的语句时 算法复杂度为O(n)，显 然他们的量级相同. 这里 对步进循环语句只考虑 循环体中语句的执行次 数，忽略该语句中步长 加1、终值判别、控制转 移等成分 例2 计算一个n维行向量和两个n阶方矩阵的乘积. l问题规模为n，算法时间 复杂度为O(2n2+2n)，忽 略外循环时，算法复杂度 为O(2n2)，显然它们具有 相同的渐进阶，且渐进常 数相同；如果仅考虑内循 环的一条语句，算法复杂 度为O(n2)，虽然依然保 证同阶，但渐进常数发生 了改变 例3 矩阵乘积 例4 计算n阶方阵下三角部分元素之和 l 算法复杂度为 O(n(n+1)/2+1). 该算法分 析时，内循环参数虽没有 和问题规模直接相关，但 它和外循环参数i相关，i 与问题规模是相关的，这 样内循环参数j间接和问 题规模相关. 算法分析时 一定得注意循环控制参数 与问题规模间的间接相关 性. 例5 计算向量分量的正弦值的最大值 l 问题规模为n，算法复杂度O(3n-2). 这里统计语句频度时，没有区分正 弦值计算与比较、数值操作上执行 时间的差异，显然后者花费较少的 时间.