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

1§2误差与算法稳定性问题教学目标：使学生理解误差分析及设计稳定算法的重要性.教学重点：绝对误差，相对误差及有效数字.教学难点：误差与有效数字之间的关系，算法稳定性.教学内容：一．误差解决自然科学或工程中的实际问题时通常先建立其数学模型，再应用某种算法在计算机上求出模型的数值结果，而这个结果与原问题的准确解之间就存在着所谓的误差.1．误差的来源（1）模型误差：用数学模型来描述实际问题时,要”简单化,理想化”例1.用21()2stgt来描述物体物体自由下落时距离与时间的关系.设自由落体在t时的实际下落距离为ts，则()tsst就是模型误差.（2）观测误差：观测数据受工具、方法、主观因素及外界干扰带来的误差.（3）截断误差：在解决实际问题时，数学模型常常难于求解，往往要近似代替，近似解与精确解之间的误差称为截断误差，又称方法误差.例2.求xe时，可将其展成级数212!!nxxxexn，在实际计算时，我们只取前面有限项2()12!!nnxxSxxn作为xe的值，这样产生的误差1()(0,)(1)!nneRxxxn就是截断误差.2（4）舍入误差：计算机的数系(,,,)FtmM内只有有限的一部分实数，余下的绝大多数的实数必须按一定的舍入规则（如四舍五入或直接截断）近似地表示为机器浮点数，这种近似引起地误差即是舍入误差.规格化浮点数：120.ctxddd其中：浮点数系的基（常用2，8，16）；c：十进制整数，范围mcM；c：定位部分；120.tddd：浮点数的小数部分或尾数，0,1idit；t：字长.2．误差的衡量（1）绝对误差（简称误差）设cx是真值x的一个近似值，则称cxx为cx对x的绝对误差，记为()cexxx.若|()|ex，则称为cx的绝对误差限.常用记法：cxx，表示ccxxx.（2）相对误差设cx是真值x的一个近似值，则称()(0)cxxexxxx为cx对x的相对误差，记为()rex.若|()|rex，则称为cx的相对误差限.注：由于精确值x一般不知道，常用()()rccexexx代替()rex.例3.有真值15000x，误差1()50ex；真值15210x，误差52()10ex.误差：后者是前者的2000倍；相对误差：前者210，后者1010.故后者近似程度更好.33．有效数字定义设cx是真值x的一个近似值，若其绝对误差限不超过其某位数字所在位置的半个单位，则从该数字开始到cx最左端第一个非零数字都称为cx的有效数字.注：设1210.10(0)mcnxaaaa，若1||10,2mncxx则cx有n位有效数字.例4.真值0.98632x，近似值0.9864cx，求cx的有效数字.解3||0.000080.510cxx，故有三位有效数字9，8，6.注：若cx是真值x用通常四舍五入的办法得到的近似值，则从被保留的最后一位到cx最左边非零数字之间的所有数字都是有效数字.引例：8.000和8.0000都是经四舍五入得到的8的近似值，但它们的意义不同.4．有效数字与（相对）误差的关系定理1设x的近似值1210.10(0)mcnxaaaa有n位有效数字，则111|()|102nrcexa.证1|()|1|()|,|()|10,0.102mnmrcccexexexxax111|()|102nrcexa.定理2设1210.10(0)mcnxaaaa，若111|()|102(1)nrcexa，则cx至少有n位有效数字.4证111|||||()|||10,2(1)nccrccxxxexxa并且111(0.0.1)10(1)10mmcxaa111111||(1)101010,2(1)2mnmncxxaa故cx至少有n位有效数字.二．算法稳定性1.问题的状态：若数据的微小误差导致计算结果的大误差，那么问题对数据的微小误差反应敏感，此时我们说问题是病态的；反之，若微小的数据变化只引起计算结果的小变化.我们说该问题是良态的.（本书主要研究良态问题）2.算法的稳定性：在设计或选择算法时，若可以尽可能的减少误差与误差积累传播，即能控制舍入误差的影响，我们称算法是稳定的，否则便是不稳定的.3.在近似计算中需注意的一些现象（提高算法稳定性）（1）避免相近二数相减例5.120.12345,0.12346aa各有五位有效数字，而120.00001aa只剩一位有效数字.几种避免技巧：i）xxxxii）ln()ln()ln(1)xxxiii）当||1x时，221cos2sin2111(1)26xxxexxx.（2）避免小分母.分母小会造成浮点溢出.注：避免绝对值很大的数作乘数.（3）避免大数吃小数.5例6.设101010,10,10abc，求abc.若按顺序()abc计算，而有效数字为十位以下，则作()ab时，a“吃掉了”b；但按()acb计算结果为10，保护了b.避免方法：i）求和时注意数的顺序的调整ii）求和时按绝对值从小到大可使和的误差减小.（4）注意计算步骤的简化，减少计算次数，避免误差积累一般来说，计算机处理下列运算的速度为,,^.例7.计算多项式01()nnpxaaxax的值（x给定）解若直接计算，在计算第k项kkax时，需k次乘法.因此共需(1)2nn次乘法和n次加法.但若改成下面形式12310()(((())))nnnnpxxxxxaxaaaaa，则只需n次乘法和n次加法即可得到函数值.（秦九韶算法）（5）选用数值稳定的算法：计算过程中舍入误差对计算结果影响不大的算法.