《数值计算方法》PPT课件.ppt

引言 用计算机解决的问题分为 数值问题：以科学计算为主 非数值问题：以排序、检索等位事务处理为 主 计算机的能力有限，其基本运算部件只能 做简单的四则运算和简单的逻辑的运算， 怎样用计算机解决实际问题？ 数值问题的解决步骤 实际问题 数学模型 程序设计 上机计算 数值结果 数值计算方法 建立数 学模型 转化为 数值公式 进行计算 数值分析是研究各种数学问题的数值 解法及其理论的一门学科。涉及 数值计算方法（可用于编程的数值计 算公式） 可靠性分析 复杂性衡量与评价 数值计算以及计算机模拟（包括当前流 行的虚拟现实的方法），已经是在工程技术 研究和经济、社会科学中广泛应用的方法， 带来巨大的经济效益 天气预报与亿次计算机 波音 777的无纸设计与有限元 CT、 核磁共振 计算流体力学与爆炸工程 能源问题与大型计算 计算作为 工程技术 研究方法 计算方法课程主要讨论如何构造求数学模 型近似解的算法，讨论算法的数学原理、 误差和复杂性，配合程序设计进行计算试 验并分析试验结果。 与纯数学的理论方法不同，用数值计算方 法所求出的结果 一般 不是解的精确值或者 准确的解析表达式，而是所求真解的某些 近似值或近似曲线。 例如方程 x2=2sinx， 在区间 (1,2)内有唯一根 , 但找不 出求根的解析式 , 只能用数值计算方法求其近似解。 有些数学问题虽有理论上的准确的公式解 , 但不一定实 用 , 例如行列式解法的 Cramer法则原则上可用来求解线性方 程组 ,用这种方法解一个 n元方程组 ,要算 n+1个阶行列式的值 , 总共需要 n!(n-1)(n+1)次乘法 ,当 n=20时 ,其乘除法运算次数 约需 1021次方 ,即使用每秒千亿次的计算机也得需要上百年 ,而 用高斯（ Guass） 消去法约需 2660次乘除法运算 ,并且愈大 ,相 差就愈大。可见研究和选择好的算法是非常重要的。 “精确”与“近似” 算法 (数值算法 ):是指有步骤地完成解数值问 题的过程。 数值算法的特点 目的性，条件和结论、输入和输出数据均要有明 确的规定与要求。 确定性，精确地给出每一步的操作 (不一定都是运 算 )定义 , 不容许有歧义。 可执行性，算法中的每个操作都是可执行的 有穷性，在有限步内能够结束解题过程 计算机上的算法，按面向求解问题的不同， 分为数值算法和非数值算法。 21世纪人才要求 科学素质：拓宽对 21世纪科学的了解； 加深对数学思想的理解； 培养用数学思考世界的习惯； 数学能力：数学知识的运用能力； 对专业问题建立数学求解方法与 实际计算能力； 应用问题中数学创造性能力 ; 计算知识：常用算法的数学理论； 在“误差、存贮、速度”之下的实 际计算方法； 对结果的数值分析方法 ; 1. 认识建立算法和对每个算法进行理论分析是基本任务， 主动适应 “ 公式多 ” 的特点； 2. 注重各章建立算法的问题的提法，搞清问题的基本提法 ，逐步深入； 3. 理解每个算法建立的数学背景，数学原理和基本线索， 对最基本的算法要非常熟悉； 4. 认真进行数值计算的训练，学习各章算法完全是为用于 实际计算，必须真会算。 记好课堂笔记 保证课堂纪律 按时完成作业 按时上课，不迟到早退 几点 要求 如何掌握每类数值方法 背景：数学模型到数值问题的转化 算法介绍：基本思想；算法描述 算法评价： 估计算法精度；分析误差的积累和传播 算法改进： 提高精度；减少内存占用 算法比较： 分析算法的优缺点 本课程对计算机相关专业的基本要求 一本院校工科专业基本都要学习本课程 掌握数值方法的基本原理 掌握常用的科学与工程计算的基本方法 能用所学方法在计算机上算出正确结果（编程 ） 本章内容 1误差的来源及分类 2误差的度量 3误差的传播 4减少运算误差的原则 第一章计算方法与误差 小结 要求掌握的内容 第一章计算方法与误差 概念 包括有效数字、绝对误差 、 绝对误差 限 、相对误差、相 对误差 限等 误差 截断误差、舍入误差的详细内容，误差种类等 分析运算误差的方法和减少运算误差的若干原则 第一章计算方法与误差 1.1 误差的来源及分类 早在中学我们就接触过误差的概念 ，如在做热力学实验中，从温度计上读 出的温度是 23.4度，就不是一个精确的 值，而是含有误差的近似值。事实上， 误差在我们的日常生活中无处不在，无 处不有。如量体裁衣，量与裁的结果都 不是精确无误的，都含有误差。 在用数值方法解题过程中可能产生的误差 归纳起来有如下几类： 1. 模型误差 2. 观测误差 3. 截断误差 4. 舍入误差 第一章计算方法与误差 用数学方法解决一个具体的实际问题，首先要建 立数学模型，这就要对实际问题进行抽象、简化 ，因而数学模型本身总含有误差，这种误差叫做 模型误差 数学模型是指那些利用数学语言模拟现实而建立 起来的有关量的描述 数学模型的准确解与实际问题的真解不同 实际问题的 真解 数学模型的 真解 为减化模型忽略次要因素 定理在特定条件下建立与实际条件有别 1. 模型误差 在数学模型中通常包含各种各样的参变量，如温度 、长度、电压等，这些参数往往是通过观测得到的 ，因此也带来了误差，这种误差叫观测误差 数学模型中的参数和原始数据，是由观测和试验得 到的 由于测量工具的精度、观测方法或客观条件的限制 ,使数据含有测量误差 ,这类误差叫做 观测误差或数 据误差 根据实际情况可以得到误差上下界 数值方法中需要了解观测误差 ,以便选择合理的数 值方法与之适应 2. 观测误差 精确公式用近似公式代替时 ,所产生的误差叫 截断 误差 例如 , 函数 f(x)用泰勒 (Taylor)多项式 3. 截断误差 n n n xn fxfxffxp ! )0( !2 )0( !1 )0()0()( )(2 1 )1( )!1( )()()()( n n nn xn fxpxfxR （ 介于 0与 x之间） 近似代替，则数值方法的截断误差是 截断误差的大小直接影响计算结果的精度和计算 工作量，是数值计算中必须考虑的一类误差 在数值计算中只能对有限位字长的数值进 行运算 需要对参数、中间结果、最终结果作有限 位字长的处理工作，这种处理工作称作舍 入处理 用有限位数字代替精确数，这种误差叫做 舍入误差 ，是数值计算中必须考虑的一类 误差 4. 舍入误差 第一章计算方法与误差 例 如在计算时用 3.14159近似代替 ， 产生的误差 R= -3.14159=0.0000026 就是舍入误差。 上述种种误差都会影响计算结果的准确 性，因此需要了解与研究误差，在数值计算 中将着重研究 截断误差、舍入误差，并对它 们的传播与积累作出分析。 1.3 误差的度量 1.3.1 绝对误差和绝对误差限 定义 1.1 设精确值 x的近似值 x* ， 称差 e(x*) =x-x* 近似值 x*的绝对误差 ， 简称误差 。 e(x*)又记为 e* 当 e*0时 ， x*称为弱 近似值 ， 当 e*0时 ， x*称为强 近 似值 |e*|越小 ， x*的精度越高 由于精确值一般是未知的 ,因而 e* 不能求出来 , 但可以根据测量误差或计算情况设法估计出它的 取值范围，即误差绝对值的一个上界或称误差限。 1.3 误差的度量 定义 1.2 设存在一个正数 ， 使 则称为近似值的绝对误差限，简称误差限或精度。 实际应用中经常使用这个量来衡量误差限 , 这就 是说 , 如果近似数 的误差限为 , 则 表明准确值 x 必落在 上 , 常采用下面的写 法 * xxe *x * * xxx * , xx * xx 来表示近似值的精度或准确值 x所在的范围。 1.3 误差的度量 a- a+ a A 例 1 设 x =3.1415926 近似值 x* =3.14,它的绝 对误差是 0.001 592 6 ， 有 x-x*=0.0015926 0.002=0.210-2 例 2 又近似值 x* =3.1416， 它的绝对误差是 0.0000074 ， 有 x-x*=0.0000074 0.000008=0.810-5 例 3 而近似值 x* =3.1415， 它的绝对误差是 0.0000926 ，有 x-x*=0.0000926 0.0001=0.110-3 可见， 绝对误差限 *不是唯一的，但 *越小越好 1.3.2 相对误差和相对误差限 只用绝对误差还不能说明数的近似程度 , 例如甲打字每 100个错一个 ,乙打字每 1000个 错一个 ,他们的误差都是错一个 ,但显然乙要 准确些 ,这就启发我们除了要看绝对误差外 , 还必须顾及量的本身。 定义 1.3 绝对误差与精确值 x的比值 x xx x exe r * * )( 称为相对误差 。 简记为 * re)( *xer 1.3.2 相对误差和相对误差限 相对误差越小 ,精度就越高 ,实际计算时 ,x通常是不知道的 ,因此可用下列公式计算相 对误差 * * x xxxee r 定义 1.4 设存在一个正数 ，使 )( *xr )( * * * * * * * x xx xx x ee rr 则称 为近似值 的相对误差限。 简记为 )( *xr *x )( *xr *r 1.3.2 相对误差和相对误差限 例 4. 甲打字每 100个错一个，乙打字每 1000个 错一个，求其相对误差 解： 根椐定义 :甲打字时的相对误差 乙打字时的相对误差 00 * 1 100 1 re 00 * 1.0 10 00 1 re 1.3.3 有效数字 定义 1.5 设 x的近似值 * 120 . 1 0 mnpx x x x x 其中 是 0到 9之间的任一个数 ,但 p是正整数 , m是整数 ,若 ix 1 0 , 1 , 2 , 3 , , , ,x i n p nmxx 10 2 1* 则称 为 x的具有 n位有效数字的近似值， 准确 到第 n位， 是 的有效数字。 *x *x 12, , , nx x x *x 规格化 1.3.3 有效数字 例 5. 3.142作为 的近似值时有几位有效数字 解： m = 1 m n =1n =-3 所以 n =4， 具有 4位有效数字 1. . 10 3 14 15 92 0 31 41 59 2 1. . 1 03 1 4 2 0 3 1 4 2 11 13 . = 0 .3 1 4 1 5 9 2 1 0 0 .3 1 4 2 1 0 1 0 .0 0 0 0 4 1 1 0 0 .0 0 0 5 1 0 2 3 1 4 2 例 6. 当取 3.141作为 的近似值时 -3.141=0.3141592 101 -0.3141101 0.0000592 101 0.0005=1/2 10-2 m-n=1-n=-2 所以 n=3具 有 3位 有效数字 推论 如果 近似数 x*误差限是某一位的半个单位 , 由该位到 x*的第一位非零数字一共有 n位 , x*就有 n位有效数字 ,也就是说准确到该位 . 再如 3.1416作为 的近似值时 -3.1416 = 0.3141592 101-0.31416101 0.00000074 101 0.00000740.00005 0.5 10-4 m-n=1-n=-4 所以 n=5 x*= 3.1416有 5位有效数字 关于有效数字说明 用 四舍五入取准确值的前 n位 x*作为近似值 ,则 x*必有 n位有效数字。如 3.142作为 的近似值 有 4位有效数字，而 3.141为 3位有效数字 有效数字相同的两个近似数，绝对误差不一定 相同。例如，设 x1*=12345,设 x2*=12.345,两者 均有 5位有效数字但绝对误差不一样 x- x1* =x- 12345 0.5= 1/2 100 x- x2* =x- 12.3450.0005= 1/210-3 把任何数乘以 10p(p=0,1, )不影响有效位数 准确值具有无穷多位有效数字 ,如三角形面积 S=1/2ah=0.5ah 因为 0.5是真值 ,没有误差 *=0,因此 n,准确值具有无穷位有效数字 1.3.4 有效数字与相对误差 定理 1.1 若 近似数 x* = 0.x1x2 xn10m具有 n 位 有效数字，则其相对误差限为 )1( 1 * 10 2 1 n r xe )1( 1 1 1 * * * 10 2 1 10 10 2 1 nm nm r xxx xxe 证 : x* = 0.x1x2 xn10m x* x110 m-1 又 x*具有 n位有效数字 ,则 x- x*1/2 10m-n )1( 1 * 10 2 1 n r xe 一般应用中可以取 r*=1/2x1 10-(n-1),n越 大 ,r*越小 , 有效数字越多，相对误差就越小 例 7 取 3.14作为 的四舍五入的近似值时，求其 相对误差限 解： 3.14=0.314 101 x1=3 m=1 四舍五入的近似值 ,其各位都是有效数字 n=3 r*=1/2x1 10-(n-1)=1/2*3 10-2=17% 1.3.4 有效数字与相对误差 例 8 已知近似数 x*有两位有效数字，试求其相 对 误差限 . 解：已知 n=2 代入公式 r*=1/2x1 10-(n-1)得 r*=1/2x1 10-1 x*的第一位有效数字 x1没有给出，可进行如下 讨论：当 x1=1 r*=1/2x1 10-1=1/2*1 10-1=5% x1=9 r*=1/2x1 10-1=1/2*9 10-1=0.56% 取 x1=1 时相对误差限为最大，即 5% 1.3.4 有效数字与相对误差 1.3.4 有效数字与相对误差 定理 1.2 若 近似数 x*=0.x1x2 xn10m的相对误差限为 则该近似数具有 n位有效数字 证 : x*=0.x1x2 xn10m x* ( x1+1) 10m-1 nmmn x x x x xx xx 10 2 110)1(10 )1(2 1 1 1 )1( 1 * * * * )1( 1 * 10 )1(2 1 n r xe 由有效数字定义可知 ,x*具有 n位有效数字。证毕 例 9 已知近似数 x*的相对误差限为 0.3%，问 x* 有几位有效数字？ 解：由 )1( 1 * 10 )1(2 1 n r xe )1( 1 10)1(2 11 0003 nx 得 当 x1=1时 ,310-3=1/410-(n-1)1210-3=10-(n-1) 上式两边取以 10为底的对数得 lg22+lg3+(-3)=-n+1 lg2=0.3010 lg3=0.4771 20.3010+0.4771-4=-n n=2.9209 当 x1=9时 ,310-3=1/2010-(n-1) 610-3=10-n 上式两边取以 10为底的对数得 lg2+lg3+(-3)=-n n=2.2219 x*至少有 3位有效数字 例 10 为使 的近似数的相对误差小于 0.1%， 问查开方表时，要取几位有效数字？ 解： 8 9 x1=8 -(n-1)lg2+2lg3+(-3) -n1.2552-4 -n2.7448 取 n =3即查平方表时 8.37取三位有效数字 70 70 3)1()1( 1 101018 11 0 00110)1(2 1 nnx 70 注意 : 已知有效数字 ,求相对误差限用公式 已知相对误差限 ,求具有几位有效数字公式 )1( 1 * 10 )1(2 1 nr x e )1( 1 * 10 2 1 nr x e 1.4.1 函数运算误差 函数运算误差可用泰勒展开式来分析 设一元函数 f(x)， 自变量 x的近似值 x*， f(x) 的近似值 f(x*)， 其误差限记为 f(x*) ，对 f(x) 在近似值 x* 附近泰勒展开 1.4 误差的传播 2* 2* )( !2 )( )()()( )( !2 )( )()()( f xfxfxf xx f xxxfxfxf 介于 x,x*之间 其中 *为 近似数 x*的绝对误差限，设 f (x* )与 f (x* )相差不大 ,可忽略 *的高次项 ,于是可得出函 数运算的误差和相对误差 多元函数亦类似，用泰勒展开即可推导出来 * * * * * * ( ) ( ) () ( ( ) ) ()r f x f x fx fx fx 例 11 已测得某场地长 L的值 L*=110m,宽 d的值 d*=80m,已知 L-L* 0.2m, d-d*0.1m 求场地面积 S=Ld的 绝对误差限和相对误差限 解： ml d s md l s d d s l l s s l d s d l s lds 110,80 )()()( , * * * * * * * * * %31.0 8 8 0 0 27)()()( * * * * * dl s s ss r 其中 (d*)=0.1m , (L*)=0.2m 绝对误差限 (s*)(800.2+110 0.1)m2=27m2 相对误差限 1.4.2 算术运算误差 计算机的数值运算主要是加、减、乘、除四 则运算，带有误差的数在多次运算过程中会进 行传播。使计算结果产生误差。 误差的变化可以用微分简单描述。注意到准 确值 x与其近似值通常很接近，其差可认为是较 小的增量，即可以把差看作微分，由此可得误 差的微分近似关系式。 xd x dx x xx x e xe dxxxxe r ln)( )( * * * 即 x的微分表示 x的绝对误差， lnx的微分表示 x的 相对误差，利用这两个关系式及微分运算可以得到一 系列有关四则运算的误差结果。 1.4.2 算术运算误差 由 d( x y)=dx dy 可得两数之和 (差）的 误差等于两数的误差之和（差）； 由 可得两数之积的相对误差等于两数的相对误差 之和； 由 可得两数商的相对误差可看作是被除数与除数 的相对误差之差。 ydxdyxd lnln)l n ( ydxd y xd lnlnln 例 12 正方形的边长约为 100cm,怎样测量才能使其 面积误差不超过 1cm2 ? 解： 设正方形边长为 x cm,测量值为 x*cm,面积 y=f(x)=x2 由于 f (x)=2x 记自变量和函数的绝对误差分别是 e*、 e(y*),则 e*=x-x* e(y*)=y-y* f (x*)(x-x*)=2x*e*=200e* 现要求 e(y*) 200e* 1 ,于是 e* （ 1/200） cm=0.005cm 要使 正方形面积误差不超过 1cm2， 测量边长时 绝对误差应不超过 0.005cm。 1.5 减少运算误差原则 误差是用来衡量数值方法好与坏的重要标志 为此对每一个算法都要进行误差分析 (1)两个相近的数相减，会严重损失有效数字 例如 x =1958.75， y =1958.32都具有五位 有效数字，但 x-y=0.43只有两位有效数字 通常采用的方法是改变计算公式 ,例如当与 很接近时 ,由于 2 1 21 lglglg x x xx 用右端代替左端公式计算 ,有效数字就不会损失 1.5 减少运算误差原则 当 x很大时可作相应的变换 xx xx 1 1 1 )1(1 1 )1( xx a r c t ga r c t g xxa r c t g 则用右端来代替左端。 1.5 减少运算误差若干原则 当 x接近 0时 x x x x s i n1 s i n s i n c os1 一般情况，当 f(x)f(x*) 时，可用泰勒展开 2* )(!2 )()()()( xxxfxxxfxfxf 取右端的有限项近似左端。 如果计算公式不能改变，则可采用增加有效位 数的方法保证精度 （ 2）防止大数 “ 吃掉 ” 小数 例 求二次方程 x2-105x+1=0的根 解：按二次方程求根公式 x1=(105+(1010-4)1/2)/2 x2=(105-(1010-4)1/2)/2 在 8位浮点数计算得 x1=(105+105 )/2=105 (正确） , x2=(105-105 )/2=0 (错误） 产生错误的原因 出现大数 1010吃掉小数 4的情况 分子部分出现两个相近数相减而丧失有 效数位常称为灾难性的抵消 （ 3）绝对值太小的数不宜做除数 当分母为两个相近数相减时 ,会丧失有效数字 )(10 0 0 0 1.0 )( 1 4 5 5.01 4 5 6.0 )( 4 分子分子分子 这里分子的误差被扩大 104倍 ,再如 若将分母变为 0.0011,即分母只有 0.0001的变化 时 ,计算结果却有了很大变化 1.5 减少运算误差若干原则 5.31 4100 1.0 14 15.3 9.28550011.0 1415.3 例 1.8 计算 0135.00125.00003.0 0012.00143.00005.0 D 解 : 分子分母分别计算后相除 (取 9位小数 ) A=0.0005*0.0143*0.0012=0.00000715*0.0012 =0.000000009(有舍入 ) B=0.0003*0.0125*0.0135=0.00000375*0.0135 =0.000000051(有舍入 ) D=A/B=0.17647 真值为 0.16948148， 所以 D只准确到小数后一位 1.5 减少运算误差若干原则 例： 计算 算法 2。分成三组因子。每组只取六位小数计算 a=0.0005/0.0003=1.666667(有舍入 ) b=0.0143/0.0125=1.144000 c=0.0012/0.0135=0.088889 (有舍入 ) D=a*b*c=1. 666667* 1.144000* 0.088889 =0.169482, 准确到小数后 5位。 0135.00125.00003.0 0012.00143.00005.0 D b c a 1.5 减少运算误差若干原则 （ 4）简化计算步骤，减少运算次数 x255=xx2x4x8x16x32x64x128 原先要做 254次乘法现只需 14次即可 又如计算多项式 p(x)=anxn an-1xn-1 a1x a0 的值 若直接计算 akxk,再逐项相加，一共要做 n+(n-1)+ +2+1=n(n+1)/2次乘法和 n次加法 1.5 减少运算误差若干原则 如果将前 n项提出 x， 则有 p(x)=（ anxn-1 an-1xn-2 a1 ） x a0 =(anxn-2an-1xn-3 a2)xa1） x a0 =( (anx an-1)x a2)x a1)x a0 写成递推公式 1.5 减少运算误差若干原则 n knkk ab nkaxbb 0 1 ),2,1( 于是 ,这种多项式求值的算法称为秦九 韶算法 ,只做 n次乘法和 n次加法 ,程序实现简单 n bxP )( 1.5.5 控制递推公式中误差的传播 对于一个数学问题的求解往往有多种数值方法 在选择数值方法时，要注意所用的数值方法不应将 计算过程中难以避免的误差放大的较快，造成计算 结果完全失真。 例 13 计算积分 并估计误差 解 容易得到递推公式 )10,2,1,0(1010 ndxx xI n n 1.1ln)10l n (101 101 00 xdxxI 1.1ln)10l n (101 10100 xdxxI 10 110 110 1110 1010101010 101010 dxx xdxx xxdxx xxxdxx xI nnnnnnnn 1 1 0 11 0 1 101 1010 n nn I ndxx xdxx )10,2,1( n 即 为 nI 110 1 nn InI )10,2,1( n 则准确的理论递推式 实际运算的递推式 两式相减有 01 101 II *0*1 101 II )(10)(10 *0*00*11 IeIIII )(10)1()()10()(10)( *00* 222* 11* IIIIIIIIIe nnnnnnnnn 这就是说 ,若 与 的误差为 = - ,即 ，则误差的递推规律为 0I *0I )( *0Ie 0I *0I )( *0*00 IeII 于是 )(10)(10)(10)( * 010*82*9*10 IeIeIeIe 计算 时的误差被扩大了 倍 ,显然算法是 数值不稳定的。 如果将递推公式 变换一种形式 *10I 1010 110 1 nn InI 1010 1 1 n n I nI 准确的理论递推式 实际运算的递推式 从而有 1010 1 1 nn I nI 1010 1 * 1 n n I nI )(101 * 11 nnnn IIII )(10 )1()(10 1)(10 1 *222*11*00 nnn n IIIIIIII 即 )(10 1)(10 1)(10 1)( *1010*22*1*0 IeIeIeIe 于是有 则这个算法的误差传递规律为 10 )()( * 1 n n IeIe 即每计算一步的误差的绝对值是上一步的十分 之一，误差的传播逐步缩小，得到很好的控制，这 个算法是数值稳定的 本章小结 误差在数值计算中是不可避免的，误差的传播和 积累直接影响到计算结果的精度。在研究算法的同时 ，必须注重误差分析，使建立起来的算法科学有效。 按照误差产生的来源可分为模型误差 、 观测误差 ， 截断误差 、 和舍入误差等 。 误差的表示法有绝对误差和相对误差两种 。 在表示一个近似数时 ,要用到有效数字的概念 ,这 在数值计算中非常有用 ,有效数字是由绝对误差决定的 通常用函数的泰勒展开对误差进行估计 作业 习题一 1.11.5 1.81.10