数值计算方法ppt课件.ppt

数值计算方法,吕同富 康兆敏 方秀男,清华大学出版社,为什么要开设这个课呢？,在数学发展中，理论和计算是紧密联系的。现代计算机的出现为大规模的数值计算创造了条件，集中而系统的研究适用于计算机的数值方法变得十分迫切和必要。数值计算方法正是在大量的数值计算实践和理论分析工作的基础上发展起来的，它不仅仅是一些数值方法的简单积累，而且揭示了包含在多种多样的数值方法之间的相同的结构和统一的原理。数值算法是进行科学计算必不可缺少的起码常识；更为重要的是通过对它们的讨论，能够使人们掌握设计数值算法的基本方法和一般原理，为在计算机上解决科学计算问题打下基础。,科学素质：拓宽对21世纪科学的了解； 加深对数学思想的理解； 培养用数学思考世界的习惯数学能力：数学知识的运用能力； 对专业中问题建立数学求解方法与 实际计算能力 应用问题中数学创造性能力计算知识：常用算法的数学理论； 在“误差、存贮、速度”之下的实 际计算方法； 对结果的数值分析方法,数学分析(或微积分),高等代数,数学软件,学习数值计算方法的准备知识,我们先来看看学过的一些知识和问题：,如果：三次方程呢？ n次方程呢？,多项式次数一般超过5次，它的根一般已经不能用公式表示,X=?,X=?,非线性方程呢？,问题二：,方程的个数是3个,那如果是20个呢？,用什么方法解？,一般的呢？,我们在数学分析中学过：用克莱姆法则能解决,理论上很“漂亮”的Cramer法则 在计算机上并不适用！,n=20,问题三,求A的特征值和特征向量,求A的特征值和特征向量?,美国的人口普查每10年举行一次，下表列出了从1940年到1990年的人口（按千人计）,能否利用这些数据合理地估计人口的数量，比如1965年的人口，甚至2015年的人口。,两个例子,问题四,问题5 数值积分,第一章 绪 论,1.1 科学计算的一般过程,1.2 数值计算方法的研究内容和特点,1.3 计算过程的误差及其控制,研究求数学问题近似解的方法和过程,实际问题,数学模型,数值计算方法的理论,程序设计,上机计算求出结果,1.1 科学计算的一般过程,应用数学,计算数学,一个科学计算过程主要包括如下几个环节：,1.1.1 数学建模：将工程问题数学化,1.1.2 对数学问题给出数值计算方法,例1 求解线性方程组,求解二次方程,是数值问题,应用有关学科的知识和数学理论，将实际工程问题，用精炼准确的数学语言对其核心部分进行描述并给出数学模型，这一过程常称为数学建模。一个好的数学模型符合下列两个方面的要求：,1.数学模型能真实准确的反映实际工程问题的本质；,2.数学模型所用的数学算法能再计算机上实现,我们能给出怎样的算法？,什么样的算法才能是好算法呢？,1.算法的速度（算法的收敛速度）；,2.算法所得到结果的精确度；,3.算法所占用的计算机资源；,1.1.3 对数值计算方法进行程序设计,1.熟练掌握一门语言，比如c语言，c+，matlab, fortran,我们在以后用到的是matlab,将数值问题机器化,1.1.4 上机计算并分析结果,理论来源于实践，要应用的实践中去,数值模拟物理过程，分析计算结果的可靠性，必要时重复上述过程。,其中算法设计是数值计算的核心内容。数值计算方法针对来源于科学与工程中的数学模型问题，介绍计算机上常用的数值方法的算法设计思想并进行算法分析。,数值计算：常称为数值分析或计算数学或计算方法。 主要是研究如何运用计算工具（如计算 器、计算机等）去获得数学问题的数值 解的理论和方法。,实践表明：计算方法正在日趋明显地成为数学 与计算机科学的交叉科学。,对那些在经典数学中，用解析方法在理论上已作出解的存在，但要求出他的解析解又十分困难，甚至是不可能的这类数学问题，数值解法就显得不可缺少，同时又十分有效。,1.2 数值计算方法的研究内容与特点,数值计算研究内容：对如下五类问题探索数值求解 方法及其与算法有关的理论分析,(2) 数值逼近（各种函数逼近问题的数值解、数值积分和微分）,(5) 最优化理论和方法,(4) 偏微分方程数值解,(3) 常微分方程数值解法,(1) 数值代数（线性方程组、非线性方程及方程组的数值解法）,算法：从给定的已知量出发，经过有限次四则运算及规定的运算顺序，最后求出未知量的数值解，这样构成的完整计算步骤称为算法。,运算量(计算量)：,一个算法所需的乘除运算总次数,计算量是衡量一个算法好坏的重要指标!,数值计算的根本任务就是研究算法,研究数值算法的任务主要有：,(1) 构造计算机上可执行的算法,(2) 构造计算复杂性好的算法,(3) 构造可靠性好的数值方法,计算机上可执行的运算：,四则运算,逻辑运算,尽可能提高数值方法的计算速度和少占存贮空间。,选择或研制能达到“数值问题”要求的计算精度的数值方法，为此须研究数值问题的性态及数值方法的稳定性。,计算方法：把求解数学问题转化为按一定次序只 进行加、减、乘、除等基本运算 数值方法。,例 1.1.1 例如：计算3次多项式 的函数值,直接计算需要6次乘法，3次加法。如果作如下改变：,只有3次乘法，3次加法。这个算法称作：秦九绍算法。,例1.1.2 解线性方程组,其中，, 克兰姆(Cramer)法则：,运算量(乘除)：,高斯消元法(Gauss)：,运算量(乘除),Gauss: 3060次,Cramer:,理论上很“漂亮”的Cramer法则 在计算机上并不适用！,解：,可得算法：,具有以下的性质：,1.,2.,单调递减,3.,4.,将问题可算化的手段：将问题可算化是设计一个算 法的第一步,(1) 用有限维空间代替无限维空间,(2) 用有限过程代替无限过程,(3) 用简单问题代替复杂问题,(4) 扰动分析：估计误差或精度,1.3 计算过程中的误差及其控制,计算公式中的运算必须是在计算机上可执行的运算,参与运算的数必须是有限小数或整数,因此，数值方法中的取数和运算往往会出现误差，算得的结果（称为计算值）一般也为近似值。,在任何科学计算中，其解的精确性总是相对的，而误差则是绝对的。,数值方法中的计算公式及参与运算的数，都和数学中的一般情况有所不同，即,1.3.1、误差的种类及来源,一个物理量的真实值和我们算出的值（即计算值）往往存在差异，它们之差称为误差。,模型误差,在建立数学模型过程中，要将复杂的现象抽象归结为数学模型，往往要忽略一些次要因素的影响，而对问题作一些简化，因此数学模型和实际问题之间有一定的误差。,观测误差,在建模和具体运算过程中所用的数据往往是通过观察和测量得到的，受观测方式、仪器精度以及外部观测条件等多种因素限制，不可能获得精确值，由此而来产生的误差。,截断误差,由于计算机只能完成有限次算术运算和逻辑运算，因此要将有些需用极限或无穷过程进行的运算有限化，对无穷过程进行截断，这就带来误差。,例:,若将前若干项的部分和作为函数值的近似公式，由于以后各项都舍弃了，自然产生了误差,Taylor展开,舍入误差,在数值计算过程中还会遇到无穷小数，因计算机受到机器字长的限制，它所能表示的数据其位数只能是有限的，如按四舍五入规则取有限位数，由此引起的误差,另外还有过失误差，这类误差是由于模型错误或方法错误所引起的，一般可以避免。,结论：误差是不可避免的,经过大量的运算之后，积累的总误差有时会大得惊人，因此如何控制误差的传播也是数值方法的研究对象。,在种误差中，前种是客观存在的，后种是计算方法引起的。数学模型一旦建立，进入具体计算时所考虑和分析的就是截断误差和舍入误差。因此本课程只涉及这种误差。,在实际问题中求精确解是没有意义的，求近似解是正常的。问题是如何尽量减少误差，提高精度。,1.3.2、误差与有效数字,定义1.2,绝对误差限或误差限,显然,有时也表示为,且,用绝对误差来刻画近似值的精确程度是有限的，因为它没有反映出它相对于精确值的大小或它占精确值的比例。例如 两个量与它们的近似值 分别为,则有误差限,虽然 的3倍，但在1000内差3显然比10内差1更精确些。这说明一个近似值的精确程度除了与绝对误差有关外，还与精确值的大小有关，所以这是可以用相对误差来比较这两个近似数的准确度。,定义1.3,绝对误差和绝对误差限仅考虑了误差值本身的大小，没有考虑准确值的大小。为了能较好地反映近似值的精确程度，还应考虑准确值的大小。,绝对误差限,相对误差限,代替相对误差,代替相对误差限,往往未知,一个数的近似数往往是通过四舍五入的原则求得的，例如：,取以下近似数,可以发现每一个近似数的绝对误差限都不超过近似数末尾数的半个单位。如果一个近似数满足这个条件，就把这个近似数从末尾到第一位非零数字之间的所有数字叫做有效数字。,则分别得到这些近似数的绝对误差,为了给出近似数的表示方法，使之既能表示大小又能表示精度，引进有效数字的概念。,定义1.5 设数 的近似值可以表示为,。如果其绝对误差限为,则称近似数 x 具有 n 位有效数字。,其中 m 是整数， 是0到9 中的一个数字，而且,定理1.1,证明,下面的结果论述了相对误差与有效数字的关系,即,由于,而,例1.2.7,解,则相对误差满足,即应取4位有效数字，近似值的误差不超过0.1%.,1.3.3、误差的传播,1.误差分析的重要性,针对，设初始误差,针对 ，设初始误差,2、数据误差的传播,计算机主要是加、减、乘、除四则运算，经过四则运算后，误差会怎么样变化？,由于精确值与误差相差很小，其差可以认为是较小的增量，即可以把误差看作微分,1.3.4、误差的控制,1.简化计算步骤，减少运算次数,x255=x.x2.x4.x8.x16.x32.x64.x128 原先要做254次乘法现只需14次即可,(2) 作减法时应避免两个相近数相减,两个相近的数相减，会使有效数字的位数严重损失！,例1.2.10,用四位浮点数计算,解,只有一位有效数字,有效数字大量损失，造成相对误差扩大。,结果仍然有四位有效数字。,这说明了算法设计的重要性。在算法设计中，若可能出现两个相近数相减，则改变计算公式，如使用三角变换、有理化等等。,取右端的有限项近似代替左端。,说明,(3) 防止大数吃小数,主要由计算机的位数引起,计算机中数的计算特点：,加法先对阶，后运算，再舍入。,乘法先运算，再舍入。,不在计算机数系中的数做四舍五入处理。,作一个有效数字为4位的连加运算,而如果将小数放在前面计算,在作连加时，为防止大数吃小数，应从小到大进行相加，如此，精度将得到适当改善。当然也可采取别的方法。,例,(3) 避免小数作除数,其中,表示绝对误差,当|y|很小时，,很大,1.3.5 算法的稳定性,一种数值算法，如果其计算舍入误差积累是可控制的，则称其为数值稳定的，反之称为数值不稳定的。数值不稳定的算法没有实用价值。,不稳定的算法可能导致计算结果不可靠甚至严重失真。因此，在计算时，应该采用稳定的数值计算方法。,如把方程组的系数舍入成两位有效数字,它的精确解为x1 = -6.222. x2= 38.25 x3= -33.65.,例,求解线性方程组,其精确解为 x1=x2=x3=1.,若对方程组的系数和中间结果均取3位10进制有效数字，然后用Gauss消元法求解，得到计算解为：,显然，该计算解的精度较差。,同样用Gauss消元法求解方程组：,也取3位10进制有效数字，得到计算解为：,容易验证，它是方程组的精确解。,上述例子表明，数值问题计算解的精度，与数值问题本身的性态有关。,定义1.3.1 在数值问题中，如果输出数据对输入数据的扰动（如误差）很敏感，即若输入数据（如原始数据）有较小的变化，会引起输出数据（如计算解）的较大变化，称这类数值问题为病态问题或坏条件问题。非病态问题又称为良态问题。问题输出变量的相对误差与输入变量的相对误差的商称为问题的条件数,算法优劣的标准,从截断误差观点看，算法必须是截断误差小，收敛速 速要快。即运算量小，机器用时少。,从舍入误差观点看，舍入误差在计算过程中要能控 制，即算法的数值要稳定。,从实现算法的观点看，算法的逻辑结构不宜太复杂， 便于程序编制和上机实现.,设计算法时应遵循的原则,要具有数值稳定性，即能控制误差的传播。,避免大数吃小数，即两数相加时，防止较小的数加 不到较大的数上。,避免两相近的数相减，以免有效数字的大量丢失。,避免分母很小或乘法因子很大，以免产生溢出。,