数值计算 第一讲

1、数值分析与算法 (1)Numerical Analysis & Algorithms清华大学 计算机系 喻文健Wenjian Yu2课程简介计算方法数值分析与算法科学计算导论（scientific computing）数值计算基础（numerical computing）课程目标介绍广泛应用于科学与工程领域的各种数值计算方法 巩固连续数学基础知识、增强实际应用能力Wenjian Yu3授课方式与考核授课方式以讲授为主，辅以作业、上机实验考评方法作业、上机实验：30%期末闭卷考试：70%附加分：3-5% (实验加分、师生互动)，编程Project?作业提交纸版课代表收齐交助教处(东主楼8-404

2、)，周日晚10:30前散选同学上课时交讲台实验在系机房检查，具体要求第5周布置Wenjian Yu4主要教学内容一.绪论 (数值分析与科学计算引论)误差的基本概念(有效数字)、数值运算的误差限、问题的敏感性与条件数、数值算法的稳定性、“抵消”现象、减小舍入误差的建议二.非线性方程解法三.线性方程组的直接解法四.线性方程组的迭代解法五.矩阵特征值计算Wenjian Yu5主要教学内容六-1.函数逼近与线性最小二乘六-2.函数插值七.数值积分与微分八.常微分方程初值问题附加.Matlab数值计算与应用补充内容、非考试要求穿插在各章内容之间类似数学基础课：公式多、推导多、还有理论证明注重实际应用：要

3、上机编程，有时还包含经验成份Wenjian Yu6数值计算的背景与概况Wenjian Yu7数值分析、科学计算、数值计算 数值计算作为当今科学研究的三种基本手段之一，是数学和计算机应用于其他学科的桥梁，因此它的发展受到广泛关注。有些发达国家甚至将科学计算作为衡量国家综合实力的一个重要方面，大力推动其发展。 参考书影印版序言科学计算的发展分硬件和软件两个方面，这里我们只考虑软件方面，即数值计算的有关算法 (数值仿真软件)“数值分析”、“数值计算”是研究求解连续数学问题的算法的学科（而不仅仅局限于计算误差的研究）对象核心Wenjian Yu8Top ten algorithms of the ce

4、ntury1.1946 Los Alamos国家实验室的J. von Neumann, S. Vlam和N. Metropolis编的Metropolis算法,即Monte Carlo方法（“随机漫步”）2.1947 兰德（RAND）公司的G. Dantzig创造的线性规划的单纯型算法（simplex method）3.1950 美国国家标准局数值分析所的M. Hestenes, E. Stiefel和C. Lanczos开创的Krylov子空间迭代法4.1951 橡树岭（Oak Ridge）国家实验室的A. House-holder形式化的矩阵计算的分解方法(矩阵的各种分解)“We trie

5、d 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转载)Wenjian Yu9Top ten algorithms of the century5.1951 IBM由J. Backus领导的小组研制Fortran最优编译器6.1

6、959-61 伦敦Ferranti Ltd.的J.G.F. Francis发明QR算法，能稳定的计算矩阵特征值7.1962 伦敦Elliot Brothers, Ltd.的Tony Hoare提出快速排序算法（Quicksort）8.1965 IBM Watson研究中心的J. Cooley与U. Princeton及AT&T Bell Lab.的J. Turkey共同提出了的FFT算法9.1977 Brigham Young大学的H. Ferguson和R. Forcede提出的整数关系侦察算法（integer relation detection）10.1987 Yale大学的L. Gre

7、engard和V. Rokhlin发明了快速多极算法(fast multipole algorithm)除了No. 5, 7, 9外，都属于或涉及数值计算的范畴!Wenjian Yu10数值算法与非数值算法算法分为“数值算法”和“非数值算法”数值算法用途非常广泛，发展迅速，具有跨学科的特点“非数值算法”的研究则通常归于“计算机科学”From D. E. Knuth, The art of computer programming, Vol. 1 (计算机程序设计艺术) We might call the subject of these books “nonnumerical analysis

8、.” Computers 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 Yu11好数值算法的特点计算效率高、计算复杂度低可靠性好：在考虑

9、实际计算的各种误差情况下，结果尽可能地准确数值计算与数值算法数值计算的特点（区别于其他计算机方向）处理连续数学的量(实数量)，问题中常涉及微分、积分和非线性。被求解的问题一般没有解析解、或理论上无法通过有限步计算求解无解析解：有解析解，但需无限步计算：sinx更多的实际应用问题通过数值模拟来解决目标：寻找快速结束(收敛)的算法，评估结果的准确度Wenjian Yu12数值计算的步骤建立数学模型（需要相关学科背景）研究数值求解方程的算法通过计算机软件实现算法在计算机上运行软件进行数值模拟将计算结果用较直观的方式输出，如图形可视化方法解释和验证计算结果，如果需要重复上面的某些步骤上述各步骤相互间紧

10、密地关联，影响着最终的计算结果和效率（问题的实际背景和要求也左右着方法的选择）本课程学习重点设计数值方法(算法)的关键：将问题简化(估计带来的误差)，然后求解简化后的问题Wenjian Yu13数值软件/程序包数值计算的软件与程序包解决常见问题，促进各个科学和工程领域的科研了解基本原理，学习算法设计和实现技巧成为聪明的软件/程序包使用者存在形式和资源互联网，免费/商业代码Fortran, C, C+, Matlab源代码使用，或API调用交互式集成环境的软件Wenjian Yu14Internet网络资源越来越丰富，使用越来越方便！Wenjian Yu15广泛应用的数值计算软件：Matlab集

11、成环境：交互式计算系统，高级编程语言数值计算、矩阵计算功能强(包含很多先进算法)，方便的计算可视化功能大量专题工具箱(Toolbox)，为专业应用提供便利建议大家学习、使用MatlabWenjian Yu16数值计算知识应用广泛 (以计算机系方向为例)人工智能、机器人控制：矩阵特征值、奇异值分解、常微分方程数值解、最小二乘拟合计算机图形学CAD：函数插值、逼近、微分方程数值解集成电路CAD（EDA）：大规模线性方程组求解、常微分方程、偏微分方程系统软件、编译、网络等方向：线性方程组求解、非线性方程组求解高性能计算：用数值算法来评测机器性能更广泛的应用电力系统仿真、大气仿真 更多科学与工程领域W

12、enjian Yu17误差分析基础Wenjian Yu18误差分析基础1.2.1误差的来源1.2.2误差及其分类误差与有效数字截断误差与舍入误差数据传递误差与计算误差1.2.3问题的敏感性与数据传递误差1.2.4算法的稳定性(通过板书讲解)Wenjian Yu19计算机浮点数系统Wenjian Yu20计算机浮点数系统与舍入误差(课本1.3节的部分内容)Wenjian Yu21计算机中的浮点数Wenjian Yu22计算机中的浮点数浮点数系统IEEE单精度224-1261275.96010-8IEEE双精度253-102210231.11010-16例: 一个简单浮点数系统,Wenjian Y

13、u23计算机中的浮点数(了解即可, 不要求证明)Wenjian Yu24抵消现象Wenjian Yu25抵消现象一元二次方程求根公式的例子解为：解决办法：计算x2可能出现的问题也类似地解决Wenjian Yu26建议与总结Wenjian Yu27减小舍入误差的几条建议采用双精度浮点数，一般舍入误差不大对包含大量计算的算法，分析舍入误差很难应遵循如下几条建议避免中间计算结果出现上(下)溢出避免“大数吃掉小数”(加、减法)避免符号相同的两相近数相减注意简化步骤，减少运算次数例：计算Wenjian Yu28总结总误差计算误差数据传递误差截断误差舍入误差如何评估大小？根据不同问题和方法进行讨论向后误差分析；区间分析法；很难定量分析问题敏感性(条件数