数值分析-Ch1-绪论

1、数 值 分 析 Numerical Analysis 李庆杨 王能超 易大义 编 华中科技大学出版社,“数值分析” 就是研究适合用计算机解决数学问题的理论和数值方法: 数值方法: 计算公式和算法步骤 理论分析：误差分析、收敛性、稳定性等,什么是数值分析?,Chapter 1 Introduction,Chapter 1 Introduction,数值分析的学科别名, 计算方法 科学与工程计算,Chapter 1 Introduction,科学计算的重要性, 科学计算是工程实践的重要工具 科学计算是继理论与实验后另一科学 研究手段,Chapter 1 Introduction,计算机发展的四个阶

2、段,第一代计算机：电子管数字计算机(1946-1958年) 第二代计算机：晶体管数字计算机(1958-1964年) 第三代计算机：集成电路数字计算机(1964-1970年) 第四代计算机：大规模集成电路计算机(1970年),科学计算的国家战略与发展, 1983 年一个由美国著名数学家向美国政府提出的报告之中， 强调“科学计算是关系到国家安全、经济发展和科技进步的关 键性环节，是事关国家命脉的大事。” 1984 年美国政府大幅度地增加对科学计算经费的支持,新建成 五个国家级超级计算中心,配备当时最高性能的计算机，建立 NSF -net 新网络。 80 年代中期我国将“大规模科学与工程计算”列入国

3、家资助重大 项目。,Chapter 1 Introduction, 1987年起美国NSF 把“科学与工程计算” ，“生物工程” “全局 性科学”作为三大优先资助的领域。 1990年美国国家研究委员会发表振兴美国数学：90年代的计 划的报告，建议对由计算引发的数学给予特殊的鼓励和资助。 1991年以美国总统倡议的形式提出了“高性能计算与通信HPCC 计划”，这是为了保持和提高美国在计算和网络的所有先进领 域中的领导地位而制定的。 1995年美国为了确保核库存的性能安全性、可靠性和更新需要 而实施的“加速战略计算创新ASCI 计划”。,Chapter 1 Introduction, 2010年希

4、拉里提出的“国家宽带战略”，“大数据研究和发展计划”也被认为是1993年时任美国副总统戈尔宣布的“信息高速公路”计划后美国政府政策层面的一次“狂飙突进”，将“大数据”上升到国家意志将在下一个10年带来深远影响。 在互联网和通信技术飞速发展20年后，一个属于“大数据”的时代，真的来了。,Chapter 1 Introduction, 2013年3月22日，奥巴马宣布以2亿美元投资“大数据”领域，在次日的电话会议上，美国政府将数据定义为“未来的新石油”，美国政府认识到了一个国家拥有数据的规模，活性及解释运用的能力将成为综合国力的重要组成部分，未来对数据的占有和控制甚至将成为继陆权、海权、空权之外另

5、一个国家核心资产。 2014.6.22报道，天河一号计算机第三次夺得世界最快计算机。,Chapter 1 Introduction,大数据, 大数据(bigdata)，或称巨量资料，指的是所涉及的资料量规模巨大到无法透过目前主流软件工具，在合理时间内达到撷取、管理、处理、并整理成为帮助企业经营决策更积极目的的资讯。(在维克托迈尔-舍恩伯格及肯尼斯库克耶编写的大数据时代中大数据指不用随机分析法(抽样调查)这样的捷径，而采用所有数据的方法)。 大数据的4V特点： Volume(大量)， Variety (多样), Value (价值)， Velocity(高速)。,Chapter 1 Introd

6、uction, Volume(大量)：数据体量巨大。 1024GB=1TB； 1024TB=1PB； 1024PB=1EB； 1024EB=1ZB； 1024ZB=YB。 到目前为止，人类生产的所有印刷材料的数据量是 200PB，而历史上全人类说过的所有的话的数据量 大约是5EB。,Chapter 1 Introduction, Variety (多样)：数据类型繁多。 拜互联网和通信技术近年来迅猛发展所赐，如今的数据类型早已不是单一的文本形式，除了网络日志、音频、视频、图片、地理位置信息等等多类型的数据对数据的处理能力提出了更高的要求。,Chapter 1 Introduction, Val

7、ue (价值)：价值密度低。 价值密度的高低与数据总量的大小成反比。以视频为例，一部一小时的视频，在连续不间断监控过程中，可能有用的数据仅仅只有一两秒。如何通过强大的机器算法更迅速地完成数据的价值“提纯”是目前大数据汹涌背景下亟待解决的难题。,Chapter 1 Introduction, Velocity(高速)：处理速度快。 这是大数据区分于传统数据挖掘最显著的特征。根据IDC的一份名为“数字宇宙”的报告，预计到2020年全球数据使用量将会达到35.2ZB。,Chapter 1 Introduction,1 数值分析的对象与特点, 插值和函数逼近 数值微分和数值积分 常微分方程数值解法 非

8、线性方程的迭代法 数值代数:求解线性和非线性方程组的直接 法和间接法 代数特征值问题的数值解法,总之，是构造数值算法,构造数值算法的基本思想,近似替代：如， 离散化：如， 递推化：如，,1 数值分析的对象与特点,(P3-例1),秦九韶算法:,数值分析的学科特点,实用性 理论性 实践性 1 面向计算机，根据计算机的特点提供可行的有效算法； 只提供加减乘除和逻辑运算 串行机和并行机 2 有可靠的理论分析:算法的收敛性、稳定性和误差分析； 3 有好的计算复杂性:时间和空间复杂性； 4 有充分的数值实验证明算法的有效性。,1 数值分析的对象与特点,学习“数值分析”需注意如下几点,1. 要掌握算法的原理

9、和思想 2. 要掌握算法的处理技巧,步骤和计算公式 3. 重视误差分析,理解收敛性,稳定性分析的理论 4. 做一定的理论分析证明与计算练习 5. 上机实践,1 数值分析的对象与特点,2 误差的基本理论,用计算机进行实际问题的数值计算时，往往求得的是问题的近似解，都存在误差； 2. 误差是不可避免的，既要允许误差，又要控制误差。要重视误差分析，分析误差的来源，误差的传播及对误差作出估计。,误差的来源主要有如下几个方面： 模型误差 观测误差不是来自于计算机 截断误差 舍入误差计算机产生的,例 传播与积累 /* Spread & Accumulation */,蝴蝶效应 纽约的一只蝴蝶翅膀一拍，风和

10、日丽的北京 就刮起台风来了？！,NY,BJ,以上是一个病态问题 /* ill-posed problem*/ 关于本身是病态的问题，我们还是留给数学家去头痛吧！,2 误差的基本理论,蝴蝶效应（Butterfly Effect）是指在一个动力系统中，初始条件下微小的变化能带动整个系统的长期的巨大的连锁反应。这是一种混沌现象。混沌现象是指发生在确定性系统中的貌似随机的不规则运动，一个确定性理论描述的系统，其行为却表现为不确定性不可重复、不可预测，这就是混沌现象。进一步研究表明，混沌是非线性动力系统的固有特性，是非线性系统普遍存在的现象。,3 误差的基本概念,定义1 设 为准确值 的近似值，记,误差

11、限 ： 的一个上界,即,相对误差： 或 .(后者方便使用),相对误差限 ： 的一个上界,即,例如，轴的设计尺寸,中0.01即是误差限,(绝对)误差 ：为正(负)时称 为强(弱)近似值,例如，测得某人身高1.78m,尺子的误差为1%,则实际身高 ：,3-12 误差与误差限,3 误差的基本概念,3 误差的基本概念,3-3 有效数字,定义2 若近似值 的误差限是某一位数字的半个单位，该位,到 的第一位非零数字共有n位，就说 有n位有效数字. 即,且,例如：对,科学记数法, m+1位整数,e*的小数点后有n-(m+1)个零,注：称为精确到,保留n-(m+1)位小数,最后一位经四舍五入得到,3 误差的基

12、本概念,有(m=0),例1 设四个数：42.195, 0.0375551, 8.00033, 2.71828. 按四舍五入写出上述各数具有4位有效数字的近似数.,解 42.195的4位有效数字近似数为42.20, |e*|=0.005 0.0375551的4位有效数字近似数为0.03756,|e*|0.000005 8.00033的4位有效数字近似数为8.000, |e*|0.0005 2.71828的4位有效数字近似数为2.718, |e*|0.0005,3 误差的基本概念,注意：8.00033的4位有效数字近似数是8.000, 而不是8. 又如：0.2300有4位有效数字，而00023只有

13、2位有效. 12300如果写成0.123105，则表示只有3位有效数字. 数字末尾的0不可随意省去！,3 误差的基本概念,例2 重力加速度g=9.80m/s,g=0.00980km/s.它们都具有3位 有效数字，其绝对误差不同(限:0.5e-2,0.5e-5)， 但相对误差(限)相同：,注: (1)相对误差(限)没有量纲，而绝对误差有量纲. (2) 对于同一量的两个不同近似值，可以通过其绝对误差来判断哪个更精确；对于两个不同量的近似值，只有通过其相对误差来比较其精确程度。,Def 1,2,例11,例12,3 误差的基本概念,有效数字与相对误差的关系, 有效数字 相对误差限,3 误差的基本概念,

14、定理2？, 相对误差限 有效数字,3 误差的基本概念,例13,例14,3 误差的基本概念,3-4 数值运算的误差估计,问题：设x的近似值为x* ，y的近似值为y* ，如下关系对吗？,分析：,(x+y)*=x*+y* (xy)*=x*y* (x/y)*=x*/y*,3 误差的基本概念,1. 算术运算的误差和绝对误差限分析特例,3 误差的基本概念,3 误差的基本概念,2 一般情况,问题：对于 y = f (x)，若用 x* 取代 x，将对y 产生什么影响？,分析：e (y*) = f (x*) f (x) e (x*) = x* x,Mean Value Theorem,= f ( )(x* x)

15、,x* 与 x 非常接近时，可认为 f ( ) f (x*) ，则有 |e (y*)| | f (x*)|e(x*)|.,即：x*产生的误差经过 f 作用后被放大/缩小了| f (x*)|倍。故称| f (x*)|为放大因子 /* amplification factor */ 或 绝对条件数 /* absolute condition number */.,3 误差的基本概念,相对误差条件数 /* relative condition number*/,f 的条件数在某一点是小大，则称 f 在该点是好条件的 /* well-conditioned */ 坏条件的 /* ill-conditi

16、oned */。,Mean Value Theorem,3 误差的基本概念,例15 : 计算 y = ln x。若 x 20，则取 x 的几位有效数字可保证 y 的相对误差 0.1% ?,解：设截取 n 位有效数字后得 x* x，则,估计 x 和 y 的相对误差上限满足近似关系, n 4,例：计算 ，取 4 位有效，即 , 则相对误差,3 误差的基本概念,3 误差的基本概念,例16,3 误差的基本概念,特例-算术运算的相对误差和相对误差限分析:,3 误差的基本概念,3 误差的基本概念,3 误差的基本概念,3 误差的基本概念,4 误差分析的方法与原则,1. 避免相近二数相减,例：a1 = 0.1

17、2345，a2 = 0.12346，各有5位有效数字。 而 a2 a1 = 0.00001，只剩下1位有效数字。, 几种经验性避免方法：,当 | x | 1 时：,4 误差分析的方法与原则,3. 避免大数吃小数,例：用单精度计算 的根。,精确解为, 算法1：利用求根公式,在计算机内，109存为0.11010，1存为0.1101。做加法时，两加数的指数先向大指数对齐，再将浮点部分相加。即1 的指数部分须变为1010，则：1 = 0.0000000001 1010，取单精度时就成为： 109+1=0.100000001010+0.00000000 1010=0.10000000 1010,大数吃小

18、数,4 误差分析的方法与原则,算法2：先解出 再利用,注：求和时从小到大相加，可使和的误差减小。,例：按从小到大、以及从大到小的顺序分别计算 1 + 2 + 3 + + 40 + 109,4. 先化简再计算，减少步骤，避免误差积累。,一般来说，计算机处理下列运算的速度为,5. 选用稳定的算法。,评价算法的准则：复杂度、精度、稳定性,4 误差分析的方法与原则,“天河一号”是中国自主研制的超级计算机，坐落在位于天津的国家超级计算中心，由140个计算机柜组成，用来执行大规模科学计算。自身没有键盘和鼠标，是通过网络的方式让用户来登陆它使用它。所以，当用户通过个人的计算机登录到“天河一号”上后，他的PC

19、机已经成为“天河一号”的末梢神经，成为一台终端设备。“天河一号”超级计算机提供的计算方式是现在业界叫作“云计算”的计算方式。 12年美国总统奥巴马在一次讲话中说：现在，不仅世界上速度最快的火车在中国？而且中国还制造出了世界上速度最快的超级计算机。,战略计算,这是因为美国克林顿总统在1995 年8月11 日宣布：“美国决定谋求真正的“零当量”全面禁止试验核武器条约”。 这并不意味着核竞赛的结束，恰恰相反是核武器计划新时代的开始，要求通过逼真的建模和模拟计算来取代传统的反复试验的工程处理方法，这主要依赖于先进的数值计算和模拟能力。 1995年8月22日（即美国总统宣布决定后的11天），能源部DOE

20、就采购世界上最快的一台计算机（速度超过万亿次运算）交付圣地亚哥实验室（96年12月安装）。 1998年7月30-31日，美国DOE/FNS 共同联合组织召开了关于“先进科学计算”的全国会议，会议强调科学模拟的重要性，希望应用科学模拟来攻克复杂的科学与工程难题。,Chapter 1 Introduction,计算机发展的四个阶段 1. 第一代计算机：电子管数字计算机（ 1946-1958 年） 硬件方面，逻辑元件采用电子管，主存储器采用汞延迟 线、磁鼓、磁芯；外存储器采用磁带。软件方面采用机器语 言、汇编语言。应用领域以军事和科学计算为主。特点是体 积大、功耗高、可靠性差、速度慢（一般为每秒数千

21、次至数 万次） 、价格昂贵，但为以后的计算机发展奠定了基础。,2. 第二代计算机：晶体管数字计算机（ 1958-1964 年） 硬件方面，逻辑元件采用晶体管，主存储器采用磁芯， 外存储器采用磁盘。软件方面出现了以批处理为主的操作系 统、高级语言及其编译程序。应用领域以科学计算和事务处 理为主。并开始进入工业控制领域。特点是体积缩小、能耗 降低、可靠性提高、运算速度提高（一般为每秒数十万次， 可高达 300 万次） 、性能比第一代计算机有很大的提高。,3. 第三代计算机：集成电路数字计算机（ 1964-1970 年） 硬件方面，逻辑元件采用中、小规模集成电路，主存储 器仍采用磁芯。软件方面出现了分时操作系统以及结构化、 规模化程序设计方法。特点是速度更快（一般为每秒数百万 至数千万次） 。而且可靠性有了显著提高，价格进一步下降， 产品走向通用话、系列化和标准化。应用领域开始进入文字 处