数值计算与最优化(lectre 2)误差及二分法数值计算与最优化(lecture 2)误差及二分法数值计算与最优化(lecture 2)误差及二分法数值计算与最优化(lecture 2)误差及二分法.ppt

* 第二讲 $1.3 计算过程中的误差及其控制 $2.1 二分法 由上面的讨论可以看出，为了求得满意的计算解，在选 用计算公式和设计算法时，都应注意如下普遍原则： (1) 防止大数吃小数 主要由计算机的位数引起 选用算法应遵循的原则 计算机中数的计算特点： 加法先对阶，后运算，再舍入。 乘法先运算，再舍入。 不在计算机数系中的数做四舍五入处理。 作一个有效数字为4位的连加运算 而如果将小数放在前面计算 在作连加时，为防止大数吃小数，应从小到大进行相加， 如此，精度将得到适当改善。当然也可采取别的方法。 例 (2) 作减法时应避免两个相近数相减 两个相近的数相减，会使有效数字的位数严重损失！ 例1.2.10 用四位浮点数计算 解 只有一位有效数字,有效数字大量损失，造成相对 误差扩大。 结果仍然有四位有效数字。 这说明了算法设计的重要性。在算法设计中，若可能出现两个相近数相减，则改变计算公式，如使用三角变换、有理化等等。 (3) 避免小数作除数和大数作乘数 小数作除数或大数作乘数会产生溢出错误，因而产生大的误差。 在算法设计时，要避免这类情况在计算公式中出现。此时可以 根据一些具体情况, 把某些算式改写成另一种等价的形式，如 分母有理化等。 根据误差传播的估计式 §3.算法的稳定性 如前所述，由于各种误差的存在，计算机往往只能近似地求解实际问题，因而计算时会冒风险。 一、问题的性态 如把方程组的系数 舍入成两位有效数字 它的精确解为x1 = -6.222... x2= 38.25… x3= -33.65... 例 求解线性方程组 其精确解为 x1=x2=x3=1. 若对方程组的系数和中间结果均取3位10进制有效数字，然后用Gauss消元法求解，得到计算解为： 显然，该计算解的精度较差。 同样用Gauss消元法求解方程组： 也取3位10进制有效数字，得到计算解为： 容易验证，它是方程组的精确解。 上述例子表明，数值问题计算解的精度，与数值问题本 身的性态有关。 定义1.3.1 在数值问题中，如果输出数据对输入数据的 扰动（如误差）很敏感，即若输入数据（如原始数据） 有较小的变化，会引起输出数据（如计算解）的较大变 化，称这类数值问题为病态问题或坏条件问题。非病态 问题又称为良态问题。问题输出变量的相对误差与输入 变量的相对误差的商称为问题的条件数 二、算法的稳定性与设计原则 例1.3.3 计算定积分 解 一个程序往往要进行大量的四则运算才能得出结果，每一步的运算均可能会产生舍入误差。在大量计算中,舍入误差是积累还是能控制,这与算法有关。 误差放大 5千倍! 并假设计算过程中不产生新的舍入误差 。 误差会放大 由公式 可推出： 显然算法不稳定。理论上成立的算法，在计算机上计算 时，由于初值的误差在计算过程中的传播，而导致结果 的失真，这是我们数值计算方法所要研究的。 (2) 利用递推公式 误差不会放大 数值稳定，在运算过程中，舍入误差不增大。 定义1.3.2 如果对于良态问题，在运算过程中,舍入误差 能控制在某个范围内的算法称之为数值稳定的算法,否则 就称之为不稳定的算法。 前面的例子说明，不稳定的算法可能导致计算结果不可 靠甚至严重失真。因此，在计算时，应该采用稳定的数 值计算方法。 算法优劣的标准 从截断误差观点看，算法必须是截断误差小，收敛速 速要快。即运算量小，机器用时少。 从舍入误差观点看，舍入误差在计算过程中要能控 制，即算法的数值要稳定。 从实现算法的观点看，算法的逻辑结构不宜太复杂， 便于程序编制和上机实现. 设计算法时应遵循的原则 要具有数值稳定性，即能控制误差的传播。 避免大数吃小数，即两数相加时，防止较小的数加 不到较大的数上。 避免两相近的数相减，以免有效数字的大量丢失。 避免分母很小或乘法因子很大，以免产生溢出。 非线性方程的求根 第 二 章 现代科学技术或工程技术领域的许多实际问题，常常可以归结为求解函数方程： 如果函数 能写成如下形式 如果有 使得 ，则称 为方程 的根， 或称 为函数 的零点。 如： ① 当f(x)为代数方程时，理论上已经证明，大于五次 的多项式一般没有代数解法。 ② 当f(x)为超越方程时，一般不能用代数方法求其根。 所以， 超越方程(含有指数和对数等) 代数方程（多项式） 对于一般的非线性方程，只能用数值方法求解。 方程求根的问题分成两步： 第二步：根的隔离 确定根所在的区间，使方程在这个小区间内仅有一个根， 该区间叫隔根区间。 第三步：根的精确化 已知根的一个近似值后，用某种方法对其进行加工，使之