《数学建模简明教程》由会员分享，可在线阅读，更多相关《数学建模简明教程（53页珍藏版）》请在金锄头文库上搜索。
1、哑涣暗拔纠悟盯晃得翌北晃己长总岔稳篆遭步头尾峡验纳锡斋监措辩谍尼数学建模简明教程数学建模简明教程数学建模简明教程国家精品课程国家精品课程膀辊周公配脸伪炔望募极泌获汽蛾享遣愁按颐楚捍氖幂鸽格骤啮聚泉补甄数学建模简明教程数学建模简明教程第八章第八章 算法基础算法基础一、一、算法概念算法概念二、数值型算法构造的常用思想二、数值型算法构造的常用思想三、数值算法可靠性三、数值算法可靠性 四、四、数值型算法设计注意事项数值型算法设计注意事项 五、五、算法的评价算法的评价目录下页返回上页结束哲茸畴芬疮缚壹仇盔湍器杨什聊氰柬毙后絮迫肉晤挪波拈汰恼贰想怎届绽数学建模简明教程数学建模简明教程 1.1 数学建模竞赛
2、的过程数学建模竞赛的过程 1.3 算法的分类算法的分类 1.4 算法的评价算法的评价 1.2 算法的概念算法的概念 一、算法概念一、算法概念目录下页返回上页结束烤部否卫钳素老融堡摆拙缄肩舞漫呵裴奏满懈积航罕呜癣抬怜爪昂笆场邑数学建模简明教程数学建模简明教程 1.1 数学建模竞赛的过程数学建模竞赛的过程 (1)提出问题：提出问题：命题人（某个领域的专家）提出命题人（某个领域的专家）提出 (2)分析问题：分析问题：参赛人首先读题，分析问题，依参赛人首先读题，分析问题，依 (3)建立模型：建立模型：辨析问题中的主要矛盾和次要矛辨析问题中的主要矛盾和次要矛 (4)模型求解：模型求解：研究解的存在性与惟
3、一性，寻找研究解的存在性与惟一性，寻找 目录下页返回上页结束实际问题实际问题；照自己的理解准确阐述问题照自己的理解准确阐述问题；间的约束关系，进而得到完备的数学模型；间的约束关系，进而得到完备的数学模型；理论、工具和方法，建立起问题中不同量之理论、工具和方法，建立起问题中不同量之盾，盾，并在合理假设的条件下，运用各种数学并在合理假设的条件下，运用各种数学求解方法，利用解对模型的正确性进行评价求解方法，利用解对模型的正确性进行评价.踊变啮订硅健场沫庄帐怀峙索滩漳岛催俐单橱亿厌玄住昔馒成烩嫁必伏雕数学建模简明教程数学建模简明教程 1.2 算法的概念算法的概念 定义定义 串行串行算法算法就是求解一个
4、问题类的无二义性就是求解一个问题类的无二义性定义定义 原始的可变化的原始的可变化的有限操作对象有限操作对象就是有限输入就是有限输入注注 对给定的输入数据，算法运行后得到的数据对给定的输入数据，算法运行后得到的数据的有穷过程，这里过程明确无歧义的描述由有限的有穷过程，这里过程明确无歧义的描述由有限操作（算术、逻辑、字符运算和读写操作等）及操作（算术、逻辑、字符运算和读写操作等）及有限操作对象合成的按一定顺序执行的有限序列有限操作对象合成的按一定顺序执行的有限序列. .数据，它所有可能允许的变化构成求解的数据，它所有可能允许的变化构成求解的问题类问题类. .结果也是有限的，结果也是有限的，这样可以
5、把算法看成有限输入这样可以把算法看成有限输入数据和有限输出结果之间的对应关系数据和有限输出结果之间的对应关系. . 目录下页返回上页结束颧尤茄左场青竞氢浙捆缘粪俱宋拔腕曼叉持婪右学眼渐忱氏篇掌拥滨蜒在数学建模简明教程数学建模简明教程 1.3 算法的分类算法的分类 定义定义 根据对象的不同可以将算法分为根据对象的不同可以将算法分为数值型数值型目录下页返回上页结束算法算法和和非数值型算法非数值型算法.将以浮点算术运算为主将以浮点算术运算为主的算法称为的算法称为数值型算法数值型算法，非数值型算法非数值型算法一般一般包括线性表、栈、队列和串、树、图，排序、包括线性表、栈、队列和串、树、图，排序、 查找
6、等数据处理方面的算法查找等数据处理方面的算法.汇改凤敲槐杜楷焰聚棱卸矫编殷难滥啥袭利曳图纺照扮拷糯创夕匡揭咒谊数学建模简明教程数学建模简明教程 1.4 算法的评价算法的评价 优劣优劣才是有价值的才是有价值的. (1) 算法可靠性评价算法可靠性评价 数值型算法：数值型算法：收敛性、稳定性、误差估计；收敛性、稳定性、误差估计； 非数值型算法：强调对于整体问题类算法非数值型算法：强调对于整体问题类算法计算结果的正确性计算结果的正确性.(2) 算法优劣评价算法优劣评价时间复杂度，空间复杂度，逻辑复杂度时间复杂度，空间复杂度，逻辑复杂度.注注 算法在保证可靠的大前提下再评价其算法在保证可靠的大前提下再评
7、价其目录下页返回上页结束坞萎结狡伟钟柄廖诗拇撞呵铃巫瓤孩寥黔象泪赚龙焊叭莉域篙凶帕疼早纤数学建模简明教程数学建模简明教程二、构造数值型算法的常用思想二、构造数值型算法的常用思想了解数值型算法构造的常用基本思想，有利于了解数值型算法构造的常用基本思想，有利于针对自己研究的具体问题提出有效可靠算法针对自己研究的具体问题提出有效可靠算法. 2.1 迭代的思想迭代的思想 2.2 直与曲的思想直与曲的思想 2.3 分段处理的思想分段处理的思想 2.4 修正的思想修正的思想 2.5 组合的思想组合的思想 2.6 自适应的思想自适应的思想 常用基本思想：常用基本思想：目录下页返回上页结束鞋丽突礁二粮甜收汰埋
8、栖平愧姑减上牡糟浸窑桔律缓墩勺韩锯静片面秉展数学建模简明教程数学建模简明教程 2.1 迭代的思想迭代的思想 非线性方程非线性方程 等价变形等价变形迭代格式迭代格式 产生迭代序列产生迭代序列如果如果则可以得到方程的解则可以得到方程的解.线性方程组线性方程组等价变形等价变形迭代格式迭代格式产生迭代向量序列产生迭代向量序列如果如果则可得到方程组的解则可得到方程组的解.目录下页返回上页结束均拖赠搞簧霹冬隘燕嚏裳淀彦荡默桌顺怖培赦驹痒渡笆蠢用罕蕊续刹小腐数学建模简明教程数学建模简明教程 2.2 直与曲的思想直与曲的思想 大多数曲线就一小范围来看大致可以看成是大多数曲线就一小范围来看大致可以看成是直线直线
9、. . 非线性方程非线性方程 的根可视为函数的根可视为函数 与与 轴的交点轴的交点. 在交点附近可以用在交点附近可以用 直线代替曲线直线代替曲线 ，相应地用直线与，相应地用直线与 x*Oyx 轴的交点轴的交点 代替曲线与代替曲线与 轴的交点轴的交点 .牛顿迭代法牛顿迭代法目录下页返回上页结束帘裹贬劝保咯说嗜蹄幢观囱嵌刨笔勇结谬伐咳体级弦敦憾陋预皂虫宽耽蒂数学建模简明教程数学建模简明教程例例 求解常微分方程初值问题求解常微分方程初值问题的欧拉折线法的欧拉折线法 典型的以折线段近似曲线的典型的以折线段近似曲线的. .xyy(x)xnxn+1PnPn+1目录下页返回上页结束犁灾消乎虫斜岸兔点量学盎宠
10、仿蛛谐夕酗您捆拆殆奶搅损鸳锯岳誊茫西占数学建模简明教程数学建模简明教程 2.3 分段处理的思想分段处理的思想 已知一组采样点已知一组采样点 值，求非采样点处值，求非采样点处 函数值的一种方法就是插值法函数值的一种方法就是插值法.当当 较大时较大时,如果直接采用高次插值如果直接采用高次插值一是计算量大一是计算量大;二是高次插值不保证收敛，也不稳定二是高次插值不保证收敛，也不稳定. .采用采用分段处理的思想分段处理的思想就能很好解决该问题就能很好解决该问题, ,即采用分段的低次插值，既能保证稳定，又即采用分段的低次插值，既能保证稳定，又收敛，计算量还小收敛，计算量还小. .目录下页返回上页结束担妄
11、袜灌坚滦惑苔铲届蛛戮芜允首恒清宠媳邑阻系乔某袄痛丝衫巧甫坞版数学建模简明教程数学建模简明教程 2.4 修正的思想修正的思想 记记 为线性方程组为线性方程组 的一个近似，一般的一个近似，一般说来残差说来残差 不等于零向量，对之不等于零向量，对之 进行修正得到更好的近似进行修正得到更好的近似 式中矩式中矩阵是由是由的的对角元素构成的矩角元素构成的矩阵 逐个超松弛逐个超松弛迭代法迭代法注注 此方法采用的就是给粗糙的解向量一个此方法采用的就是给粗糙的解向量一个修正量修正量，以得到更好的解近似以得到更好的解近似. .目录下页返回上页结束咱窥栗页荒湖吱宪琉诗隅穴段打屡划语濒材噪揍淆瘤枯茵区猴腊暇轩晓条数学
12、建模简明教程数学建模简明教程 2.5 组合的思想组合的思想 对精度较低的解近似进行组合，以期望得到对精度较低的解近似进行组合，以期望得到近似精度高的解近似近似精度高的解近似. . 例例 龙贝格求积算法龙贝格求积算法. .计算积分计算积分 将区间将区间 等分等分 个子个子区间区间,采用复化梯形公式得到的近似值为采用复化梯形公式得到的近似值为目录下页返回上页结束倡超掺匹泽疮醉煞程败下应莉寸驱座罪永泄躯河澳谈拂酥牙砖村袱坛享鸣数学建模简明教程数学建模简明教程 2.6 自适应的思想自适应的思想 自适应在算法构造中是非常重要的思想，它在自适应在算法构造中是非常重要的思想，它在构造算法时也同时兼顾了局部特
13、征构造算法时也同时兼顾了局部特征.小小的步长，变化平坦的地方，步长较大一些的步长，变化平坦的地方，步长较大一些. . 例例 当使用复化梯形公式计算积分时，在函数当使用复化梯形公式计算积分时，在函数值变化较大的地方使用较多的节点，即使用较值变化较大的地方使用较多的节点，即使用较xyxyf(x)f(x)自适应自适应非自适应非自适应目录下页返回上页结束迎订纸里鹰靖窖桨顺病颠磅习撮破匪钵呢畅帜怠馒宛库逃呢吞洗锤检份晃数学建模简明教程数学建模简明教程三、数值算法的可靠性三、数值算法的可靠性 本节介绍算法可靠性的三个方面：本节介绍算法可靠性的三个方面： (1)算法的收敛性算法的收敛性：研究当运行时间趋于无
14、限研究当运行时间趋于无限长时，算法的解是否趋于真实解，即截断长时，算法的解是否趋于真实解，即截断误差是否趋于零误差是否趋于零. (2)算法的稳定性算法的稳定性：就是当原始数据有小的误就是当原始数据有小的误差时，算法计算出的结果是否也有小扰动，差时，算法计算出的结果是否也有小扰动，而不是很大的变化而不是很大的变化.(3)误差估计误差估计：其其用途是设计循环的终止条件，用途是设计循环的终止条件，让数值解满足给定的精度要求让数值解满足给定的精度要求.目录下页返回上页结束阴坊扮藏光噎辅恩先玻淤藤杭吗萎废帖诧湿他馒渐冗祝称遍枪裙坟板坏些数学建模简明教程数学建模简明教程 3.1 近似解序列的收敛性近似解序
15、列的收敛性 迭代迭代是构造数值问题算法的基本思想之一，是构造数值问题算法的基本思想之一，迭代得到问题解的一个近似序列迭代得到问题解的一个近似序列 ，如果如果 ，且，且 就是原问题的解，就是原问题的解，则称该迭代算法收敛到问题的解则称该迭代算法收敛到问题的解. . 多变量问题的迭代算法，产生的近似解序列多变量问题的迭代算法，产生的近似解序列是向量序列是向量序列 ，目录下页返回上页结束拿栏翱亨瞳弃亨字皇文慈蕴眷失雏朔锤哦圭拌德蓖剔把乔溜率专满拥食情数学建模简明教程数学建模简明教程 3.1.1 向量序列收敛定义向量序列收敛定义 定义定义 如存在向量如存在向量 使向量序使向量序列列 的各分量构成的数列
16、收敛到向量的各分量构成的数列收敛到向量的对应分量，即的对应分量，即 称称向量序列向量序列 收敛到向量收敛到向量 . 注注 上述收敛被称为按分量收敛，此定义虽然上述收敛被称为按分量收敛，此定义虽然直观，但不便于理论分析，因此引入向量按范直观，但不便于理论分析，因此引入向量按范数收敛的定义数收敛的定义.目录下页返回上页结束谰选佃驹窿硅渴毋袭箩硼梧核霞译厨虾才小匡濒劳返獭凡酪挑怪暖歪爪塑数学建模简明教程数学建模简明教程 3.1.2 范数概念范数概念 定义定义 定义在定义在 上的实值函数上的实值函数 ，如果满足，如果满足1) 非负性，即非负性，即2) 齐次性，即齐次性，即3) 三角不等式，即三角不等式
17、，即则称函数则称函数 是该向量空间上的一种是该向量空间上的一种范数范数. . 注注 范数概念是对距离的一种抽象和推广范数概念是对距离的一种抽象和推广.目录下页返回上页结束咏撰磕与诬奢两氓烷脆局隔蓖堰衡妖戈囚关软架惟贺捣酸盏帧嚎畅橱诺魔数学建模简明教程数学建模简明教程 3.1.3 常用向量范数常用向量范数 对于向量对于向量 ，常用的范数有，常用的范数有 例例 计算向量计算向量 的各种范数的各种范数 解解目录下页返回上页结束限吝特邪都炬鞋墒劫渍诬贝墓袭拟憨粹毁锻浓议策梢狞螺蛆锅集啥邓朽侍数学建模简明教程数学建模简明教程 3.1.4 常用的矩阵范数常用的矩阵范数 定义定义 对于矩阵对于矩阵A，常用的
18、范数有，常用的范数有 行和范数行和范数列和范数列和范数谱范数谱范数目录下页返回上页结束盎色绚或蝉听敲渠晚蓑蠢冶慨主涧怀簇闪悠等俱依妇枪十听祖结了提裁拧数学建模简明教程数学建模简明教程 3.1.5 等价性定理、收敛阶等价性定理、收敛阶 定理定理 向量序列向量序列 收敛到向量收敛到向量 的的 充分必要条件是存在某种向量范数充分必要条件是存在某种向量范数 使得使得 定义定义 对于收敛的向量序列，如果满足对于收敛的向量序列，如果满足 这里这里c为为收敛常数收敛常数，称该向量，称该向量p阶收敛阶收敛. 按范数收敛按范数收敛目录下页返回上页结束纫引头沉使那乱吱其翰炯噶胡运怂君厄提霖湃泵间壶铬幂德陈煽家烷嫁
19、实数学建模简明教程数学建模简明教程 3.1.5 收敛速度收敛速度 小结小结 收敛阶用来刻画和比较收敛速度的快慢收敛阶用来刻画和比较收敛速度的快慢p越大收敛速度越快越大收敛速度越快. .当当p1时称为线性收敛；时称为线性收敛；当当p大于大于1 1时称为超线性收敛；时称为超线性收敛；当当p2时为平方收敛（二次收敛）；时为平方收敛（二次收敛）； 收敛阶相同的算法说明收敛速度快慢基本相当，收敛阶相同的算法说明收敛速度快慢基本相当， 更进一步的比较需考察收敛常数更进一步的比较需考察收敛常数c，c小的收敛小的收敛 速度更快一点速度更快一点.目录下页返回上页结束御弛窘岁隧柜尉恫塘风缕响娶仁峨味浸步肚勃藩肚历
20、械费宰扦淄导拙朔撒数学建模简明教程数学建模简明教程例例 比较下列数列的收敛速度比较下列数列的收敛速度解解 三个数列都会收敛到三个数列都会收敛到 0,但速度不同但速度不同目录下页返回上页结束薄蔫厚奔花坡古窟放恨硬式滓厄厘励霉酒力掷蜜夹螺虹涌到柞瘪敬毋睡釉数学建模简明教程数学建模简明教程线形收敛线形收敛, ,而而 二次收敛二次收敛, ,因此因此 收敛最快收敛最快, , 比比 的收敛常数小的收敛常数小,因此收敛稍快因此收敛稍快.目录下页返回上页结束砸官谢甥否叠滋晨廷证件禹古绝诣称泰绣僳吵鞍斗篙斤燎本僳遇扇旧遭瓷数学建模简明教程数学建模简明教程 我们知道，通常给算法提供的输入数据会有我们知道，通常给算
21、法提供的输入数据会有误差，计算机在运算过程中还会有新的误差误差，计算机在运算过程中还会有新的误差产生产生. 需要回答的一个问题是：需要回答的一个问题是： 当原始数据有小的误差时，算法计算出的当原始数据有小的误差时，算法计算出的 结果是否也是有小扰动，而不是大的变化结果是否也是有小扰动，而不是大的变化.这就是算法的这就是算法的稳定性问题稳定性问题. 3.2 误差和数值算法的稳定性误差和数值算法的稳定性 目录下页返回上页结束瘦尹炳巩流饭盈蚜磺专仟钟瓜捕桓煽丸杨匣条楚姚祥撞救阑冯罩丝我铡也数学建模简明教程数学建模简明教程 3.2.1 误差的产生误差的产生 模型误差；模型误差；模型建立时因舍去次要矛盾
22、而模型建立时因舍去次要矛盾而产生的误差产生的误差. . 观测误差；观测误差；模型中包含一些参数是通过仪模型中包含一些参数是通过仪表观测得到的，观测过程中带来的误差表观测得到的，观测过程中带来的误差. 截断误差；截断误差；算法必须在有限步内执行结束，算法必须在有限步内执行结束，将无穷过程截断为有限过程时产生的误差将无穷过程截断为有限过程时产生的误差. . 舍入误差；舍入误差；由于计算机表示的数据字长有限由于计算机表示的数据字长有限无法准确表示所有实数，由此产生误差无法准确表示所有实数，由此产生误差.目录下页返回上页结束续镇萧敢雍幕看凡憋拳湿榜取裁爹胃漫厩元咕麻翟圣勒决录尺摄冤宏扬窥数学建模简明教
23、程数学建模简明教程 3.2.2 浮点数系及溢出浮点数系及溢出 浮点数系浮点数系是计算机常用的实数表示系统，一个是计算机常用的实数表示系统，一个浮点数的表示由正负号、有限小数形式的尾数、浮点数的表示由正负号、有限小数形式的尾数、以及确定小数点位置的阶码三部分组成以及确定小数点位置的阶码三部分组成. .0100000001100000000000000000000阶数s尾数t上溢界：上溢界：计算机能表示的最大数算机能表示的最大数 . 下溢界：下溢界：计算机能表示的最小数算机能表示的最小数3232位位=23=23位尾数位尾数+7+7位阶数位阶数+1+1位阶数符号位位阶数符号位+1+1位尾数符号位位尾
24、数符号位目录下页返回上页结束暮哑央葫燃术痔氛认状峦峨睫妙烟蜜静逼浮套梢穗足吞遭防驯盲搐辈皇串数学建模简明教程数学建模简明教程 3.2.3 初值误差的传播初值误差的传播 由于误差传播研究困难，经常研究某种假设下由于误差传播研究困难，经常研究某种假设下误差的传播规律误差的传播规律. .如如初值误差传播初值误差传播是在每一步是在每一步都准确计算的假设下，即不考虑截断误差和运都准确计算的假设下，即不考虑截断误差和运算进一步引入的舍入误差，研究误差传播规律算进一步引入的舍入误差，研究误差传播规律. 例、例、 对函数对函数 用用 近似近似 则则 目录下页返回上页结束啸砰狸截先蛆厦腺预援画喜獭徊忠怀涝柞耕爆
25、咀魄怯烘故汗柠亦毫睬茂晒数学建模简明教程数学建模简明教程 3.2.4 数值稳定性数值稳定性 数值稳定的数值稳定的, , 否则称其为数值不稳定否则称其为数值不稳定. .舍入误差分析是非常繁杂困难的舍入误差分析是非常繁杂困难的, , 而舍入误差而舍入误差不可避免不可避免, , 运算量又相当大运算量又相当大, , 为此为此, , 人们提出人们提出了了 数值稳定性数值稳定性 这一概念对舍入误差是否影响这一概念对舍入误差是否影响产生可靠的结果进行定性分析产生可靠的结果进行定性分析. . 定义定义 一个算法一个算法,如果在运算过程中舍入误差在如果在运算过程中舍入误差在一定条件下能够得到控制一定条件下能够得
26、到控制, , 或者舍入误差的或者舍入误差的增增长不影响产生可靠的结果长不影响产生可靠的结果, , 则称该算法是则称该算法是目录下页返回上页结束蹬亩筐窥阻镶敲潜握昭孩仕私蓑盂纱旨捍阿酒簿轰钒臭昔戍斧赚抬浓兑裁数学建模简明教程数学建模简明教程 例例 计算积分序列计算积分序列 ，由于，由于解法解法1 向向前前迭代迭代 可以采用迭代的解法求解可以采用迭代的解法求解.计算初值计算初值 建立迭代格式建立迭代格式 目录下页返回上页结束蹲图撑舵酚满旺阂鸽储轴嘴籍鸣禄挂乎刨漓厦眺袜嗓胯息衣坤课酋柞佣瑚数学建模简明教程数学建模简明教程解法解法2 向向后后迭代迭代 利用上面不等式计算初值利用上面不等式计算初值 建立
27、迭代格式建立迭代格式 目录下页返回上页结束基损类辞扮沪站负五邓吏吹摩耙酗挛暑库接粳运巨屠藕虽繁稠闷形搅手前数学建模简明教程数学建模简明教程严重失真严重失真目录下页返回上页结束豁垃招斩竣劈盘掳逆血始匡烬玉浮铝也绝丈讲消熄灰衣鞍痒臀宁乐销颧懊数学建模简明教程数学建模简明教程的显著性分析的显著性分析. .注注 算法的稳定性不同于建立模型过程中因素算法的稳定性不同于建立模型过程中因素小结小结 向前迭代算法是一个稳定性不好的算法向前迭代算法是一个稳定性不好的算法.的舍入误差传播到的舍入误差传播到 时增大时增大5倍，如此进行，倍，如此进行， 传播到传播到 时将增大时将增大 倍倍. 向后迭代算法是一个稳定的
28、算法向后迭代算法是一个稳定的算法.虽然初始值虽然初始值 精度不高精度不高, 但每计算一步但每计算一步,舍入误差会减小舍入误差会减小 为原来的五分之一为原来的五分之一, 取得了很好的计算效果取得了很好的计算效果.目录下页返回上页结束挪绰秤供擂坚镁旗笛绚对让四拿赡棋丈弄佬和真抹奉锚剥歇庚贰奇虽彬拢数学建模简明教程数学建模简明教程四、数值算法设计注意事项四、数值算法设计注意事项对于一个数值型算法除了其正确性（如收敛性），对于一个数值型算法除了其正确性（如收敛性）， 研究其效率（如收敛速度）研究其效率（如收敛速度）,鲁棒性（如稳定性）鲁棒性（如稳定性）是很重要的，同时程序设计或实现时如下几个是很重要的
29、，同时程序设计或实现时如下几个问题也不可忽视：问题也不可忽视： 4.1 减少计算次数减少计算次数 4.2 避免相近数相减避免相近数相减 4.3 避免大数吃小数避免大数吃小数 4.4 避免很小的数做分母，防止溢出出现避免很小的数做分母，防止溢出出现 4.5 正确使用实数相等的比较正确使用实数相等的比较 目录下页返回上页结束火默饥脾帅字隔嗡鸟因崖爹泄邓懦蜘滇削候勇哑全辛届平癌洱谨套姬荧孟数学建模简明教程数学建模简明教程 4.1 减少计算次数减少计算次数 设计算法时，好的算法能有效减少运算时间，设计算法时，好的算法能有效减少运算时间， 减小误差的积累减小误差的积累.对计算机而言，乘除法花费对计算机而
30、言，乘除法花费 机时大大多于加减法，因此数值型算法以减机时大大多于加减法，因此数值型算法以减少少乘除法运算次数为主乘除法运算次数为主. . 例例 一般多项式求值问题一般多项式求值问题秦九韶算法秦九韶算法目录下页返回上页结束傣掠达忿淄笆韦堤岳佣敷寨今膏祈洛垣尊禹虽趁崔瞩哆溜对父级纸饭纫嘲数学建模简明教程数学建模简明教程 4.2 避免相近数相减避免相近数相减 两个相近数相减会快速消减有效数字的位数两个相近数相减会快速消减有效数字的位数. 例例 和和 都有都有5位有效数字，但是位有效数字，但是 只有只有1位有效位有效数字数字.注、注、通过改变算法可以避免这种现象通过改变算法可以避免这种现象. 例例
31、已知已知解法解法1解法解法2 1位有效位有效数字数字4位有效位有效数字数字目录下页返回上页结束被泡狈篇杀淀位匪嗽瑰束倪祥肇壬粗葫柔疽沙害鹰聪箩存僻幻莫悟押箭碌数学建模简明教程数学建模简明教程一些避免相近数相减算法一些避免相近数相减算法 目录下页返回上页结束肯弃峰惨宏射尘麓痘伦僳舆懂涧幽幌萨贤套把嗅薪郑傀由沿穿议撒膝傀沈数学建模简明教程数学建模简明教程 4.3 避免大数吃小数避免大数吃小数 定义定义 在计算机做加法时，两加数的指数在计算机做加法时，两加数的指数先向大指数对齐，再将浮点部分相加，如先向大指数对齐，再将浮点部分相加，如两个数指数相差太大，就会出现小数无法两个数指数相差太大，就会出现小
32、数无法加进去的现象加进去的现象.例例 、用单精度计算用单精度计算 的根的根解法解法1 求根公式求根公式 解法解法2 根与系数关系根与系数关系错误错误目录下页返回上页结束舱蓬市嘲预仑碧平挤皿窑祸烈孕寺踊青滓州摆势豆憎步荚吱秘兢卉凯侵谜数学建模简明教程数学建模简明教程 4.4 其他注意事项其他注意事项 避免很小的数做分母，防止溢出错误避免很小的数做分母，防止溢出错误正确使用实数相等比较算法正确使用实数相等比较算法在判断两个实数是否相等时，不应写成在判断两个实数是否相等时，不应写成而是先按精度需要设定一个很小的数而是先按精度需要设定一个很小的数 ，然后判断两数差的绝对值是否小于然后判断两数差的绝对值
33、是否小于 目录下页返回上页结束恫奥摸竭阁柑英靶沦翻快晓践壕刽癌载翠糟丫附役眶逗审数柯堵俊庇停揽数学建模简明教程数学建模简明教程五、算法的评价五、算法的评价同一问题可用不同算法解决，在分析了算法的同一问题可用不同算法解决，在分析了算法的可靠性之后，就需要对其效率进行分析可靠性之后，就需要对其效率进行分析.复杂度复杂度来考虑来考虑. 一个算法的效率评价主要从一个算法的效率评价主要从时间复杂度时间复杂度和和空间空间注、注、进行算法分析和评价的目的在于选择合适进行算法分析和评价的目的在于选择合适的算法和改进算法的算法和改进算法.目录下页返回上页结束噎萍曰晴萧摘寨壬稀嗣袱陶犁荐驶潜佑细津韭击赶困栏抠五渐
34、错俐野粥诚数学建模简明教程数学建模简明教程 5.1 时间复杂度定义时间复杂度定义 某算法的时间开销某算法的时间开销理论分析理论分析大多不可行大多不可行计算机实测计算机实测可行但不必要可行但不必要比较算法时，只需要知道那种花费的时间多比较算法时，只需要知道那种花费的时间多,那种花费的时间少那种花费的时间少.并且时间花费和算法中语并且时间花费和算法中语句的执行次数成正比句的执行次数成正比.目录下页返回上页结束肩钙棵厨煽辰训德建魔篷扬聋蚜妆磊雁粪尧尧念尝朱壮已洋丁炙耘秩喷仗数学建模简明教程数学建模简明教程 5.1 时间复杂度定义时间复杂度定义 定义定义一个算法中的语句执行次数称为算法一个算法中的语句
35、执行次数称为算法时间频度是算法需要完成多少工作的度量时间频度是算法需要完成多少工作的度量. .时间频度时间频度,记为记为 ,其中其中 是问题的规模是问题的规模. . 定义定义 算法时间频度是问题规模算法时间频度是问题规模 的函数的函数 则称则称 是是 的同数量级函数，记作的同数量级函数，记作称称 为算法的为算法的渐进时间复杂度渐进时间复杂度，简称，简称 时间复杂度时间复杂度.目录下页返回上页结束卯嘲毗秘基牺胸汰温端陪坑病异消碉冰许斩迈展急津郑高唬胁诫握逞滇暇数学建模简明教程数学建模简明教程 5.2 问题的规模问题的规模 定义定义 将标识问题类中不同问题大小的参数将标识问题类中不同问题大小的参数
36、定义定义为为问题的规模问题的规模. .时所需存储空间的度量，时所需存储空间的度量，涉及到除原始数据涉及到除原始数据外所需要额外增加的存储空间外所需要额外增加的存储空间. 定义定义 空间复杂度空间复杂度是对算法在计算机内执行是对算法在计算机内执行 例例 向量向量 和和的内积的内积 解解 问题的规模为问题的规模为 ，空间复杂度为，空间复杂度为 .目录下页返回上页结束酝颅疤木感沏雾役棕梦揭嘛玩瓮彼妈盂承金菲耙瘦粮霜牧流核雌败炕踏昏数学建模简明教程数学建模简明教程 例例 时间频度随规模变化分析时间频度随规模变化分析解解 算法算法 和和 的时间复杂度都是的时间复杂度都是 ,但但渐进常数渐进常数 ，意味着
37、当问题规模意味着当问题规模 较大时，较大时， 花费的时间基本上是花费的时间基本上是 的的3/4.3/4.目录下页返回上页结束池围咸扣耗瓷庇否忧据铺您挂裴言璃晃渍采荚瘸茵予证蓬掩撵萝畴压这镶数学建模简明教程数学建模简明教程注注 按数量级递增排列的时间复杂度有按数量级递增排列的时间复杂度有:随着问题规模随着问题规模n的不断增大，上述时间复杂度的不断增大，上述时间复杂度不断增大，算法的执行效率越低不断增大，算法的执行效率越低.常数阶常数阶线性阶线性阶线性对数阶线性对数阶平方阶平方阶立方阶立方阶指数阶指数阶阶乘阶阶乘阶:目录下页返回上页结束栅涤刨纤挫甭绒餐畔怠田莆奥暮钎洒蜡责壬铭迸拟潍吧堂躺齐砖逻牟承
38、姚数学建模简明教程数学建模简明教程n102030log10n0.000 001 0秒 0.000001 3秒 0.000001 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 n，执行给定时间复杂度的算法耗时比较，执行给定时间复杂度的算法耗时比较目录下页返回上页结束番痔投椰安挚简迢涧频讲沮额菌越乙奶霓吨滔馁撩艳馅遮癣州威瘟祸阴糕数学建模简
39、明教程数学建模简明教程 5.3 时间复杂度分析时间复杂度分析 考虑算法的渐进时间复杂度，即随着问题规模考虑算法的渐进时间复杂度，即随着问题规模 的增大时间频度的变化趋势的增大时间频度的变化趋势. 注注 通常时间耗费是问题规模的单调增加函数，通常时间耗费是问题规模的单调增加函数，因而算法中的一些与问题规模无关的语句执行因而算法中的一些与问题规模无关的语句执行 时间可以不予考虑，因为该语句的频度是时间可以不予考虑，因为该语句的频度是 . . 注注 由于编译系统对循环语句中循环次数的控由于编译系统对循环语句中循环次数的控制在编译时已经计算好，分析时可以不予考虑制在编译时已经计算好，分析时可以不予考虑
40、. . 当对渐进常数的大小不关心，仅考虑其渐进阶当对渐进常数的大小不关心，仅考虑其渐进阶 数时，只需分析循环中某一个语句的执行频度数时，只需分析循环中某一个语句的执行频度. .目录下页返回上页结束膘携搪画哩骂异肯草这罢檬你勉迈它滚绒烈堪布虏旨糯呼抚匙屯济伞抑试数学建模简明教程数学建模简明教程 例例1 计算两个向量点乘积的算法复杂度计算两个向量点乘积的算法复杂度. . 向量向量 和和 输入参数输入参数: :问题规模问题规模 , 输出参数输出参数: :点积点积addadd 算法伪代码算法伪代码: :add=0；For i =1:nadd=add+x(i)*y(i)end i1nn+1全部统计的算法
41、复杂度全部统计的算法复杂度 , ,忽略循环外忽略循环外语语句的算法复杂度为句的算法复杂度为 . .目录下页返回上页结束缴旭睛烷睛体锡涎辫凹吗企脱禹红哨垮逼吟呼咬术政归脐药喻刮银碉辐闹数学建模简明教程数学建模简明教程 例例2 计算一个向量和两个矩阵乘积计算一个向量和两个矩阵乘积. . 向量向量 输入参数输入参数: :问题规模问题规模 ,矩阵矩阵 输出参数输出参数: : For i=1:n y(i)=0 z(i)=0 for j=1:n y(i)=y(i)+x(j)*a(i,j) z(i)=z(i)+x(j)*b(i,j) end j end inn 算法伪代码算法伪代码: :算法复杂度算法复杂度
42、目录下页返回上页结束老蝎藩畅户境柱踪毫掌虞褐邻麻墒侥姥君辈罪凰馅墒允遇迪哮疯垢首删溜数学建模简明教程数学建模简明教程 例例3 计算向量分量正弦值的最大值计算向量分量正弦值的最大值. . 向量向量 输入参数输入参数: :问题规模问题规模 , 输出参数输出参数: :最大值最大值maxmax 算法伪代码算法伪代码: :算法复杂度算法复杂度 max=sin(x(1) for i=2:n t=sin(x(i) if tmax max=t endif end i1n-1n-1n-13n-2目录下页返回上页结束威纤掐颧睛瓷臆铡蹋渔拣俏稼完娜过苞虞仕音鸡垫谚在歼亿零朋澜蝶喉气数学建模简明教程数学建模简明教程分
43、析并不是算法分析的全部内容分析并不是算法分析的全部内容，它仅考虑了它仅考虑了 注注 例例2 2循环结构中有两条执行语句循环结构中有两条执行语句, ,如果只考如果只考 虑一条语句虑一条语句, ,算法复杂度为算法复杂度为 , ,可见与总可见与总 时间复杂度同阶时间复杂度同阶, ,但渐进常数不同但渐进常数不同, ,说明数量级说明数量级 数量级最高项的级数量级最高项的级. 注注 例例3 3选择结构中的语句只有在判断条件成立选择结构中的语句只有在判断条件成立 的时候才被执行的时候才被执行, ,我们考虑了最坏的一种情形我们考虑了最坏的一种情形, , 即每次都会被执行即每次都会被执行, ,这样分析出来的复杂度是这样分析出来的复杂度是 该问题类的一个上界该问题类的一个上界, ,被称为被称为最坏时间复杂度最坏时间复杂度. . 目录下页返回上页结束扩饯漳尸默僚粪真猾合赵掏谜坯仙跳屁灭沙巡存顷灭徊酌脓恕沈矿排焰建数学建模简明教程数学建模简明教程再见目录下页返回上页结束胡寸碑粕颊畴阔她辆旁冤肄唇鲍示惰通诊俯兔铱四毙湖触碱满伪乘涉刺牺数学建模简明教程数学建模简明教程
