计算方法第一章

1、数值计算方法数值计算方法The Method of Numerical ComputationNumerical Analysis教教 材材林成森 编著数值计算方法 上下册科学出版社 1998什么是科学计算 科学计算就是研究如何在计算机上解决工程中数学问题。 科学计算包含数值方法研究和应用研究两部分。 数值方法研究包含理论和算法两部分， 这是科学计算的核心部分，即计算数学。 应用部分：计算物理，计算流体，计算生物学，计算大气物理，数值预报，CAD/CAM, 大规模社会计算等等。 在科学研究中，科学计算已成为与理论研究和实验研究相并列的三大重要手段之一。科学计算回顾 从人类结绳记事起，就开始了计

2、算，就孕育了计算数学。 现代科学计算的主要发展阶段是从电子计算机诞生开始。 计算数学与其他学科的结合，开拓出更为广阔的新天体。象计算物理，计算流体，计算生物学，计算大体物理，数值预报，CAD/CAM等等。科学计算回顾“科学计算”一词首次出现在1983年，由美国国防部、能源部、国家科学基金会及国家航天局等单位主持下，一个由美国著名数学家拉克斯（P.Lax）为首的不同学科的专家委员会向美国政府提出的报告之中，强调“科学计算是关系到国家安全、经济发展和科技进步的关键性环节，是事关国家命脉的大事。” 1984年美国政府大幅度地增加对科学计算经费的支持, 新建成五个国家级超级计算中心（分别在普林斯顿大学

3、、圣地亚哥、伊里诺大学、康奈尔大学、匹兹堡），配备当时最高性能的计算机，建立NSF-net新网络。科学计算回顾 1987年起美国NSF把“科学与工程计算”、“生物工程”、“全局性科学”作为三大优先资助的领域。 1990年美国国家研究委员会发表振兴美国数学：90年代的计划的报告，建议对由计算引发的数学给予特殊的鼓励和资助。报告指出由于大存储的高速计算机的使用已导致了科学和技术方面的两大突出进展：一是大量用于设计工作的实验被数学模型的研究逐步取代，如航天飞机设计、反应堆设计、人工心瓣膜设计等；二是能获取和存储大量的数据，并能提取隐秘的信息，如计算机层析X射线摄影，核磁共振等。科学计算回顾1991年

4、以美国总统倡议的形式提出了“高性能计算与通信（HPCC）计划”。这是为了保持和提高美国在计算和网络的所有先进领域中的领导地位而制定的。该计划为期五年（19921996），由美国8个重要部门负责实施。投资的重点（43）是发展先进的软件技术与并行算法，关键技术是可扩展的大规模并行计算。 要求到1996年高性能计算能力提高14倍，达到每秒万亿次浮点运算速度（1012 Teraops/S）。计算机网络通迅能力提高1百倍，达到每秒109位（Gigabits/S）。 该计划中列举的“挑战”项目有：磁记录技术、药物设计、催化、燃烧、海洋模拟、臭氧洞、空气污染、高速民用运输机、数字解剖、蛋白质结构设计、金星成

5、像等。科学计算回顾 80年代中期我国将“大规模科学与工程计算”列入国家资助重大项目。 1985-1990 现代数学研究NSFC 200万程民德，其中计算数学50万冯康 1991-1995 攀登一期，大规模科学与工程计算的方法和理论，500万冯康石钟慈 1996-1999 攀登二期500万石钟慈 2000-2004 973一期，大规模科学计算研究，3000万杜强 2006-2010 973二期，高性能科学计算研究，2500万陈志明科学计算回顾 大规模科学计算研究 复杂流动的高精度数值模拟 物质性质机理的多尺度计算研究 油藏模拟与波动问题及其反问题计算 基础计算方法的创新与发展 大规模计算工程软件

6、系统的基础理论和实施科学计算回顾高性能科学计算研究 创新计算方法的基础理论研究 大规模并行计算研究 复杂流动问题的高性能算法研究 材料物性的多物理多尺度计算研究科学计算与其他学科的关系 数学学科始终是科学计算发展的依托；科学计算反过来又给数学各分支提出了新问题、新方法、新思想。 计算机科学的发展强烈影响着科学计算的内容、方法、地位和层次。由于计算机的发展，许多数学软件的生成、开拓、丰富和发展，给数学，特别是科学计算以更大的便利。 科学计算对其他学科的渗透，吸收以及相互结合，提出了丰富的研究内容，开拓着新的方向，提出了新的理论课题。 科学计算发展的生命力是由于计算机科学和数学学科的发展，它的源动

7、力来自于各自然科学和工程技术，以及人类改造自然，建设家园的需求和任务。科学计算与其他学科的关系 科学计算的许多方法、方向，乃至理论课题，常常起源于或者萌芽于其他相关的自然学科，其中包括数学学科。有限元的发展非常突出的表现了这一点，它起源于结构分析，后来由许多数学家与力学家共同丰富和发展了它。 偏微分方程数值方法作为科学计算的另一典型方向，它的发展，丰富，同样展现了数学家与物理，力学家共同智慧的结晶。古老的差分方法在当代取得了迅速而深刻的发展，最具代表性的是高分辨方法的兴起。 Courant，Von Neumann奠基的差分方法理论，在后来的弱解问题研究中，首先从热力学理论受到启发，Lax 等许

8、多数学家对熵条件从不同侧面进行了研究，并在数值实现中得到了具体的贯彻。科学计算与其他学科的关系 在八、九十年代的间断解方法设计中，以各种丰富的形式，如Up-winding（迎风），TVD，ENO/WENO ，MUSCL，PPM，Roe方法，GRP（广义Riemann问题方法），Godunov方法以及间断有限元方法得以实现，从不同途径保证了通过间断（激波等）时的熵增原理，真正得到了合乎物理实际的解，在数值解过程中实现了解的唯一性，这许多方法的提出，有的正是著名的流体力学专家和工程技术专家。 许多其它学科的专家学者，还在不断通过他们的实践和研究，丰富和创新着偏微分数值解的方法、方案、理论。核武器的

9、研制只靠实验和理论不能完全解决问题,何况做一次实验要付出巨大的代价,必须采用计算的方法。计算工作者为我国成功地独立自主发展核武器做出了历史性的贡献.我国独立于西方创始了有限元方法。这一方法特别适用于大型工程计算,在水坝、桥梁、飞机、船舶的设计以及油田开发和核武器研制等方面得到了广泛的应用.在我国导弹与航天技术研究方面,也正是计算数学工作者针对飞行器头部气动力以及烧蚀、飞行控制和结构分析等问题发展了一系列有效算法,较好地解决了计算问题,从技术上满足了航天事业发展的需要.计算数学专业简介 1955年由于国民经济发展需要， 曾远荣（南京大学函数论教研室主任） 坚持要发展计算数学，并得到领导的支持。于

10、是他集中人才，收集资料，有计划有步骤地带领一批中青年开展学术讨论班，对分析中数值方法、微分方程数值解、线代数计算、函数逼近论及计算数学的理论与应用，大力开展学习研究。 南京大学作为一个基点，是国内最早开展计算数学研究的单位之一，由此逐步发展到开课、招生，于1958年正式建立计算数学专业，主要人员何旭初、徐家福、苏煜城等。 1980 年何旭初创办高校计算数学学报， 1992年英文版（苏煜城）。 高校计算数学会议。计算数学专业简介 主要研究方向 优化及其在管理科学中的应用 微分方程数值解法 计算流体力学 非线性方程数值解法 师资力量共24人，教授10人， 副教授9人，讲师5 人。 在研项目：国家自

11、然科学基金重点项目1项，面上项目5项，教育部新世纪人才基金1项，参与973项目1项。课程设置 本科：数值计算I、数值计算II、偏微分方程数值解法。 研究生：根据不同研究方向设置各种类型的课程。 数值计算I、II的主要内容： 函数插值、数值积分、数值微分、曲线拟合；线性方程组的数值解法、非线性方程及方程组的数值解法、特征值和特征向量的数值解法；常微分方程的数值解法。 偏微分方程数值解法：双曲、椭圆、抛物型方程的差分方法。 数值计算方法是一门专门研究如何从给定问题的已知数据得到所需计算结果的学科，它被广泛应用于各个自然科学领域，也被用于多个社会科学领域. 数值计算方法包括数值代数，数值逼近，微分方

12、程的数值解法，最优化，概率统计. 数值代数： 线性方程组的数值计算方法；数据拟合；矩阵特征值问题. 数值逼近：数值插值；数值积分；数值微分. 微分方程的数值解法：常微分方程的数值解法；偏微分方程的数值解法. 最优化：无约束最优化；约束最优化；各种规划问题. 概率统计先行课程先行课程 数学分析 ( Mathematical Analysis ) 线性代数 ( Linear Algebra ) 常微分方程 ( Original Differential Equation 简写为 ODE ) 计算机基础及计算机语言第一章第一章 算术运算中的误差分析初步算术运算中的误差分析初步 数值方法、算法 误差来

13、源 误差大小的衡量方法 舍入误差与有效数字 数据误差在算术运算中的传播 机器误差数值方法数值方法( (Numerical Method)Numerical Method)： 数值方法是对给定问题的输入数据和所需计算结果之间的关系的一种明确的描述。例： 用 Newton 法 ( 将在 Ch2 4 中讨论) 计算 3 。给定3的一个初始近似值 )0(,00 xx由迭代公式： ,2, 1,)3(2111nxxxnnn产生一个序列 ,10nxxx算法：算法：( (Algorithm)Algorithm) 它是算术和逻辑运算的完整描述，按一定顺序执行这些运算，经有限步把输入数据的每一个容许集转换成输出数

14、据。建立数值方法的基本原则：建立数值方法的基本原则： 便于在计算机上实现 计算工作量尽量小 存储量尽量小 问题的解与近似解的误差小误差的来源误差的来源( (Error Resource)Error Resource)：模型误差 ( Model Error )数据误差 ( Data Error )截断误差 (Truncation Error )离散误差 ( Discrete Error )数据计算过程中的误差误差大小的衡量：误差大小的衡量：绝对误差 （ absolute error ) 相对误差 （ relative error )误差界 （ bound of error ) 舍入误差与有效数字

15、舍入误差与有效数字 舍入误差 （rounding error )（四舍五入表示近似数产生的误差 ） 有效数字 第一位非零数字到最右边的数字为止的所有的数字被称为有效数字有效数字。数据误差在算术运算中的传播数据误差在算术运算中的传播 初始数据误差和计算结果中产生的误差之间的关系 要注意避免相减相消要注意避免相减相消。设yx,分别是初始数据yx,的近似值，即yxeyyexx,yxee ,分别是yx,的绝对误差。考察用yx,分别代替yx,计算函数值 ),(yxfz 产生的误差。即),(yxfz 的误差。 假设绝对误差yxee ,的绝对值都很小，且),(yxf可微，则z的误差 ),(),(yxfyxf

16、zzez可以近似地表示成 yxzeyxyfeyxxfe),)(),)( （5. 1）而且， yeyxyfzyxeyxxfzxzeryxzz),)(),)( yxryxyfzyryxxfzx),)(),)( (5. 2)进行算术运算时初始数据误差和计算结果中产生的误差之间有下列关系（1）:),(yxyxf绝对误差： yxyxeee；相对误差： yxyxryxyryxxr从上式可见，接近相等的同号数相减时，会使计算结果的误差变得很大。 故应避免相减相消故应避免相减相消。（2）:),(xyyxf 绝对误差： yxyxexeye； 相对误差： yxyxrrr （3）:/),(yxyxf 绝对误差： 2

17、/yexeyeyxyx； 从上式可见， 应避免绝对值很小的数作分母。 相对误差： yxyxrrr/例 1 求方程 0,02acbxax 的两个根分别为 aacbbx2421和 aacbbx2422若,0b且042 acb，则1x需改为 acbbcx4221例例 2 计算表达式 xcos1。 当 0 x时 为避免相减相消，应利用 恒等式 2sin2cos12xx 机器误差机器误差 计算机中数的表示 浮点运算和舍入误差设计算机中的数x为有限位小数，表示为 tkkkJdx11010 (6.1)其中UJL（L 和 U 是正整数或零）t 为计算机的字长字长，tidi, 1,都是9 , 2 , 1 , 0

18、中的一个数字若记 ttkkkdddda211. 010 (6.2)则 Jax10 (6.3) 令 xxxR 则对十进制系统有tRxx105),1 ( (6.11)对二进制系统有 t2 (6.16)若用只“舍”不“入”的断位法，则界为 t 110 或 t 12 例 3 在5, 3,10ULtp的断位机上 对数 0.0438 , 0.0693 , 13.2 进行加法运算那么 先加前两个数后再加第三个数为 0.13310 若先加后两个数再加第一个数为 0.13210 由此可见，对于浮点运算，通通常常的的运运算算规规律律 不不再再成成立立。 作乘法运算时，不必对阶。下下面面考考察察计计算算机机中中浮浮

19、点点数数的的算算术术运运算算的的舍舍入入误误差差： 设 Fyx,，均为规格化的浮点数。 用)/(),(),(yxflyxflyxfl分别表示得到准确的yxyxyx/,后按相关舍入规则进行舍入的结果，即 Ryxyxfl)()( RRyxyxflyxyxfl)/()/(,)()(就上述例 2， 3101255562. 0 yx因此31012556. 0)(,yxflFyx而据(6.11)和(6.16)式，立得下述定理：定理定理 1 )1)()(1yxyxfl (6.17) )1)()(2yxyxfl (6.18) )1)()(3yxyxfl (6.19) )1)(/()/(4yxyxfl (6.2

20、0)其中 , 4 , 3 , 2 , 1, iepsi （二进制系统）（十进制系统）tteps2105下下面面讨讨论论更更复复杂杂的的浮浮点点运运算算的的误误差差界界： 通过例子可见，在做做三三个个以以上上的的数数的的加加法法运运算算时时，需需要要考考虑虑相相加加的的两两个个同同号号数数的的阶阶数数应应尽尽量量接接近近。 定义 )()(zyxflflzyxfl据(6.17)式，)1 ()1)(1)()1)()1)()1)()(221211zyxzyxzyxflzyxfl (6.21)其中 . 2 , 1, iepsi为估计)1 (i，先证明下面的引理引引理理（Lemma） 若), 2 , 1(niepsi， 且01. 0epsn，则 niiepsnepsn101. 11)1 (1， (6.23)其中 二进制系统）十进制系统）；(2(105tteps(6.23)式还可改写成 1,01. 11)1 (1niiepsn (6.24)证证明明 ( Proof ) 由假设epsi，有 nininepseps