《数值分析与算法》第一讲数值计算的背景与概况

1、数数 值值 分分 析析 (1)Numerical AnalysisWenjian Yu2课程简介课程简介n计算方法计算方法n数值分析与算法数值分析与算法n科学计算导论科学计算导论（scientific computing）n数值计算基础数值计算基础（numerical computing）n课程目标课程目标介绍广泛应用于介绍广泛应用于科学与工程科学与工程领域的各种数值计领域的各种数值计算方法算方法 巩固巩固连续数学连续数学基础知识、增强实际应用能力基础知识、增强实际应用能力Wenjian Yu3教材教材n数值分析与算法数值分析与算法(第第2版版)清华大学出版社清华大学出版社, 2015年年课件

2、课件n参考书参考书喻文健喻文健 译译, “Matlab数值计算数值计算”, 机械工业出版社，机械工业出版社，2006年年李庆扬李庆扬 等等, 数值分析数值分析(第第5版版)，清华大学出版社清华大学出版社, 2009年年 http:/ Yu4授课方式与考核授课方式与考核n授课方式授课方式以讲授为主，辅以作业、上机实验以讲授为主，辅以作业、上机实验n考评方法考评方法作业、上机实验：作业、上机实验：35%期末闭卷考试期末闭卷考试：65%附加分：附加分：12% (实验加分、师生互动实验加分、师生互动)n作业提交纸版作业提交纸版课代表课代表收齐、或自行上交收齐、或自行上交, 周二上课交讲台周二上课交讲台

3、批改后作业也在课上取批改后作业也在课上取东主楼机房检查，提交报告东主楼机房检查，提交报告具体要求第具体要求第5周布置周布置Wenjian Yu5主要教学内容主要教学内容n一一.数值计算导论数值计算导论概述、误差分析基础概述、误差分析基础(近似、有效数字、误差分类、问近似、有效数字、误差分类、问题的敏感性、算法的稳定性题的敏感性、算法的稳定性)、浮点算术系统与舍入误、浮点算术系统与舍入误差差(“抵消抵消”现象、减小舍入误差的建议等现象、减小舍入误差的建议等)n二二.非线性方程解法非线性方程解法n三三.线性方程组的直接解法线性方程组的直接解法n四四.线性方程组的迭代解法线性方程组的迭代解法n五五.

4、矩阵特征值计算矩阵特征值计算Wenjian Yu6主要教学内容主要教学内容n六六-1.函数逼近与线性最小二乘函数逼近与线性最小二乘n六六-2.函数插值函数插值n七七.数值积分与微分数值积分与微分n八八.常微分方程初值问题常微分方程初值问题n附加附加.Matlab数值计算与应用数值计算与应用补充内容、非考试要求补充内容、非考试要求穿插在各章内容中穿插在各章内容中类似数学基础课：公式多、推导多、还有理论证明类似数学基础课：公式多、推导多、还有理论证明注重实际应用：要上机编程、实验，有时还需要点经验注重实际应用：要上机编程、实验，有时还需要点经验Wenjian Yu7学习本课程的建议学习本课程的建议

5、n往届学生的主要问题往届学生的主要问题到了大三、大四，已不到了大三、大四，已不适应适应本课程考试形式本课程考试形式思想上不思想上不重视重视、投入精力不够、投入精力不够n措施和建议措施和建议教师要改进教学，调整考核机制教师要改进教学，调整考核机制学生要严格要求自己，把握学生要严格要求自己，把握听课听课、作业、实验环、作业、实验环节节重点理解问题背景、算法思路和具体步骤重点理解问题背景、算法思路和具体步骤(会算会算)适当进行公式推导、算法复杂度分析与比较，提适当进行公式推导、算法复杂度分析与比较，提高解决具体问题的能力高解决具体问题的能力借助借助教学演示网站教学演示网站、Matlab软件软件, 提

6、升学习兴趣提升学习兴趣!多人不及格，多人不及格，甚至影响毕业甚至影响毕业Wenjian Yu8数值计算的背景与概况数值计算的背景与概况Wenjian Yu9数值分析、科学计算、数值计算数值分析、科学计算、数值计算 数值计算，也称为科学计算，已成为当今科学研究的数值计算，也称为科学计算，已成为当今科学研究的三种三种基本手段基本手段之一。它是计算数学、计算机科学和其他工程学之一。它是计算数学、计算机科学和其他工程学科相结合的产物，并随着计算机的普及和各门类科学技术科相结合的产物，并随着计算机的普及和各门类科学技术的迅速发展日益受到人们的重视。的迅速发展日益受到人们的重视。 参考书译者序参考书译者序

7、科学计算的发展分硬件和软件两个方面，这里我们只考科学计算的发展分硬件和软件两个方面，这里我们只考虑软件方面，即虑软件方面，即数值计算的有关算法数值计算的有关算法 (数值仿真软件数值仿真软件)“数值分析数值分析”、“数值计算数值计算”是研究求解连续数学问题的是研究求解连续数学问题的算法的学科（而不仅仅局限于计算误差的研究）算法的学科（而不仅仅局限于计算误差的研究）对象对象核心核心Wenjian Yu10Top ten algorithms of the centuryn1.1946 美国美国Los Alamos国家实验室的国家实验室的J. von Neumann, S. Ulam和和N. Met

8、ropolis提出的提出的Metropolis算法（算法（Monte Carlo方法最成功、最有影响的一个）方法最成功、最有影响的一个）n2.1947 美国兰德（美国兰德（RAND）公司的）公司的G. Dantzig提出的解线性提出的解线性规划的单纯形算法（规划的单纯形算法（simplex method）n3.1950 美国美国UCLA大学与美国国家标准局数值分析所的大学与美国国家标准局数值分析所的M. Hestenes, E. Stiefel和和C. Lanczos开创的开创的Krylov子空间迭子空间迭代法代法(Lanczos过程、过程、CG算法算法)n4.1950s 美国橡树岭（美国橡树

9、岭（Oak Ridge）国家实验室的）国家实验室的A. Householder形式化的矩阵分解方法形式化的矩阵分解方法(表示为矩阵分解表示为矩阵分解)“We tried to assemble the 10 algorithms with the greatest influence on the development and practice of science and engineering in the 20th century”Editors of IEEE Computational Science and Engineering, Jan. 2000 (后被后被SIAM转载转载

10、)Wenjian Yu11Top ten algorithms of the centuryn5.1957 美国美国IBM的的J. Backus领导开发的领导开发的Fortran最优编译器最优编译器n6.1959-61 英国英国Ferranti Ltd.的的J.G.F. Francis发明发明QR算法，算法，能稳定的计算矩阵特征值能稳定的计算矩阵特征值n7.1962 英国英国Elliot Brothers, Ltd.的的Tony Hoare提出快速排提出快速排序算法（序算法（Quicksort）n8.1965 美国美国IBM Watson研究中心的研究中心的J. Cooley与普林斯顿大与普林

11、斯顿大学及学及AT&T Bell Lab.的的J. Turkey共同提出了的共同提出了的FFT算法算法n9.1977 美国美国Brigham Young大学的大学的H. Ferguson和和R. Forcede提出的整数关系侦察算法提出的整数关系侦察算法(integer relation detection)n10.1987 美国美国Yale大学的大学的L. Greengard和和V. Rokhlin发明的发明的快速多极算法快速多极算法(fast multipole algorithm)除了除了No. 5, 7, 9外，都属于或涉及数值计算的范畴外，都属于或涉及数值计算的范畴!Wenj

12、ian Yu12数值算法与非数值算法数值算法与非数值算法n算法分为算法分为“数值算法数值算法”和和“非数值算法非数值算法”n数值算法用途非常广泛，发展迅速，具有跨学科的特数值算法用途非常广泛，发展迅速，具有跨学科的特点点n“非数值算法非数值算法”的研究则通常归于的研究则通常归于“计算机科学计算机科学”From D. E. Knuth, The art of computer programming, Vol. 1 (计算机程序设计艺术计算机程序设计艺术) We might call the subject of these books “nonnumerical analysis.” Comp

13、uters have traditionally been associated with the solution of numerical problems such as Numerical computer programming is an extremely interesting and rapidly expanding field, and many books have been written about it. The art of computer programming系列系列Wenjian Yu13n好数值算法的特点好数值算法的特点计算效率高、计算复杂度低计算效率

14、高、计算复杂度低可靠性好：在考虑实际计算的各种误差情况下，结果尽可靠性好：在考虑实际计算的各种误差情况下，结果尽可能地准确可能地准确数值计算与数值算法数值计算与数值算法n数值计算的特点数值计算的特点（区别于其他计算机方向）（区别于其他计算机方向）处理连续数学的量处理连续数学的量(实数量实数量)，问题中常涉及微分、积分，问题中常涉及微分、积分和非线性。被求解的问题一般没有解析解、或理论上无和非线性。被求解的问题一般没有解析解、或理论上无法通过有限步计算求解法通过有限步计算求解n无解析解：无解析解：n有解析解，但需无限步计算：有解析解，但需无限步计算：sin(x)n更多的实际应用问题通过数值模拟来

15、解决更多的实际应用问题通过数值模拟来解决目标目标：寻找迅速完成的：寻找迅速完成的(迭代迭代)算法，评估结果的准确度算法，评估结果的准确度Wenjian Yu14数值计算的步骤数值计算的步骤建立数学模型（需要相关学科背景）建立数学模型（需要相关学科背景）研究数值求解方程的算法研究数值求解方程的算法通过计算机软件实现算法通过计算机软件实现算法在计算机上运行软件进行数值模拟在计算机上运行软件进行数值模拟将计算结果用较直观的方式输出，如图形可视化方法将计算结果用较直观的方式输出，如图形可视化方法解释和验证计算结果，如果需要重复上面的某些步骤解释和验证计算结果，如果需要重复上面的某些步骤上述各步骤相互间

16、紧密地关联，影响着最终的计算结果上述各步骤相互间紧密地关联，影响着最终的计算结果和效率（问题的实际背景和要求也左右着方法的选择）和效率（问题的实际背景和要求也左右着方法的选择）本课程学习重点本课程学习重点 设计数值方法设计数值方法(算法算法)的关键：将问题简化的关键：将问题简化(估计带来的估计带来的误差误差)，然后求解简化后的问题，然后求解简化后的问题Wenjian Yu15数值软件数值软件/程序包程序包n数值计算的软件与程序包数值计算的软件与程序包解决常见问题，促进各个科学和工程领域的科研解决常见问题，促进各个科学和工程领域的科研了解基本原理，学习算法设计和实现技巧了解基本原理，学习算法设计

17、和实现技巧成为聪明的软件成为聪明的软件/程序包使用者程序包使用者n存在形式和资源存在形式和资源商业软件商业软件/免费软件，互联网上共享的程序包免费软件，互联网上共享的程序包Fortran, C, C+, Matlab源代码使用，或源代码使用，或API调用调用交互式集成环境的软件交互式集成环境的软件Wenjian YInternet网络资源越来越网络资源越来越丰富，使用越来越方便！丰富，使用越来越方便！345Wenjian Yu17n广泛应用的数值计算软件：广泛应用的数值计算软件：Matlab集成环境：交互式计算系统，高级编程语言集成环境：交互式计算系统，高级编程语言数值计算、矩阵

18、计算功能强数值计算、矩阵计算功能强(包含很多先进算法包含很多先进算法)，方便，方便的计算可视化功能的计算可视化功能大量专题工具箱大量专题工具箱(Toolbox)，为专业应用提供便利，为专业应用提供便利建议大家学习、使用建议大家学习、使用MatlabWenjian Yu18n数值计算知识应用广泛数值计算知识应用广泛 (以计算机相关方向为例以计算机相关方向为例)人工智能、机器人控制：矩阵特征值、奇异值分解、常人工智能、机器人控制：矩阵特征值、奇异值分解、常微分方程数值解、最小二乘拟合微分方程数值解、最小二乘拟合计算机图形学计算机图形学CAD：函数插值、逼近、微分方程数值解：函数插值、逼近、微分方程

19、数值解集成电路集成电路CAD（EDA）：大规模线性方程组求解、常微）：大规模线性方程组求解、常微分方程、偏微分方程分方程、偏微分方程系统软件、编译、网络等方向：线性方程组求解、非线系统软件、编译、网络等方向：线性方程组求解、非线性方程组求解性方程组求解高性能计算：用数值算法来评测机器性能高性能计算：用数值算法来评测机器性能电力系统仿真、大气仿真，。电力系统仿真、大气仿真，。n是数学规划是数学规划/最优化算法的基础，部分内容也是大最优化算法的基础，部分内容也是大数据分析、机器学习中一些复杂算法的基础数据分析、机器学习中一些复杂算法的基础Wenjian Yu19误差分析基础误差分析基础Wenjia

20、n Yu20误差分析基础误差分析基础n1.2.1误差的来源误差的来源n1.2.2误差及其分类误差及其分类误差与有效数字误差与有效数字数据传递误差与计算误差数据传递误差与计算误差截断误差与舍入误差截断误差与舍入误差n1.2.3问题的敏感性与数据传递误差问题的敏感性与数据传递误差n1.2.4算法的稳定性算法的稳定性Wenjian Yu21误差的来源误差的来源n模型误差模型误差 ( (忽略摩擦、空气阻力忽略摩擦、空气阻力) )n数据误差数据误差 常数或测量值、前一步计算常数或测量值、前一步计算 的结果的结果n截断误差截断误差 方法误差方法误差 例例: : sin(x)= = n舍入误差舍入误差 计算

21、时表示数的位数有限计算时表示数的位数有限需需“四舍五入四舍五入”计算前计算前计算中计算中例例1.1 用球表面积公式计算地球表面积用球表面积公式计算地球表面积24Ar模型误差数据误差数据误差舍入误差Wenjian Yu22误差及其分类误差及其分类n便于绝对误差限便于绝对误差限相对误差限相对误差限Wenjian Yu23误差及其分类误差及其分类nWenjian Yu24误差及其分类误差及其分类n以上是根据以上是根据正确的有效数字位数正确的有效数字位数判断判断相对误差限相对误差限反过来呢？反过来呢？Wenjian Yu25误差及其分类误差及其分类nWenjian Yu26误差及其分类误差及其分类nW

22、enjian Yu27误差及其分类误差及其分类nWenjian Yu28误差及其分类误差及其分类nf(x)=sinx, x=1Wenjian Yu29问题的敏感性问题的敏感性 (数据传递误差数据传递误差)n范数范数(近似公式近似公式)Wenjian Yu30问题的敏感性问题的敏感性 (数据传递误差数据传递误差)nWenjian Yu31算法的稳定性算法的稳定性n与问题的敏感性相对应的一个概念；也叫与问题的敏感性相对应的一个概念；也叫数值稳定性数值稳定性n1结果对计算结果对计算过程中的扰动过程中的扰动不敏感的算法是不敏感的算法是稳定的稳定的算法算法n例例1.7 对长度对长度100的数组求和的数组

23、求和, 每个数只有每个数只有2位数字精度位数字精度n算法算法1: 按存储顺序对这按存储顺序对这100个数直接累加个数直接累加n若实际数据为若实际数据为1.0, 0.01, , 0.01 (99个个), 则结果？则结果？n算法算法2: 先按元素绝对值递增的顺序排序先按元素绝对值递增的顺序排序, 再依次求和再依次求和n对上述数据取值对上述数据取值, sum=0.99+1.0= 2.0, 更准确更准确!n2对包含一系列计算的过程对包含一系列计算的过程, 若计算中的小扰动不放大若计算中的小扰动不放大或放大不严重或放大不严重, 则该过程对应的算法是则该过程对应的算法是稳定的稳定的算法算法sum=1.0算

24、法算法2比算法比算法1更稳定！更稳定！Wenjian Yu32算法的稳定性算法的稳定性n每步仅做每步仅做一次减法一次减法n20.38196630.236068180.000144190.00015420-0.000010 , Wenjian Yu33算法的稳定性算法的稳定性n每步仅做每步仅做一次减法一次减法思考思考: 从条件数角度分析算法从条件数角度分析算法2为何不稳定为何不稳定n20.38196630.236068180.000144190.00015420-0.000010Wenjian Yu34算法的稳定性算法的稳定性nWenjian Yu35计算机浮点数系统计算机浮点数系统Wenjia

25、n Yu36计算机浮点数系统与舍入误差计算机浮点数系统与舍入误差n(课本1.3节的部分内容)Wenjian Yu37计算机中的浮点数计算机中的浮点数nWenjian Yu38计算机中的浮点数计算机中的浮点数n浮点数系统浮点数系统IEEE单精度单精度224-1261275.96010-8IEEE双精度双精度253-102210231.11010-16例例: 一个简单浮点数系统一个简单浮点数系统,(5位二进制位二进制)2.210-308Wenjian Yu39计算机中的浮点数计算机中的浮点数n(证明留做课后思考)应用定理应用定理1.2可证明可证明!，2进制进制应用定理应用定理1.3证明证明!Wenjian Yu40抵消现象抵消现象n(操作数操作数往往往往有误差有误差)Wenjian Yu41抵消现象抵消现象n一元二次方程求根公式的例子一元二次方程求根公式的例子解为：解为：解决办法：解决办法：bbacbbaccbbacbbaccx xa abbacbbacbbacbbac22221 122224424422 24444计算计算x2可能出现的问题也类似地解决可能出现的问题也类似