数学建模简明教程市公开课一等奖百校联赛特等奖课件.pptx
《数学建模简明教程市公开课一等奖百校联赛特等奖课件.pptx》由会员分享,可在线阅读,更多相关《数学建模简明教程市公开课一等奖百校联赛特等奖课件.pptx(53页珍藏版)》请在咨信网上搜索。
1、数学建模简明教程国家精品课程国家精品课程第1页第八章第八章 算法基础算法基础一、一、算法概念算法概念二、数值型算法结构惯用思想二、数值型算法结构惯用思想三、数值算法可靠性三、数值算法可靠性 四、数值型算法设计注意事项四、数值型算法设计注意事项 五、五、算法评价算法评价目录下页返回上页结束第2页 1.1 数学建模竞赛过程数学建模竞赛过程 1.3 算法分类算法分类 1.4 算法评价算法评价 1.2 算法概念算法概念 一、算法概念一、算法概念目录下页返回上页结束第3页 1.1 数学建模竞赛过程数学建模竞赛过程 (1)提出问题:提出问题:命题人(某个领域教授)提出命题人(某个领域教授)提出 (2)分析
2、问题:分析问题:参赛人首先读题,分析问题,依参赛人首先读题,分析问题,依(3)建立模型:建立模型:辨析问题中主要矛盾和次要矛辨析问题中主要矛盾和次要矛 (4)模型求解:模型求解:研究解存在性与惟一性,寻找研究解存在性与惟一性,寻找 目录下页返回上页结束实际问题实际问题;照自己了解准确阐述问题照自己了解准确阐述问题;间约束关系,进而得到完备数学模型;间约束关系,进而得到完备数学模型;理论、工具和方法,建立起问题中不一样量之理论、工具和方法,建立起问题中不一样量之盾,盾,并在合理假设条件下,利用各种数学并在合理假设条件下,利用各种数学求解方法,利用解对模型正确性进行评价求解方法,利用解对模型正确性
3、进行评价.第4页 1.2 算法概念算法概念 定义定义 串行串行算法算法就是求解一个问题类无二义性就是求解一个问题类无二义性定义定义 原始可改变原始可改变有限操作对象有限操作对象就是有限输入就是有限输入注注 对给定输入数据,算法运行后得到数据对给定输入数据,算法运行后得到数据有穷过程,这里过程明确无歧义描述由有限有穷过程,这里过程明确无歧义描述由有限操作(算术、逻辑、字符运算和读写操作等)及操作(算术、逻辑、字符运算和读写操作等)及有限操作对象合成按一定次序执行有限序列有限操作对象合成按一定次序执行有限序列.数据,它全部可能允许改变组成求解数据,它全部可能允许改变组成求解问题类问题类.结果也是有
4、限,结果也是有限,这么能够把算法看成有限输入这么能够把算法看成有限输入数据和有限输出结果之间对应关系数据和有限输出结果之间对应关系.目录下页返回上页结束第5页 1.3 算法分类算法分类 定义定义 依据对象不一样能够将算法分为依据对象不一样能够将算法分为数值型数值型目录下页返回上页结束算法算法和和非数值型算法非数值型算法.将以浮点算术运算为主将以浮点算术运算为主算法称为算法称为数值型算法数值型算法,非数值型算法非数值型算法普通普通包含线性表、栈、队列和串、树、图,排序、包含线性表、栈、队列和串、树、图,排序、查找等数据处理方面算法查找等数据处理方面算法.第6页 1.4 算法评价算法评价 优劣优劣
5、才是有价值才是有价值.(1)算法可靠性评价算法可靠性评价 数值型算法:数值型算法:收敛性、稳定性、误差预计;收敛性、稳定性、误差预计;非数值型算法:强调对于整体问题类算法非数值型算法:强调对于整体问题类算法计算结果正确性计算结果正确性.(2)算法优劣评价算法优劣评价时间复杂度,空间复杂度,逻辑复杂度时间复杂度,空间复杂度,逻辑复杂度.注注 算法在确保可靠大前提下再评价其算法在确保可靠大前提下再评价其目录下页返回上页结束第7页二、结构数值型算法惯用思想二、结构数值型算法惯用思想了解数值型算法结构惯用基本思想,有利于了解数值型算法结构惯用基本思想,有利于针对自己研究详细问题提出有效可靠算法针对自己
6、研究详细问题提出有效可靠算法.2.1 迭代思想迭代思想 2.2 直与曲思想直与曲思想 2.3 分段处理思想分段处理思想 2.4 修正思想修正思想 2.5 组合思想组合思想 2.6 自适应思想自适应思想 惯用基本思想:惯用基本思想:目录下页返回上页结束第8页 2.1 迭代思想迭代思想 非线性方程非线性方程 等价变形等价变形迭代格式迭代格式 产生迭代序列产生迭代序列假如假如则能够得到方程解则能够得到方程解.线性方程组线性方程组等价变形等价变形迭代格式迭代格式产生迭代向量序列产生迭代向量序列假如假如则可得到方程组解则可得到方程组解.目录下页返回上页结束第9页 2.2 直与曲思想直与曲思想 大多数曲线
7、就一小范围来看大致能够看成是大多数曲线就一小范围来看大致能够看成是直线直线.非线性方程非线性方程 根可视为函数根可视为函数 与与 轴交点轴交点.在交点附近能够用在交点附近能够用 直线代替曲线直线代替曲线 ,对应地用直线与,对应地用直线与 x*Oyx 轴交点轴交点 代替曲线与代替曲线与 轴交点轴交点 .牛顿迭代法牛顿迭代法目录下页返回上页结束第10页例例 求解常微分方程初值问题求解常微分方程初值问题欧拉折线法欧拉折线法 经典以折线段近似曲线经典以折线段近似曲线.xyy(x)xnxn+1PnPn+1目录下页返回上页结束第11页 2.3 分段处理思想分段处理思想 已知一组采样点已知一组采样点 值,求
8、非采样点处值,求非采样点处 函数值一个方法就是插值法函数值一个方法就是插值法.当当 较大时较大时,假如直接采取高次插值假如直接采取高次插值一是计算量大一是计算量大;二是高次插值不确保收敛,也不稳定二是高次插值不确保收敛,也不稳定.采取采取分段处理思想分段处理思想就能很好处理该问题就能很好处理该问题,即采取分段低次插值,既能确保稳定,又即采取分段低次插值,既能确保稳定,又收敛,计算量还小收敛,计算量还小.目录下页返回上页结束第12页 2.4 修正思想修正思想 记记 为线性方程组为线性方程组 一个近似,普通一个近似,普通说来残差说来残差 不等于零向量,对之不等于零向量,对之 进行修正得到更加好近似
9、进行修正得到更加好近似 式中矩式中矩阵阵是由是由对对角元素角元素组组成矩成矩阵阵 逐一超松弛逐一超松弛迭代法迭代法注注 此方法采取就是给粗糙解向量一个此方法采取就是给粗糙解向量一个修正量修正量,以得到更加好解近似以得到更加好解近似.目录下页返回上页结束第13页 2.5 组合思想组合思想 对精度较低解近似进行组合,以期望得到对精度较低解近似进行组合,以期望得到近似精度高解近似近似精度高解近似.例例 龙贝格求积算法龙贝格求积算法.计算积分计算积分 将区间将区间 等分等分 个子个子区间区间,采取复化梯形公式得到近似值为采取复化梯形公式得到近似值为目录下页返回上页结束第14页 2.6 自适应思想自适应
10、思想 自适应在算法结构中是非常主要思想,它在自适应在算法结构中是非常主要思想,它在结构算法时也同时兼顾了局部特征结构算法时也同时兼顾了局部特征.小小步长,改变平坦地方,步长较大一些步长,改变平坦地方,步长较大一些.例例 当使用复化梯形公式计算积分时,在函数当使用复化梯形公式计算积分时,在函数值改变较大地方使用较多节点,即使用较值改变较大地方使用较多节点,即使用较xyxyf(x)f(x)自适应自适应非自适应非自适应目录下页返回上页结束第15页三、数值算法可靠性三、数值算法可靠性 本节介绍算法可靠性三个方面:本节介绍算法可靠性三个方面:(1)算法收敛性算法收敛性:研究当运行时间趋于无限研究当运行时
11、间趋于无限长时,算法解是否趋于真实解,即截断长时,算法解是否趋于真实解,即截断误差是否趋于零误差是否趋于零.(2)算法稳定性算法稳定性:就是当原始数据有小误就是当原始数据有小误差时,算法计算出结果是否也有小扰动,差时,算法计算出结果是否也有小扰动,而不是很大改变而不是很大改变.(3)误差预计误差预计:其其用途是设计循环终止条件,用途是设计循环终止条件,让数值解满足给定精度要求让数值解满足给定精度要求.目录下页返回上页结束第16页 3.1 近似解序列收敛性近似解序列收敛性 迭代迭代是结构数值问题算法基本思想之一,是结构数值问题算法基本思想之一,迭代得到问题解一个近似序列迭代得到问题解一个近似序列
12、 ,假如假如 ,且,且 就是原问题解,就是原问题解,则称该迭代算法收敛到问题解则称该迭代算法收敛到问题解.多变量问题迭代算法,产生近似解序列多变量问题迭代算法,产生近似解序列是向量序列是向量序列 ,目录下页返回上页结束第17页 3.1.1 向量序列收敛定义向量序列收敛定义 定义定义 如存在向量如存在向量 使向量序使向量序列列 各分量组成数列收敛到向量各分量组成数列收敛到向量对应分量,即对应分量,即 称称向量序列向量序列 收敛到向量收敛到向量 .注注 上述收敛被称为按分量收敛,此定义即使上述收敛被称为按分量收敛,此定义即使直观,但不便于理论分析,所以引入向量按范直观,但不便于理论分析,所以引入向
13、量按范数收敛定义数收敛定义.目录下页返回上页结束第18页 3.1.2 范数概念范数概念 定义定义 定义在定义在 上实值函数上实值函数 ,假如满足,假如满足1)非负性,即非负性,即2)齐次性,即齐次性,即3)三角不等式,即三角不等式,即则称函数则称函数 是该向量空间上一个是该向量空间上一个范数范数.注注 范数概念是对距离一个抽象和推广范数概念是对距离一个抽象和推广.目录下页返回上页结束第19页 3.1.3 惯用向量范数惯用向量范数 对于向量对于向量 ,惯用范数有,惯用范数有 例例 计算向量计算向量 各种范数各种范数 解解目录下页返回上页结束第20页 3.1.4 惯用矩阵范数惯用矩阵范数 定义定义
14、 对于矩阵对于矩阵A,惯用范数有,惯用范数有 行和范数行和范数列和范数列和范数谱范数谱范数目录下页返回上页结束第21页 3.1.5 等价性定理、收敛阶等价性定理、收敛阶 定理定理 向量序列向量序列 收敛到向量收敛到向量 充分必要条件是存在某种向量范数充分必要条件是存在某种向量范数 使得使得 定义定义 对于收敛向量序列,假如满足对于收敛向量序列,假如满足 这里这里c为为收敛常数收敛常数,称该向量,称该向量p阶收敛阶收敛.按范数收敛按范数收敛目录下页返回上页结束第22页 3.1.5 收敛速度收敛速度 小结小结 收敛阶用来刻画和比较收敛速度快慢收敛阶用来刻画和比较收敛速度快慢p越大收敛速度越快越大收
15、敛速度越快.当当p1时称为线性收敛;时称为线性收敛;当当p大于大于1 1时称为超线性收敛;时称为超线性收敛;当当p2时为平方收敛(二次收敛);时为平方收敛(二次收敛);收敛阶相同算法说明收敛速度快慢基本相当,收敛阶相同算法说明收敛速度快慢基本相当,更深入比较需考查收敛常数更深入比较需考查收敛常数c,c小收敛小收敛 速度更加快一点速度更加快一点.目录下页返回上页结束第23页例例 比较以下数列收敛速度比较以下数列收敛速度解解 三个数列都会收敛到三个数列都会收敛到 0,但速度不一样但速度不一样目录下页返回上页结束第24页线形收敛线形收敛,而而 二次收敛二次收敛,所以所以 收敛最快收敛最快,比比 收敛
16、常数小收敛常数小,所以收敛稍快所以收敛稍快.目录下页返回上页结束第25页 我们知道,通常给算法提供输入数据会有我们知道,通常给算法提供输入数据会有误差,计算机在运算过程中还会有新误差误差,计算机在运算过程中还会有新误差产生产生.需要回答一个问题是:需要回答一个问题是:当原始数据有小误差时,算法计算出当原始数据有小误差时,算法计算出 结果是否也是有小扰动,而不是大改变结果是否也是有小扰动,而不是大改变.这就是算法这就是算法稳定性问题稳定性问题.3.2 误差和数值算法稳定性误差和数值算法稳定性 目录下页返回上页结束第26页 3.2.1 误差产生误差产生 模型误差;模型误差;模型建立时因舍去次要矛盾
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数学 建模 简明 教程 公开 一等奖 联赛 特等奖 课件
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【快乐****生活】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【快乐****生活】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。