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

第二讲$1.3 计算过程中的误差及其控制$2.1 二分法由上面的讨论可以看出，为了求得满意的计算解，在选用计算公式和设计算法时，都应注意如下普遍原则：(1)防止大数吃小数主要由计算机的位数引起选用算法应遵循的原则选用算法应遵循的原则计算机中数的计算特点：计算机中数的计算特点：加法先对阶，后运算，再舍入。乘法先运算，再舍入。不在计算机数系中的数做四舍五入处理。作一个有效数字为4位的连加运算而如果将小数放在前面计算在作连加时，为防止大数吃小数，应从小到大进行相加从小到大进行相加，如此，精度将得到适当改善。当然也可采取别的方法。例例(2)作减法时应避免两个相近数相减两个相近的数相减，会使有效数字的位数严重损失！例例1.2.10用四位浮点数计算 解解只有一位有效数字,有效数字大量损失，造成相对误差扩大。结果仍然有四位有效数字。这说明了算法设计的重要性。在算法设计中，若可能出现两个相近数相减，则改变计算公式，如使用三角变换、有理化等等。(3)避免小数作除数和大数作乘数小数作除数或大数作乘数会产生溢出错误，因而产生大的误差。在算法设计时，要避免这类情况在计算公式中出现。此时可以根据一些具体情况,把某些算式改写成另一种等价的形式，如分母有理化等。根据误差传播的估计式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.1.二分法二分法二分法是方程求根最常用而且也是最保险的方法之一。一、算法的基本思想将区间对分，保留有根的区间，舍去无根的区间。如此往复，以逐步逼近方程的根。基本条件：基本条件：二、算法的步骤a x0 b a1 b1三、算法的收敛性 此时有误差估计误差估计：常用来估计k的值四、算法的优点与缺点 缺点：缺点：不能求偶数重根及复根；收敛速度非常缓慢，与以1/2为公比的等比级数相同；没有充分利用函数值。因此一般不单独使用，往往为其它快速方法提供初值。优点优点：计算简单且必收敛，是一种可靠的算法；对函数性质要求低，只要求函数f(x)连续就可以了。用二分法求方程 在1,1.5内的实根，要求 解解即可推出所需的迭代次数满足 在区间1,1.5上至少存在一个根。其具体过程如下：例例2.1.1由于因而由误差估计式 的符号0 01 11.51.51.251.25-1 11.251.251.51.51.3751.375+2 21.251.251.3751.3751.31251.3125-3 31.31251.31251.3751.3751.34381.3438+4 41.31251.31251.34381.34381.32811.3281+5 51.31251.31251.32811.32811.32031.3203-6 61.32031.32031.32811.32811.32421.3242-例例2.1.22.1.2解解即可推出所需的迭代次数满足 因而函数 在区间1,2上存在惟一的零点。由于以及由误差估计式二分法的一种修正是试位法试位法。在二分法中，原来区间的中点为新的区间的一个端点。因此，每迭代一步，区间的长度均减半。在试位法中，不用中点，而用过点 与 的直线的零点作为新区间的一个端点。在实际计算中，试位法比二分法往往收敛得要快。在试位法的每一步计算中，有