数值计算与最优化lecture计算方法PPT课件

1、第1页/共49页要求:1. 课前预习和课后复习,并及时完成课后作业.（掌握构造方法的原理和思想）2. 课余将书本上的程序进行上机计算, 掌握并熟练运用Matlab进行数值计算。（掌握运用数值计算方法在计算机上解决各类工程问题）课程成绩：平时成绩（含考勤、作业及平时表现）30%期末考试成绩 70%第2页/共49页$1.1 引引 言言第一章三大科学方法：理论研究、科学实验、科学计算科学计算核心技术：数值计算技术和计算机技术计算数学、图像处理、统计分析、计算机仿真。科学计算包含：第3页/共49页一个科学计算过程主要包括如下几个环节：(1) 数学建模：将工程问题数学化工程中的数学模型一般可分为三类：(

2、2) 算法设计：将数学问题数值化(指标：速度和精度)连续型（确定型）离散型（统计型）不确定型（随机型）本书重点讨论例1.1.4 求解线性方程组bAx 求解二次方程02cbxax是数值问题cbabA,与系数常数项向量输入的数据是系数矩阵21,xxx 和方程的解输出的数据是解向量第4页/共49页求解微分方程0)0(32yxy不是数值问题xxy3,2函数但输出的不是数据而是输入的虽是数据将其变成数值问题，即将其“离散化”xxy32即将求函数nnxxxxyxyxy2121),(,),(),(改变成求函数值“离散化”是将非数值问题的数学模型化为数值问题的主要方法，这也是计算方法的任务之一第5页/共49页

3、(3) 程序设计：将数值问题机器化实现要求：最简练的计算机语言最快的速度最少的存储空间第6页/共49页(4) 上机计算并分析结果：数值模拟物理过程，分析计算结果的可靠性，必要时重复上述过程。其中算法设计是数值计算的核心内容。数值计算方法针对来源于科学与工程中的数学模型问题，介绍计算机上常用的数值方法的算法设计思想并进行算法分析。第7页/共49页 数值计算：常称为数值分析或计算数学或计算方法。 主要是研究如何运用计算工具（如计算 器、计算机等）去获得数学问题的数值 解的理论和方法。实践表明：计算方法正在日趋明显地成为数学 与计算机科学的交叉科学。 对那些在经典数学中，用解析方法在理论上已作出解的

4、存在，但要求出他的解析解又十分困难，甚至是不可能的这类数学问题，数值解法就显得不可缺少，同时又十分有效。第8页/共49页边缘科学：计算物理，计算力学，计算化学， 计算生物学，计算经济学等。算法：从给定的已知量出发，经过有限次四则运算及规定的运算顺序，最后求出未知量的数值解，这样构成的完整计算步骤称为算法。运算量( (计算量) )： 一个算法所需的乘除运算总次数计算量是衡量一个算法好坏的重要指标! !数值计算的根本任务就是研究算法第9页/共49页 研究数值算法的任务主要有：(1) 构造计算机上可执行的算法(2) 构造计算复杂性好的算法(3) 构造可靠性好的数值方法计算机上可执行的运算： 四则运算

5、逻辑运算尽可能提高数值方法的计算速度和少占存贮空间。选择或研制能达到“数值问题”要求的计算精度的数值方法，为此须研究数值问题的性态及数值方法的稳定性。计算方法：把求解数学问题转化为按一定次序只 进行加、减、乘、除等基本运算 数值方法。第10页/共49页例1.1.1 已知 a0, a1, a2 , an, x, 计算多项式：1110( ).nnnnp xa xaxa xa直接计算：运算量（乘法）1(1)2 1(1).2nnn n 秦九韶算法（1247年）：1210( )( ()nnnp xx xx a xaaaa10,1,2,1,0( )nnkkkbabbxa knnp xb运算量：. n第11

6、页/共49页例1.1.2 解线性方程组,Axb其中，1212(),( ,) ,( ,) .TTijn nnnAaxx xxbb bb 克兰姆(Cramer)法则：,1,2, .iiAxinA 运算量(乘除)：(1)! (1)(1)! (1)nnnnnn 高斯消元法(Gauss)：运算量(乘除)3211.33nnn2 0n 取Gauss: 3060次Cramer:121930.78(10/)19(20+1)! (20-1)5.1 10年次 秒理论上很“漂亮”的CramerCramer法则 在计算机上并不适用！第12页/共49页 数值计算研究内容：对如下五类问题探索数值求解 方法及其与算法有关的理

7、论分析(2) 数值逼近（各种函数逼近问题的数值解、数值积分和微分）(5) 最优化理论和方法(4) 偏微分方程数值解(3)(3) 常微分方程数值解法(1) 数值代数（线性方程组、非线性方程及方程组的数值解法）第13页/共49页 将问题可算化的手段：将问题可算化是设计一个算 法的第一步(1)(1) 用有限维空间代替无限维空间(2) 用有限过程代替无限过程(3) 用简单问题代替复杂问题(4) 扰动分析：估计误差或精度第14页/共49页计算公式中的运算必须是在计算机上可执行的运算参与运算的数必须是有限小数或整数因此，数值方法中的取数和运算往往会出现误差，算得的结果（称为计算值）一般也为近似值。在任何科

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

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

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

11、绝对误差，简称误差x因为准确值往往是未知甚至是无法知道的，*( )xxx因此往往也无法求出。*( )xxx而只能知道绝对值的某个上界，即*|( ) | |().xxxx*()xx数值称为近似值 的一个绝对误差限或误差限,简记为第20页/共49页显然*xxx有时也表示为*xx0且152x 例：对于51000 y15*x1000*y2)(*x5)(*y哪个更精确呢?吗？15*xx准确值的范围*( )xxxxyxy对于同一个准确值 而言，或 越小，近似值也就越精确。但是对不同的数 和 而言，误差 和误差限 的大小就不完全能反映出近似值和谁的近似程度好。第21页/共49页定义1.2.2 *0 xxx设

12、为准确值，为 的一个近似值。称*()()xxxxxx*x为近似值 的相对误差。*()()rrxxxxx*xr则称为近似值 的一个相对误差限。绝对误差和绝对误差限仅考虑了误差值本身的大小，没有考虑准确值的大小。为了能较好地反映近似值的精确程度，还应考虑准确值的大小。r若存在正数满足第22页/共49页| xr绝对误差限相对误差限*()()xxxxxx|*xr代替相对误差代替相对误差限15*x1000*y2)(*x5)(*y因此%33.13152)(*xr%5 . 010005)(*yr*x绝对误差用来衡量 的精度高低比较直观，但无法衡量精度的好坏；而相对误差用来衡量精度的好坏更合理。往往未知第23

13、页/共49页例1.2.1*2.718 281822.718 28.reee已知，其近似值为，求 的绝对误差限 和相对误差限解*ee 绝对误差82001000. 0|0.000 00182 002000. 061026102|*er28718. 2102628718. 2102661071. 0是唯一的并不和*r第24页/共49页三、有效数字定点数：小数点的位置固定在个位数后。机器数：计算机中可表示的数。为了提高精度，机器数通常是用浮点数表示的。x在计算机中，一般实数 均按舍入原则表示成：12( )0.,mtfl xa aa 称为 进制浮点数称为基数称为尾数或数码称为阶码第25页/共49页12,

14、011ta aa而只能是 ， ， ，中的数字。10( )afl x 时称为规格化浮点数。其中基数是正整数，一般取为，但为照顾习惯和书写方便，通常化为十进制数输入或输出。阶码是整数。一定型号的计算机，尾数的位数t是固定的，称为计算机的位数；阶码m也有一定的取值范围：12mmm( )0 xxxfl x因此，计算机存储或运算的数 其绝对值| |不能过大，否则计算机因“溢出”而停止计算；| |也不能过小，否则计算机自动令 ，得出难以预料的结果。第26页/共49页有4位有效数字有6位有效数字定义1.2.3 *|xxxxxxxxnn1设 为准确值，如果近似值 的误差限是10，即21| ( )|=|10，2

15、则称，并称的第一个非零数字位到小数点后n位的全部数字准确到小数点后n位的为有效数字。65592141. 359141. 3*142. 3*7592141. 3*有8位有效数字1415. 3*只有4位有效数字！由于计算机只能表示有限个数，故通常利用某种舍入规则(如四舍五入，截断误差等)，将数进行浮点化。因而势必产生舍入误差。第27页/共49页定理1.2.1 的近似值的表达式为作为若xx*1210.10 ,0kmxa aaa *(1)xn若 具有 位有效数字，则其相对误差 满足*xn则 至少有 位有效数字。11| (1/(2) 10na *(2)x反之，若 的相对误差 满足| 0.5 10n，证明

16、kmaaax10. 021*有位有效数字时有当,)1(*nx*| |xx nk105 . 0*10.10| 10kkax下面的结果论述了相对误差与有效数字的关系第28页/共49页 xx* xx*10.5 10|0.10knkxxxa111102na 111|102na 即*(2)x若 的相对误差 满足| 0.5 10n*|xxxk10n105 . 0k10n105 . 0nk105 . 0则有*xn至少有 位有效数字。第29页/共49页例1.2.7少取几位有效数字？，应至的相对误差不超过要使%1 . 020解. 4201a的首位数是.*20位有效数字有的近似值设nx*1|*|0.5 10| *

17、|0.nxxxa则相对误差满足001. 0104211n%1 . 0097. 3n即应取4位有效数字，近似值的误差不超过0.1%.第30页/共49页四、误差的传播1、数据误差的传播121212( ,),*,*,*nnnyf x xxx xxxxx设，的近似值为，12*( *,*,*)nyf xxx121( )*(,)()innixiyyyfxxxx12112( ,)( )( )( )( ,)innxiiinfx xxyyxxyf x xx由多元函数的Taylor展开公式可得，的绝对误差为：相对误差为：称为 f 的条件数，其绝对值的大小可反映函数值对数据的敏感程度第31页/共49页利用上面的误差

18、估计公式，可以得到两个数的和、差、积、商的误差估计121212211221212212121212121212121212()()(/)/()()(/)xxx xxxxxxxxxxxxxxxxx xxx 第32页/共49页2、舍入误差的传播( )( )txfl xfl x在字长为 的十进制计算机中，设 经四舍五入得到机器数，即浮点数，且的浮点表示形式为1( )0.5 105,|0.tfl x - xxxat| ( )|=10( )fl x为的一个相对误差限。121( )0.10(0),mtfl xa aaa 12( )( )ta aafl xtfl x则为的 位有效数字，且的相对误差满足因舍入

19、导致的相对误差限仅与计算机的字长有关，通常称相对误差限 为计算机的相对精度。5t10即5t10第33页/共49页( )(1),|5 10 .tfl xx在计算机中，数需首先转化为机器数，比如浮点数，在运算器中参与运算后仍需将运算结果转化成浮点数的形式进行存储。( )( )fl xxxx令，则有12xx设 ，为浮点数，则12121121221212312124()()(1),()()(1),()()(1),(/)(/)(1),fl xxxxfl xxxxfl x xx xfl xxxx|5 101,2,3,4.tii其中第34页/共49页由上面的讨论可以看出，为了求得满意的计算解，在选用计算公式

20、和设计算法时，都应注意如下普遍原则：(1) 防止大数吃小数主要由计算机的位数引起选用算法应遵循的原则计算机中数的计算特点：加法先对阶，后运算，再舍入。乘法先运算，再舍入。不在计算机数系中的数做四舍五入处理。第35页/共49页作一个有效数字为4位的连加运算4697. 0 ,4896. 0 ,4987. 01234. 0104吃了将小数大数而如果将小数放在前面计算4012. 04697. 04896. 04987. 01234. 01041234. 01041234. 0104012. 04697. 04896. 04987. 041236. 0104在作连加时，为防止大数吃小数，应从小到大进行相

21、加，如此，精度将得到适当改善。当然也可采取别的方法。 例第36页/共49页(2) 作减法时应避免两个相近数相减两个相近的数相减，会使有效数字的位数严重损失！例1.2.10用四位浮点数计算 76017591解522102 .0101316.0101318.076017591只有一位有效数字,有效数字大量损失，造成相对误差扩大。56101734.0105768.01760759176017591结果仍然有四位有效数字。这说明了算法设计的重要性。在算法设计中，若可能出现两个相近数相减，则改变计算公式，如使用三角变换、有理化等等。第37页/共49页(3) 避免小数作除数和大数作乘数( )y2112xx

22、21xxy对于21xxy 对于( )y2221121xxx|21xx或( )y|2x( )y小数作除数或大数作乘数会产生溢出错误，因而产生大的误差。在算法设计时，要避免这类情况在计算公式中出现。此时可以根据一些具体情况, 把某些算式改写成另一种等价的形式，如分母有理化等。根据误差传播的估计式第38页/共49页算法的稳定性如前所述，由于各种误差的存在，计算机往往只能近似地求解实际问题，因而计算时会冒风险。一、问题的性态第39页/共49页123123123111123611113234121114734560 xxxxxxxxx1231231230.500.331.80.500.330.251.1

23、0.330.250.200.78xxxxxxxxx如把方程组的系数舍入成两位有效数字它的精确解为x1 = -6.222. x2= 38.25 x3= -33.65.例求解线性方程组其精确解为 x1=x2=x3=1.第40页/共49页若对方程组的系数和中间结果均取3位10进制有效数字，然后用Gauss消元法求解，得到计算解为：1231.090.4880.491.xxx，123123132314254226xxxxxxxx显然，该计算解的精度较差。同样用Gauss消元法求解方程组：也取3位10进制有效数字，得到计算解为：1239.001.006.00.xxx ，容易验证，它是方程组的精确解。第41

24、页/共49页上述例子表明，数值问题计算解的精度，与数值问题本身的性态有关。定义1.3.1 在数值问题中，如果输出数据对输入数据的扰动（如误差）很敏感，即若输入数据（如原始数据）有较小的变化，会引起输出数据（如计算解）的较大变化，称这类数值问题为病态问题或坏条件问题。非病态问题又称为良态问题。问题输出变量的相对误差与输入变量的相对误差的商称为问题的条件数第42页/共49页二、算法的稳定性与设计原则例1.3.3101dxexeIxnn计算定积分7 , 2 , 1 , 0n解nI101xndexe101xnexe101dxexenxn11nnI0,I(1) 先计算721,III然后再计算一个程序往往要进行大量的四则运