数值计算与最优化(lecture1)计算方法第一章

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数值计算与最优化原理,主讲教师：白敏茹 副教授,Email:minru-,Tel：,要求,:,1.课前预习和课后复习,并及时完成课后作业.（掌握构造方法的原理和思想）,2.课余将书本上的程序进行上机计算,掌握并熟练运用Matlab进行数值计算。（掌握运用数值计算方法在计算机上解决各类工程问题）,课程成绩,：,平时成绩（含考勤、作业及平时表现）30%,期末考试成绩 70%,$1.1 引,言,第一章,三大科学方法：,理论研究、科学实验、科学计算,科学计算核心技术：数值计算技术和计算机技术,计算数学、图像处理、统计分析、计算机仿真。,科学计算包含：,一个科学计算过程主要包括如下几个环节：,(1)数学建模,：将工程问题数学化,工程中的数学模型一般可分为三类：,(2)算法设计,：将数学问题数值化(指标：速度和精度),连续型（确定型）,离散型（统计型）,不确定型（随机型）,本书重点讨论,例,求解线性方程组,求解二次方程,是数值问题,求解微分方程,不是数值问题,将其变成数值问题，即将其“离散化”,“离散化”是将非数值问题的数学模型化为数值问题,的主要方法，这也是计算方法的任务之一,(3)程序设计,：将数值问题机器化,实现要求：,最简练的计算机语言,最快的速度,最少的存储空间,(4)上机计算并分析结果,：数值模拟物理过程，分析计算结果的可靠性，必要时重复上述过程。,其中,算法设计,是数值计算的,核心内容,。数值计算方法针对来源于科学与工程中的数学模型问题，介绍计算机上常用的数值方法的算法设计思想并进行算法分析。,数值计算：,常称为,数值分析,或,计算数学,或,计算方法,。,主要是研究如何运用计算工具（如计算,器、计算机等）去获得数学问题的,数值,解,的理论和方法。,实践表明：计算方法正在日趋明显地成为数学,与计算机科学的,交叉科学,。,对那些在经典数学中，用解析方法在理论上已作出解的存在，但要求出他的解析解又十分困难，甚至是不可能的这类数学问题，数值解法就显得不可缺少，同时又十分有效。,1.2 数值计算方法的研究内容,边缘科学：,计算物理，计算力学，计算化学，,计算生物学，计算经济学等。,算法,：,从给定的已知量出发，经过有限次四则运算及,规定的运算顺序，最后求出未知量的数值解，这样构,成的完整计算步骤称为算法。,运算量,(计算量),：,一个算法所需的乘除运算总次数,计算量是衡量一个算法好坏的重要指标!,数值计算的根本任务就是研究算法,研究数值算法的任务主要有：,(1)构造计算机上可执行的算法,(2)构造计算复杂性好的算法,(3)构造可靠性好的数值方法,计算机上可执行的运算：,四则运算,逻辑运算,尽可能提高数值方法的计算速度和少占存贮空间。,选择或研制能达到“数值问题”要求的计算精度的数值方法，为此须研究数值问题的性态及数值方法的稳定性。,计算方法：把求解数学问题转化为按一定次序只,进行加、减、乘、除等基本运算,数值方法。,例,已知,a,0,a,1,a,2,a,n,x,计算多项式：,直接计算,：,运算量,（乘法）,秦九韶算法,（1247年）：,运算量,：,例,解线性方程组,其中，,克兰姆(Cramer)法则,：,运算量,(乘除)：,高斯消元法(Gauss),：,运算量,(乘除),Gauss:,3060次,Cramer:,理论上很“漂亮”的Cramer法则,在计算机上并不适用！,数值计算研究内容：,对如下五类问题探索数值求解,方法及其与算法有关的理论分析,(2),数值逼近（各种函数逼近问题的数值解、数值积分和微分）,(5),最优化理论和方法,(4),偏微分方程数值解,(3),常微分方程数值解法,(1),数值代数（线性方程组、非线性方程及方程组的数值解法）,将问题可算化的手段：,将问题可算化是设计一个算,法的第一步,(1),用有限维空间代替无限维空间,(2),用有限过程代替无限过程,(3),用简单问题代替复杂问题,(4),扰动分析：估计误差或精度,1.3 计算过程中的误差及其控制,计算公式中的运算必须是在计算机上可执行的运算,参与运算的数必须是有限小数或整数,因此，数值方法中的取数和运算往往会出现误差，算得,的结果（称为计算值）一般也为近似值。,在任何科学计算中，其解的精确性,总是相对的，而误差则是绝对的。,数值方法中的计算公式及参与运算的数，都和数学中的,一般情况有所不同，即,一、误差的种类及来源,一个物理量的真实值和我们算出的值（即计算值）往往存在差异，它们之差称为,误差,。,模型误差,在建立数学模型过程中，要将复杂的现象抽象归结为数学模型，往往要忽略一些次要因素的影响，而对问题作一些简化，因此数学模型和实际问题之间有一定的误差。,观测误差,在建模和具体运算过程中所用的数据往往是通过观察和测量得到的，,受观测方式、仪器精度以及外部观测条件等多种因素,限制,，不可能获得精确值，由此而来产生的误差,。,截断误差,由于计算机只能完成有限次算术运算和,逻辑运算，因此要将有些需用极限或无,穷过程进行的运算有限化，对无穷过程,进行截断，这就带来误差。,例:,若将前若干项的部分和作为函数值的近似公式，,由于以后各项都舍弃了，自然产生了误差,Taylor展开,舍入误差,在数值计算过程中还会遇到无穷小数，因,计算机受到机器字长的限制，它所能表示,的数据其位数只能是有限的，如按四舍五,入规则取有限位数，由此引起的误差,另外还有过失误差，这类误差是由于模型错误或方法,错误所引起的，一般可以避免。,结论：,误差是不可避免的,经过大量的运算之后，积累的总误差有时会大得惊,人，因此如何控制误差的传播也是数值方法的研究,对象。,在种误差中，前种是客观存在的，后种是计算方法引起的。数学模型一旦建立，进入具体计算时所考虑和分析的就是,截断误差和舍入误差。,因此本课程只涉及这种误差。,在实际问题中求精确解是没有意义的，求近似解是正常的。问题是如何尽量减少误差，提高精度。,二、误差和误差限,定义,绝对误差限或误差限,显然,有时也表示为,且,哪个更精确呢?,定义,绝对误差和绝对误差限仅考虑了误差值本身的大小，没,有考虑准确值的大小。为了能较好地反映近似值的精确,程度，还应考虑准确值的大小。,绝对误差限,相对误差限,代替相对误差,代替相对误差限,因此,往往未知,解,三、有效数字,定点数：,小数点的位置固定在个位数后。,机器数：,计算机中可表示的数。,为了提高精度，机器数通常是用,浮点数,表示的。,称为基数,称为尾数或数码,称为阶码,其中基数是正整数，一般取为，但为照顾习惯和书写方便，通常化为十进制数输入或输出。阶码是整数。,一定型号的计算机，尾数的位数t是固定的，称为,计算机,的位数,；阶码m也有一定的取值范围：,有4位有效数字,有6位有效数字,定义,有8位有效数字,只有,4,位有效数字！,由于计算机只能表示有限个数，故通常利用某种,舍入规则,(如,四舍五入,，截断误差等)，将数进行浮点化。因而势必产生舍入误差。,定理,证明,下面的结果论述了相对误差与有效数字的关系,即,则有,例,解,则相对误差满足,即应取4位有效数字，近似值的误差不超过0.1%.,四、误差的传播,1、数据误差的传播,由多元函数的Taylor展开公式可得，,的,绝对误差,为：,相对误差,为：,称为 f 的条件数，其绝对值的大小可反映函数值对数据的敏感程度,利用上面的误差估计公式，可以得到两个数的,和、差、积、商的误差估计,2、舍入误差的传播,因舍入导致的相对误差限仅与计算机的字长有关，通常,称相对误差限 为,计算机的相对精度,。,即,在计算机中，数需首先转化为机器数，比如浮点数，在,运算器中参与运算后仍需将运算结果转化成浮点数的形,式进行存储。,由上面的讨论可以看出，为了求得满意的计算解，在选,用计算公式和设计算法时，都应注意如下普遍原则：,(1)防止大数吃小数,主要由计算机的位数引起,选用算法应遵循的原则,计算机中数的计算特点：,加法先对阶，后运算，再舍入。,乘法先运算，再舍入。,不在计算机数系中的数做四舍五入处理。,作一个有效数字为4位的连加运算,而如果将小数放在前面计算,在作连加时，为防止大数吃小数，应,从小到大进行相加,，,如此，精度将得到适当改善。当然也可采取别的方法。,例,(2)作减法时应避免两个相近数相减,两个相近的数相减，会使有效数字的位数严重损失！,例,用四位浮点数计算,解,只有,一位有效数字,有效数字大量损失，造成相对,误差扩大。,结果仍然有,四位有效数字,。,这说明了算法设计的重要性。,在算法设计中，若可能出现两个相近数相减，则改变计算公式，如使用三角变换、有理化等等。,(3)避免小数作除数和大数作乘数,小数作除数或大数作乘数会产生溢出错误，因而产生大的误差。,在算法设计时，要避免这类情况在计算公式中出现。此时可以,根据一些具体情况,把某些算式改写成另一种等价的形式，,如,分母有理化等。,根据误差传播的估计式,3.,算法的稳定性,如前所述，由于各种误差的存在，计算机往往只能近似地求解实际问题，因而计算时会冒风险。,一、问题的性态,如把方程组的系数,舍入成两位有效数字,它的精确解为x,1,=-6.222.,x,2,=38.25,x,3,=-33.65.,例,求解线性方程组,其精确解为,x,1,=,x,2,=,x,3,=1.,若对方程组的系数和中间结果均取3位10进制有效数字，然后用Gauss消元法求解，得到计算解为：,显然，该计算解的精度较差。,同样用Gauss消元法求解方程组：,也取3位10进制有效数字，得到计算解为：,容易验证，它是方程组的精确解。,上述例子表明，数值问题计算解的精度，与数值问题本,身的性态有关。,定义,在数值问题中，如果输出数据对输入数据的,扰动（如误差）很敏感，即若输入数据（如原始数据）,有较小的变化，会引起输出数据（如计算解）的较大变,化，称这类数值问题为,病态问题,或,坏条件问题,。非病态,问题又称为,良态问题,。问题输出变量的相对误差与输入,变量的相对误差的商称为问题的,条件数,二、算法的稳定性与设计原则,例,计算定积分,解,一个程序往往要进行大量的四则运算才能得出结果，每一步的运算均可能会产生舍入误差。在大量计算中,舍入误差是积累还是能控制,这与算法有关。,误差放大,5千倍!,并假设计算过程中不产生新的舍入误差。,误差会放大,由公式,可推出：,显然算法不稳定。理论上成立的算法，在计算机上计算,时，由于初值的误差在计算过程中的传播，而导致结果,的失真，这是我们数值计算方法所要研究的。,(2)利用递推公式,误差不会放大,数值稳定，在运算过程中，舍入误差不增大。,定义,如果对于良态问题，在运算过程中,舍入误差,能控制在某个范围内的算法称之为,数值稳定的,算法,否则,就称之为,不稳定的,算法。,前面的例子说明，不稳定的算法可能导致计算结果不可,靠甚至严重失真。因此，在计算时，应该采用稳定的数,值计算方法。,算法优劣的标准,从,截断误差,观点看，算法必须是截断误差小，收敛速,速要快。即运算量小，机器用时少。,从,舍入误差,观点看，舍入误差在计算过程中要能控,制，即算法的数值要稳定。,从,实现算法,的观点看，算法的逻辑结构不宜太复杂，,便于程序编制和上机实现,.,设计算法时应遵循的原则,要具有数值稳定性,，即能控制误差的传播。,避免大数吃小数,，即两数相加时，防止较小的数加,不到较大的数上。,避免两相近的数相减,，以免有效数字的大量丢失。,避免分母很小或乘法因子很大,，以免产生溢出。,