数值分析第1章数值分析与科学计算引论.ppt

2019/7/16,数值分析与科学计算引论,1,第1章 数值分析与科学计算引论,数值分析的对象、作用与特点 数值计算的误差 数值计算的误差定性分析与避免误差危害 数值计算中算法设计的技术,2019/7/16,数值分析与科学计算引论,2,1.1 数值分析的对象、作用与特点,1.1.1 研究对象与作用,计算数学 根据实际问题的数学模型提出问题求解的数值计算方法，并对方法进行理论分析和软件实现.,1.1.2 特点,算法能在计算机上实现，并有好的计算复杂性；,面向计算机，提供切实可行的有效算法；,有可靠的理论分析，能达到精度要求，算法的收敛性与数 值稳定性，算法的误差分析；,通过数值实验 证明算法行之有效。,计算机上实现数值计算，解决实际问题.,1.1.3 实际应用,2019/7/16,数值分析与科学计算引论,3,1.2 数值计算的误差,1.2.1 误差的来源与分类,模型误差在将实际问题归结为数学模型时，需要对问题作一定的简化和假设。,观测误差 数学模型中需要用到的一些系数、初值等常数来自于测量仪器或统计资料，由于客观条件和仪器精度的限制不可避免有误差。,方法误差 (截断误差) 模型的准确解与用数值方法求得的近似解之间的误差称为“截断误差”。,舍入误差在上机实际计算时，由于计算机对所运算的对象按机器字长四舍五入而产生的最终计算解与模型的准确解之间的误差。,实际算法: 有限、四则运算化,（理论计算误差）,2019/7/16,数值分析与科学计算引论,4,误差的产生,实际问题,数学模型,建 模,模型 误差,观测 误差,数值方法,数值解,离散,截断 误差,计算,舍入 误差,实例,2019/7/16,数值分析与科学计算引论,5,大家一起猜？,1,1 / e,将 作Taylor展开后再积分,| 舍入误差 |,= 0.743 ,由截去部分 引起,由留下部分 引起,解：,2019/7/16,数值分析与科学计算引论,6,1.2.2 误差与有效数字,绝对误差 /* absolute error */,其中，x 准确值，x*x的近似值,，例如：,上常记为,误差绝对值不能超过某个正数,工程,注：e* 理论上讲是唯一确定的，可能取正，也可能取负。 e*0 时，x*称为强近似值，e* 0 不唯一，当然 越小越具有参考价值。,通常是不知道的,根据具体情况，可事先估计出误差的范围,误差绝对值的“上界”，或称“误差限”，即有,2019/7/16,数值分析与科学计算引论,7,例2 设=3.1415926 近似值A=3.14,它的绝对误差是 0.0015926，有, - A =0.0015926 0.002=0.210-2,可见，绝对误差限*不是唯一的，但*越小越好,例3 又近似值A =3.1416，它的绝对误差是0.0000074，有,| - A |=0.0000074 0.000008=0.810-5,例4 又近似值A =3.1415，它的绝对误差是0.0000926，有,| - A |= =0.0000926 0.0001=0.110-3,绝对误差限并不能很好地反映近似值的好坏，,x*=10， x*=1 ，y*=10000， y*=5,虽然y*是x*的5倍，但在10000内差5显然比10内差1好。,2019/7/16,数值分析与科学计算引论,8,相对误差 /* relative error */,x* 的相对误差限,实际计算中，相对误差通常取为：,2019/7/16,数值分析与科学计算引论,9,例5,解,结论?,俗称“好坏”、“多少”是相对的,设 ， ， ， ，,估计近似数 的绝对误差与相对误差。,但 是 的一个好的近似， 不是 的好的近似。,2019/7/16,数值分析与科学计算引论,10,有效数字,4,3,若近似值 x*的误差限是某一位的半个单位,该位到 x* 的第一位 非零数字共有 n 位,就说 x*有 n 位有效数字.,证明,注：如果x*是由x四舍五入得到的近似值，则x*的每一位 都是有效数字。当x已知 时，可根据需要产生每位皆有效 的近似值。,有 n 位有效数字的x*可表示为,2019/7/16,数值分析与科学计算引论,11,有效数字与相对误差的关系, 有效数字 相对误差限,已知 x* 有 n 位有效数字，则其相对误差为, 相对误差限 有效数字,已知 x* 的相对误差满足,可见 x* 至少有 n 位有效数字。,2019/7/16,数值分析与科学计算引论,12,假设 * 取到 n 位有效数字，则其相对误差上限满足,要保证其相对误差限小于0.001%，只要保证其上限满足,已知 a1 = 3，则从以上不等式可解得 n 6 log6，即 n 6，应取 * = 3.14159。,例7 为使 的相对误差小于0.001%,至少应取几位有效数字？,解,2019/7/16,数值分析与科学计算引论,13,问题： 这些公式的形式有什么特点？使你想到什么？,代数运算的误差估计,1.2.3 数值运算的误差估计,2019/7/16,数值分析与科学计算引论,14,函数值的误差估计,问题：对于 y = f (x)，若用 x* 取代 x，将对y 产生什么影响？,由函数的泰勒展开式,函数值的相对误差（限），有：,2019/7/16,数值分析与科学计算引论,15,相对误差条件数,f 的条件数在某一点是小大，则称 f 在该点是好条件的 坏条件的。,问题：,则 的近似值,于是函数值 的误差,2019/7/16,数值分析与科学计算引论,16,1.3 误差定性分析与避免误差危害,一个工程或科学计算问题往往要运算千万次，由于每步运算都有误差，如果每步都做误差分析是不可能的，也不科学.,误差积累有正有负，绝对值有大有小，都按最坏情况估计误差限得到的结果比实际误差大得多，这种保守的误差估计不反映实际误差积累.,概率分析法 威尔金森(Wilkinson )的向后误差分析法 穆尔(Moore)的区间分析法.,1.3.1 舍入误差的定量分析方法,2019/7/16,数值分析与科学计算引论,17,例8 计算, 公式一:,注意此公式精确成立,?,?,? !,! !,发生了 什麽 ?!,1.3.2 数值稳定性与误差的传播,2019/7/16,数值分析与科学计算引论,18,考察第n步的误差, 公式二:,注意此公式与公式一 在理论上等价。,方法：先估计一个IN ,再反推要求的In ( n N )。,可取,2019/7/16,数值分析与科学计算引论,19,取,2019/7/16,数值分析与科学计算引论,20,考察反推一步的误差：,以此类推，对 n N 有：,误差逐步递减, 这样的算法称为稳定的算法。,舍入误差的定性分析,一个算法如果输入数据有扰动（即误差），而计算过程中舍入误差不增长,则称此算法是数值稳定的，否则此算法就称为不稳定的。,数值稳定性/* Numerical Stability */,2019/7/16,数值分析与科学计算引论,21,病态问题 输入数据的微小扰动（即误差），引起输出数据（即问题解）的相对误差很大的数学问题。,（3.3）,称为计算函数值问题的条件数.,计算函数值 时，,若 有扰动 ，,相对误差为 ，,函数值 的相对误差为,相对误差比值,1.3.2 病态问题与条件数,病态问题举例计算函数值问题的条件数,很大的问题病态问题,2019/7/16,数值分析与科学计算引论,22,函数,它表示相对误差可能放大 倍.,如 ，,有 ，,自变量相对误差为 ，,函数值相对误差为 ，,一般情况下,条件数 就认为是病态， 越大，病态越严重.,的条件数,若取,这时问题可以认为是病态的.,计算函数值问题举例,2019/7/16,数值分析与科学计算引论,23,避免相近二数相减。,举例：a1 = 0.12345，a2 = 0.12346，各有5位有效数字。 而 a2 a1 = 0.00001，只剩下1位有效数字。, 几种经验性避免方法：,当 | x | 1 时：,避免小分母 : 分母小会造成舍入误差增大。,选用稳定的算法。,1.3.3 避免误差危害的若干原则,2019/7/16,数值分析与科学计算引论,24,避免大数吃小数,举例：用单精度计算 的根。,精确解为, 算法1：利用求根公式,在计算机内，109存为0.11010，1存为0.1101。做加法时，两加数的指数先向大指数对齐，再将浮点部分相加。即1 的指数部分须变为1010，则：1 = 0.0000000001 1010，取单精度时就成为： 109+1=0.100000001010+0.00000000 1010=0.10000000 1010,大数吃小数,2019/7/16,数值分析与科学计算引论,25,算法2：先取 再利用,求和时从小到大相加，可使和的误差减小。,举例：按从小到大、以及从大到小的顺序分别计算 1 + 2 + 3 + + 40 + 109,先化简再计算，减少步骤，避免误差积累。,一般来说，计算机处理下列运算的速度为,如计算多项式的值用秦九韶法(P11).,2019/7/16,数值分析与科学计算引论,26,算法设计的好坏 影响计算结果的精度，好算法大量节省计算时间.,1.4 数值计算中算法设计的技术,算法设计的一个重要原则减少运算次数,1.4.1 多项式求值的秦九韶算法,设给定 次多项式,求 处的值 .,直接计算 再相加,加法次数,减少计算量，减少误差,多项式求值,乘法次数,计 算 量,2019/7/16,数值分析与科学计算引论,27,记,（4.1）,则 .,求 在 点的值.,其中,秦九韶算法,计算量,加法次数,乘法次数,优点,由（4.1）式,2019/7/16,数值分析与科学计算引论,28,对 求导得,故 .,则,（4.1）,其中,计算 的秦九韶算法,2019/7/16,数值分析与科学计算引论,29,此处,例8 设 ，用秦九韶算法求 和 的值.,用（4.1）和（4.2）式构造出计算表格（1-2）,解,2019/7/16,数值分析与科学计算引论,30,迭代法举例开方运算,迭代法数值计算普遍使用的重要方法,1.4.2 迭代法与开方求值,迭代法的构造,先给定一个初始近似 ，令 ， 是一个 校正量，称为增量，,按同一公式重复计算逐次逼近真值的方法,即,舍去高阶项 ，则得,即,2019/7/16,数值分析与科学计算引论,31,（4.4）,这里 不是的真值，但它是真值 的进一步近似，重复以 上过程进行迭代,它可逐次求得 若,则 ，容易证明序列 对任何 均收敛,1次加法 1次除法 1次移位,例9 用迭代法（4.4）求 ，取,若计算精确到 ，由（4.4）式可求得,迭代3次误差即小于,解,2019/7/16,数值分析与科学计算引论,32,1.4.3 以直代曲与化整为“零”,数值计算：将非线性问题线性化。,圆周率 的计算是古代数学的一个光辉成就，充分体现了以直代曲化整为“零”的思想.,图1-1,几何：在局部范围内用直线近似曲线。,2019/7/16,数值分析与科学计算引论,33,方程求根的牛顿迭代法,求函数方程 的根,图1-2,以直代曲相当于用切线方程,的根 近似 ，从而,（4.5）,牛顿迭代法以直代曲举例,几何上表现为平面上的一条曲线,它与 轴交点的横坐标即为方程的根 .,2019/7/16,数值分析与科学计算引论,34,（4.6）,定积分计算的梯形公式与复合梯形公式,梯形公式