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

数值分析(1)NumericalAnalysisWenjianYu2课程简介计算方法数值分析与算法科学计算导论（scientificcomputing）数值计算基础（numericalcomputing）课程目标介绍广泛应用于科学与工程领域的各种数值计算方法巩固连续数学基础知识、增强实际应用能力WenjianYu3教材数值分析与算法(第2版)清华大学出版社,2015年课件参考书喻文健译,“Matlab数值计算”,机械工业出版社，2006年李庆扬等,数值分析(第5版)，清华大学出版社,2009年授课方式与考核授课方式以讲授为主，辅以作业、上机实验考评方法作业、上机实验：35%期末闭卷考试：65%附加分：1~2%(实验加分、师生互动)作业提交纸版课代表收齐、或自行上交,周二上课交讲台批改后作业也在课上取东主楼机房检查，提交报告具体要求第5周布置WenjianYu5主要教学内容一.数值计算导论概述、误差分析基础(近似、有效数字、误差分类、问题的敏感性、算法的稳定性)、浮点算术系统与舍入误差(“抵消”现象、减小舍入误差的建议等)二.非线性方程解法三.线性方程组的直接解法四.线性方程组的迭代解法五.矩阵特征值计算WenjianYu6主要教学内容六-1.函数逼近与线性最小二乘六-2.函数插值七.数值积分与微分八.常微分方程初值问题附加.Matlab数值计算与应用补充内容、非考试要求穿插在各章内容中类似数学基础课：公式多、推导多、还有理论证明注重实际应用：要上机编程、实验，有时还需要点经验WenjianYu7学习本课程的建议往届学生的主要问题到了大三、大四，已不适应本课程考试形式思想上不重视、投入精力不够措施和建议教师要改进教学，调整考核机制学生要严格要求自己，把握听课、作业、实验环节重点理解问题背景、算法思路和具体步骤(会算)适当进行公式推导、算法复杂度分析与比较，提高解决具体问题的能力借助教学演示网站、Matlab软件,提升学习兴趣!多人不及格，甚至影响毕业WenjianYu8数值计算的背景与概况WenjianYu9数值分析、科学计算、数值计算数值计算，也称为科学计算，已成为当今科学研究的三种基本手段之一。它是计算数学、计算机科学和其他工程学科相结合的产物，并随着计算机的普及和各门类科学技术的迅速发展日益受到人们的重视。参考书译者序科学计算的发展分硬件和软件两个方面，这里我们只考虑软件方面，即数值计算的有关算法(数值仿真软件)“数值分析”、“数值计算”是研究求解连续数学问题的算法的学科（而不仅仅局限于计算误差的研究）对象核心WenjianYu10Toptenalgorithmsofthecentury1.1946美国LosAlamos国家实验室的J.vonNeumann,S.Ulam和N.Metropolis提出的Metropolis算法（MonteCarlo方法最成功、最有影响的一个）2.1947美国兰德（RAND）公司的G.Dantzig提出的解线性规划的单纯形算法（simplexmethod）3.1950美国UCLA大学与美国国家标准局数值分析所的M.Hestenes,E.Stiefel和C.Lanczos开创的Krylov子空间迭代法(Lanczos过程、CG算法)4.1950’s美国橡树岭（OakRidge）国家实验室的A.Householder形式化的矩阵分解方法(表示为矩阵分解)“Wetriedtoassemblethe10algorithmswiththegreatestinfluenceonthedevelopmentandpracticeofscienceandengineeringinthe20thcentury”EditorsofIEEEComputationalScienceandEngineering,Jan.2000(后被SIAM转载)WenjianYu11Toptenalgorithmsofthecentury5.1957美国IBM的J.Backus领导开发的Fortran最优编译器6.1959-61英国FerrantiLtd.的J.G.F.Francis发明QR算法，能稳定的计算矩阵特征值7.1962英国ElliotBrothers,Ltd.的TonyHoare提出快速排序算法（Quicksort）8.1965美国IBMWatson研究中心的J.Cooley与普林斯顿大学及AT&TBellLab.的J.Turkey共同提出了的FFT算法9.1977美国BrighamYoung大学的H.Ferguson和R.Forcede提出的整数关系侦察算法(integerrelationdetection)10.1987美国Yale大学的L.Greengard和V.Rokhlin发明的快速多极算法(fastmultipolealgorithm)除了No.5,7,9外，都属于或涉及数值计算的范畴!WenjianYu12数值算法与非数值算法算法分为“数值算法”和“非数值算法”数值算法用途非常广泛，发展迅速，具有跨学科的特点“非数值算法”的研究则通常归于“计算机科学”FromD.E.Knuth,Theartofcomputerprogramming,Vol.1(《计算机程序设计艺术》)……Wemightcallthesubjectofthesebooks“nonnumericalanalysis.”Computershavetraditionallybeenassociatedwiththesolutionofnumericalproblemssuchas……Numericalcomputerprogrammingisanextremelyinterestingandrapidlyexpandingfield,andmanybookshavebeenwrittenaboutit.Theartofcomputerprogramming系列WenjianYu13好数值算法的特点计算效率高、计算复杂度低可靠性好：在考虑实际计算的各种误差情况下，结果尽可能地准确数值计算与数值算法数值计算的特点（区别于其他计算机方向）处理连续数学的量(实数量)，问题中常涉及微分、积分和非线性。被求解的问题一般没有解析解、或理论上无法通过有限步计算求解无解析解：有解析解，但需无限步计算：sin(x)更多的实际应用问题通过数值模拟来解决目标：寻找迅速完成的(迭代)算法，评估结果的准确度WenjianYu14数值计算的步骤建立数学模型（需要相关学科背景）研究数值求解方程的算法通过计算机软件实现算法在计算机上运行软件进行数值模拟将计算结果用较直观的方式输出，如图形可视化方法解释和验证计算结果，如果需要重复上面的某些步骤上述各步骤相互间紧密地关联，影响着最终的计算结果和效率（问题的实际背景和要求也左右着方法的选择）本课程学习重点•设计数值方法(算法)的关键：将问题简化(估计带来的误差)，然后求解简化后的问题WenjianYu15数值软件/程序包数值计算的软件与程序包解决常见问题，促进各个科学和工程领域的科研了解基本原理，学习算法设计和实现技巧成为聪明的软件/程序包使用者存在形式和资源商业软件/免费软件，互联网上共享的程序包Fortran,C,C++,Matlab源代码使用，或API调用交互式集成环境的软件网络资源越来越丰富，使用越来越方便！[3][4][5]WenjianYu17广泛应用的数值计算软件：Matlab集成环境：交互式计算系统，高级编程语言数值计算、矩阵计算功能强(包含很多先进算法)，方便的计算可视化功能大量专题工具箱(Toolbox)，为专业应用提供便利建议大家学习、使用MatlabWenjianYu18数值计算知识应用广泛(以计算机相关方向为例)人工智能、机器人控制：矩阵特征值、奇异值分解、常微分方程数值解、最小二乘拟合计算机图形学CAD：函数插值、逼近、微分方程数值解集成电路CAD（EDA）：大规模线性方程组求解、常微分方程、偏微分方程系统软件、编译、网络等方向：线性方程组求解、非线性方程组求解高性能计算：用数值算法来评测机器性能电力系统仿真、大气仿真，。。。。。。是数学规划/最优化算法的基础，部分内容也是大数据分析、机器学习中一些复杂算法的基础WenjianYu19误差分析基础WenjianYu20误差分析基础§1.2.1误差的来源§1.2.2误差及其分类误差与有效数字数据传递误差与计算误差截断误差与舍入误差§1.2.3问题的敏感性与数据传递误差§1.2.4算法的稳定性WenjianYu21误差的来源模型误差(忽略摩擦、空气阻力)数据误差常数或测量值、前一步计算的结果截断误差方法误差例:sin(x)=…舍入误差计算时表示数的位数有限需“四舍五入”计算前计算中例1.1用球表面积公式计算地球表面积24Ar模型误差数据误差数据误差舍入误差WenjianYu22误差及其分类便于绝对误差限相对误差限WenjianYu23误差及其分类WenjianYu24误差及其分类以上是根据正确的有效数字位数判断相对误差限反过来呢？WenjianYu25误差及其分类WenjianYu26误差及其分类WenjianYu27误差及其分类WenjianYu28误差及其分类f(x)=sinx,x=1WenjianYu29问题的敏感性(数据传递误差)范数(近似公式)WenjianYu30问题的敏感性(数据传递误差)WenjianYu31算法的稳定性与问题的敏感性相对应的一个概念；也叫数值稳定性1结果对计算过程中的扰动不敏感的算法是稳定的算法例1.7对长度100的数组求和,每个数只有2位数字精度算法1:按存储顺序对这100个数直接累加若实际数据为1.0,0.01,…,0.01(99个),则结果？算法2:先按元素绝对值递增的顺序排序,再依次求和对上述数据取值,sum=0.99+1.0=2.0,更准确!2对包含一系列计算的过程,若计算中的小扰动不放大或放大不严重,则该过程对应的算法是稳定的算法sum=1.0算法2比算法1更稳定！WenjianYu32算法的稳定性每步仅做一次减法n20.38196630.236068……180.000144190.00015420-0.000010…,WenjianYu33算法的稳定性每步仅做一次减法思考:从条件数角度分析算法2为何不稳定n20.38196630.236068……180.000144190.00015420-0.000010WenjianYu34算法的稳定性WenjianYu35计算机浮点数系统WenjianYu36计算机浮点数系统与舍入误差(课本1.3节的部分内容)WenjianYu37计算机中的浮点数WenjianYu38计算机中的浮点数浮点数系统IEEE单精度224-1261275.96010-8IEEE双精度253-102210231.11010-16例:一个简单浮点数系统,(5位二进制)~2.210-308WenjianYu39计算机中的浮点数(证明留做课后思考)应用定理1.2可证明!，2进制应用定理1.3证明!WenjianYu40抵消现象(操作数往往有误差)WenjianYu41抵消现象一元二次方程求根公式的例子解为：解决办法：bbacbbaccxabbacbbac22122442244计算x2可能出现的问题也类似地解决(算法的调整)WenjianYu42保证计算结果的准确性WenjianYu43减