数值分析-1(重庆大学本科版)

1、1第1章 绪论计算方法/数值计算胡小兵胡小兵E-mail: 重庆大学数学与统计学院重庆大学数学与统计学院2主要内容主要内容q 了解算法的概念和特征；了解算法的概念和特征；q 理解误差、相对误差、有效数字的基本概念；理解误差、相对误差、有效数字的基本概念；q 理解误差传播及其避免方法。理解误差传播及其避免方法。3算法算法是对问题求解过程的一种描述，是为解决一个或一类是对问题求解过程的一种描述，是为解决一个或一类问题给出的一个确定的、有限长的操作序列。问题给出的一个确定的、有限长的操作序列。q 算法的算法的5个性质：个性质：算法及其性质算法及其性质l有穷性有穷性： 对于任意一组合法的输入值，在执行

2、对于任意一组合法的输入值，在执行有穷步骤之后一定能结束。即算法中的操作步骤有穷步骤之后一定能结束。即算法中的操作步骤为有限个，且每个步骤都能在有限时间内完成。为有限个，且每个步骤都能在有限时间内完成。 4算法的算法的5个性质个性质l确定性确定性： 确定性表现在对算法中每一步的描述确定性表现在对算法中每一步的描述都没有二义性，只要输入相同，初始状态相同，都没有二义性，只要输入相同，初始状态相同，则无论执行多少遍，所得结果都应该相同。则无论执行多少遍，所得结果都应该相同。l可行性可行性： 算法中的所有操作都可以通过已经算法中的所有操作都可以通过已经实现的基本操作运算有限次来实现。实现的基本操作运算

3、有限次来实现。5算法的算法的5个性质个性质l有输入有输入： 作为算法加工对象的量值，通常体现作为算法加工对象的量值，通常体现为算法中的一组变量。为算法中的一组变量。l有输出有输出： 它是一组与它是一组与“输入输入”有确定关系的量有确定关系的量值，是算法进行信息加工后得到的结果，这种确值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。定关系即为算法的功能。6算法常用描述形式（算法常用描述形式（1） l数学公式数学公式与与文字说明描述文字说明描述： 这种方式符合人们这种方式符合人们的理解习惯，和算法的推证相衔接，易于学习接的理解习惯，和算法的推证相衔接，易于学习接受，但不方便转换成程

4、序语言。受，但不方便转换成程序语言。l框图描述框图描述： 这种方式描述计算过程流向清楚，这种方式描述计算过程流向清楚，易于编制程序，但对初学者有一个习惯过程。此易于编制程序，但对初学者有一个习惯过程。此外框图描述格式不统一，详略难以掌握。外框图描述格式不统一，详略难以掌握。7算法常用描述形式算法常用描述形式(2) l伪代码描述伪代码描述： 它是表述算法的一种通用的语言，它是表述算法的一种通用的语言，有特定的表述程序和语句。它独立于计算机的硬有特定的表述程序和语句。它独立于计算机的硬件和软件系统，可以很容易地转换某种实用的计件和软件系统，可以很容易地转换某种实用的计算机高级语言，同时也具有一定的

5、可读性。算机高级语言，同时也具有一定的可读性。l程序语言描述程序语言描述： 用计算机语言描述的算法，即用计算机语言描述的算法，即计算机可直接运行算法。计算机可直接运行算法。 8数值型算法的基本特点数值型算法的基本特点(1) q无穷过程的无穷过程的截断截断： 例例1 1 计算计算 sin x的值的值，40,x 根据根据 Taylor 公式公式： 这是一个无穷级数，我们只能在适当的地方这是一个无穷级数，我们只能在适当的地方“截断截断”，使计算量不太大，而精度又能满足要求。，使计算量不太大，而精度又能满足要求。( 1.1)35721sin( 1)3!5!7!(21)!nnxxxxxxn LL9数值型

6、算法的基本特点数值型算法的基本特点(2) 如如计算计算 sin 0.5，取，取 n = 3479625.0!75.0!55.0!35.05.05.0sin753据泰勒余项公式，它的误差应为：据泰勒余项公式，它的误差应为：! 9) 1(99R4, 0( 1.2)791013.3362880)4/(R结果已相当精确结果已相当精确, ,实际上结果的六位数字都是正确的实际上结果的六位数字都是正确的。10数值型算法的基本特点数值型算法的基本特点(3) q连续过程的连续过程的离散化离散化：例例2 2 计算积分值计算积分值：1011dxxI将将0，1分为分为4等分，等分，分别计算分别计算4个小曲边梯形个小曲

7、边梯形的面积的近似值，然后的面积的近似值，然后加起来作为积分的近似加起来作为积分的近似值值(如图如图1-1).图1-111数值型算法的基本特点数值型算法的基本特点(4) 结果：结果：I0.697 024，与精确值与精确值0.693 147比较，可比较，可知结果不够精确，如进一步细分区间，精度可以知结果不够精确，如进一步细分区间，精度可以提高。提高。3 , 2 , 1 , 0,41iihxhihxfxfTiii2)()(130iiTI12 假定假定x0是是 的一个近似值，的一个近似值，x0 0 0 0，则则 也是也是 的一个近似值，且的一个近似值，且 x0 0 和和 两个近似值必有一个大于两个近

8、似值必有一个大于 ，另一个小于另一个小于 。数值型算法的基本特点数值型算法的基本特点(5) q迭代迭代计算：指某一简单算法的多次重复，后一次使计算：指某一简单算法的多次重复，后一次使用前一次的结果。这种形式易于在计算程序中实现，用前一次的结果。这种形式易于在计算程序中实现，在程序中表现为在程序中表现为“循环循环”过程过程.aa0 xa 例例3 3 不用开平方计算不用开平方计算 ( (a0)0)的值的值. .a0 xaaa13数值型算法的基本特点数值型算法的基本特点(6) 如计算如计算 ，取取 x0 = 2= 2，有：有：3可以设想它们的平均值应为的更好的平均值，于是设计下面可以设想它们的平均值

9、应为的更好的平均值，于是设计下面的算法：的算法：计算有计算有：x0 0=2=2 x1 1=1.75=1.75 x2 2=1.732 142 9=1.732 142 9 x3 3=1.732 050 8=1.732 050 8 kkkxaxx211(k = 0,1,2,) (1.8)kkkxxx3211(k = 0,1,2,)14误差误差 是人们用来描述数值计算中近似解的精确程度，是科是人们用来描述数值计算中近似解的精确程度，是科学计算中的一个十分重要的概念。学计算中的一个十分重要的概念。q 误差的来源误差的来源误差误差l 从实际问题中抽象出数学模型从实际问题中抽象出数学模型 模型误差模型误差l

10、 通过测量和实验得到模型中的各种数据通过测量和实验得到模型中的各种数据 测量误差测量误差由于由于模型误差模型误差与与测量误差测量误差不是计算过程中产生的，所以在不是计算过程中产生的，所以在数值计算中主要考虑数值计算中主要考虑截断误差截断误差和和舍入误差舍入误差对计算结果的对计算结果的影响。影响。15误差的来源误差的来源l截断误差（方法误差）截断误差（方法误差）：数学模型常难于直接求：数学模型常难于直接求解，往往要近似替代，简化为易于求解的问题，这解，往往要近似替代，简化为易于求解的问题，这种简化带入误差称为种简化带入误差称为截断误差截断误差或或方法误差方法误差。l舍入误差舍入误差：计算机只能处

11、理有限数位的小数运：计算机只能处理有限数位的小数运算，初始参数或中间结果都必须进行四舍五入运算，初始参数或中间结果都必须进行四舍五入运算，这必然产生舍入误差。算，这必然产生舍入误差。误差分析是一门比较艰深的专门学科。当发现计算结果与实际不符误差分析是一门比较艰深的专门学科。当发现计算结果与实际不符时，一个训练有素的计算工作者应当能诊断出误差的来源，并采取时，一个训练有素的计算工作者应当能诊断出误差的来源，并采取相应的措施加以改进，直至建议对模型进行修改相应的措施加以改进，直至建议对模型进行修改.16q误差与误差限误差与误差限误差的基本概念误差的基本概念定义定义1.1 设设 x* 是准确值，是准

12、确值，x 是它的一个近似值，是它的一个近似值，称称 e =x - x* 为近似值为近似值x的的绝对误差绝对误差，简称，简称误差误差。绝对误差：绝对误差：*exxx 近似值近似值 x* 精确值精确值l 可能取正，也可能取负，与x同量纲。l 越小越具有参考价值。l 但却不能很好地表示近似值的精确程度。但却不能很好地表示近似值的精确程度。17误差的基本概念误差的基本概念误差一般无法准确计算，只能根据测量或计算情误差一般无法准确计算，只能根据测量或计算情况估计出它的绝对值的一个上限，这个上界称为况估计出它的绝对值的一个上限，这个上界称为近似值近似值 x 的的误差限误差限，记为，记为 |x - x*|，

13、其意义是：，其意义是：x-x*x+在工程中常记为：在工程中常记为： x*= x。如如 L = 10.20.05mm，R = 150010018相对误差与相对误差限相对误差与相对误差限 绝对误差绝对误差不能完全刻画近似值的精度，还不能完全刻画近似值的精度，还应考虑被测值的大小。应考虑被测值的大小。定义定义1.2 ： 误差误差 e 与精确值与精确值 x*的比值的比值称为称为 x 的的相对误差相对误差。即：。即：*rexxexxl无量纲，常用百分比表无量纲，常用百分比表示，可正可负示，可正可负。l不能准确计算，而是用不能准确计算，而是用相对误差限来估计相对误差限来估计。19相对误差限相对误差限*|r

14、rxxexxl 若存在正数若存在正数 r，使得，使得 |er| r，则称，则称 r 为为相对误差限相对误差限l 实际上由于实际上由于 x* 不知道，用上式无法确定不知道，用上式无法确定r ，常用常用 x 代代x* 作分母，此时作分母，此时：|rx20相对误差限相对误差限-举例举例例例5 若测得高速段路长为若测得高速段路长为25001m，课桌，课桌长为长为1201cm，则，则 显然后者比前者相对误差大。显然后者比前者相对误差大。(1)10.04%2500r(2)10.83%120rl 近似值的精确程度取决于近似值的精确程度取决于 相对误差相对误差 的大小。的大小。l 实际计算中我们所能得到的是实

15、际计算中我们所能得到的是 误差限误差限 或或 相对误差限。相对误差限。21有效数字有效数字有效数字：有效数字：如果近似值如果近似值 x 的误差限的误差限是它某一数位的是它某一数位的半个单位，我们就说半个单位，我们就说 x 准确到该位，从这一位起直到前面准确到该位，从这一位起直到前面第一个非零数字为止的所有数字称第一个非零数字为止的所有数字称 x 的有效数字。的有效数字。 如：如：x=0.a1a2an10m，其中其中a1，a2，an是是09之中的整数，且之中的整数，且a10。如。如e=|x-x*|=0.510m-l，1 ln，则称，则称 x 有有 l 位有效数字位有效数字. 如：如：=3.141

16、59265则则3.14和和3.1416分别有分别有3位和位和5位有效数字。而位有效数字。而3.143相对于相对于也只能有也只能有3位有效数字位有效数字.22有效数字有效数字例：例： = 3.14159265 ，近似值，近似值 x1 = 3.1415，x2 = 3.1416问：问：x1, x2 分别有几位有效数字？分别有几位有效数字？例：例：写出下列各数的具有写出下列各数的具有 5 位有效数字的近似值位有效数字的近似值 187.9325，0.03785551，8.000033答案：答案：187.93，0.037856，8.0000答案：答案：4，5注：数字末尾的注：数字末尾的 0 不可以随意添加

17、或省略！不可以随意添加或省略！23有效数字有效数字在更多的情况，我们不知道准确值在更多的情况，我们不知道准确值 x*。如果我们认为计算。如果我们认为计算结果各数位可靠，将它四舍五入到某一位，这时结果各数位可靠，将它四舍五入到某一位，这时从这一位起从这一位起到前面第一个非零数字共到前面第一个非零数字共 l 位，它与计算结果之差必小于该位，它与计算结果之差必小于该位的半个单位位的半个单位.我们习惯上说将计算结果保留我们习惯上说将计算结果保留 l 位有效数字位有效数字。 定理定理1.11.1 设近似值设近似值 x = 0.a1a2an10m有有n位有效数字，则其位有效数字，则其相对误差限相对误差限:

18、111021nra24有效数字有效数字定理定理1.21.2 设近似值设近似值 x=0.a1a2an10m的的相对误差限为相对误差限为:111102(1)nra 则它则它至少至少有有 n 位有效数字。位有效数字。有效位数越有效位数越多，相对误多，相对误差限越小差限越小25定理定理1.2 证明证明*| 0.5 10m nxx证明：证明：显然显然 | x |(a1+1)10m - 1*1111|1|10(1) 10|2(1)nmxxxxxaxa 由定义由定义1.3知知 x 有有 n 位有效数字位有效数字。26例子例子例例 计算计算 sin(1.2)，问要取几位有效数字才，问要取几位有效数字才能保证相

19、对误差限不大于能保证相对误差限不大于0.01%解关于解关于n的不等式：的不等式： 10-n1810-5 = 1.810-4所以取所以取 n = 4，即可满足要求。，即可满足要求。解解 sin1.2=0.93，故，故a1=9, m=041110%01. 01021nra27设计数值型算法的基本原则设计数值型算法的基本原则 对函数对函数 f(x) 的计算：设的计算：设 x 是是 x * 的近似值，则结果误差的近似值，则结果误差:用泰勒展式分析用泰勒展式分析 ，将，将 f(x*) Taylor展开：展开：2)*()()*)()(*)(2xxfxxxfxfxf *)()()(xfxfxfeq函数计算的

20、误差传播函数计算的误差传播28设计数值型算法的基本原则设计数值型算法的基本原则 2*)()(*)()(2xxfxxxfxfe )(|2)(|)(| )(|)(|2xfxxfxfe 忽略第忽略第2 2项高阶无穷小之后，可得函数项高阶无穷小之后，可得函数f f( (x x) )的误差限估的误差限估计式：计式：)(| )(|)(|xxfxfe（1.10）29设计数值型算法的基本原则设计数值型算法的基本原则 四则运算可以看作是二元函数运算，按公式四则运算可以看作是二元函数运算，按公式(1.10)(1.10)易易得近似数作四则运算后的误差限公式得近似数作四则运算后的误差限公式: :)()()(2121x

21、xxx)(|)(|)(122121xxxxxx22122121)(|)(|xxxxxxx)11. 1 ()12. 1 ()13. 1 (其中其中(1.11)取等号，是因为作为多元函数，加减法的一次取等号，是因为作为多元函数，加减法的一次函数，泰勒展开没有二次余项。函数，泰勒展开没有二次余项。30例子例子例例5：若电压若电压V=220 5V，电阻电阻R=300 10 ，求电流求电流 I 并并计算其计算其误差限误差限及及相对误差限相对误差限。)(0411. 090000530010220)(|)(|)(2ARVRRVI所以所以)(0411. 07333. 0AI0.0411( )5.6%0.7333rI2200.7333( )300VIAR解：解：31四则运算中误差的传播四则运算中误差的传播1. 避免两个相近的数相减避免两个相近的数相减说明说明：造成有效数字在算法中突然变少，相对误差在这：造成有效数字在算法中突然变少，相对误差在这一步的突然扩大。一步的突然扩大。解解 原式原式 = 0.1318= 0.13181010-2 -2 - 0.1316- 0.13161010-2 -2 = 0.2= 0.21010-5 -5 。 原式原式= =就得到就得到4 4位有效数字的