第一章概论2误差与算法稳定性问题

1、 2 误差与算法稳定性问题教学目标：使学生理解误差分析及设计稳定算法的重要性.教学重点：绝对误差，相对误差及有效数字.教学难点：误差与有效数字之间的关系，算法稳定性.教学内容：一误差解决自然科学或工程中的实际问题时通常先建立其数学模型，再应用某种算法在计算机上求出模型的数值结果，而这个结果与原问题的准确解之间就存在着所谓的误差.1误差的来源（1） 模型误差：用数学模型来描述实际问题时, 要”简单化, 理想化”例1. 用来描述物体物体自由下落时距离与时间的关系.设自由落体在时的实际下落距离为，则就是模型误差.（2） 观测误差：观测数据受工具、方法、主观因素及外界干扰带来的误差.（3） 截断误差：

2、在解决实际问题时，数学模型常常难于求解，往往要近似代替，近似解与精确解之间的误差称为截断误差，又称方法误差.例2. 求时，可将其展成级数，在实际计算时，我们只取前面有限项作为的值，这样产生的误差就是截断误差.（4） 舍入误差：计算机的数系内只有有限的一部分实数，余下的绝大多数的实数必须按一定的舍入规则（如四舍五入或直接截断）近似地表示为机器浮点数，这种近似引起地误差即是舍入误差.规格化浮点数：其中：浮点数系的基（常用2，8，16）； ：十进制整数，范围； ：定位部分；：浮点数的小数部分或尾数，；：字长.2误差的衡量（1） 绝对误差（简称误差） 设 是真值的一个近似值，则称为对的绝对误差，记为.

3、若，则称为的绝对误差限.常用记法：，表示.（2）相对误差 设是真值的一个近似值，则称为对的相对误差，记为.若，则称为的相对误差限.注：由于精确值一般不知道，常用代替.例3.有真值，误差；真值，误差.误差：后者是前者的2000倍；相对误差：前者，后者.故后者近似程度更好.3有效数字定义 设是真值的一个近似值，若其绝对误差限不超过其某位数字所在位置的半个单位，则从该数字开始到最左端第一个非零数字都称为的有效数字.注：设，若则有位有效数字.例4. 真值，近似值，求的有效数字.解 ，故有三位有效数字9，8，6.注：若是真值用通常四舍五入的办法得到的近似值，则从被保留的最后一位到最左边非零数字之间的所有

4、数字都是有效数字.引例：和都是经四舍五入得到的8的近似值，但它们的意义不同.4有效数字与（相对）误差的关系定理1设的近似值有位有效数字，则.证 .定理2 设，若，则至少有位有效数字.证 并且故至少有位有效数字.二算法稳定性1. 问题的状态：若数据的微小误差导致计算结果的大误差，那么问题对数据的微小误差反应敏感，此时我们说问题是病态的；反之，若微小的数据变化只引起计算结果的小变化.我们说该问题是良态的.（本书主要研究良态问题）2. 算法的稳定性：在设计或选择算法时，若可以尽可能的减少误差与误差积累传播，即能控制舍入误差的影响，我们称算法是稳定的，否则便是不稳定的.3. 在近似计算中需注意的一些现象（提高算法稳定性）（1）避免相近二数相减例5.各有五位有效数字，而只剩一位有效数字.几种避免技巧：i）ii）iii）当时，.（2）避免小分母.分母小会造成浮点溢出.注：避免绝对值很大的数作乘数.（3）避免大数吃小数.例6.设，求.若按顺序计算，而有效数字为十位以下，则作时，“吃掉了”；但按计算结果为10，保护了.避免方法：i） 求和时注意数的顺序的调整ii） 求和时按绝对值从小到大可使和的误差减小.（4）注意计算步骤的简化，减少计算次数，避免误差积累一般来说，计算机处理下列运算的速度为.例7.计算多项式的值（给定）解 若直接计算，在计算第项时，需次乘法.因此共