DOCX《第一章》

8 页例 4) 内容提要 误差 误差分析与数值稳定性 数值计算中算法设计的技术 数学软件(略) 误差分析方法 算法的数值稳定性 病态问题与条件数 避免误差危害 误差分析 误差分析 数值计算中的误差分析很重要,但也很复杂 在计算过程中,误差会传播、积累、对消 对每一步运算都做误差分析比较不切实际 (运算次数通常都在千万次以上) 定量分析工作量大,都到的误差界往往不太实用. 目前在数值计算中更关注的是误差的定性分析 误差分析 定性分析 定性分析包括研究数值问题的适定性,数值问题与原问题 的相容性,数值算法的稳定性,避免扩大误差的准则等 定性分析的核心是原始数据的误差和计算中产生的误差对 最终计算结果的影响 算法有 优劣 之分,问题有 好坏 之别,即使不能定量地估计出最终误差,但是若能判别计算过程中误差不会被任意放大,那就能放心地实施计算,这就是定性分析的初衷. 数值稳定性 数学问题的适定性和数值算法的稳定性 数学问题的适定性(well-posedness):满足 (1) 对任意满足一定条件的数据,存在一个解 (2) 对任意满足一定条件的数据,解是唯一的 (3) 问题的解关于输入数据是连续的 否则就称问题是不适定的(ill-posed) 通俗描述:如果输入数据的微小扰动会引起输出数据(即计算结果)的很大变化(误差),则称该数值问题是病态的,否则就是良态的. 病态问题举例 例:解线性方程组 解: 当?=1 时,无解 当??1 时,解为 若??1,则?的微小误差可能会引起解的很大变化 比如 ?=0.9990 时, x?500.25;

如果输入数据有 0.0001 的误差,即?*=0.9991, 则x*?555.81,误差约为 55.56! 因此,此时的问题就是病态的! 病态问题与条件数 设一元函数 f (x) 可微,x*为x的近似值,则有 其中 Cp 就称为 f (x) 的条件数. 一般情况下,条件数大于

10 时,就认为问题是病态的 条件数越大问题病态就越严重 病态是问题本身固有的性质,与数值算法无关 对于病态问题,选择数值算法时需要更加谨慎 算法的稳定性 通过递推公式可得(每次都保留

3 位有效数字) ? ? ? ? ? 算法稳定性 但显然有 算法稳定性 考察第 n 步的误差 即有 误差以

5 倍 的速度增长! 我们需要改变算法! 说明该计算过程是 不稳定 的! 数值稳定性 具体思路:先估计一个 SN ,再反过来求 Sn ( n <

N ) 在数值计算中,误差不可避免, 算法的稳定性是一个非常重要的性质. ex11.m 数值稳定性 算法的稳定性 例:教材第

9 页,例5(自己练习) 在计算过程中,如果误差不增长或能得到有效控制,则称该算法是稳定的,否则为不稳定的. 数值计算中,不要采用不稳定的算法! 数值计算注意事项 避免相近的数相减 例:a1 = 0.12345,a2 = 0.12346,各有5位有效数字. 而a2 ? a1 = 0.00001,只剩下1位有效数字. 例:教材第

11 至12 页,例7,8,9,10 (自己练习) 数值计算注意事项 避免数量级相差很大的数相除 可能会产生溢出的情形(超出计算机所能表示的范围) 避免大数吃小数 例:计算 (109+10-9-109)/10-9 例:按从小到大、以及从大到小的顺序分别计算 S=1 +

2 +

3 + … +

40 +

108 求和时 从小到大 相加,可使结果的误差减小 ex12.m 数值计算注意事项 简化计算,避免误差积累 选用稳定的算法 例:已知 p(x) = xn + xn-1+ ・・・ + x + 1, 计算 n =

20 时, p(8) 的值. 如果直接代入计算,则需 n(n-1)/2 次乘法和 n 次加法运算 如果将 p(x) 改写为: p(x)x + 1) x+1)x + 1) ・・・)x +