




kok电子竞技权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
kok电子竞技:文档简介
1、数学学院 信息与计算科学系 第三节第三节 设计算法时应注意的原则设计算法时应注意的原则 一、简化计算步骤一、简化计算步骤, 减少运算次数减少运算次数 计算多项式的值计算多项式的值: 0 ( ) n k nk k Pxa x 每项每项 ak xk 有有k 次乘法运算次乘法运算, 因此计算因此计算 Pn (x) 共需共需 1 1 2 2 n n n 次乘法和次乘法和n 次加法运算。次加法运算。 如将如将 Pn (x) 写成写成: 1210nnnn Pxa xaxaxaxa 例例1 数学学院 信息与计算科学系 用递推算法用递推算法: 01 , , 1,2, . nkkn k uauuxakn 最终最
2、终 Pn (x)=un 共需共需n 次乘法和次乘法和n 次加法运算。次加法运算。 一般地要注意一般地要注意: 能在循环外计算能在循环外计算, 就不要放在循环就不要放在循环 内计算。内计算。 1210nnnn Pxa xaxaxaxa 数学学院 信息与计算科学系 二、二、 注意避免两个相近数的相减注意避免两个相近数的相减 如用四位有效数字计算如用四位有效数字计算: 例例2 17013 13.04 13 0.04 结果只有一位有效数字;结果只有一位有效数字; 两个相近的数相减两个相近的数相减, 有效数字会大大损失。有效数字会大大损失。 170130.0384048 如改为:如改为: 11 1701
3、30.03840 13.041317013 有四位有效数字有四位有效数字, 新算法避免了两个相近数的相减。新算法避免了两个相近数的相减。 数学学院 信息与计算科学系 三、防止大数三、防止大数 “吃掉吃掉” 小数小数 例例3 解解 用五位十进制计算机进行计算用五位十进制计算机进行计算: 0.1被大数被大数“吃掉吃掉”了了,从而从而 有有 1000 1 524920.152492 i 55 5 524920.10.52492 100.000001 10 0.52492 10 1000 1 524920.1 i 计算计算 数学学院 信息与计算科学系 如改为如改为 0.1 就没有被吃掉。就没有被吃掉。
4、 这也是构造算法时要注意的问题这也是构造算法时要注意的问题, 避免重要的参数避免重要的参数 被吃掉。被吃掉。 1000 1 0.15249210052492 i 55 5 0.01 100.52492 10 0.52502 1052505 1000 1 524920.1 i 数学学院 信息与计算科学系 四、避免除数的绝对值远小于被除数的绝对值四、避免除数的绝对值远小于被除数的绝对值 当当| x | y | 时时, 舍入误差会扩大舍入误差会扩大 例例4 73 11 2 14 100.510 1 510 10 xx x x 很小的数作除数有时还会造成计算机的溢出而停机。很小的数作除数有时还会造成计
5、算机的溢出而停机。 3 0.510 的舍入误差均为的舍入误差均为 , 而而 的舍入误差为的舍入误差为:,则则 7 10 xy y x 2 )()()(yxyyxyx yx , 数学学院 信息与计算科学系 五、使用数值稳定的算法五、使用数值稳定的算法 用分部积分公式得递推用分部积分公式得递推 公式公式: 例例5 1 1 0 ,0,1,2, nx n Ix edxn In=1-nIn-1 , 在运算过程中在运算过程中,舍入误差能控制在某个范围内的算法舍入误差能控制在某个范围内的算法 称为称为数值稳定的算法数值稳定的算法,否则就称为否则就称为不稳定的算法不稳定的算法. 用四位有效数字计算用四位有效数
6、字计算: 近似值近似值 的递推公式的递推公式: n I ,1 1 nn nII 误差误差 的递推公式的递推公式:)( n Ie , )()( 1 nn IneIe 0 1 1 0 1 0 6321. 0 1 I edxeI x 数学学院 信息与计算科学系 算法算法 一一 代入得下表代入得下表 1 1 0 ,0,1,2, nx n Ix edxn 于是于是 与精确值已经面目全非。与精确值已经面目全非。 87 ,II 0 1 0 6321. 01IeI 5 6 7 8 9 n 0.1408 0.1120 0.2180 -0.7280 7.5520 0.14553 0.12680 0.11238 0
7、.10093 0.09161 0.6321 0.3678 0.2642 0.2074 0.1704 0.63212 0.36787 0.26424 0.20727 0.17089 0 1 2 3 4 近似值近似值 精确值精确值 In 近似值近似值精确值精确值 In n n I n I ,1 1 nn nII 数学学院 信息与计算科学系 4 0 105 . 0)( Ie 算法一算法一 )()( 1 nn IneIe 由于计算由于计算 有误差有误差 0 I 0 1 0 6321. 01IeI 不计中间再产生的舍入误差不计中间再产生的舍入误差 )(!)( 0 IenIe n 40320!8)( 8
8、Ie 到到 I8 时时 误差扩大了误差扩大了4万倍万倍, 因而该算法是不稳定的。因而该算法是不稳定的。 ,1 1 nn nII 数学学院 信息与计算科学系 可以估计出可以估计出 故故 1 1 0 11 n e I nn 1 1 0 ,0,1,2, nx n Ix edxn 算法二算法二 误差误差 nIeIe nn )()( 1 1111. 0409. 01250. 04046. 0 87 II nII nn )1( 1 则则 如果递推式改为如果递推式改为 In-1 =(1-In )/n 数学学院 信息与计算科学系 由由 列表如下列表如下,)1(,1000. 0 19 nIII nn 4 3 2
9、 1 0 n 0.1709 0.2073 0.2642 0.3679 0.6321 0.17089 0.20272 0.26424 0.36787 0.63212 0.1000 0.1000 0.1125 0.1268 0.1455 0.09161 0.10093 0.11238 0.12680 0.14553 9 8 7 6 5 近似值近似值精确值精确值 In 近似值近似值精确值精确值 In n n I n I 数学学院 信息与计算科学系 11 9!362880 故该算法是稳定的。故该算法是稳定的。 若计算若计算 I9 有误差有误差 , 由由 其传播到其传播到 引起引起 的误差仅为的误差仅为 0 I ,)()( 11 nIeIe nn
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
kok电子竞技:最新文档
- 2025至2030年中国烧结真空炉数据监测研究kok电子竞技
- 社区养老服务的多维度创新实践kok电子竞技
- 2025年光电测沙仪项目合作计划书
- 科技赋能下的班级文化建设新模式
- 轻质碳酸钠企业ESG实践与创新战略研究kok电子竞技
- 家具塑料企业县域市场拓展与下沉战略研究kok电子竞技
- 防锈油脂企业县域市场拓展与下沉战略研究kok电子竞技
- 电子工厂的电路板质量检测与评估
- 高纯气体及特种试剂企业ESG实践与创新战略研究kok电子竞技
- 非金属矿企业ESG实践与创新战略研究kok电子竞技
- 2024kok电子竞技合同范本之711便利店加盟合同
- 2022电力监控系统网络安全监测装置说明书
- 公路工程标准施工招标文件(2018年kok电子竞技)
- 义务教育kok电子竞技(2024)五kok电子竞技 信息科技 《第3课 游戏体验寻规律》教学设计
- 近三年投标没有发生过重大质量安全事故的书面声明范文
- 《工程热力学》(第四kok电子竞技)全册配套完整课件
- 2024时事政治考试题库(100题)
- 2024年司法考试真题及答案
- 胆总管切开取石T管引流术护理查房参考课件
- YYT 1814-2022 外科植入物 合成不可吸收补片 疝修补补片
- 工程机械设备综合保险
评论
0/150
提交评论