数值计算方法第一章.ppt

,黑龙江科技大学,1,数值计算方法,徐 晶,理学院数学系,Mobile,:13946162373,E-mail:,309807913,Office:,理学院数学系,210,2,教材,(Text Book),数值计算方法 令锋 傅守忠 等编著,（国防工业出版社）,参考书目,(Reference),数值分析,王金铭 刘艳秋 陈欣 大连理工大学出版社,数值分析,李庆扬 王能超 易大义 华中科技大学出版社,计算方法典型例题与解法,高培旺等 国防科技大学出版社,计算方法典型例题与分析,孙守忠 科学出版社,教材及参考书,微积分,线性代数,常微分方程,C,、,C+,语言,预备知识,教学进度,课次,教学内容,1,第,1,章 数值计算方法概论,2,2.1,对分区间法,2.2,简单迭代法,3,2.3,加速收敛迭代法,2.4,牛顿迭代法,2.5,正割法,4,3.1 Gauss,列主元消去法,5,3.2 LU,分解法,6,3.3,三对角方程组的追赶法,7,4.1,向量范数与矩阵范数,8,4.2 Jacobi,迭代法,4.3 Gauss-Seidel,迭代法,9,4.4,迭代法的收敛性,4.5,逐次超松弛迭代法,10,5.1,代数插值法及其唯一性,5.2 Lagrange,插值法,11,5.3 Newton,插值法,5.4,Hermite,插值法,12,5.5,三次样条插值法,13,5.6,最小二乘拟合法,14,6.1,插值型求积公式,6.2,三个常用的求积公式及其误差,15,6.3,复化求积公式,16,6.4 Romberg,求积公式,6.5 Gauss,求积公式,6.6,数值微分法,17,7.1 Euler,方法,7.2,高阶,Taylor,方法,18,7.3,Runge-Kutta,法,5,1.,闭卷考试占,60%,2.,出勤占,10%,3.,测验及平时作业占,30%,成绩构成,一、数值计算方法,能够做什么？,1.1,数值计算方法的基本内容与特点,今有上禾三秉，中禾二秉，下禾一秉，实三十九斗；,上禾二秉，中禾三秉，下禾一秉，实三十四斗；,上禾一秉，中禾二秉，下禾三秉，实二十六斗。,问上、中、下禾实一秉各几何？,答曰：上禾一秉九斗四分斗之一。中禾一秉四斗四分斗之一。下禾一秉二斗四分斗之三。,-,九章算术,1,、一个两千年前的例子,线性方程组的求解！,2,、天体力学中的,Kepler,方程,x,是行星运动的轨道，它是时间,t,的函数,.,非线性方程求根！,全球定位系统：在地球的任何一个位置，至少可以同时收到,4,颗以上卫星发射的信号,3,、,全球定位系统（,Global Positioning System,GPS),表示地球上一个接收点,R,的当前位置，卫星,S,i,的位置为,，则得到下列非线性方程组,记为,其中，,非线性方程组的求解！,4,、已经测得在某处海洋不同深度处的水温如下：,深度（,M,）,466 741 950 1422 1634,水温（,o,C,）,7.04 4.28 3.40 2.54 2.13,根据这些数据，希望合理地估计出其它深度（如,500,米，,600,米，,1000,米,）处的水温,.,插值法！,5,、人口预测,下面给出的是中国,1900,年到,2000,年的人口数，,我们的目标是预测未来,的人口数（数据量较大时）,1950,55196,1960,66207,1970,82992,1980,98705,1990,114333,2000,126743,数据拟合！,6,、铝制波纹瓦的长度问题,建筑上用的一种铝制波纹瓦是用一种机器将一块平整的铝板压制而成的,.,假若要求波纹瓦长,4,英尺,每个波纹的高度,(,从中心线,),为,1,英寸,且每个波纹以近似,2,英寸为一个周期,.,求制做一块波纹瓦所需铝板的长度,L.,这个问题就是要求由函数,f,(,x,)=sin,x,给定的曲线从,x,=0,到,x,=48,英寸间的弧长,L,.,由微积分学我们知道,所求的弧长可表示为,:,上述积分称为第二类椭圆积分,它不能用普通方法来计算,.,数值积分！,计算机辅助设计：,波音,777,应用三维立体建模，数字化设计与有限元计算的第一架喷气客机。,天气预报：,计算能力的发展将把海洋、大气和生态系统的综合知识融合成一个气象变化模型。,医学与生物工程：,CT,、,核磁共振与,Radon,变换；至病基因与药物设计；人造生物材料的彷真响应；传染病动力学模型。,现代科学计算在工程计算中的应用,电子系统自动化设计,：,大规模集成电路的设计与逻辑检测。,材料设计,：,性能设计的大规模计算与模拟：设计用于生产新的高热值、高压材料中的化学蒸发沉淀反应器。,车辆与道路工程设计与模拟,：,车辆与道路相互作用综合系统设计。,存储与物流系统：,工农业发展使得产品的存储、交流和时效性极大提高；废物和垃圾问题成为城市生活的重大问题。规划计算和系统分析成为常用计算方法。,燃烧与爆炸工程：,燃烧对环境的影响；计算流体力学,与爆炸工程。,网络设计与计算：,搜索引擎的设计,航空航天工程：,神州飞船系列,信息与通信工程：,GPS,卫星导航,二、数值计算方法的意义、内容与方法,软件的核心就是算法。,20,世纪最伟大的科学技术发明,-,计算机,计算机是对人脑的模拟，它强化了人的思维智能；,计算机的发展和应用，已不仅仅是一种科学技术,现象，而且成了一种政治、军事、经济和社会现象；,没有软件的支持，超级计算机只是一堆废铁而已；,算法犹如乐谱，软件犹如,CD,盘片，硬件如同,CD,唱机。,理论研究,科学实验,科学计算,计算数学,诺贝尔奖得主,计算物理学家,Wilson,提出,现代科学研究的三大支柱,科学方法论的巨大变革,：如果说,伽利略和牛顿,在科学发展史上奠定了实验和理论这两大科学方法的支柱，那么由,冯,.,诺依曼,研制的现代电子计算机把计算推上了人类科学活动的前沿，使计算成为,第三种方法,。,21,世纪信息社会的两个主要特征：,“计算机无处不在”,“数学无处不在”,21,世纪信息社会对科技人才的要求：,-,会用数学解决实际问题,-,会用计算机进行科学计算,建立数学模型,选取计算方法,编写上机程序,计算得出结果,科学计算解题过程,数值计算方法是计算数学的一个主要组成部分，,“,什么是,数值计算方法？,”,它主要研究使用计算机求解各种科学与工程计算问题的数值方法（近似方法）,;,对求得的解的精度进行评估以及在计算机上实现求解等。,数值计算方法已经成为计算机处理实际问题的一个重要手段，从宏观天体运动学到微观分子细胞学，从工程系统到社会经济系统，无一能离开数值计算方法。因此，数值计算与计算机模拟被称为,“第三种科学研究方法”。,科学计算可视化是目前研究的热门问题，下面的艺术图形是基于科学计算的数据表示的例子,分形图,混沌图,1,、,数值逼近,插值与拟合、,FFT,、数值积分与微分,2,、数值代数,代数基础、线性代数方程组的解法、非线性代数方程（组）的解法、特征值与特征向量,3,、微分方程数值解,ODE,、,PDE,和有限元法,4,、最优化方法*,无约束优化与约束优化方法,融进了机器学习计算、仿生计算、网络计算、以数据为核心的计算和各种普适计算、非线性科学计算等内容。,传统的数值计算的主要研究内容,现代计算方法：,数值计算方法的主要特点,借助计算机提供切实可行的数学算法,.,想,的精确度,;,收敛且稳定,;,误差可以分析或估计,.,所提出的算法必须具有：可靠的理论分析,;,理,时间复杂性好,_,指节省时间；,空间复杂性好,_,指节省存储量。,计算复杂性好,通过数值实验证明算法行之有效,.,采用“,近似替代,”方法,逼近,采用“,构造性,”方法,采用“,离散化,”方法,把求连续变量的问题转化为求离散变量的问题,采用“,递推化,”方法,复杂的计算归结为简单过程的多次重复，易于用循环结构来实现（迭代法）。,采用各种,搜索,方法,构造数值算法的主要手段,希 望：,求近似解，但方法简单可行，行之有效,（计算量小，误差小,需存储单元少,等）,以计算机为工具，易在计算机上实现。,计算机运算,:,只能进行加，减，乘，除等算术运算和一,些逻辑运算。,数值计算方法：,把求解数学问题转化为按一定次序只进行,加，减，乘，除等基本运算,.,设计数值算法的出发点？,三、如何学好数值计算方法？,hhhhhhhhhhhhhgggg,几点纪律要求,上课至少提前,2,分钟到教室，不早退,上课期间手机静音,课,前预,习，课,后复,习,，及时解决存在的问题,课堂上认真听讲，适当记笔记，积极回答问题,作业独立完成，保质保量按时上交,有事提前请假，否则，记无故旷课,威尔金森,（,James Hardy.Wilkinson,，,1919-1986,）,Wilkinson,是数值分析和数值计算的,开拓者和奠基人,。,1940,年，开始研究弹道的数学模型与数值计算。,1946,年成为,Turing,的助手，协助设计,Pilot ACE,计算机。,1969,年他当选为英国皇家学会院士；,1970,年工业和应用数学会,(s1am),授予他冯,诺伊曼奖；,1987,年他获得美国数学会的,chauvenet,奖。著名的美国阿尔贡国家实验室曾聘威尔金森为荣誉高级研究员并两次向他授奖。,Wilkinson,在数值分析研究领域作出了杰出贡献，是数值计算的早期开拓者，其工作加速了数字计算机,(,在科学计算中,),的使用。他研究的主要问题是线性代数方程组和矩阵特征值问题的数值解法，特别是他的向后误差分析法,(backward error analysis),的创造性工作奠定了数值分析和数值计算早期的理论基础。,1975,年,J.H.Wilkinson,成为第五位图灵奖获得者。,36,用计算机进行实际问题的数值计算时，往往求得是问题的,近似解,，都存在误差。,误差公理：,任何测量（观测）都存在误差。,误差是不可避免的，即要,允许,误差，又要,控制,误差。,1.2,误差的基本理论,一、,误差的来源与分类,从实际问题中抽象出数学模型,模型误差,Model Error,例,:,质量为,m,的物体，在重力作用下,自由下落，,其下落距离,s,与时间,t,的关系是：,其中,g,为重力加速度。,通过测量得到模型中参数的值,观测误差,Observation Error,截断误差,方法误差,Truncation Error,例如，当函数,用,Taylor,多项式,近似代替时，数值方法的截断误差是,与,0,之间。,在,舍入误差,Round-off Error,用计算机、计算器和笔算，都只能用有限位,=3.1415926,小数来代替无穷小数或用位数较少的小数来,代替位数较多的有限小数，如：,四舍五入后,在数值计算方法中，主要研究,截断误差,和,舍入误差,（包括初始数据的误差）对计算结果的影响！,二、误差的概念,1,、绝对误差,Absolute Error,是近似值 的,绝对误差,简称为,误差,。,若 近似值偏大，称,“强近似”,或,“盈近似”,若 近似值偏小，称,“弱近似”,或,“亏近似”,注,越小，精度越高；,定义,1-1,：,设 是准确值，为,的一个近似值，称,例,1,、,用毫米刻度尺测量长度为 的物体，测得其长度为 ，是物体实际长度的一个近似值，由于直尺以毫米,为,刻度，故误差不超过半个毫米，则有：,通常记为：,绝对误差限,例,2,、,真空中光速,c,的近似值为,例,1,、,用毫米刻度尺测量长度为 的物体，测得其长度为 ，是物体实际长度的一个近似值，由于直尺以毫米,为,刻度，故误差不超过半个毫米，则有：,在应用上，常常采用下列写法来刻划 的精度。,因准确值 往往无法知道，只能估计：,（上界）,叫做 的,绝对误差限,。,即 落在 内。,44,例如，有两个量 ，,则,虽然 比 大,4,倍，,但,比,所以除考虑误差的大小外，还应考虑准确值 本身的大小,.,要小得多，这说明 近似 的程度比 近似 的程度好,.,45,定义,1-2,：,相对误差,实际计算中，常用下式代替：,2,、,相对误差：,Relative Error,因实际误差 未知，常采用：,相对误差限,近似值的误差 与准确值,x,的比值,46,定义,1-3,：若近似值 的误差限是某一位的半个单位，,该位到 的第一位非零数字共有 位，就说,有 位,有效数字,。,例,意义：,有效数字越多，误差限越小，数值越准确。,3,、,有效数字,significant digits,如果一个近似数的所有数字均为,有效数字,，则称之为,有效数,。,47,则 有 位有效数字，精确到 。,类似,科学计数法,式中,(,小数点后,1,位）；,可以为零；,为整数。,如果,48,有效数字与相对误差的关系,有效数字,相对误差限,已知,x,*,有,n,位,有效数字,，则其,相对误差限,为,相对误差限,有效数字,已知,x,*,的,相对误差限,可写为,则,可见,x,*,至少,有,n,位,有效数字,。,Th1.2,：,设,反之,若 的相对误差的绝对值大于 ，,其中 为整数,为正整数,。,有 位有效数字。,则 至多,若 至多有 位有效数字,即 是有效数字,而 不是有效数字,则 的相对误差的绝对值必大于,;,证明：,不是有效数字,反之,若,则,不是有效数字，,即 至多有 位有效数字,.,51,例,为使 的相对误差小于,0.001%,至少应取几位有效数字？,解,假设,*取到,n,位有效数字，则其相对误差上限为,要保证其相对误差小于,0.001%,，只要保证其上限满足,已知,a,1,=3,，则从以上不等式可解得,n,6,log6,，即,n,6,，应取,*,=3.14159,。,52,注意：,准确值经,“,四舍五入,”,后，都为有效数字；,有效数字位数相同，误差可能不同；,例如：,但 相同时，有效位数越多，误差越小。,移动小数点时，不要改变有效数字；,例如：,常数、系数、准确数有无数多个有效数字。,例如：，,0.02030,有,4,位有效数字，而,0.0203,只有,3,位有效。,12300,如果,写成,0.123,10,5,，则表示只有,3,位有效数字。,数字末尾的,0,不可随意省去！,53,按四舍五入原则写出下列各数具有,5,位有效数字的,近似数：,解：,按定义，,187.93,的,5,位有效数字近似数是,8.0000,，而不是,8,，,例,187.9325,0.03785551,8.000033,2.7182818.,上述各数具有,5,位有效数字的近似数分别是,因为,8,只有,1,位有效数字,.,注意：,0.037856,8.0000,2.7183.,54,加、减、乘、除运算的误差为：,4,、数值运算的误差估计,（避免绝对值很大的数为乘数）,（避免,为很小的数为除数）,（避免两相近数相减运算,）,5,、函数的误差估计,当自变量有误差时，计算函数值也会产生误差，其误差限可利用函数的,Taylor,展开式进行估计。,设 是一元函数，的近似值为,以 近似 ，其误差限记作 ，可用,Taylor,展开,介于,之间,.,取绝对值得,假定 与 的比值不太大,可忽略 的高阶项,于是可得计算函数的误差限为,当 为多元函数时计算,如果,的近似值为,则 的近似为,于是函数值 的误差 由,Taylor,展开,得：,假定 与 的比值不太大,可忽略 的高阶项,于是可得计算函数的误差限为,于是误差限为,而 的相对误差限为,(1.2.1),(1.2.2),例,:,已测得某场地长 的值为,宽 的值为,已知,.,试求,面积 的绝对误差限与相对误差限,.,其中,由式,(1.2.1),得,解,:,因,而,于是绝对误差限为,相对误差限为,数值计算在设计算法时首先关心的是由它产生的计算结果的稳定性，而算法的稳定性与舍入误差是否增长密切相关。一个算法如果输入数据有微小扰动（即误差），而在计算过程中舍入误差不增长，则称此算法是,数值稳定的,，否则称其为,数值不稳定。,1.3,数值算法设计的原则,61,（,3,）不在计算机数系中的数做四舍五入处理。,例,在四位浮点十进制数的计算机上计算,1+10,4,（,1,）加法先对阶,后运算,再舍入；,（,2,）乘法先运算,再舍入；,=0.1000,10,5,=10,4,=,0.10001,10,5,=0.,0000,1,10,5,+0.,1000,10,5,(,对阶,，,靠高阶),解,1+10,4,=0.1000,10,1,+0.1000,10,5,(,浮点数形式,),(,运,算),(,舍入,),计算机中数的计算特点,例：求定积分的值,.,解：,直接积分可产生递推公式,若取初值,可得递推公式,按公式就可以逐步算出,注意此公式,精确,成立，且,What happened?!,不稳定的算法！,这就是误差传播所引起的危害,!,NY,BJ,蝴蝶效应,纽约的一只蝴蝶翅膀一拍，风和日丽的北京就刮起台风来了？！,这是一个,病态问题,由题设中的递推公式（,1,）可看出，,的误差扩大了,5,倍后传给,，因而初值,的误差对以后各步,这就造成 的计算结果,严重失真。,计算结果的影,响，随着,的增大愈来愈严重。,要怎么做才能解决这个问题呢,?,可求得,I,9,0.017,，,按改写后的公式可逐次求得,不妨设,I,9,I,10,，,于是由,将,公式,变为,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,稳定的算法！,在我们今后的讨论中，,误差,将不可回避，,算法的,稳定性,会是一个非常重要的话题。,注：,递推公式,(1),的舍入误差以,5,的幂次增长进行传播，因此是,数值不稳定的，,而递推公式,(2),的舍入误差在一定范围内以,0.2,的幂次进行传播，随着,n,的增大，误差逐步减少，因此该算法是,数值稳定的,。,因此，可以看出数值不稳定的算法是不能使用的，实际计算中对任何输入数据都是数值稳定的算法，称为,无条件稳定。,而对某些数据数值稳定，对其它数据数值不稳定的算法，称为,条件稳定,。,1.,简化计算步骤，避免误差积累。,一般来说，计算机处理下列运算的速度为,例：,多项式求值：给定的,x,求下列,n,次多项式的值,。,解：,1.,用一般算法，即直接求和法；,2.,逐项求和法；,3.,秦九韶方法,(,即,Hornor,算法）；,先计算,x,2,x,3,x,n,再作线性组合，需做,2,n,-1,次,乘法和,n,次,加法。,解法一：,直接求和法,解法二：逐项求和法,按顺序依次计算每一项的值再求和，需做,n,(,n,+1)/2,次,乘法和,n,次,加法。,解法三：秦九韶算法（即,Horner,算法）,只需做,n,次,乘法和,n,次,加法。且可以递推实现。,好处：节省计算时间；,减少舍入误差。,2,.,要避免两个相近的数相减,在数值计算中，两个相近的数作减法时有效数字会损失。,例,:,求,的,值。,当,x,=1000,，,y,的准确值为,0.01580,放大相对误差限，导致计算结果有较大误差！,类似地,(2),若,将,原式,改写为,则,y,=0.01581,(1),直接相减,有,3,位有效数字！,只有,1,位有效数字,当,|,x,|1,时：,3.,尽量避免绝对值太小的数作分母,例：,如分母变为,0.0011,，也即分母只有,0.0001,的变化时,结果相差这么大,!,4.,避免大数,吃,小数,精确解为,算法,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,：,先解出,再利用,注：,求和时从小到大相加，可使和的误差减小。,例：,按从小到大、以及从大到小的顺序分别计算,1+2+3+40+10,9,5.,尽量采用数值稳定性好的算法,在计算过程中产生的舍入误差能被控制在一定的,范围内，且对最后的结果影响不大的算法称为,数,值稳定算法,。不是数值稳定的算法称为,数值不稳,定算法,。,数值稳定：运算中误差不增长；,数值不稳定：运算中误差不断增长，产生积累。,约翰,冯,诺依曼（,John von Neumann,1903-1957,）美藉匈牙利人，,1930,年接受了普林斯顿大学客座教授的职位，西渡美国。,1931,年成为该校终身教授。,1933,年成为新成立的普林斯顿高等研究院的终身研究员。,1951,年至,1953,年任美国数学会主席。,冯,诺依曼是,20,世纪少有的数学科学通才，在许多领域都有重要的贡献，被西方人誉为“,数学奇才、计算机之父,”。冯,诺依曼对人类的最大贡献是对计算机科学、计算机技术和数值分析的开拓性工作。,并行计算,一、电子计算机的并行计算分类,传统计算机一般采用,Von Neumann,结构，每一时刻,只有一个进程的算法，即,串行算法。,并行计算机每一时刻具有,2,个以上,的进程的算法称为,并行算法。并行机必须包含,2,台以上,处理机，按指令流是,单个还是多个并行算法可分为两类：,SIMD,算法,适用于单指令流多数据流系统；,MIMD,算法,适用于多指令流多数据流系统,。,按照进程之间是否同步可将并行算法分为,:,同步算法,:,是指在,k,个进程的算法中有些进程的若干算,法必须在另一些进程的某些算法之后执行；,异步算法,:,指,k,个进程间有信息联系但不须同步，它只,能在一个具有,k,台处理机的,MIMD,系统中实现。,二、并行计算的算法设计,并行算法设计的重要原则是,“分而治之”。,其基本思想,是把问题依次划分为可以独立完成的较小问题，将规模,逐,次减半,的二分技术是并行算法设计的一种基本技术。,二分算法的设计原理是反复地将所给计算问题加工成,规模减半的同类计算问题而计算。可利用串行算法来改造,或设计并行算法，不少数值算法包含了可直接利用的并行,性。还可以根据并行算法的特点设计具有新思想的新算法，它的出发点仍然是“分而治之”的原理，符合此原理的区域、算子、系统的分裂方法和技术是设计和实现并行处理的重要手段。,此外，异步数值算法基本上是,混乱迭代法,，是并行算,法最富有特色的组成部分之一。,