《数值分析》》ppt课件

1、数数 值值 分分 析析理 学 院刘 秀 娟第第 1 1 章章 绪绪 论论1.1 1.1 数值分析的研讨数值分析的研讨对象对象l数值分析是近代数学的一个重要分支，它是研讨各种数学问题的数值解法，包括方法的构造和求解过程的实际分析。l在电子计算机成为数值计算的主要工具之后，那么要求研讨适宜于计算机运用的数值计算方法，为了更好地阐明数值分析的研讨对象，我们调查用计算机处文科学计算问题时阅历的几个过程： 提问：数值分析是做什么用的？提问：数值分析是做什么用的？ 提问：数值分析是做什么用的？提问：数值分析是做什么用的？选择数值选择数值计算方法计算方法程序设计程序设计上机计算上机计算求出结果求出结果构造数

2、构造数学模型学模型实实 际际 问问 题题l义务：数值分析的义务是提供在计算义务：数值分析的义务是提供在计算机上实践可行的，有可靠实际分析、机上实践可行的，有可靠实际分析、计算复杂性好的各种数值计算方法。计算复杂性好的各种数值计算方法。l特点：数值分析是与计算机及其它科特点：数值分析是与计算机及其它科学有亲密关系的数学课程，因此它即学有亲密关系的数学课程，因此它即具有纯数学的高度笼统性与严密科学具有纯数学的高度笼统性与严密科学性的特点，同时又具有运用广泛性与性的特点，同时又具有运用广泛性与数值实验的高度技术性，除此之外，数值实验的高度技术性，除此之外，它还有以下几个根本特点：它还有以下几个根本特

3、点： 1、采用、采用“构造性方法；构造性方法； 2、采用、采用“离散化方法；离散化方法； 3、采用、采用“递推化方法；递推化方法； 4、采用、采用“近似替代方法等等。近似替代方法等等。 研讨内容研讨内容l线性方程组的数值解线性方程组的数值解l矩阵特征值与特征向量计算矩阵特征值与特征向量计算l非线性方程的数值解非线性方程的数值解l数值逼近数值逼近l数值积分数值积分l常微、偏微的数值解常微、偏微的数值解 研讨方法研讨方法l实际分析实际分析l算法分析算法分析l误差分析误差分析l收敛性分析收敛性分析l收敛速度收敛速度 1.2 误差知识与算法知识误差知识与算法知识1.2.1 误差的来源与分类误差的来源与

4、分类 在工程技术的计算中，估计计算结在工程技术的计算中，估计计算结果的准确度是非常重要的任务，而影响果的准确度是非常重要的任务，而影响准确度的是各种各样的误差。误差的来准确度的是各种各样的误差。误差的来源是复杂的，但主要有以下四种：源是复杂的，但主要有以下四种： 从实践问题中笼统出数学模型从实践问题中笼统出数学模型 模型误差模型误差 ( Modeling Error ) 经过丈量得到模型中参数的值经过丈量得到模型中参数的值 观测误差观测误差 ( Measurement Error ) 求近似解求近似解 方法误差方法误差 (截断误差截断误差 ( Truncation Error ) ) 机器字长

5、有限机器字长有限 舍入误差舍入误差 ( Roundoff Error )模型误差模型误差l处置实践问题时，要建立数学模型，通常模型只处置实践问题时，要建立数学模型，通常模型只是近似的。由此产生的数学模型解与实践问题的是近似的。由此产生的数学模型解与实践问题的解解 之间的误差叫模型误差。之间的误差叫模型误差。l例如例如 l是实践问题的解，而假设数学模型的解是是实践问题的解，而假设数学模型的解是l由此产生的误差叫作模型误差。由此产生的误差叫作模型误差。8656sin,010yxxx656,010 ,yxx观测误差观测误差l数学模型中包含某些变量，如时间、长度、电压数学模型中包含某些变量，如时间、长

6、度、电压等，它们普通是经过观测来获得。由于观测得到等，它们普通是经过观测来获得。由于观测得到的数据与实践数据之间有误差，这种误差叫观测的数据与实践数据之间有误差，这种误差叫观测误差。误差。截断误差截断误差l求解数学模型所用的数值计算方法，假设是一种求解数学模型所用的数值计算方法，假设是一种近似的方法，只能得到模型的近似解，由此产生近似的方法，只能得到模型的近似解，由此产生的误差称为截断误差或方法误差。的误差称为截断误差或方法误差。舍入误差舍入误差l由于计算机的字长有限，参与运算的数据及其由于计算机的字长有限，参与运算的数据及其运算结果在计算机中存放会产生误差。这种误运算结果在计算机中存放会产生

7、误差。这种误差叫舍入误差或计算误差。差叫舍入误差或计算误差。l例如例如 在在 16 位微机上计算，单精度实数存放位微机上计算，单精度实数存放仅有仅有 7 位有效数字。在其上运算，会有位有效数字。在其上运算，会有l1 3 0.333 333 3, l(1.000 002)2 1.000 004 0,l后者的准确结果是后者的准确结果是 4 1012。dxex 102 近近似似计计算算: :例例大家一同猜？大家一同猜？ dxe2x1011 / e解法之一：将解法之一：将 作作Taylor展开后再积分展开后再积分2xe 91!4171!3151!21311)!4!3!21(10864210dxxxxx

8、dxe2xS4R4 ( Remainder ),104 Sdxe2x取取那那么么 111!5191!414R称为截断误差称为截断误差 ( Truncation Error ).005091!414.R 这这里里7430024010333014211013114.S 0010200050. | 舍入误差舍入误差 ( Roundoff Error ) |006000100050102.dxe-x 的的总总体体误误差差计计算算= 0.747 由截去部分由截去部分( excluded terms )引起引起由留下部分由留下部分( included terms )引起引起1.2.2 绝对误差、相对误差与

9、有效数字绝对误差、相对误差与有效数字 (Error and Significant Digits ) 定义定义 绝对误差绝对误差 (absolute error) ex x 10006074302.dxex例如：例如：其中其中 x 为准确值，为准确值，x* 为为 x 的近似值。的近似值。|e|的上界的上界记为记为e , 称为绝对误差限称为绝对误差限 (accuracy),工程上常记工程上常记为为 x = x* e .提问：绝对误差限的大小能否完全地提问：绝对误差限的大小能否完全地表示近似值的好坏？表示近似值的好坏？l例如：有两个量例如：有两个量l l 问：谁的近似程度要好一些？问：谁的近似程度

10、要好一些？l 51000,110yx思索定义定义 近似值近似值 x* 的相对误差的相对误差 (relative error).rexxexx.|rx定义定义 近似值近似值 x* 的相对误差上限的相对误差上限(界界) (relative accuracy).reex由于准确值由于准确值 x 未知未知, 实践上总把实践上总把 作为作为x*的的 相对误差，并且仍记为相对误差，并且仍记为er , 即即ex例例1 用最小刻度为毫米的卡尺丈量直杆甲用最小刻度为毫米的卡尺丈量直杆甲和直杆乙，分别读出长度为和直杆乙，分别读出长度为 a=312mm 和和 b=24mm，问：问：(a)，(b)， r(a)，r(b

11、)各是多各是多少？两直杆的实践长度少？两直杆的实践长度 x 和和 y 在什么范围在什么范围内？内？ 解：解：mmymmmmxmmbbbaaammbarr5 .245 .23,5 .3125 .311%,08. 2245 . 0)()( %,16. 03125 . 0)()( ,5 . 0)()( 例例2 设设 a=-2.18 ， b=2.1200 是分别由准确是分别由准确值值x和和y 经过四舍五入而得到的近似值，经过四舍五入而得到的近似值，问：问： (a)，(b)， r(a)，r(b) 各是多各是多少？少？解：解：%0024. 01200. 200005. 0)()( %,23. 018. 2

12、005. 0)()( 05000. 0)(,005. 0)(bbbaaabarr有效数字有效数字 ( significant digits) ( significant digits)四舍五入带来的绝对误差限四舍五入带来的绝对误差限 凡是由准确值凡是由准确值 x 经四舍五入而得到近似值经四舍五入而得到近似值 x*，其，其绝对误差限等于该近似值末位的半个单位。绝对误差限等于该近似值末位的半个单位。定义定义 有效数字有效数字 设设 x* 是数是数 x 的近似值，假设的近似值，假设 x* 的绝对误差限是的绝对误差限是它的某一位的半个单位，并且从该位到它的第一位它的某一位的半个单位，并且从该位到它的第

13、一位非零数字共有非零数字共有 n 位，那么称用位，那么称用 x* 近似近似 x 时，具有时，具有 n 位有效数字。位有效数字。用科学计数法，记用科学计数法，记其中其中 ,01 amnaa.ax10021* *| 0 5 10m nxx.假设假设 (即即 an 的截取按四舍五入的截取按四舍五入规那么规那么)，那么那么 x* 至少有至少有n 位有效数字，且准确到位有效数字，且准确到10m n.有效数字确实定方法有效数字确实定方法有效数字的位数有效数字的位数 n = 近似数科学记数法的幂指近似数科学记数法的幂指 数绝对误差限科学记数法的幂指数数绝对误差限科学记数法的幂指数.当差为负整数时，表示没有效

14、数字当差为负整数时，表示没有效数字! ! 把误差限把误差限表示为表示为0.50.510m10mn, n, 当指数当指数 m m n n 是最小是最小的整数时的整数时, , 有效数字的位数准确地是有效数字的位数准确地是 n. n.例例3 以下近似值的绝对误差限都是以下近似值的绝对误差限都是0.005， 问：各个近似值有几位有效数字？问：各个近似值有几位有效数字？41086. 0,0312. 0,38. 1cba3位：1，3，81位：30位3 14159265358979323 1416.;*.例例问：问： 有几位有效数字？请证明他的结论。有几位有效数字？请证明他的结论。* 证明：证明：。，and

15、位精确到小数点后第位有效数字有45105 . 0105 . 01031416. 05141 有效数字有效数字 相对误差限相对误差限121110 51010010201102mnnrmnn.x*.a aa.aa知知 x* 有有 n 位有效数字，那么其相对误差限为位有效数字，那么其相对误差限为 相对误差限相对误差限 有效数字有效数字1121111110|*| *|0102(1)10(1)100 5102(1)nmrnmmnxxx.a aaa.a111102(1)nra知知 x* 的相对误差限可写为的相对误差限可写为那么那么可见可见 x* 至少有至少有 n 位有效数字。位有效数字。有效数字与相对误差

16、的关系有效数字与相对误差的关系例：为使例：为使 * 的相对误差小于的相对误差小于0.001%, 至少应至少应取几位有效数字？取几位有效数字？解：假设解：假设 * 取到取到 n 位有效数字，那么其相对误差上限为位有效数字，那么其相对误差上限为111102nra要保证其相对误差小于要保证其相对误差小于0.001%，只需保证其上限满足，只需保证其上限满足111100.001%2nra知知 a1 = 3，那么从以上不等式可解得，那么从以上不等式可解得 n 6 log6，即即 n 6，应取，应取 * = 3.14159。1.2.3 函数求值的误差估计函数求值的误差估计问题一：对于函数问题一：对于函数 y

17、 = f (x) y = f (x)，假设用，假设用 x x* * 取代取代 x x， 将对将对 y y 产生什么影响？产生什么影响？分析：分析：e(y) = f (x) f (x*) e(x) = x x *= f ( )(x x *)x* 与与 x 非常接近时，可以为非常接近时，可以为 f ( ) f (x*) ，那么，那么有：有：|e(y)| | f (x*)|e(x)| (1) (2)即：即：x*产生的误差经过产生的误差经过 f 作用后被放大作用后被放大/减少了减少了| f (x*)|倍。故称倍。故称| f (x*)|为放大因子为放大因子 ( amplification factor

18、) 或或 绝对条件数绝对条件数 ( absolute condition number ).)( *)()(xxfy( )|( )|( *)re yeyf x( )|( ) |*re xexx( )( *)*( *)*( *)( )( *)rf xf xxxxxxf xxxfxe xf x相对误差条件数相对误差条件数 ( relative condition number) f 的条件数在某一点是小的条件数在某一点是小大，那么称大，那么称 f 在该点在该点是好条件的是好条件的 ( well-conditioned ) 坏条件的坏条件的 ( ill-conditioned )。)4()(!)()

19、()3()(!)()(,0)()()()()()()()1( kkkkkkakafyaekafyeaf，afafaf则有如果有问题二：对于问题二：对于n n 元函数元函数 将对将对 u u 产生什么影响？产生什么影响？，xaxxxfuiin的近似值是),(21，xaii代替用） 6（ )(), ,()(） 5（ )(),()(121121iniininiinaxaaafuaexaaafue问题三：四那么运算结果的误差估问题三：四那么运算结果的误差估计计 设设a,b a,b 分别是准确值分别是准确值x,y x,y 的近似值，的近似值，那么那么0,)()( . 3)()()( . 2)()()(

20、1.2bbabbabaabbaabbaba 设设a,b a,b 分别是准确值分别是准确值x,y x,y 的近似值，那么的近似值，那么)()( 7.)()()( 6.)()()( 5.)()()( 4.bababaabbabababababarrrrrrrr例例4 设有三个近似数设有三个近似数 a=2.31,b=1.93,c=2.24它们都有三位有效数字，试计算它们都有三位有效数字，试计算p=a+bc，并问：并问：p的计算结果能有几位有效数字？的计算结果能有几位有效数字？ 例例5 )()(ppr和?),()871.0,30.1 (.0005.0871.0,005.030.1,cos),(有几位有

21、效数字能则的近似值作为如果用设u，yxffuyxxyyxf(p) 0.025852位f(x,y) 0.495430.39%(u) 0.00220.005p 6.6332)(pr1.2.4 算法及其计算复杂性算法及其计算复杂性定义定义 算法算法 就是规定了怎样从输入数据计算出数就是规定了怎样从输入数据计算出数值问题解的一个有限的根本运算序列值问题解的一个有限的根本运算序列. 定义算法的计算复杂性定义算法的计算复杂性 是指在到达给定精度时是指在到达给定精度时,该算法所需的计算量和所占的内存空间该算法所需的计算量和所占的内存空间. 前者叫前者叫时间复杂性，后者叫空间复杂性时间复杂性，后者叫空间复杂性

22、.例子例子 计算下面多项式的值。输入数据为计算下面多项式的值。输入数据为ai和和x，输出数据为输出数据为 p(x) 的值。的值。iniixaxp0)(算法一算法一算法二秦九韶法算法二秦九韶法0001(1,2, ),( )kkknknsasa xp xsss10(1,2,1,0),( )nnkkkknnTaTxTap xTiniixaxp0)(12121012112102301210( ) =() = ()nnnnnnnnnnnnp xa xaxa xa xaa xaxa xa xaa xaxa x xaxa13210 = = ()nnaxaxa xaxaxa秦九韶法原理秦九韶法原理Tn=anT

23、n-1= xTn+an-1T0= xT1+a0T1= xT2+a1算法比较算法比较算法一算法一 所需乘法次数为所需乘法次数为 n(n+1)/2,n(n+1)/2,加法次数为加法次数为n n。 算法二算法二 所需乘法次数为所需乘法次数为n n，加法次数也为，加法次数也为n n。 两种算法所占内存空间根本一样。两种算法所占内存空间根本一样。算法二是算法二是12471247年我国数学家秦九韶初次提出年我国数学家秦九韶初次提出的。的。算法一算法一 逐个相乘要用逐个相乘要用254254次乘法。次乘法。算法二算法二 14 14次乘法。次乘法。例子 计算 的值。255x思索128643216842255xx

24、xxxxxxx算法比较1. 防止相近二数相减防止相近二数相减例：例：a1 = 0.12345a1 = 0.12345，a2 = 0.12346a2 = 0.12346，各有，各有5 5位有效位有效数字。数字。 而而 a2 a2 a1 = 0.00001 a1 = 0.00001，只剩下，只剩下1 1位有位有效数字。效数字。 几种阅历性防止方法：几种阅历性防止方法：;xxxx ;1lnlnln xxx当当 | x | 1 时：时：;2sin2cos12xx .6121112xxxex 设计算法时应遵照的一些原那么2. 防止小分母防止小分母 : 分母小会呵斥浮点溢出分母小会呵斥浮点溢出 ( ove

25、r flow )3. 防止大数吃小数防止大数吃小数例：用单精度计算例：用单精度计算 的根。的根。010)110(992 xx准确解为准确解为110291 x,x 算法算法1: 1: 利用求根公式利用求根公式aacbbx242 在计算机内，在计算机内，109存为存为0.11010，1存为存为0.1101。做加法。做加法时，两加数的指数先向大指数对齐，再将浮点部分相加。时，两加数的指数先向大指数对齐，再将浮点部分相加。即即1 的指数部分须变为的指数部分须变为1010，那么：，那么：1 = 0.0000000001 1010，取单精度时就成为：，取单精度时就成为： 109+1=0.100000001

26、010+0.00000000 1010=0.10000000 1010大数吃小数大数吃小数024,102422921 aacbbxaacbbx算法算法2:先解出先解出 再利用再利用9211024)( aacbbsignbx11010991221 xacxacxx例：按从小到大、以及从大到小的顺序分别计例：按从小到大、以及从大到小的顺序分别计算算1 + 2 + 3 + + 40 + 1094. 先化简再计算，减少步骤，防止误差积累。先化简再计算，减少步骤，防止误差积累。普通来说，计算机处置以下运算的速度为普通来说，计算机处置以下运算的速度为 exp ,5. 选用稳定的算法选用稳定的算法,控制舍入

27、误差的传播。控制舍入误差的传播。误差传播与积累误差传播与积累.210110,n,dxexeIxnn 例：计算例：计算11.nnIn I公式一：公式一：111111000011dd1d .nxnxnxnxnx exx en xexxexeee 留意此公式准确成立留意此公式准确成立, 由于由于 10011d1063212056 xIex.ee记为记为*0,I80000 5 10 .EII.那么初始误差那么初始误差 1101001111dd ,(1)1nnnnxexIxexIeee nn391414231519594249414122764807131632896000121030592000111

28、088128000101.367879440111415*13*14*12*13*11*12*10*11*9*10*0*1.II.II.II.II.II.II.II ? ! !What happened?!调查第调查第n步的误差步的误差nE| )1()1( |*11* nnnnnnInIIIE| !01En|Enn 1111(1)nnnnIn IIIn 公式公式方法：先估计一个方法：先估计一个IN ,IN ,再反推要求的再反推要求的 In ( n In ( n N )N )。(unstable algorithm), 我们有责任改动。我们有责任改动。 呵斥这种情况的是不稳定的算法呵斥这种情况的是不稳定的算法 迅速积累迅速积累, ,可见初始的小扰动可见初始的小扰动801050| .E误差呈递增误差呈递增. .调查反推一步的误差：调查反推一步的误差：|1)1 (1)1 (1|*1NNNNENININE 以此类推，对以此类推，对 n N 有：有：1|.(1).(1)nNEEN Nn误差逐渐递减误差逐渐递减, 这样的算法称为稳定的