《数值分析知识内容 (4).pdf》由会员分享，可在线阅读，更多相关《数值分析知识内容 (4).pdf（6页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1.3 误差定性分析与避免误差危害 数值运算中的误差分析是个很重要而复杂的问题，上节讨论了不精确数据运算结果的误差限，它只适用于简单情形，然而一个工程或科学计算问题往往要运算千万次，由于每步运算都有误差，如果每步都做误差分析是不可能的，也不科学.采用有效的方法对误差做出定量估计是很难的.为了确保数值计算结果的正确性，首先需对数值计算问题做定性分析，为此本节讨论以下三个问题.1.3.1 算法的数值稳定性 用一个算法进行计算，由于初始数据误差（由舍入误差造成的）在计算中传播使计算结果误差增长很快，则称该算法是数值不稳定的，否则是数值稳定的.例 7 计算积分108,1,0,10ndxxxEnn.解：
2、由 ndxxdxxxxEEnnnnn11010101011011,可得两个递推算法.算法 1：8,2,1,1011nEnEnn.算法 2：1,7,8),1(1011nEnEnn.利用 MATLAB 的库函数 quadl 计算数值积分，得到算法 1 的初始值 E0=0.095310179,算法 2 的初始值 E8=0.010194390.利用 MATLAB 程序递推计算，结果见表 1-1.表 1-1 两算法计算值与精确值比较 算法1的MATLAB计算程序如下：E0=0.09531;%算法1的初始值 E(1)=1-10*E0;for n=2:8 E(n)=1/n-10*E(n-1);%递推计算 e
3、nd E%利用MATLAB的quadl计算积分值E8 E8=quadl(x.8./(x+10),0,1)算法 2 的计算程序省略.由表 1-1 可知，算法 1 是不稳定的，算法 2 是稳定的.n nE(算法 1)nE(算法 2)*nE(精确值)0 0.09531 0.0953 0.09531018 1 0.0469 0.0469 0.04689820 2 0.0310 0.0310 0.03101798 3 0.0233 0.0232 0.02315353 4 0.0167 0.0185 0.01846471 5 0.0333 0.0154 0.01535290 6-0.1667 0.0131
4、 0.01313766 7 1.8095 0.0115 0.01148056 8-17.9702 0.0102 0.01019439 由于串行运算的舍入误差是逐步传递的，所以可用“向后误差”分析方法，即把舍入误差的影响看成是初值误差即输入数据误差的传播.因此，有下述定义.【定义 4】对于某个算法，若输入数据的误差在计算过程中迅速增长而得不到控制，则称该算法是数值不稳定的（Unstable Algorithm），否则是数值稳定的（Stable Algorithm）.对于例 7，当仅考虑初始值有误差时，对于算法 1，由 1*1*101,101nnnnEnEEnE，可知误差nnnEE*满足：,2,1
5、,)10(1001nnnn，因此算法 1 是不稳定的.对于算法 2，同理可知误差iiiEE*满足：1,1,1011nniii，所以nn1010，因此算法 2 是稳定的.蝴蝶效应：什么是蝴蝶效应（Butterfly Effect）？先从美国麻省理工学院气象学家爱德华洛伦兹（Lorenz，混沌学创始人）的发现谈起.1961 年冬天，为了预报天气，洛伦兹用计算机求解仿真地球大气的 13 个方程式.为了更细致地考察结果，他把一个中间解取出，提高精度再送回.而当他喝了杯咖啡以后回来再看时竟大吃一惊：本来很小的差异，结果却偏离了十万八千里！计算机没有毛病，于是，洛伦兹认定，他发现了新的现象：“对初始值的极
6、端不稳定性”.这个发现非同小可，以致科学家都不理解，几家科学杂志也都拒登他的文章，认为“违背常理”：相近的初值代入确定的方程，结果也应相近才对，怎么能大大远离呢！差之毫厘，谬以千里.18 年后，洛伦兹在华盛顿的美国科学促进会的一次讲演中提出：在大气运动过程中，即使各种误差和不确定性很小，也有可能在过程中将结果积累起来，经过逐级放大，形成巨大的大气运动.接着，他举出了一个后来闻名于世的例子：一只蝴蝶在巴西扇动翅膀，有可能会在美国的德克萨斯引起一场龙卷风.他的演讲和结论给人们留下了极其深刻的印象.从此以后，所谓“蝴蝶效应”之说就不胫而走，名声远扬了.1.3.2 病态数学问题与条件数 上面讨论的数值
7、稳定性是对算法而言的，这里的病态则是数学问题即数学模型本身的性质，与算法无关.所谓病态数学问题是指这样的问题：当输入数据（如参数、初始值等）有微小摄动时，会引起解的大扰动；相反的问题为良态数学问题.因为实现算法时总有舍入误差，所以对于病态的数学问题，用任何算法求数值解都是不稳定的.但是，良态数学问题的算法未必是数值稳定的.病态和良态是相对的，界线比较模糊，病态越严重，对算法稳定性的影响越大.通常用条件数(Condition Number)来衡量问题的病态程度，条件数越大病态可能越严重.不同的数学问题条件数的定义是不同的，例如线性代数方程组的条件数定义可参见第 3 章.这里举一个简单的例子.例
8、8 函数求值问题)(xfy 的条件数定义为：)()()()(xfxf xxfcondxC.这是因为 axfcondxaxxfxf xxfaxxfxfafxfafrr)()()()()()()()()(，若取对数函数)ln(xy，则其条件数为)ln(/1)(xxC，它的值与x有关.如 5.100)01.1(,5.99)99.0(,95.0)9.0(,43.0)1.0(CCCC，22.0)100(,43.0)10(CC，可见，x越接近 1，条件数越大，从而求对数函数值的相对误差越大.1.3.3 避免误差危害的若干原则 数值计算中首先要分清问题是否病态和算法是否数值稳定，计算时还应尽量避免误差危害，
9、防止有效数字的损失，下面给出若干原则.一、避免两相近的数相减 在数值计算中两相近数相减有效数字会严重损失.例 9 计算2cos1（用四位函数表示三角函数值）.0006.09994.012cos1，具有四位有效数字的近似数 0.9994，经过运算，只有一位有效数字.这说明必须尽量避免出现这类运算.最好是改变计算方法，防止这种现象产生.对于上式，若利用三角恒等式2sin2cos12xx 进行公式变换，则 000613.01sin22cos12 具有三位有效数字.也可将xcos展开成泰勒（Taylor）级数后，按!4!2cos142xxx 来进行计算.这两种算法都避开了两个相近数相减的不利情况.又如
10、，当x很大时，xxxx111，用右边算式代替左端，可减少有效数字的损失.如果无法改变算式，则采用增加有效位数进行运算；在计算机上则采用双倍字长的高精度运算.二、注意简化计算步骤，减少运算次数 同样一个计算问题，如果能减少运算次数，不但可节省计算机的计算时间，还能减少舍入误差.这是数值计算必须遵从的原则，也是“数值分析”要研究的重要内容.例 10 计算多项式0111)(axaxaxaxPnnnnn的值.若直接计算kkxa再逐项相加，一共需做 2)1(12)1(nnnn 次乘法和n次加法.若采用秦九韶算法 011)()(axaxaxaxPnnn，只要n次乘法和n次加法就可算出)(xPn的值.思考：
11、秦九韶算法为什么减少了运算次数？避免了重复计算.对于4次代数多项式15642)(234xxxxxP，计算2x时的多项式值)2(P.秦九韶算法的MATLAB计算程序如下：a=-1 5-6 4 2;%4次多项式的系数 x=2;n=length(a);P=a(n);for k=n-1:-1:1 P=P*x+a(k);%秦九韶算法的递推计算 end P%输出多项式的值 MATLAB内嵌多项式值的计算函数为polyval，下面数组a的元素为多项式的系数，由高次幂至低次幂排列.利用MATLAB函数计算多项式值：a=2 4-6 5-1;P=polyval(a,2)秦九韶算法：秦九韶算法是我国宋代的一位数学家
12、秦九韶提出的.国外文献通常称这种算法为霍纳（Horner）算法，其实 Horner 的工作比秦九韶晚了五个多世纪.秦九韶（1202-1261），字道古，四川安岳人，我国南宋数学家，1247 年写成数学九章.霍纳（W.G.Horner，1789-1837），英国人.例 11 用克莱姆（Cramer）法则求解线性方程组 Ax=b.用克莱姆法则求解 n 阶线性方程组，当 n=20 时，需要计算 21 个 20 阶行列式.按行列式定义计算，每个行列式需要计算（20-1)20！次乘法，如果加减法的计算次数忽略不计，则总的计算量约为 211920！.假设计算机每秒可作 1 亿次乘除法运算，则求解这样一个线
13、性方程组需用的时间是多少？利用 Matlab 程序解算如下：n=1:20;zjl=21*19*prod(n);%总计算量 ms=zjl/100000000;%占用CPU的时间（秒）ns=ms/60/60/24/365%转换为年数 程序运行，得到需用的时间约为 307816 年.天啊，30 多万年的时间！如果改用第3章的高斯（Gauss）消元法只需2千多次乘除运算，并且n越大两种算法的计算量差别越大.这说明当我们把一个数学模型转化为计算机程序时，对算法的研究是十分重要的.【注】一个算法的计算代价也就是完成计算需要支付的金额.算法由算术运算组成，用计算机来实现.计算机计费的主要依据有两项：一是使用
14、中央处理器（CPU）的时间，主要由算术运算的次数决定；二是占用存储器的空间，主要由使用数据的数量决定.算法的计算代价称为算法的复杂度，其中，算法的计算量称为时间复杂度；算法需占用存储空间的量度称为空间复杂度.三、要避免用绝对值很小的数除数 用绝对值很小的数作除数，舍入误差会增大，甚至会在计算机中造成“溢出”错误.如计算yx，若xy 0，则可能对计算结果带来严重影响，使数值不稳定，应尽量避免.又如，计算xx11，当0 x时，分母的绝对值很小，此算法是数值不稳定的.四、两数相加要防止大数“吃”掉小数 在数值运算中参加运算的数有时数量级相差很大，而计算机位数有限，如不注意运算次序就可能出现大数“吃掉
15、”小数的现象，影响计算结果的可靠性.例如，在五位十进制计算机上，计算 12346+0.1-12345.将运算的数写成规格化形式，在计算机内运算时要对阶，因此 12346+0.6+0.6-12345=0.12346105+0.000006105+0.000006105-0.12345105=0.12346105-0.12345105=1 结果显然不可靠，这是由于运算中出现了大数 12346“吃掉”小数 0.6 造成的.因此，应合理安排运算顺序，防止参与运算的数在数量级相差悬殊时，大数“淹没”小数的现象发生.多个数相加时，最好从其中绝对值最小的数到绝对值最大的数依次相加；多个数相乘时，最好从其中有效位数最多的数到有效位数最少的数依次相乘.