数值分析第一章绪论.ppt

数值分析,数值分析 能够做什么？,1 Introduction,研究使用计算机求解各种科学与工程计算问题的数值方法（近似方法），对求得的解的精度进行评估，以及如何在计算机上实现求解等。 数值分析课程中所讲述的各种数值方法在科学与工程计算、信息科学、管理科学、生命科学等交叉学科中有着广泛的应用,应用问题举例,今有上禾三秉，中禾二秉，下禾一秉，实三十九斗； 上禾二秉，中禾三秉，下禾一秉，实三十四斗； 上禾一秉，中禾二秉，下禾三秉，实二十六斗。 问上、中、下禾实一秉各几何？ 答曰：上禾一秉九斗四分斗之一。中禾一秉四斗四分斗之一。下禾一秉二斗四分斗之三。-九章算术,1、一个两千年前的例子,2、天体力学中的Kepler方程,x是行星运动的轨道，它是时间t 的 函数.,全球定位系统：在地球的任何一个位置，至少可以同时收到4颗以上卫星发射的信号,3、全球定位系统（Global Positioning System,GPS),表示地球上一个接收点R的当前位置，卫星Si的位置为 ，则得到下列非线性方程组,记为,其中，,4、已经测得在某处海洋不同深度处的水温如下： 深度（M） 466 741 950 1422 1634 水温（oC）7.04 4.28 3.40 2.54 2.13 根据这些数据，希望合理地估计出其它深度（如500米，600米，1000米）处的水温,5、用比较简单的函数代替复杂的函数,误差为最小，即距离为最小 （在不同的度量意义下）,6、人口预测,下面给出的是中国1900 年到2000年的人口数， 我们的目标是预测未来 的人口数（数据量较大时）,7、铝制波纹瓦的长度问题,建筑上用的一种铝制波纹瓦是用一种机器将一块平整的铝板压制而成的.,假若要求波纹瓦长4英尺,每个波纹的高度(从中心线)为1英寸,且每个波纹以近似2英寸为一个周期. 求制做一块波纹瓦所需铝板的长度L.,这个问题就是要求由函数f(x)=sin x 给定的曲线从x=0到x=48英寸间的弧长L. 由微积分学我们知道,所求的弧长可表示为:,上述积分称为第二类椭圆积分,它不能用普通方法来计算.,数值计算方法的意义、内容与方法,软件的核心就是算法。,20 世纪最伟大的科学技术发明-计算机,计算机是对人脑的模拟，它强化了人的思维智能；,计算机的发展和应用，已不仅仅是一种科学技术 现象，而且成了一种政治、军事、经济和社会现象；,没有软件的支持，超级计算机只是一堆废铁而已；,算法犹如乐谱， 软件犹如CD盘片， 而硬件如同CD唱机。,计算数学,现代科学研究的三大支柱,21世纪信息社会的两个主要特征： “计算机无处不在” “数学无处不在”,21世纪信息社会对科技人才的要求： -会用数学解决实际问题 -会用计算机进行科学计算,建立数学模型,选取计算方法,编写上机程序,计算得出结果,科学计算解题过程,一、计算数学的产生和早期发展,计算数学是数学的一个古老的分支，虽然数学不仅仅 是计算，但推动数学产生和发展的最直接原因还是 计算问题。,二、二十世纪计算数学的发展,数值代数,最优化计算,数值逼近,计算几何,概率统计计算,蒙特卡罗方法,微分方程的数值解法,微分方程的反演问题,数值代数：方程求根、线性方程组求解、 特征值和特征向量的计算、 非线性方程组的求解；,数值逼近：插值与函数逼近、数值微分 和积分、 最小二乘法；,微分方程数值解：常微分方程数值解； 偏微分方程数值解： 差分法 有限元法 有限体积法,三、数值计算的主要内容,教材 数值分析(21世纪数学系列教材) 李庆扬等（华中科技大学出版社）,参考书目 数值计算方法 徐涛 编著 （吉林科学技术出版社） 应用数值方法 使用MATLAB和C语言 Robert J.Schilling & Sandra L.Harris （机械工业出版社） 数值分析基础教程 李庆扬 编 （高等教育出版社） 现代数值分析 李庆扬、易大义、王能超 编著 （高等教育出版社） 数值分析与科学计算 Jeffery J.Leader 著，张威，刘志军，李艳红等译，（清华大学出版社),2 算 法,一、算法的概念,描述算法可以有不同的方式。例如，可以用日常语言 和数学语言加以叙述，也可以借助形式语言（算法语言） 给出精确的说明，也可以用框图直观地显示算法的全貌。,定义：由基本运算及运算顺序的规定所构成的完整的 解题步骤，称为算法。,例：求解二元一次联立方程组,用行列式解法：首先判别,（1）如果 ，则令计算机计算,输出计算的结果x1，x2。,（2）如果D= 0，则或是无解，或有无穷多组解。,是否为零，存在两种可能：,令,通过求解过程，可以总结出算法步骤如下：,S2 计算,S3 如果,则输出原方程无解或有无穷多组解的信息;,否则,S1 输入,S4 输出计算的结果,二、算法优劣的判别, 计算量的大小, 存贮量, 逻辑结构,例：用行列式解法求解线性方程组: n阶方程组，要计算n + 1个n阶行列式的值， 总共需要做n! (n - 1) (n + 1) 次乘法运算。,n=20 需要运算多少次？,n=100?,一、误差的来源与分类,从实际问题中抽象出数学模型 模型误差,例:质量为m的物体，在重力作用下,自由下落， 其下落距离s 与时间t 的关系是：,其中 g 为重力加速度。,3 误 差,通过测量得到模型中参数的值 观测误差,求近似解 方法误差 (截断误差）,例如，当函数,用Taylor多项式,近似代替时，数值方法的截断误差是,机器字长有限 舍入误差,用计算机、计算器和笔算，都只能用有限位, = 3.1415926,小数来代替无穷小数或用位数较少的小数来,代替位数较多的有限小数，如：,四舍五入后,在数值计算方法中，主要研究截断误差和舍入误差 （包括初始数据的误差）对计算结果的影响！,二、 误差的概念,1、绝对误差与绝对误差限,例 :若用以厘米为最小刻度的尺去量桌子的长，大约为1.45米，求1.45米的绝对误差。,1.45米的 绝对误差=？,不知道！,是近似值 的绝对误差,简称为误差。,定义：设 是准确值，为 的一个近似值，称,但实际问题往往可以估计出 不超过某个正数 ，,即 则称 为绝对误差限，有了绝对误差限,就可以知道 的范围为,即 落在 内。,在应用上，常常采用下列写法来刻划 的精度。,2、相对误差与相对误差限,定义：设 是准确值， 是近似值，是近似值的误差，,通常取,为近似值 的相对误差，记作 ，,称,一般情况下是不知道 的，怎么办？,事实上，当 较小时,是 的二次方项级,故可忽略不计.,相应地，若正数,满足,则称 为 的相对误差限。,3 、有效数字,定义：如果,则说 近似表示 准确到小数后第 位，并从这,由上述定义,第 位起直到最左边的非零数字之间的一切数字都,称为有效数字，并把有效数字的位数称为有效位数。,定义 :,也即，若,其中， 是1到9中的一个数字； 是 0到9中一个数字； 为整数，且,就说 有 位有效数字。,取 作 的近似值， 就有三位有效数字；,取 作 的近似值， 就有五位有效数字。,例如：,注： 若一近似数是由原真值经四舍五入得到， 则必为有效数.,4 、误差限与有效数字的关系,则 至少具有 位有效数字。,Th1.1：,对于用 式表示的近似数 ，若 具有 位有效,数字，则其相对误差限为,反之，若 的相对误差限为,Th1.2：,设,反之,若 的相对误差的绝对值大于 ，,其中 为整数, 为正整数, 。,若 至多有 位有效数字,即 是有效数字,而 不是有效数字,则 的相对误差的绝对值必大于 ;,证明：,不是有效数字,反之,若,则,4 数值运算的误差估计,一、四则运算,两个近似数 与 ,其误差限分别为 及 ,它们进行加减乘除运算得到的误差限分别为,二、函数误差估计,当自变量有误差时，计算函数值也会产生误差，其误差限可利用函数的Taylor展开式进行估计。,设 是一元函数， 的近似值为 ,以 近似 ，其误差限记作 ，可用Taylor展开,假定 与 的比值不太大,可忽略 的高阶项,于是可得计算函数的误差限为,当 为多元函数时计算 ,如果,的近似值为 ,则 的近似为,于是函数值 的误差 由Taylor展开,得：,于是误差限为,而 的相对误差限为,(1.3.1),(1.3.2),例:已测得某场地长 的值为 ,宽 的值为 ,已知 , .试求 面积 的绝对误差限与相对误差限.,解: 因,其中,由式(1.3.1)得,而,于是绝对误差限为,相对误差限为,5 数值计算中应该注意的一些原则,1.要使用数值稳定的算法,例：求,的值.,解：由于,初值,递推公式,按公式就可以逐步算出,注意此公式精确成立,What happened?!,不稳定的算法 ！,这就是误差传播所引起的危害 !,由题设中的递推公式可看出， 的误差扩大了,5倍后传给 ，因而初值 的误差对以后各步,这就造成 的计算结果严重失真。,计算结果的影响，随着 的增大愈来愈严重。,要怎么做才能解决这个问题呢?,可求得I9 0.017，按改写后的公式可逐次求得,不妨设I9 I10，于是由,I8 0.019 I7 0.021 I6 0.024 I8 0.028 I4 0.034 I3 0.043 I2 0.058 I1 0.088 I0 0.182,稳定的算法 ！,在我们今后的讨论中，误差将不可回避， 算法的稳定性会是一个非常重要的话题。,2.要避免两个相近的数相减,在数值计算中，两个相近的数作减法时 有效数字会损失。,例: 求,的值。当x = 1000，y 的准确值为0.01580,(1)、直接相减,类似地,(2) 将原式改写为,则 y = 0.01581,3.尽量避免绝对值太小的数作分母,例：,如分母变为0.0011，也即分母只有0.0001的变化时,结果相差这么大!,4. 避免大数吃小数,精确解为, 算法1：利用求根公式,例：用单精度计算 的根。,在计算机内，109存为0.11010，1存为0.1101。做加法时，两加数的指数先向大指数对齐，再将浮点部分相加。即1 的指数部分须变为1010，则：1 = 0.0000000001 1010，取单精度时就成为： 109+1=0.100000001010+0.00000000 1010=0.10000000 1010,算法2：先解出,再利用,注：求和时从小到大相加，可使和的误差减小。,例：按从小到大、以及从大到小的顺序分别计算,1 + 2 + 3