算术运算中的误差分析初步绪论课件

1、算术运算中的误差分析初步绪论,1,数值计算方法,算术运算中的误差分析初步绪论,2,数值计算方法”介绍科学计算中最常用和最基本的数值方法，它是在“高等数学”与“线性代数”课基础上开设的重要的应用数学专业基础课程。它讨论的是如何运用现代计算工具高效求解科学与工程中的数值计算问题,简介,计算方法，过去有不少人称之为数值分析，现在更多的人称之为科学计算，其核心思想就是通过有限步的加、减、乘、除四则运算得到某个连续变量的近似值,算术运算中的误差分析初步绪论,3,计算方法的研究对象和内容就是研究求解各种数学问题的数值方法及其理论，并且将方法在计算机上实现，求出问题的数值解，或者说是问题的近似解。还要分析算

2、法的收敛性、稳定性、误差分析等，这样才能保证计算结果的可靠性,算术运算中的误差分析初步绪论,4,1.1 计算方法的意义和特点,3）基于离散数据建立数学模型时,无法采用传统数学方法获得所需解的三种有代表性的情形,1）所涉及的数学模型无系统的求解析解的方法,2）所涉及数学模型的解法计算量大，只适用于规模较小的情形,计算方法（又称为数值分析）的任务就是研究如何对给定的问题构建只须进行有限步四则运算的计算模型，以便有效地借助于计算机迅速求出所需要的数值解。这种计算模型通常又称为计算格式,算术运算中的误差分析初步绪论,5,计算方法不同于纯粹数学学科的一些新特点,1）形散神不散,计算方法的涉及面十分广泛，

3、各种数值方法因依附于相应的数学分支而表现得相对独立。但计算方法作为一门独立的研究分支，自有贯穿于其中的精髓，这就是数学模型离散化所要遵循的相容性原则，控制误差积累的数值稳定性要求，以及评价计算格式优劣的计算复杂性，为适应大型计算机的计算，现今又提出了并行性要求,2）理论分析的严谨性与实用准则的近似性的对立统一,算术运算中的误差分析初步绪论,6,数值分析能够做什么,研究使用计算机求解各种数学问题的数值方法（近似方法），对求得的解的精度进行评估，以及如何在计算机上实现求解等,算术运算中的误差分析初步绪论,7,在计算机上是否根据数学公式编程就能得到正确结果,研究例子:求解线性方程组 其准确解为x1=

4、x2=x3=1,如把方程组的系数舍入 成两位有效数字,它的解为x1 =-6.222. x2=38.25 x3=-33.65,算术运算中的误差分析初步绪论,8,计算机解决实际问题的步骤 建立数学模型 选择数值方法 编写程序 上机计算,算术运算中的误差分析初步绪论,9,数值计算方法是研究并解决数学问题的数值近似解的方法，简称计算方法，也叫数值分析等。 算法：从给定的已知量出发，经过有限次四则运算及规定的运算顺序，最后求出未知量的数值解，这样构成的完整计算步骤称为算法,0.1 数值计算方法和算法,算术运算中的误差分析初步绪论,10,运算量,一个算法所需的乘除运算总次数. 计算量是衡量一个算法好坏的重

5、要指标,算术运算中的误差分析初步绪论,11,算法优劣的重要性,例1 已知 a0, a1, a2 , an, x, 计算多项式： 直接计算：运算量（乘） 秦九韶算法（1247年）： 运算量,算术运算中的误差分析初步绪论,12,例 2 解线形方程组,其中， 克兰姆(Cramer)法则： 运算量(乘除)： 高斯消元法(Gauss)： 运算量(乘除) Gauss: 3060次； Cramer,算术运算中的误差分析初步绪论,13,本课程的任务,建立各种数学问题的数值计算算法的方法和理论。 通俗地讲，就是为各种实际问题提供有效的数值近似解方法。 提供在计算机上实际可行的、理论可靠的、计算复杂 性好的各种常

6、用算法,算术运算中的误差分析初步绪论,14,本课程的任务,建立各种数学问题的数值计算算法的方法和理论。 通俗地讲，就是为各种实际问题提供有效的数值近似解方法。 提供在计算机上实际可行的、理论可靠的、计算复杂 性好的各种常用算法,算术运算中的误差分析初步绪论,15,参考书： 1.计算方法引论（第二版），徐萃薇，孙绳武编著。 高等教育出版社，2002 2. 数值分析, 李庆扬，王能超，易大义编。 清华大 学出版社 ,2001 3. 数值计算方法, 关治，陈景良。清华大学出版社，1990,算术运算中的误差分析初步绪论,16,计算方法：内容和意义 计算方法是研究数学问题的数值计算方法及其相关理论的课程

7、。计算方法这个名称更确切说应该是“数学数值计算方法”，但由于数学的一般性，通常就简称“数值计算方法”或“数值方法”或“计算方法”。另外，计算方法课程与另一门称为数值分析的课程则是大同小异，通常认为后者偏理论一些,根据计算方法课程的任务，计算方法课程的基本架构是： 1 ） 给出一类类典型的数学问题的数值提法（包括其应用背景和理论背景）；2 ） 构造求解该类问题数值解（而不是解析解）的各种数值计算方法，并作其誤差分析； 3 ） 进一步把数值计算方法设计成计算机算法及予以上机计算,数学的数值计算实质上是一种近似处理，所以最基础本的概念就是误差的概念。所谓误差，就是一个量的准确值与其近似值之差,算术运

8、算中的误差分析初步绪论,17,现实中，具体的科学、工程问题的解决,实际问题,物理模型,数学模型,数值方法,计算机求结果,计算方法是一种研究并解决数学问题的数值近似解方法,随着计算机的飞速发展，数值分析方法已深入到计算物理、计算力学、计算化学、计算生物学、计算经济学等各个领域。本课仅限介绍最常用的数学模型的最基本的数值分析方法,算术运算中的误差分析初步绪论,18,计算方法的特性,理论性：数学基础 实践性,计算方法连接了模型到结果的重要环节,算术运算中的误差分析初步绪论,19,内容,1、数值逼近数学分析中的数值求解，如微分、积分,2、数值代数线性代数的数值求解，如解线性方程组、逆矩阵、特征值、特征

9、向量,3、微分方程常微分，Runge-Kutta法、积分法,100亿/秒，算3,000年，而Gauss消元法2660次,算术运算中的误差分析初步绪论,20,计算方法研究的对象,研究数值方法的设计、分析和有关理论基础与软件实现,计算方法又称：计算数学、数值方法、数值分析等。 计算方法的分枝有最优化方法、计算几何、计算概率统计等,算术运算中的误差分析初步绪论,21,什么是算法和计算量,算法：从给定的已知量出发，经过有限次四则运算及规定的运算顺序，最后求出未知量的数值解，这样构成的完整计算步骤称为算法。 计算量：一个算法所需的乘除运算总次数，单位是flop. 计算量是衡量一个算法好坏的重要标准,算术

10、运算中的误差分析初步绪论,22,数值分析或数值计算方法主要是研究如何运用计算机去获得数学问题的数值解的理论和方法.对那些在经典数学中,用解析方法在理论上已作出解的存在,但要求出他的解析解又十分困难,甚至是不可能的这类数学问题,数值解法就显得不可缺少,同时有十分有效,算术运算中的误差分析初步绪论,23,计算机解决科学计算问题时经历的几个过程 实际问题数学模型数值计算方法程序设计上机运行求出解 实际问题数学模型：由实际问题应用科学知识和数学理论建立数学模型的过程，是应用数学的任务,算术运算中的误差分析初步绪论,24,数值计算方法程序设计计算结果：根据数学模型提出求解的数值计算方法，直到编出程序上机

11、算出解，是计算数学的任务。 数值计算方法重点研究：求解的数值方法及与此有关的理论 包括：方法的收敛性，稳定性，误差分析，计算时间的最小（也就是计算费用）,占用内存空间少,算术运算中的误差分析初步绪论,25,有的方法在理论上虽不够严格，但通过实际计算，对比分析等手段，被证明是行之有效的方法，也可以采用。因此，数值分析既有纯数学高度抽象性与严密科学性的特点，又有应用的广泛性与实验的高度技术性特点，是一门与使用计算机密切结合的实用性很强的数学课程,算术运算中的误差分析初步绪论,26,1.1 引言 数值分析又称计算方法, 它是研究各种数 学问题的数值解法及其理论的一门学科,数值分析的任务,实际问题,数

12、学模型,数值计算方法,程序设计,上机计算,数值结果,根据数学模型提出求解的数值计算方法直到编出程序上机算出结果，这一过程边是数值分析研究的对象,算术运算中的误差分析初步绪论,27,1. 对于要解决的问题建立数学模型 2. 研究用于求解该数学问题近似解的算法和过程 3. 按照2进行计算，得到计算结果,数值方法解题的一般过程,算术运算中的误差分析初步绪论,28,数值计算以及计算机模拟（包括当前流行的虚拟现实的方法），已经是在工程技术研究和经济、社会科学中广泛应用的方法，带来巨大的经济效益 天气预报与亿次计算机 波音777的无纸设计与有限元 CT、核磁共振 计算流体力学与爆炸工程 能源问题与大型计算

13、,算术运算中的误差分析初步绪论,29,计算方法课程主要讨论如何构造求数学模型近似解的算法，讨论算法的数学原理、误差和复杂性，配合程序设计进行计算试验并分析试验结果。 与纯数学的理论方法不同，用数值计算方法所求出的结果一般不是解的精确值或者准确的解析表达式，而是所求真解的某些近似值或近似曲线,算术运算中的误差分析初步绪论,30,例如方程 x2=2sinx，在区间(1,2)内有唯一根, 但找不出求根的解析式, 只能用数值计算方法求其近似解。有些数学问题虽有理论上的准确的公式解, 但不一定实用, 例如行列式解法的Cramer法则原则上可用来求解线性方程组,用这种方法解一个n元方程组,要算n+1个阶行

14、列式的值,总共需要n!(n-1)(n+1)次乘法,当n=20时,其乘除法运算次数约需1021次方,即使用每秒千亿次的计算机也得需要上百年,而用高斯（Guass）消去法约需2660次乘除法运算,并且愈大,相差就愈大。可见研究和选择好的算法是非常重要的,算术运算中的误差分析初步绪论,31,算法(数值算法):是指有步骤地完成解数值问 题的过程。 数值算法的特点 目的性，条件和结论、输入和输出数据均要有明 确的规定与要求。 确定性，精确地给出每一步的操作(不一定都是运算)定义, 不容许有歧义。 可执行性，算法中的每个操作都是可执行的 有穷性，在有限步内能够结束解题过程 计算机上的算法，按面向求解问题的

15、不同， 分为数值算法和非数值算法,算术运算中的误差分析初步绪论,32,1 数值计算方法的意义、内容与方法,软件的核心就是算法,20 世纪最伟大的科学技术发明-计算机,计算机是对人脑的模拟，它强化了人的思维智能,计算机的发展和应用，已不仅仅是一种科学技术 现象，而且成了一种政治、军事、经济和社会现象,没有软件的支持，超级计算机只是一堆废铁而已,算法犹如乐谱， 软件犹如CD盘片， 而硬件如同CD唱机,算术运算中的误差分析初步绪论,33,现代科学研究的三大支柱,计算数学,算术运算中的误差分析初步绪论,34,21世纪信息社会的两个主要特征： “计算机无处不在” “数学无处不在,21世纪信息社会对科技人

16、才的要求： -会“用数学”解决实际问题 -会用计算机进行科学计算,算术运算中的误差分析初步绪论,35,建立数学模型,选取计算方法,编写上机程序,计算得出结果,科学计算解题过程,算术运算中的误差分析初步绪论,36,一、计算数学的产生和早期发展,计算数学是数学的一个古老的分支，虽然数学不仅仅 是计算，但推动数学产生和发展的最直接原因还是 计算问题,二、二十世纪计算数学的发展,数值代数,最优化计算,数值逼近,计算几何,概率统计计算,蒙特卡罗方法,微分方程的数值解法,微分方程的反演问题,算术运算中的误差分析初步绪论,37,数值计算的主要内容,数值代数：方程求根、线性方程组求解、 特征值和特征向量的计算

17、、 非线性方程组的求解,数值逼近：插值、数值微分和积分、 最小二乘法,微分方程数值解： 常微分方程数值解； 偏微分方程数值解： 差分法 有限元法 有限体积法,算术运算中的误差分析初步绪论,38,数值计算方法的研究对象和特点 随着电子技术的发展和科学研究、生产实践的需要，电子计算机的使用日益广泛。计算机作为科学计算的主要工具越来越不可缺少，因而要求研究适合计算机使用的数值计算方法。为了更具体地说明数值计算方法的研究对象，我们考察用计算机解决科学计算问题的一般过程，可以概括为 实际问题数学模型计算方法程序设计上机计算 由实际问题应用有关科学知识和数学理论建立数学模型这一过程，通常作为应用数学的任务

18、。而根据数学模型提出求解的计算方法直到编出程序上机算出结果，进而对计算结果进行分析，这一过程则是计算数学的任务，也是数值计算方法的研究对象。因此，数值计算方法 就是研究用计算机解决数学问题的数值方法及其理论。它的内容包括：误差理论、线性与非线性方程(组)的数值解、矩阵的特征值与特征向量计算、曲线拟合与函数逼近、插值方法、 数值积分与数值微分、常微分方程与偏微分方程数值解等,算术运算中的误差分析初步绪论,39,数值计算方法应有的特点。概括起来有四点,第一，面向计算机，要根据计算机特点提供实际可行的有效算法，即算法只能包括加、减、 乘、除运算和逻辑运算，是计算机能直接处理的。 第二，有可靠的理论分

19、析，能任意逼近并达到精度要求，对近似算法要保证收敛性和数值稳 定性，还要对误差进行分析，这些都建立在相应数学理论基础上。 第三，要有好的计算复杂性，时间复杂性好是指节省时间，空间复杂性好是指节省存储量， 这也是建立算法要研究的问题，它关系到算法能否在计算机上实现。 第四，要有数值实验，即任何一个算法除了从理论上要满足上述三点外，还要通过数值试验 证明是行之有效的。 根据“数值计算”的特点，学习时，首先要注意方法处理的技巧及其与计算机的结合，要重 视误差分析、收敛性及稳定性的基本理论，其次，要通过例子，学习使用各种数值方法解决实际计算问题,算术运算中的误差分析初步绪论,40,计算方法课程是数学与

20、应用数学的一门必修课程，计算方法是随着计算机产生发展而建立的一个重要数学分支，其性质是研究建立应用计算机解决各种数学问题的数值计算方法与理论；任务是提供计算机上实际可行的、理论可靠的，计算复杂性好的各种常用算法；内容主要包括误差理论，方程求根，线性方程组求解，插值方法，数值积分，微分方程数值解法等。计算方法既具有理论上的高度抽象性与严密逻辑性，又具有应用的广泛性和高度技术性,算术运算中的误差分析初步绪论,41,计算方法的任务与特点,实际问题数学问题提供计算方法 程序设计上机计算结果分析,算术运算中的误差分析初步绪论,42,基本的数学计算问题,1.大型线性代数方程组Ax=b求解; 2.矩阵A的特

21、征值和特征向量计算; 3.非线性方程 求解(求根); 4.积分 计算; 5.常微分方程初值问题求解; 6.其它,算术运算中的误差分析初步绪论,43,求精确解(值)一般非常困难。例如,1. 方程组阶数n很大，例如n=20,计算机运算速度 1亿次/秒,用不好的方法,大约需算30多万年; 好方法不到一分钟。另外，有计算结果可靠性 问题。 2. 特征值定义,算术运算中的误差分析初步绪论,44,3. 形式复杂时求根和求积分很困难。 4.线性微分方程易解， 如 非线性方程难解，如,希 望： 求近似解，但方法简单可行，行之有效 （计算量小，误差小等）。以计算机为工 具，易在计算机上实现。 计算机运算: 只能

22、进行加，减，乘，除等算术运 算和一些逻辑运算。 计算方法： 把求解数学问题转化为按一定次序只 进行加，减，乘，除等基本运算 数值方法,算术运算中的误差分析初步绪论,45,浅谈计算数学的过去和未来,计算数学”就是研究在计算机上解决数学问题的理论和数值方法,今天的数值计算方法，无论从形式到内容，还是从工具到效果，已远非半世纪前Von Neumann、Lax等先驱们所处的环境和条件了，计算机技术和应用软件的发展，让计算数学展开了双翼。许多迅速发展的其他学科和社会进步给计算数学的发展开拓出 更为广阔的新天地,算术运算中的误差分析初步绪论,46,主要谈二个方面：从计算物理的发展过程来看计算数学的过去；计

23、算数学的未来50年.1-3,一. 计算数学发展的历史回顾,1. 从计算物理谈起,计算数学的发展与科学工程计算是紧密相联的，计算数学的发展历史也就是与其他学科结合，利用计算机不断形成新的理论及数值方法并不断形成新的学科的历史，例如：“计算物理,算术运算中的误差分析初步绪论,47,年月美国总统发布命令，可以揭开曼哈顿计划的内幕，部分内容可以解密。故以“计算物理方法”丛书的名义陆续编辑出版,我们常说,计算物理的物质基础是计算机； 计算物理的关键技术是“计算方法”和“程序设计”; 计算物理发展的原始动力是美国核武器研制的刺激,算术运算中的误差分析初步绪论,48,三位计算机设计大师的贡献,H. Aike

24、n (1900-1973,哈佛大学的博士研究生毕业。因做博士论文涉及到空间电荷传导问题的计算，1937年提出方案，1939年得到IBM资助，1944年建成投入使用。这是继电式计算机Mark I,算术运算中的误差分析初步绪论,49,J. W. Manchly (1907-1980,宾夕法尼亚物理博士，因从事天气预报需要想设计计算机，1942年提出计算机方案，1945年底竣工，这就是世界上第一台电子计算机ENIAC机,J. Von Neumann (1903-1956,普林斯顿高级研究所，1945年在普林斯顿研制成MANIAC机，有力地支持美国氢弹研制，称为计算机之父。（与中国的109丙机、J-5

25、01机相当,算术运算中的误差分析初步绪论,50,美国从1942年8月13日开始曼哈顿计划，到1945年制造出三颗原子弹：代号为：“三一”，用于试验（7月16日），“瘦子”投于广岛(8月6日)，“胖子”投于长崎(8月9日)。历时三年，涉及到理论物理、爆轰物理、中子物理、金属物理、弹体弹道等大量的数值计算,1949年8月苏联第一次原子弹爆炸后，杜鲁门总统在1950年1月31日下令继续研究各种类型的原子弹武器，成立以氢弹之父特勒(E. Teller)为首的氢弹研制小组。直到1952年10月31日爆炸了代号为“麦克”的核试验,算术运算中的误差分析初步绪论,51,数值方法和数值软件过去50年的主要进展附录,Before 1940,Newtons method; Gaussian elimination; Gauss quadrature; least squares fitting; Adams and Runge-Kutta formulas;Richardson extrapolation,算术运算中的误差分析初步绪论,52,1940-1970,floating point arithmetic; Fortran ; finite differences; finite elements; FFT; simplex algorithm; Monte Carlo; or