数值计算方法_第一章数值计算方法的意义内容与方法.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数 值 计 算 方 法,陈研,chenyancau.,edu,.,cn,Tel:[phone],新学科综合楼,4-201,中国农业大学资源和环境学院,2005年9月,1,数值计算方法的意义、内容与方法,软件的核心就是算法。,20 世纪最伟大的科学技术发明-计算机,计算机是对人脑的模拟，它强化了人的思维智能；,计算机的发展和应用，已不仅仅是一种科学技术,现象，而且成了一种政治、军事、经济和社会现象；,没有软件的支持，超级计算机只是一堆废铁而已；,算法犹如乐谱，,软件犹如,CD,盘片，,而硬件如同,CD,唱机算法的研究和应用正是本课程的主题！,现代科学研究的三大支柱,理论研究,科学实验,科学计算,计算数学,21世纪信息社会的两个主要特征：,“,计算机无处不在,”,“,数学无处不在,”,21世纪信息社会对科技人才的要求：,-会,“,用数学,”,解决实际问题,-会用计算机进行科学计算,建立数学模型,选取计算方法,编写上机程序,计算得出结果,科学计算解题过程,一、,计算数学的产生和早期发展,计算数学是数学的一个古老的分支，虽然数学不仅仅,是计算，但推动数学产生和发展的最直接原因还是,计算问题,。,二、,二十世纪计算数学的发展,数值代数,最优化计算,数值逼近,计算几何,概率统计计算,蒙特卡罗方法,微分方程的数值解法,微分方程的反演问题,数值计算的主要内容,数值代数：方程求根、线性方程组求解、,特征值和特征向量的计算、,非线性方程组的求解；,数值逼近：插值、数值微分和积分、,最小二乘法；,微分方程数值解：,常微分方程数值解；,偏微分方程数值解：,差分法,有限元法,有限体积法,教材,数值计算方法 徐涛,编著（吉林科学技术出版社）,参考书目,应用,数值方法,使用,MATLAB,和,C,语言,Robert J.Schilling&Sandra L.Harris,（,机械工业出版社）,Numerical Recipes in C+,The Art of Scientific Computing Second Edition,William H.Press,等著,（电子工业出版社）,现代数值分析,李庆扬、易大义、王能超,编著,（高等教育出版社）,2,算 法,一、算法的概念,描述算法可以有不同的方式。例如，可以用日常语言,和数学语言加以叙述，也可以借助形式语言（算法语言）,给出精确的说明，也可以用框图直观地显示算法的全貌。,定义：由基本运算及运算顺序的规定所构成的完整的,解题步骤，称为,算法,。,例1：一群小兔一群鸡，两群合到一群里，要数腿共48，,要数脑袋整17，多少小兔多少鸡？,算术方法：,若,没有小兔，则鸡应是17只,总,腿数：21734,一只小兔增加 2条腿，,应该有,只,小兔,10只小鸡,代数方法：,设有,x,只小鸡，,y,只小兔，,(-2)*(,i)+(ii),得,只,小兔,高斯消去法,例：求解二元一次联立方程组,用行列式解法：首先判别,（1）,如果 ，则令计算机计算,输出计算的结果,x,1,，,x,2,。,（2）,如果,D,=,0，,则或是无解，或有无穷多组解。,是否为零，存在两种可能：,令,通过求解过程，可以总结出算法步骤如下：,S2,计算,S3,如果,则输出原方程无解或有无穷多组解的信息,;,否则,S1,输入,S4,输出计算的结果,输入,D=a,11,a,22,-a,12,a,21,D=0,开始,输出,x,1,x,2,结 束,No,输出无解信息,Yes,二、算法的优劣,计算量小,存贮量少,逻辑结构简单,例：用行列式解法求解线性方程组:,n,阶方程组，要计算,n,+1,个,n,阶行列式的值，,总共需要做,n,!(,n,-1)(,n,+1),次乘法运算。,n=20,需要运算多少次？,n=100?,一、,误差的背景介绍,1.,来源与分类,从实际问题中抽象出数学模型,模型误差,3,数值计算中的误差,例1:质量为,m,的物体，在重力作用下，自由下落，,其下落距离,s,与时间,t,的关系是：,（1.1）,其中,g,为重力加速度。,通过测量得到模型中参数的值,观测误差,求近似解 方法误差,(截断误差）,机器字长有限,舍入误差,用计算机、计算器和笔算，都只能用有限位小数,来代替无穷小数或用位数较少的小数来代替位数较多,的有限小数，如：,=3.1415926,x,=8.12345,四舍五入后,在,数值计算方法中，主要研究,截断误差,和,舍入误差,（包括初始数据的误差）对计算结果的影响！,二、绝对误差、相对误差和有效数字,1绝对误差与绝对误差限,例,2,:若用以厘米为最小刻度的尺去量桌子的长，,大约为,1.45,米，求,1.45,米的绝对误差。,1.45,米的,绝对误差=,？,不知道！,定义,1,：设,x,是准确值,，,x,*,为,x,的一个近似值,，称,是近似值,x,的,绝对误差,简称为,误差,。,（,1.5）,但实际问题往往可以估计出 不超过某个正数,，即，,，则称,为绝对误差限，有了绝对误差限,就可以知道,x,范围为,即,x,落在 内。在应用上，常常采用下列,写法来刻划,x,*,的精度。,2,相对误差和相对误差限,（,1.6）,定义2：,设,x,是准确值，,x,*,是近似值，称,满足,为近似值,x,的,相对误差,，相应地，若正数 ，,则称 为,x,的,相对误差限,。,3,有效数字,则说,x*,近似表示,x,准确到小数后第,n,位，并从这第,n,位起,直到最左边的非零数字之间的一切数字都称为,有效数字,，,并把有效数字的位数称为,有效位数,。,定义3：,如果,（,1.7）,由上述定义,有效数位为,3,位,有效数位为,5,位,有效数位为,4,位误差的传播与积累,例3：,蝴蝶效应,纽约的一只蝴蝶翅膀一拍，风和日丽的北京就刮起台风来了？！,NY,BJ,以上是一个病态问题,4,数值计算中应该注意的一些原则,1,要使用数值稳定的算法,例4：求,（,n,=0,1,2,8）,的值。,解：由于,初值,递推公式,（,1.8）,注意此公式,精确,成立,按,(1.8),式就可以逐步算出,What happened?!,不稳定的算法！,由递推公式,（1.8）,可看出，,I,n,-1,的误差扩大了,5,倍后传给,I,n,，,因而初值,I,0,的误差对以后各步计算结果的影响，随着,n,的增大,愈来愈严重。这就造成,I,4,的计算结果严重失真。,这就是误差传播所引起的危害,!,改变公式：,将,公式,变为,不妨设,I,9,I,10,，,于是由,可求得,I,9,0.017，,按公式,（1.9）,可逐次求得,（1.9）,I,8,0.019,I,7,0.021,I,6,0.024,I,8,0.028,I,4,0.034,I,3,0.043,I,2,0.058,I,1,0.088,I,0,0.182,稳定的算法！,在我们今后的讨论中，,误差,将不可回避，,算法的,稳定性,会是一个非常重要的话题。,2,要避免两个相似数相减,在数值计算中，两个相近的数作减法时有效数字会损失。,（,1.10）,的,值。,当,x,=1000,，,y,的准确值为,0.01580,1直接相减,2、,将,（1.10）,改写为,则,y,=0.01581,例,5:,求,类似地,2.,绝对值太小的数不宜作除数,例,6,：,如分母变为,0.0011,，也即分母只有,0.0001,的变化时,3.避免大数,吃,小数,例7：用单精度计算 的根。,精确解为,算法1：利用求根公式,在计算机内，10,9,存为0.1,10,10,，1存为0.1,10,1,。,做加法时，两加数的指数先向大指数对齐，再将浮点部分相加。即1 的指数部分须变为,10,10,，则：1=0.0000000001,10,10,，取单精度时就成为：,10,9,+1=0.10000000,10,10,+0.00000000 10,10,=0.10000000 10,10,算法,2,：先解出,注：,求和时从小到大相加，可使和的误差减小。,例8：按从小到大、以及从大到小的顺序分别计算,4.先化简再计算，减少步骤，避免误差积累。,一般来说，计算机处理下列运算的速度为,1+2+3+40+10,9,再利用,5.算法的,递推性,计算机上使用的算法常采用递推化的形式，递推,化的基本思想是把一个复杂的计算过程归结为简单过程,的多次重复。这种重复在程序上表现为循环。递推化的,优点是简化结构和节省计算量,。,多项式求值：,给定的,x,求下列,n,次多项多的值,。,解：,1,.用一般算法，即直接求和法；,2.,逐项求和法；,3,.秦九韶方法；,例,9,：用秦和韶方法求多项式,在,x,=-0.2,的值。,解：,K,a,5,-K,v,K,0,0.00833,0.00833,v,0,=,a,5,1,0.04167,0.04,v,1,=,v,0,x,+,a,4,2,0.16667,0.15867,v,2,=,v,1,x,+,a,3,3,0.5,0.46827,v,3,=,v,2,x,+,a,2,4,1,0.90635,v,4,=,v,3,x,+,a,1,5,1,0.81873,v,5,=,v,4,x,+,a,0,