数值计算方法ppt课件.ppt

《数值计算方法ppt课件.ppt》由会员分享，可在线阅读，更多相关《数值计算方法ppt课件.ppt（55页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、吕同富 康兆敏 方秀男清华大学出版社 在数学发展中，理论和计算是紧密联系的。现代计算机在数学发展中，理论和计算是紧密联系的。现代计算机的出现为大规模的数值计算创造了条件，集中而系统的研究的出现为大规模的数值计算创造了条件，集中而系统的研究适用于计算机的数值方法变得十分迫切和必要。数值计算方适用于计算机的数值方法变得十分迫切和必要。数值计算方法正是在大量的数值计算实践和理论分析工作的基础上发展法正是在大量的数值计算实践和理论分析工作的基础上发展起来的，它不仅仅是一些数值方法的简单积累，而且揭示了起来的，它不仅仅是一些数值方法的简单积累，而且揭示了包含在多种多样的数值方法之间的相同的结构和统一的原

2、理包含在多种多样的数值方法之间的相同的结构和统一的原理。数值算法是进行科学计算必不可缺少的起码常识；更为重。数值算法是进行科学计算必不可缺少的起码常识；更为重要的是通过对它们的讨论，能够使人们掌握设计数值算法的要的是通过对它们的讨论，能够使人们掌握设计数值算法的基本方法和一般原理，为在计算机上解决科学计算问题打下基本方法和一般原理，为在计算机上解决科学计算问题打下基础。基础。科学素质：拓宽对21世纪科学的了解； 加深对数学思想的理解； 培养用数学思考世界的习惯数学能力：数学知识的运用能力； 对专业中问题建立数学求解方法与 实际计算能力 应用问题中数学创造性能力计算知识：常用算法的数学理论； 在

3、“误差、存贮、速度”之下的实 际计算方法； 对结果的数值分析方法 数学分析数学分析( (或微积分或微积分) )高等代数高等代数数学软件数学软件学习数值计算方法的准备知识学习数值计算方法的准备知识我们先来看看学过的一些知识和问题：350 x5 / 3x 2 2 38 0 xx 1,233*34*2*( 8)2*2x 如果：三次方程呢？ n次方程呢？ 多项式次数一般超过5次，它的根一般已经不能用公式表示65323970 xxxxxX=?2320 xexxX=?非线性方程呢？问题二： 66821222321321321xxxxxxxxx 3342212321321321xxxxxxxxx 22033

4、12332321xxxxxx 23033123232321xxxxxxx方程的个数是3个那如果是20个呢？用什么方法解？一般的呢？11 11221121 1222221 122.nnnnnnnnnna xa xa xba xa xa xba xa xa xb我们在数学分析中学过：用克莱姆法则能解决,1,2, .iiAxinA121930.78(10/)19(20+1)! (20-1)5.1 10年次 秒理论上很理论上很“漂亮漂亮”的的CramerCramer法法则则 在计算机上并不适用！在计算机上并不适用！n=20问题三110201221A求A的特征值和特征向量1111.A.nnnnaaaa求

5、A的特征值和特征向量?美国的人口普查每美国的人口普查每10年举行一次，下表列出了从年举行一次，下表列出了从1940年到年到1990年的人口（按千人计）年的人口（按千人计）年年194019501960197019801990人口人口（千（千人）人）132165151326179323203302226542249633能否利用这些数据合理地估计人口的数量，比如能否利用这些数据合理地估计人口的数量，比如1965年的人口，年的人口，甚至甚至2015年的人口。年的人口。两个例子两个例子问题四问题问题5 数值积分数值积分2101201211010sin?,sin?cos?,1?,ln?xxdxxx dx

6、x dxdxxedx10120111010?,?cos?,?,?xxxdxx dxxdxe dxe dx第一章 绪 论1.1 科学计算的一般过程1.2 数值计算方法的研究内容和特点1.3 计算过程的误差及其控制研究求数学问题近似解的方法和过程研究求数学问题近似解的方法和过程实际问题数学模型数值计算方法的理论程序设计上机计算求出结果1.1 科学计算的一般过程科学计算的一般过程应用数学计算数学一个科学计算过程主要包括如下几个环节：一个科学计算过程主要包括如下几个环节：1.1.1 数学建模数学建模：将工程问题数学化1.1.2 对数学问题给出数值计算方法对数学问题给出数值计算方法例1 求解线性方程组b

7、Ax 求解二次方程02cbxax是数值问题cbabA,与系数常数项向量输入的数据是系数矩阵21,xxx 和方程的解输出的数据是解向量 应用有关学科的知识和数学理论，将实际工程问题，用精炼准确的数学语言对其核心部分进行描述并给出数学模型，这一过程常称为数学建模。一个好的数学模型符合下列两个方面的要求：1.数学模型能真实准确的反映实际工程问题的本质；2.数学模型所用的数学算法能再计算机上实现我们能给出怎样的算法？什么样的算法才能是好算法呢？1.算法的速度（算法的收敛速度）； 2.算法所得到结果的精确度；3.算法所占用的计算机资源；1.1.3 对数值计算方法进行程序设计对数值计算方法进行程序设计1.

8、熟练掌握一门语言，比如c语言，c+，matlab, fortran我们在以后用到的是matlab将数值问题机器化1.1.4 上机计算并分析结果理论来源于实践，要应用的实践中去 数值模拟物理过程，分析计算结果的可靠性，必要时重复上述过程。其中算法设计是数值计算的核心内容。数值计算方法针对来源于科学与工程中的数学模型问题，介绍计算机上常用的数值方法的算法设计思想并进行算法分析。 数值计算：数值计算：常称为数值分析数值分析或计算数学计算数学或计算方法计算方法。 主要是研究如何运用计算工具（如计算 器、计算机等）去获得数学问题的数值数值 解解的理论和方法。实践表明：计算方法正在日趋明显地成为数学 与计

9、算机科学的交叉科学交叉科学。 对那些在经典数学中，用解析方法在理论上已作出解的存在，但要求出他的解析解又十分困难，甚至是不可能的这类数学问题，数值解法就显得不可缺少，同时又十分有效。 数值计算研究内容：数值计算研究内容：对如下五类问题探索数值求解 方法及其与算法有关的理论分析(2) 数值逼近（各种函数逼近问题的数值解、数值积分和微分）(5) 最优化理论和方法(4) 偏微分方程数值解(3)(3) 常微分方程数值解法(1) 数值代数（线性方程组、非线性方程及方程组的数值解法）算法算法：从给定的已知量出发，经过有限次四则运算及规定的运算顺序，最后求出未知量的数值解，这样构成的完整计算步骤称为算法。运

10、算量运算量( (计算量计算量) )： 一个算法所需的乘除运算总次数计算量是衡量一个算法好坏的重要指标计算量是衡量一个算法好坏的重要指标! !数值计算的根本任务就是研究算法数值计算的根本任务就是研究算法 研究数值算法的任务主要有：研究数值算法的任务主要有：(1) 构造计算机上可执行的算法构造计算机上可执行的算法(2) 构造计算复杂性好的算法构造计算复杂性好的算法(3) 构造可靠性好的数值方法构造可靠性好的数值方法计算机上可执行的运算： 四则运算逻辑运算尽可能提高数值方法的计算速度和少占存贮空间。选择或研制能达到“数值问题”要求的计算精度的数值方法，为此须研究数值问题的性态及数值方法的稳定性。计算

11、方法：把求解数学问题转化为按一定次序只 进行加、减、乘、除等基本运算 数值方法。 例例 1.1.1 例如：计算例如：计算3次多项式次多项式 的函数值的函数值 0122333)(axaxaxaxp 直接计算需要直接计算需要6次乘法，次乘法，3次加法。如果作如下改变：次加法。如果作如下改变：0122333)(axaxaxaxp 0123)(axaxaxa 只有只有3次乘法，次乘法，3次加法。这个算法称作：次加法。这个算法称作：秦九绍算法。秦九绍算法。例例1.1.2 解线性方程组,Axb其中，1212(),( ,.,) ,( ,.,) .TTijn nnnAaxx xxbb bb 克兰姆(Crame

12、r)法则：,1,2, .iiAxinA 运算量(乘除)：(1)! (1)(1)! (1)nnnnn 高斯消元法(Gauss)：运算量(乘除)3211.33nnn2 0n 取Gauss: 3060次Cramer:121930.78(10/)19(20+1)! (20-1)5.1 10年次 秒理论上很理论上很“漂亮漂亮”的的CramerCramer法法则则 在计算机上并不适用！在计算机上并不适用！解：解：ndxxdxxxxIInnnnn15551011011 可得算法：可得算法：01ln6ln50.182315(1,2,.,20)nnIIInn计算积分计算积分20, 1 , 0510 ndxxxI

13、nn的递推关系式，并研究它的误差传递。的递推关系式，并研究它的误差传递。例例1.1.3具有以下的性质：0nI 1.2.nI单调递减3.lim0nnI4.5561 , 0nnnxxxxx 时时，)1(51)1(61 nInn 将问题可算化的手段：将问题可算化的手段：将问题可算化是设计一个算 法的第一步(1)(1) 用有限维空间代替无限维空间(2) 用有限过程代替无限过程(3) 用简单问题代替复杂问题(4) 扰动分析：估计误差或精度计算公式中的运算必须是在计算机上可执行的运算参与运算的数必须是有限小数或整数因此，数值方法中的取数和运算往往会出现误差，算得的结果（称为计算值）一般也为近似值。在任何科

14、学计算中，其解的精确性在任何科学计算中，其解的精确性总是相对的，而误差则是绝对的。总是相对的，而误差则是绝对的。数值方法中的计算公式及参与运算的数，都和数学中的一般情况有所不同，即1.3.1、误差的种类及来源一个物理量的真实值和我们算出的值（即计算值）往往存在差异，它们之差称为误差误差。模型误差在建立数学模型过程中，要将复杂的现象抽象归结为数学模型，往往要忽略一些次要因素的影响，而对问题作一些简化，因此数学模型和实际问题之间有一定的误差。观测误差在建模和具体运算过程中所用的数据往往是通过观察和测量得到的，受观测方式、仪器精度以及外部观测条件等多种因素限制，不可能获得精确值，由此而来产生的误差。

15、截断误差由于计算机只能完成有限次算术运算和逻辑运算，因此要将有些需用极限或无穷过程进行的运算有限化，对无穷过程进行截断，这就带来误差。231.2!3!xxxex 357sin.3!5!7!xxxxx234ln(1).2!3!4!xxxxx例:若将前若干项的部分和作为函数值的近似公式，由于以后各项都舍弃了，自然产生了误差Taylor展开舍入误差在数值计算过程中还会遇到无穷小数，因计算机受到机器字长的限制，它所能表示的数据其位数只能是有限的，如按四舍五入规则取有限位数，由此引起的误差3.14159265.21.414213562.110.166666666.3!61415927. 34142136

16、. 12 16666667. 0! 31另外还有过失误差，这类误差是由于模型错误或方法错误所引起的，一般可以避免。结论：误差是不可避免的误差是不可避免的经过大量的运算之后，积累的总误差有时会大得惊人，因此如何控制误差的传播也是数值方法的研究对象。在种误差中，前种是客观存在的，后种是计算方法引起的。数学模型一旦建立，进入具体计算时所考虑和分析的就是截断误差和舍入误差。因此本课程只涉及这种误差。在实际问题中求精确解是没有意义的，求近似解是正常的。问题是如何尽量减少误差，提高精度。1.3.2、误差与有效数字定义定义1.2 *xxx设为准确值， 为 的一个近似值。称*exx.x为近似值 的绝对误差，简

17、称误差*x因为准确值往往是未知甚至是无法知道的，*exx因此往往也无法求出。*exx而只能知道绝对值的某个上界，即*| |.exxx数值 称为近似值 的一个绝对误差限或误差限,简记为显然*xxx有时也表示为*xx0且152x 例：对于51000 y 用绝对误差来刻画近似值的精确程度是有限的，因为它用绝对误差来刻画近似值的精确程度是有限的，因为它没有反映出它相对于精确值的大小或它占精确值的比例。例没有反映出它相对于精确值的大小或它占精确值的比例。例如如 两个量与它们的近似值两个量与它们的近似值 分别为分别为*yx 和和yx和和31000,1000110,10* yyxx则有误差限则有误差限3,

18、1* yyxxyx 虽然虽然 的的3倍，但在倍，但在1000内差内差3显然比显然比10内差内差1更精确些。更精确些。这说明一个近似值的精确程度除了与绝对误差有关外，还与精这说明一个近似值的精确程度除了与绝对误差有关外，还与精确值的大小有关，所以这是可以用相对误差来比较这两个近似确值的大小有关，所以这是可以用相对误差来比较这两个近似数的准确度。数的准确度。xy 是是定义定义1.3 *0*xxx设为准确值， 为的一个近似值。称*rexxexxx为近似值 的相对误差。*rrxxeexxxr则称为近似值 的一个相对误差限。绝对误差和绝对误差限仅考虑了误差值本身的大小，没有考虑准确值的大小。为了能较好地

19、反映近似值的精确程度，还应考虑准确值的大小。r若存在正数满足| *|rx绝对误差限相对误差限*rexxexx*|rx代替相对误差代替相对误差限往往未知3.1415926.10.001.14159. 3,142. 3,14. 3321 一个数的近似数往往是通过四舍五入的原则求得的，例如：一个数的近似数往往是通过四舍五入的原则求得的，例如：取以下近似数取以下近似数 可以发现每一个近似数的绝对误差限都不超过近似数可以发现每一个近似数的绝对误差限都不超过近似数末尾末尾数的半个单位数的半个单位。如果一个近似数满足这个条件，就把这个近似。如果一个近似数满足这个条件，就把这个近似数从末尾到第一位非零数字之间

20、的所有数字叫做数从末尾到第一位非零数字之间的所有数字叫做有效数字有效数字。20.0004.30.000002.21021005. 0 310210005. 0 51021000005. 0 则分别得到这些近似数的绝对误差则分别得到这些近似数的绝对误差为了给出近似数的表示方法，使之既能表示大小又能表示精度，引进有效数字的概念。定义定义1.5 设数设数 的近似值可以表示为的近似值可以表示为120.10mnx *xnmxx 1021* 。如果其绝对误差限为。如果其绝对误差限为则称近似数则称近似数 x 具有具有 n 位有效数字。位有效数字。其中其中 m 是整数，是整数， 是是0到到9 中的一个数字，而

21、且中的一个数字，而且 ), 2 , 1(nii 01 定理定理1.1 *xx若 作为的近似值的表达式为12n10.10 ,0mxa aaa (1)rxn若 具有 位有效数字，则其相对误差限满足xn则 至少有 位有效数字。111102nra (2)rx反之，若 的相对误差满足111102(1)nra ，证明证明12n0.10mxa aa (1),xn当 有 位有效数字时 有*| |exx0.5 10m n下面的结果论述了相对误差与有效数字的关系*10.5 10|0.10m nrmxxexa111102na 111|102nra 即(2)rx若 的相对误差满足111102(1)nra ，由于|rx

22、而11| (1) 10mxa111111(1) 1010102(1)2mnm naa 例例1.2.7少取几位有效数字？，应至的相对误差不超过要使%1 . 020解解. 4201a的首位数是20.xn设的近似值 有 位有效数字1|*|0.5 10|0.nrxxexa则相对误差满足001. 0104211n%1 . 0097. 3n即应取4位有效数字，近似值的误差不超过0.1%.1.3.3、误差的传播1.误差分析的重要性误差分析的重要性115nnIIn11155nnIIn针对，设初始误差0()e I10()5 ().( 5)()nnne Ie Ie I 针对 ，设初始误差20()e I012020

23、11()( ).()5( 5)e Ie Ie I 2、数据误差的传播、数据误差的传播 计算机主要是加、减、乘、除四则运算，经过四则运算后，误差会怎么样变化？ 由于精确值与误差相差很小，其差可以认为是较小的增量，即可以把误差看作微分*ln*rexxdxxxdxedxxx 1.3.4、误差的控制、误差的控制1.简化计算步骤，减少运算次数x255255= =x.x2.2.x4.4.x8.8.x16.16.x32.32.x64.64.x128128 原先要做原先要做254254次乘法现只需次乘法现只需1414次即可次即可(2) 作减法时应避免两个相近数相减两个相近的数相减，会使有效数字的位数严重损失！

24、例例1.2.10用四位浮点数计算 76017591解解522102 .0101316.0101318.076017591只有一位有效数字,有效数字大量损失，造成相对误差扩大。56101734.0105768.01760759176017591结果仍然有四位有效数字。这说明了算法设计的重要性。在算法设计中，若可能出现两个相近数相减，则改变计算公式，如使用三角变换、有理化等等。很接近时，应用很接近时，应用和和如果如果21xx1122lnlnln.xxxx应应用用很很大大时时当当,x,111 xxxx一一般般情情况况，时时当当)()(*xfxf 可可用用泰泰勒勒展展开开 )(2)( )( )()(*

25、xxxfxxxfxfxf取右端的有限项近似代替左端。取右端的有限项近似代替左端。说说明明(3) 防止大数吃小数主要由计算机的位数引起计算机中数的计算特点：计算机中数的计算特点：加法先对阶，后运算，再舍入。乘法先运算，再舍入。不在计算机数系中的数做四舍五入处理。作一个有效数字为4位的连加运算4697. 0 ,4896. 0 ,4987. 01234. 0104吃了将小数大数而如果将小数放在前面计算4012. 04697. 04896. 04987. 01234. 01041234. 01041234. 0104012. 04697. 04896. 04987. 041236. 0104在作连加时

26、，为防止大数吃小数，应从小到大进行相加从小到大进行相加，如此，精度将得到适当改善。当然也可采取别的方法。 例例(3) 避免小数作除数2( )xydxxdydyy2( )( )( )xye xxe yeyy其中( )xey( )e x( )e y表示绝对误差当|y|很小时，( )xey很大算法的稳定性算法的稳定性 一种数值算法，如果其计算舍入误差积累是可控制一种数值算法，如果其计算舍入误差积累是可控制的，则称其为的，则称其为数值稳定的数值稳定的，反之称为，反之称为数值不稳定的数值不稳定的。数值不稳定的算法没有实用价值。数值不稳定的算法没有实用价值。不稳定的算法可能导致计算结果不可靠甚至严重失真。

27、因此，在计算时，应该采用稳定的数值计算方法。123123123111123611113234121114734560 xxxxxxxxx1231231230.500.331.80.500.330.251.10.330.250.200.78xxxxxxxxx如把方程组的系数舍入成两位有效数字它的精确解为x1 = -6.222. x2= 38.25 x3= -33.65.例例求解线性方程组其精确解为 x1=x2=x3=1.若对方程组的系数和中间结果均取3位10进制有效数字，然后用Gauss消元法求解，得到计算解为：1231.090.4880.491.xxx，123123132314254226xx

28、xxxxxx显然，该计算解的精度较差。同样用Gauss消元法求解方程组：也取3位10进制有效数字，得到计算解为：1239.001.006.00.xxx ，容易验证，它是方程组的精确解。上述例子表明，数值问题计算解的精度，与数值问题本身的性态有关。定义定义1.3.1 在数值问题中，如果输出数据对输入数据的扰动（如误差）很敏感，即若输入数据（如原始数据）有较小的变化，会引起输出数据（如计算解）的较大变化，称这类数值问题为病态问题或坏条件问题。非病态问题又称为良态问题。问题输出变量的相对误差与输入变量的相对误差的商称为问题的条件数算法优劣的标准算法优劣的标准从截断误差观点看，算法必须是截断误差小，收敛速 速要快。即运算量小，机器用时少。从舍入误差观点看，舍入误差在计算过程中要能控 制，即算法的数值要稳定。从实现算法的观点看，算法的逻辑结构不宜太复杂， 便于程序编制和上机实现.设计算法时应遵循的原则设计算法时应遵循的原则要具有数值稳定性，即能控制误差的传播。避免大数吃小数，即两数相加时，防止较小的数加 不到较大的数上。避免两相近的数相减，以免有效数字的大量丢失。避免分母很小或乘法因子很大，以免产生溢出。