数值计算和最优化lecture误差和二分法

由上面讨论能够看出，为了求得满意计算解，在选用计算公式和设计算法时，都应注意以下普遍标准：(1)预防大数吃小数主要由计算机位数引发选取算法应遵照标准计算机中数计算特点：加法先对阶，后运算，再舍入。乘法先运算，再舍入。不在计算机数系中数做四舍五入处理。数值计算和最优化lecture误差和二分法第1页作一个有效数字为4位连加运算而假如将小数放在前面计算在作连加时，为预防大数吃小数，应从小到大进行相加，如此，精度将得到适当改进。当然也可采取别方法。例数值计算和最优化lecture误差和二分法第2页(2)作减法时应防止两个相近数相减两个相近数相减，会使有效数字位数严重损失！例1.2.10用四位浮点数计算

解只有一位有效数字,有效数字大量损失，造成相对误差扩大。结果依然有四位有效数字。这说明了算法设计主要性。在算法设计中，若可能出现两个相近数相减，则改变计算公式，如使用三角变换、有理化等等。数值计算和最优化lecture误差和二分法第3页(3)防止小数作除数和大数作乘数小数作除数或大数作乘数会产生溢犯错误，因而产生大误差。在算法设计时，要防止这类情况在计算公式中出现。此时能够依据一些详细情况,把一些算式改写成另一个等价形式，如分母有理化等。依据误差传输预计式数值计算和最优化lecture误差和二分法第4页§3.算法稳定性如前所述，因为各种误差存在，计算机往往只能近似地求解实际问题，因而计算时会冒风险。一、问题性态数值计算和最优化lecture误差和二分法第5页如把方程组系数舍入成两位有效数字它准确解为x1=-6.222...x2=38.25…x3=-33.65...例求解线性方程组其准确解为x1=x2=x3=1.数值计算和最优化lecture误差和二分法第6页若对方程组系数和中间结果均取3位10进制有效数字，然后用Gauss消元法求解，得到计算解为：显然，该计算解精度较差。一样用Gauss消元法求解方程组：也取3位10进制有效数字，得到计算解为：轻易验证，它是方程组准确解。数值计算和最优化lecture误差和二分法第7页上述例子表明，数值问题计算解精度，与数值问题本身性态相关。定义1.3.1在数值问题中，假如输出数据对输入数据扰动（如误差）很敏感，即若输入数据（如原始数据）有较小改变，会引发输出数据（如计算解）较大变化，称这类数值问题为病态问题或坏条件问题。非病态问题又称为良态问题。问题输出变量相对误差与输入变量相对误差商称为问题条件数数值计算和最优化lecture误差和二分法第8页二、算法稳定性与设计标准例1.3.3计算定积分解一个程序往往要进行大量四则运算才能得出结果，每一步运算均可能会产生舍入误差。在大量计算中,舍入误差是积累还是能控制,这与算法相关。数值计算和最优化lecture误差和二分法第9页误差放大5千倍!并假设计算过程中不产生新舍入误差。误差会放大由公式可推出：数值计算和最优化lecture误差和二分法第10页显然算法不稳定。理论上成立算法，在计算机上计算时，因为初值误差在计算过程中传输，而造成结果失真，这是我们数值计算方法所要研究。(2)利用递推公式误差不会放大数值稳定，在运算过程中，舍入误差不增大。

数值计算和最优化lecture误差和二分法第11页定义1.3.2假如对于良态问题，在运算过程中,舍入误差能控制在某个范围内算法称之为数值稳定算法,不然就称之为不稳定算法。前面例子说明，不稳定算法可能造成计算结果不可靠甚至严重失真。所以，在计算时，应该采取稳定数值计算方法。数值计算和最优化lecture误差和二分法第12页算法优劣标准从截断误差观点看，算法必须是截断误差小，收敛速速要快。即运算量小，机器用时少。从舍入误差观点看，舍入误差在计算过程中要能控制，即算法数值要稳定。从实现算法观点看，算法逻辑结构不宜太复杂，便于程序编制和上机实现.数值计算和最优化lecture误差和二分法第13页设计算法时应遵照标准要含有数值稳定性，即能控制误差传输。防止大数吃小数，即两数相加时，预防较小数加不到较大数上。防止两相近数相减，以免有效数字大量丢失。防止分母很小或乘法因子很大，以免产生溢出。数值计算和最优化lecture误差和二分法第14页非线性方程求根第二章数值计算和最优化lecture误差和二分法第15页当代科学技术或工程技术领域许多实际问题，经常能够归结为求解函数方程：假如函数能写成以下形式假如有使得，则称为方程根，或称为函数零点。数值计算和最优化lecture误差和二分法第16页如：①当f(x)为代数方程时，理论上已经证实，大于五次多项式普通没有代数解法。②当f(x)为超越方程时，普通不能用代数方法求其根。

所以，超越方程(含有指数和对数等)代数方程（多项式）对于普通非线性方程，只能用数值方法求解。数值计算和最优化lecture误差和二分法第17页方程求根问题分成两步：第二步：根隔离确定根所在区间，使方程在这个小区间内仅有一个根，该区间叫隔根区间。第三步：根准确化已知根一个近似值后，用某种方法对其进行加工，使之满足给定精度要求。第一步：根存在性数值计算和最优化lecture误差和二分法第18页求隔根区间普通方法理论依据：数值计算和最优化lecture误差和二分法第19页本章主要介绍二分法与迭代法（包含Newton迭代法及其变型、弦割法等）§1.二分法二分法是方程求根最惯用而且也是最保险方法之一。一、算法基本思想将区间对分，保留有根区间，舍去无根区间。如此往复，以逐步迫近方程根。基本条件：数值计算和最优化lecture误差和二分法第20页二、算法步骤数值计算和最优化lecture误差和二分法第21页ax0ba1b1三、算法收敛性此时有误差预计：惯用来预计k值数值计算和最优化lecture误差和二分法第22页四、算法优点与缺点缺点：不能求偶数重根及复根；收敛速度非常迟缓，与以1/2为公比等比级数相同；没有充分利用函数值。所以普通不单独使用，往往为其它快速方法提供初值。优点：计算简单且必收敛，是一个可靠算法；对函数性质要求低，只要求函数f(x)连续就能够了。用二分法求方程

在[1,1.5]内实根，要求

解即可推出所需迭代次数满足

在区间[1,1.5]上最少存在一个根。其详细过程以下：

例2.1.1因为因而由误差预计式数值计算和最优化lecture误差和二分法第23页

符号011.51.25-11.251.51.375+21.251.3751.3125-31.31251.3751.3438+41.31251.34381.3281+51