计算方法1_绪论与误差等

1、Numerical Analysis能源与动力工程学院能源与动力工程学院 刘火星刘火星 82316418课程介绍课程介绍l 绪论绪论l 误差分析误差分析(2)(2)l 线性方程组的解法线性方程组的解法(6)(6)l 常微分方程的初值问题常微分方程的初值问题(6)(6)l 矩阵的特征值和特征向量矩阵的特征值和特征向量(2)(2)l 插值和拟合插值和拟合l 数值微分和数值积分数值微分和数值积分l 非线性方程解法非线性方程解法Course Outlinel数值分析，颜庆津，北京航空航天大学出版社，数值分析，颜庆津，北京航空航天大学出版社，2002006 6l徐翠薇、孙绳武，计算方法引论（第二版），徐

2、翠薇、孙绳武，计算方法引论（第二版），高等教育出版社，高等教育出版社，20022002lRichard L. Burden & J. Douglas Faires, Richard L. Burden & J. Douglas Faires, Numerical Analysis (Seventh Edition), Numerical Analysis (Seventh Edition), 高高等教育出版社，等教育出版社，20012001主要参考书主要参考书成绩评定方法成绩评定方法l平时成绩：平时成绩：20%l期末考试期末考试: : 80%先修课程先修课程l高等数学高等数学l

3、线性代数线性代数l程序设计语言程序设计语言C,C+,Fortran,Matlab,Mathematica1 1 绪论绪论Introduction1.1 1.1 关于计算方法关于计算方法1.2 1.2 计算方法的过去和未来计算方法的过去和未来1.3 1.3 误差分析误差分析1.1.4 4 在近似计算中需要注意的问题在近似计算中需要注意的问题目次目次现实中，具体的科学、工程问题的解决：现实中，具体的科学、工程问题的解决：实际问题实际问题物理模型物理模型数学模型数学模型数值方法数值方法计算机求解计算机求解计算方法是一种研究并解决计算方法是一种研究并解决数学问题的数值数学问题的数值近似解近似解方法方法

4、 随着计算机的飞速发展，数值分析方随着计算机的飞速发展，数值分析方法已深入到计算物理、计算力学、计算化法已深入到计算物理、计算力学、计算化学、计算生物学、计算经济学等各个领域。学、计算生物学、计算经济学等各个领域。本课仅限介绍最常用的数学模型的最基本本课仅限介绍最常用的数学模型的最基本的数值分析方法。的数值分析方法。1.1 1.1 关于计算方法关于计算方法 在计算机上是否根据数学公式编程在计算机上是否根据数学公式编程就能得到正确结果就能得到正确结果? ?研究例子:求解线性方程组123123123111123611113234121114734560 xxxxxxxxx1231231230 50

5、0 331 80 500 330 251 10 330 250 200 78.xxxxxxxxx如把方程组的系数舍入成两位有效数字它的解为 x1 =-6.222 x2 =38.25 x3 =-33.65.准确解为x1=x2=x3=1lNumerical analysis is the study of algorithms for the problems of continuous mathematics -Lloyd N. Trefethenl“计算方法计算方法”就是研究在计算机上解决数学问就是研究在计算机上解决数学问题的理论和数值方法题的理论和数值方法计算方法研究的对象计算方法研究的对象

6、: 研究数值方法的研究数值方法的设计设计、分析分析和和有关理论有关理论基础与基础与软件实现。软件实现。F计算方法又称：计算数学、数值方法、数值分析等计算方法又称：计算数学、数值方法、数值分析等F计算方法的分枝有最优化方法、计算几何、计算概率统计算方法的分枝有最优化方法、计算几何、计算概率统计等计等计算方法的内容计算方法的内容l 连续系统的离散化连续系统的离散化l 离散性方程的数值求解离散性方程的数值求解 n计算数学的发展与科学工程计算是紧密相计算数学的发展与科学工程计算是紧密相联的，计算数学的发展历史也就是与其他联的，计算数学的发展历史也就是与其他学科结合，利用计算机不断形成新的理论学科结合，

7、利用计算机不断形成新的理论及数值方法并不断形成新的学科的历史，及数值方法并不断形成新的学科的历史，例如：例如：“计算物理计算物理” “计算流体力学计算流体力学”1.2 1.2 计算方法的过去和未来计算方法的过去和未来nH. Aiken (1900-1973)n哈佛大学博士，因做博士论文涉及到空间哈佛大学博士，因做博士论文涉及到空间电荷传导问题的计算，电荷传导问题的计算，1937年提出方案，年提出方案，1939年得到年得到IBM资助，资助，1944年建成投入使年建成投入使用。这是继电式计算机用。这是继电式计算机Mark I三位计算机设计大师的贡献三位计算机设计大师的贡献nJ. W. Mauchl

8、y (1907-1980)n宾夕法尼亚物理博士，因从事天气预报需宾夕法尼亚物理博士，因从事天气预报需要想设计计算机，要想设计计算机，1942年提出计算机方案，年提出计算机方案，1945年底竣工，这就是世界上第一台电子年底竣工，这就是世界上第一台电子计算机计算机ENIAC机机三位计算机设计大师的贡献三位计算机设计大师的贡献nJ. Von Neumann (1903-1957)n普林斯顿高级研究所，普林斯顿高级研究所，1945年在普林斯顿年在普林斯顿研制成研制成MANIAC机，有力地支持美国氢机，有力地支持美国氢弹研制，称为计算机之父弹研制，称为计算机之父三位计算机设计大师的贡献三位计算机设计大师

9、的贡献n在研制原子弹和氢弹过程中，许多物在研制原子弹和氢弹过程中，许多物理规律必须通过计算机上的计算摸清理规律必须通过计算机上的计算摸清楚。计算物理、理论物理与实验物理楚。计算物理、理论物理与实验物理相辅相成相互促进共同发展，形成现相辅相成相互促进共同发展，形成现代物理学的三大分支代物理学的三大分支n由于核武器研制需要，由于核武器研制需要，1950年全球只有年全球只有15台，到了台，到了1962年年9月仅美国就有月仅美国就有16187台计台计算机算机计算数学发展的历史回顾计算数学发展的历史回顾l1983年一个由美国著名数学家拉克斯年一个由美国著名数学家拉克斯(P. Lax)为为首的不同学科的专

10、家委员会向美国政府提出的首的不同学科的专家委员会向美国政府提出的报告之中，强调报告之中，强调“科学计算是关系到国家安全、科学计算是关系到国家安全、经济发展和科技进步的关键性环节，是事关国经济发展和科技进步的关键性环节，是事关国家命脉的大事。家命脉的大事。” l1984年美国政府大幅度地增加对科学计算经费年美国政府大幅度地增加对科学计算经费的支持的支持, 新建成五个国家级超级计算中心（分别新建成五个国家级超级计算中心（分别在普林斯顿大学、圣地亚哥、伊里诺大学、康在普林斯顿大学、圣地亚哥、伊里诺大学、康奈尔大学、匹兹堡），配备当时最高性能的计奈尔大学、匹兹堡），配备当时最高性能的计算机，建立算机，

11、建立NSF-net新网络新网络l 80年代中期我国将年代中期我国将“大规模科学与工程计算大规模科学与工程计算”列入国家资助重大项目列入国家资助重大项目l1987年起美国年起美国NSF把把“科学与工程计算科学与工程计算”、“生物工程生物工程”“”“全局性科学全局性科学”作为三大优先资作为三大优先资助的领域助的领域l由于大存储的高速计算机的使用已导致了科学由于大存储的高速计算机的使用已导致了科学和技术方面的两大突出进展：和技术方面的两大突出进展：大量用于设计工作的实验被数学模型的研大量用于设计工作的实验被数学模型的研究逐步取代，如航天飞机设计、反应堆设究逐步取代，如航天飞机设计、反应堆设计、人工心

12、瓣膜设计等计、人工心瓣膜设计等能获取和存储大量的数据，并能提取隐秘能获取和存储大量的数据，并能提取隐秘的信息，如计算机层析的信息，如计算机层析X射线摄影，核磁射线摄影，核磁共振等共振等l1991年以美国总统倡议的形式提出了年以美国总统倡议的形式提出了“高性能高性能计算与计算与通信计划通信计划”。这是为了保持和提高美国。这是为了保持和提高美国在计算和网络的所有先进领域中的领导地位而在计算和网络的所有先进领域中的领导地位而制定的。计划为期五年（制定的。计划为期五年（19921996），投资），投资的重点是发展先进的软件技术与并行算法，关的重点是发展先进的软件技术与并行算法，关键技术是可扩展的大规模

13、并行计算键技术是可扩展的大规模并行计算l要求到要求到1996年高性能计算能力提高年高性能计算能力提高14倍，达倍，达到每秒万亿次浮点运算速度（到每秒万亿次浮点运算速度（1012 Teraops/S）。计算机网络通迅能力提高）。计算机网络通迅能力提高1百倍，达到每百倍，达到每秒秒109位（位（Gigabits/S）l该计划中列举的该计划中列举的“挑战挑战”项目有：磁记录技术项目有：磁记录技术、药物设计、催化、燃烧、海洋模拟、臭氧洞、药物设计、催化、燃烧、海洋模拟、臭氧洞、空气污染、高速民用运输机、数字解剖、蛋、空气污染、高速民用运输机、数字解剖、蛋白质结构设计、金星成像等白质结构设计、金星成像等

14、l1993年初美国总统发布年初美国总统发布“发展信息高速公路发展信息高速公路”（NII）的总统令）的总统令l1994年年4月美国总统发布月美国总统发布“建立国家（地球）建立国家（地球）空间数据基础实施空间数据基础实施”（NSDI）的总统令）的总统令数值方法和数值软件过去数值方法和数值软件过去50年的主要进展年的主要进展Before 1940Newtons method; Gaussian elimination; Gauss quadrature; least squares fitting; Adams and Runge-Kutta formulas;Richardson extrapol

15、ation1940-1970floating point arithmetic; Fortran ; finite differences; finite elements; FFT; simplex algorithm; Monte Carlo; orthogonal linear algebra; spline function1970-2000quasi-Newton iterations; adaptivity; stiff ODE solvers; software libraries; Matlab; multigrid; sparse and iterative linear a

16、lgebra; spectral methods; interior point methods计算数学未来计算数学未来50年的展望年的展望l将更多的通过声音，而不是键盘向计算机传递信将更多的通过声音，而不是键盘向计算机传递信息，而计算机将更多地以图象而不是数字反映结息，而计算机将更多地以图象而不是数字反映结果果l数值计算将更具有适应性、迭代性、灵活性。计数值计算将更具有适应性、迭代性、灵活性。计算能力大得惊人算能力大得惊人l数值计算中更具智能性数值计算中更具智能性数学软件数学软件lMATLABMATLABnMATLABMATLAB是建立在向量、数组和矩阵基础上是建立在向量、数组和矩阵基础上的

17、一种分析和仿真工具软件包，包含各种的一种分析和仿真工具软件包，包含各种能够进行常规运算的能够进行常规运算的“工具箱工具箱”，如常用，如常用的矩阵代数运算、数组运算、方程求根、的矩阵代数运算、数组运算、方程求根、优化计算及函数求导积分符号运算等；同优化计算及函数求导积分符号运算等；同时还提供了编程计算的编程特性，通过编时还提供了编程计算的编程特性，通过编程可以解决一些复杂的工程问题；也可绘程可以解决一些复杂的工程问题；也可绘制二维、三维图形，输出结果可视化。目制二维、三维图形，输出结果可视化。目前，已成为工程领域中较常用的软件工具前，已成为工程领域中较常用的软件工具包之一。包之一。 lMATLA

18、BMATLABlMAPLEMAPLElMATLABMATLABlMAPLEMAPLElMATHEMATICMATHEMATICMapleMaple是加拿大滑铁卢大学是加拿大滑铁卢大学(University of (University of Waterloo)Waterloo)和和Waterloo Maple SoftwareWaterloo Maple Software公司注册公司注册的一套为微积分、线性代数和微分方程等高等数的一套为微积分、线性代数和微分方程等高等数学使用的软件包。它是当今世界上最优秀的几个学使用的软件包。它是当今世界上最优秀的几个数学软件之一，它以良好的使用环境、强有力的

19、数学软件之一，它以良好的使用环境、强有力的符号计算、高精度的数值计算、灵活的图形显示符号计算、高精度的数值计算、灵活的图形显示和高效的编程功能，为越来越多的教师、学生和和高效的编程功能，为越来越多的教师、学生和科研人员所喜爱，并成为他们进行数学处理的工科研人员所喜爱，并成为他们进行数学处理的工具。具。MapleMaple软件适用于解决微积分、解析几何、线软件适用于解决微积分、解析几何、线性代数、微分方程、计算方法、概率统计等数学性代数、微分方程、计算方法、概率统计等数学分支中的常见计算问题。分支中的常见计算问题。 MathematicaMathematica是目前比较流行的符号运算是目前比较流

20、行的符号运算软件之一，它不仅可以完成微积分、线性软件之一，它不仅可以完成微积分、线性代数及数学各个分支公式推演中的符号演代数及数学各个分支公式推演中的符号演算，而且可以数值求解非线性方程、优化算，而且可以数值求解非线性方程、优化等问题。它不仅是数学建模的得力助手，等问题。它不仅是数学建模的得力助手，也是大学数学教育和科学研究不可或缺的也是大学数学教育和科学研究不可或缺的工具。工具。n原始误差原始误差模型误差模型误差（忽略（忽略次要因素次要因素，物理模型，物理模型，数学模型）数学模型）n计算误差计算误差舍入误差舍入误差（计算机数据表示方法（计算机数据表示方法造成）造成）n方法误差方法误差截断误差

21、截断误差（算法（算法本身造成）本身造成）1.3 1.3 误差分析误差分析 计算机字长有限导致实数不能精确存储，于是产生计算机字长有限导致实数不能精确存储，于是产生舍入误差舍入误差。例如：在例如：在10位十进制数限制下：位十进制数限制下： 130.3333333333 本应本应130.3333333333 1.0000022-1.000004=0 本应本应1.0000022-1.000004 =1.0000040000 04-1.000004 =0.0000000000 04 舍入误差舍入误差(Round-off Errors)0000333.0313333.000001356.024142.1

22、0000074.01416.34,33333.031,41421356.12,1415926.31.1121 位小数，则位小数，则若在计算机上只能取若在计算机上只能取例例舍入误差很小，本课程将研究它在运算过程中是否舍入误差很小，本课程将研究它在运算过程中是否能有效控制。能有效控制。用近似的值去代替数学上的准确值带来的误差。用近似的值去代替数学上的准确值带来的误差。例如：例如： 泰勒级数泰勒级数 零阶近似零阶近似 : : 一阶近似一阶近似 : : 二阶近似二阶近似 : : 截断误差截断误差(Truncation Error )完全的泰勒级数完全的泰勒级数: : 余项余项 (n(n阶近似阶近似)

23、:) : : 介于介于 xi and xi+1 x = xi+1- xi余项：余项：Taylor Taylor 级数表示为级数表示为: : 截去的部分截去的部分 零阶近似零阶近似 : : 截断误差截断误差 : : 一阶近似一阶近似 Rn :零阶近似零阶近似 R Rn n : :斜率斜率 : :误差误差 误差限误差限 有效数字有效数字Def若用若用x*表示表示x准确值的一个近似值。则此近准确值的一个近似值。则此近似值似值x*和准确值和准确值x的差称为误差，用的差称为误差，用e*来表示来表示e*x*xDef若若|e*|x*x|*称为近似值称为近似值x*的误差限。的误差限。例例1.2已知已知x*=3

24、.14159，求近似值，求近似值x1=3.14，x2=3.142，x3=3.1416的误差限。的误差限。解解 000008.0000007.01416.3x0005.000041.0142.3x002.000159.014.3x321 所以误差限所以误差限1=0.002，2=0.0005，3=0.000008 有效数字有效数字Def若若x的近似值的近似值x*的误差限是某一位上的半个单的误差限是某一位上的半个单位，该位到位，该位到x*的第一位非零数字共有的第一位非零数字共有n位，则称位，则称x*有有n位有效数字位有效数字若用若用x*表示表示x的近似值，并将的近似值，并将x*表示成表示成x*0.a

25、1a2an10m若若|x*x|0.510mn则近似值则近似值x*有有n位有效数字位有效数字(1.1) 例例1.3 设设x*=0.0270是某数是某数x经经“四舍五入四舍五入”所得所得，则误差，则误差|e(x*)|不超过不超过x*末位的半个单位，即：末位的半个单位，即：|x*x|0.510 -4 又又 x*= =0.2710-1 , ,故该不等式又可写为故该不等式又可写为|x*x|0.510 -1-3由有效数字定义可知由有效数字定义可知, , x*有有3 3位有效数字位有效数字, ,分别是分别是2,72,7，0 0。 例例1.4 设设x32.93,x*32.89, ,则则|x*x|0.040.0

26、50.510-1即即|x*x|0.5102-3由有效数字定义可知由有效数字定义可知, , x*有有3 3位有效数字位有效数字, ,分别是分别是3,2,83,2,8。由于由于x*中的数字中的数字9 9不是有效数字，故不是有效数字，故x*不是有效数。不是有效数。1.3 相对误差和绝对误差相对误差和绝对误差xx*xx*e*er 设设 x准确值准确值 x* 近似值近似值称称为近似值为近似值x* 的相对误差的相对误差实用中，常用实用中，常用*xx*x*x*e*er 表示近似值表示近似值x* 的相对误差，称的相对误差，称*x*r 为相对误差限为相对误差限相应的，相应的，e*称称为绝对误差，为绝对误差，称为

27、绝对误差称为绝对误差限限有效数位与误差的关系有效数位与误差的关系位位有有效效数数字字至至少少具具有有则则反反之之，若若n*x10)1a(21*en11r n11r10a21*e 有效数位有效数位n n越多，则绝对误差越多，则绝对误差| |e*| |越小越小形如形如(1.1)式的式的近似数近似数x*具有具有n位有效数字，则位有效数字，则其相对误差限可取为其相对误差限可取为基本算术运算基本算术运算设设x*和和y*分别是分别是x和和y的近似值，把它们的误差近似地的近似值，把它们的误差近似地看做是相应地微分，即看做是相应地微分，即dx x*x， dy y*y则则d（xy）dx dyd（xy）xdy y

28、dxd（x/y）（xdyydx ）/y2 误差传播误差传播(1.3)和和(1.4)给出了由自变量的误差引起的函数值给出了由自变量的误差引起的函数值的误差的近似式（误差传播）。的误差的近似式（误差传播）。*)x(e*)x(f)x*x)(! 2/)(f ()x*x*)(x(f)x( f*)x( fy*y*)y(e2 一元函数一元函数设设yf(x)，若若x的近似值是的近似值是x*，用用f(x*) 去近似去近似f(x)的误的误差可用差可用Taylor公式估计公式估计*)x(e*x*)x( f*)x(f*)e(x*)x( f*)x(f*y*)y(e*)y(e*)x( f*yrr 得得两两边边除除以以(1

29、.3)(1.4)多元函数情形多元函数情形*)x,*,x*,x( f*y)x,x,x( fyn21n21 则则*)x(e*)x,*,x*,x(f*)y(ein21n1ii *)x(e*x*)x,*,x*,x( f*)x,*,x*,x(f*)y(eirin21n21in1ir 可可得得中中，分分别别取取在在式式2/1,21,2121xxxxxx)x,x( f)6 . 1 ( )7.1()x,x(xemaxxxe21)i(r2i1)21(r*同同号号 )2(r)1(r)21(r*xexexxe )x(exexexexxe*2r)1(r)2(r)1(r)*2*1(r* 由多元函数的由多元函数的Tayl

30、orTaylor展开公式类似可得展开公式类似可得 (1.5) (1.6) (1.8) (1.9) 例例1.5 测得某桌面的长测得某桌面的长a的近似值的近似值a*=120cm, ,宽宽b的近的近似值似值b*=60cm。若已知。若已知|e(a*)|0.2cm, , |e(b*)|0.1cm。 试求近似面积试求近似面积s*=a*b* 的绝对误差限与相对误差限的绝对误差限与相对误差限。2cm241.01202.060|*)b(e|*a|*)a(e|*b|*)s(e|*)b(e*a*)a(e*b*)b(eb*)b*,a(s*)a(ea*)b*,a(s*)s(e 解解: 面积面积s=ab,在公式在公式（1.5）中中,将将y=f(x1,x2) 换为换为 s=ab, 则则相对误差限为相对误差限为%33.06012024*s*)s(e|*)s(e|r 1.4 在近似计算中需要注意的问题在近似计算中需要注意的问题（1 1）尽量简化计算步骤，减少乘除运算的次数尽量简化计算步骤，减少乘除运算的次数 例