数值计算与最优化(lecture2)误差及二分法.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)为超越方程时，一般不能用代数方法求其根。,所以，,超越方程(含有指数和对数等),代数方程（多项式）,对于一般的非线性方程，只能用数值方法求解。,方程求根的问题分成两步：,第二步：根的隔离,确定根所在的区间，使方程在这个小区间内仅有一个根， 该区间叫隔根区间。,第三步：根的精确化,已知根的一个近似值后，用某种方法对其进行加工，使之 满足给定的精度要求。,第一步：根的存在性,求隔根区间的一般方法,理论依据：,本章主要介绍二分法与迭代法（包括Newton迭代法及 其变型、弦割法等）,1. 二分法,二分法是方程求根最常用而且也是最保险的方法之一。,一、算法的基本思想,将区间对分，保留有根的区间，舍去无根的区间。如此 往复，以逐步逼近方程的根。,基本条件：,二、算法的步骤,a x0 b,a1 b1,三、算法的收敛性,此时有误差估计：,常用来估计k的值,四、算法的优点与缺点,缺点：不能求偶数重根及复根；收敛速度非常缓慢，与以1/2为公比的等比级数相同；没有充分利用函数值。因此一般不单独使用，往往为其它快速方法提供初值。,优点：计算简单且必收敛，是一种可靠的算法；对函数性质要求低，只要求函数f(x)连续就可以了。,用二分法求方程,在1,1.5内的实根，,要求,解,即可推出所需的迭代次数满足,在区间1,1.5上至少存在一个根。,其具体过程如下：,例2.1.1,由于,因而,由误差估计式,例2.1.2,解,即可推出所需的迭代次数满足,因而函数 在区间1,2上存在惟一的零点。,由于,以及,由误差估计式,二分法的一种