数值分析第1章绪论.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唱机。,计算数学,诺贝尔奖得主,计算物理学家 Wilson提出 现代科学研究的三大支柱,21世纪信息社会的两个主要特征： “计算机无处不在” “数学无处不在”,21世纪信息社会对科技人才的要求： -会用数学解决实际问题 -会用计算机进行科学计算,科学方法论的巨大变革： 如果说伽利略和牛顿在科学发展史上奠定了实验和理论这两大科学方法的支柱，那么由冯.诺依曼研制的现代电子计算机把计算推上了人类科学活动的前沿，使计算成为第三种方法。,建立数学模型,选取计算方法,编写上机程序,计算得出结果,科学计算解题过程,数值计算方法是计算数学的一个主要组成部分，,“什么是数值计算方法？”,它主要研究使用计算机求解各种科学与工程计算问题的数值方法（近似方法）;对求得的解的精度进行评估以及在计算机上实现求解等。,数值计算方法已经成为计算机处理实际问题的一个重要手段，从宏观天体运动学到微观分子细胞学，从工程系统到社会经济系统，无一能离开数值计算方法。因此，数值计算与计算机模拟被称为“第三种研究科学方法”。,科学计算可视化是目前研究的热门问题，下面的艺术图形是基于科学计算的数据表示的例子,分形图,混沌图,一、计算数学的产生和早期发展,计算数学是数学的一个古老的分支，虽然数学不仅仅 是计算，但推动数学产生和发展的最直接原因还是 计算问题。,二、二十世纪计算数学的发展,数值代数,最优化计算,数值逼近,计算几何,概率统计计算,蒙特卡罗方法,微分方程的数值解法,微分方程的反演问题,传统的数值计算的主要研究内容： 1、数值逼近 插值与拟合、FFT、数值积分与微分 2、数值代数 代数基础、线性代数方程组的解法、非线性代数方程（组）的解法、特征值与特征向量 3、微分方程数值解 ODE、PDE和有限元法 4、最优化方法 无约束优化与有约束优化方法,现代计算方法：融进了机器学习计算、仿生计算、网络计算、以数据为核心的计算和各种普适计算、非线性科学计算等内容。,数值计算方法的主要特点,借助计算机提供切实可行的数学算法.,通过数值实验证明算法行之有效.,采用“近似替代”方法逼近 采用“构造性”方法 采用“离散化”方法 把求连续变量的问题转化为求离散变量的问题 采用“递推化”方法 复杂的计算归结为简单过程的多次重复，易于用循环结构来实现（迭代法）。 采用各种搜索方法,构造数值算法主要手段,如何学好数值计算方法？,希 望： 求近似解，但方法简单可行，行之有效 （计算量小，误差小,需存储单元少等）, 以计算机为工具，易在计算机上实现。 计算机运算: 只能进行加，减，乘，除等算术运算和一 些逻辑运算。 数值计算方法： 把求解数学问题转化为按一定次序只进行 加，减，乘，除等基本运算.,设计数值算法的出发点？,威尔金森（James Hardy .Wilkinson，1919-1986） Wilkinson是数值分析和数值计算的开拓者和奠基人。1940 年，开始研究弹道的数学模型与数值计算。 1946 年成为Turing 的助手，协助设计 Pilot ACE 计算机。1969年他当选为英国皇家学会院士；1970年工业和应用数学会(s1am)授予他冯诺伊曼奖；1987年他获得美国数学会的chauvenet奖。著名的美国阿尔贡国家实验室曾聘威尔金森为荣誉高级研究员并两次向他授奖。,Wilkinson在数值分析研究领域作出了杰出贡献，是数值计算的早期开拓者，其工作加速了数字计算机 ( 在科学计算中 ) 的使用。他研究的主要问题是线性代数方程组和矩阵特征值问题的数值解法，特别是他的向后误差分析法 (backward error analysis)的创造性工作奠定了数值分析和数值计算早期的理论基础。 1975 年 J. H. Wilkinson成为第五位图灵奖获得者。,教材 现代科学与工程计算 孟大志 刘伟（高等教育出版社）,参考书目 数值分析 孙志忠 袁慰平等（东南大学出版社,第二版） 应用数值方法 使用MATLAB和C语言 Robert J.Schilling & Sandra L.Harris （机械工业出版社） 数值分析基础教程 李庆扬 编 （高等教育出版社） 现代数值分析 李庆扬、易大义、王能超 编著 （高等教育出版社） 数值分析与科学计算 Jeffery J.Leader 著，张威，刘志军，李艳红等译，（清华大学出版社),2 算 法,一、算法的概念,描述算法可以有不同的方式。例如，可以用日常语言 和数学语言加以叙述，也可以借助形式语言（算法语言） 给出精确的说明，也可以用框图直观地显示算法的全貌。,定义：由基本运算及运算顺序的规定所构成的完整的 解题步骤，称为算法。,例：求解二元一次联立方程组,用行列式解法：首先判别,输出计算的结果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多项式,近似代替时，数值方法的截断误差是,与0之间。,在,机器字长有限 舍入误差,用计算机、计算器和笔算，都只能用有限位, = 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 算法的数值稳定性,数值计算在设计算法时首先关心的是由它产生的计算结果的稳定性，而算法的稳定性与舍入误差是否增长密切相关。一个算法如果输入数据有微小扰动（即误差），而在计算过程中舍入误差不增长，则称此算法是数值稳定的，否则称其为数值不稳定。,例：求定积分,的值.,解：直接积分可产生递推公式,若取初值,可得递推公式,按公式就可以逐步算出,注意此公式精确成立，且,What happened?!,不稳定的算法 ！,这就是误差传播所引起的危害 !,蝴蝶效应 纽约的一只蝴蝶翅膀一拍，风和日丽的北京就刮起台风来了？！,这是一个病态问题,由题设中的递推公式（1）可看出， 的误差扩大了,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,稳定的算法 ！,在我们今后的讨论中，误差将不可回避， 算法的稳定性会是一个非常重要的话题。,注：递推公式(1)的舍入误差以5的幂次增长进行传播，因此是数值不稳定的，而递推公式(2)的舍入误差在一定范围内以0.2的幂次进行传播，随着n的增大，误差逐步减少，因此该算法是数值稳定的。,因此，可以看出数值不稳定的算法是不能使用的，实际计算中对任何输入数据都是数值稳定的算法，称为无条件稳定。而对某些数据数值稳定，对其它数据数值不稳定的算法，称为条件稳定。,病态问题和条件数,如果问题的输入数据有微小扰动，就会引起输出结果数据 （即解）的很大扰动，称这样的问题为病态问题。相反的情形 称为良态问题。对于病态的数学问题，用通常的算法求数值解 都是不稳定的。,病态和良态是相对的，没有严格的界限，通常用条件数大小 来衡量问题的病态程度，条件数越大病态可能越严重。,条件数c(x)越大，f(x)的相对误差越大，通常认为,时，问题是病态的。,1.要避免两个相近的数相减,在数值计算中，两个相近的数作减法时 有效数字会损失。,例: 求,的值。当x = 1000，y 的准确值为0.01580,6 数值计算中应该注意的一些原则,类似地,(2) 若将原式改写为,则 y = 0.01581,(1)直接相减,有3位有效数字！,只有1位有效数字,2.尽量避免绝对值太小的数作分母,例：,如分母变为0.0011，也即分母只有0.0001的变化时,结果相差这么大!,3. 避免大数吃小数,精确解为,例：用单精度计算 的根。,在计算机内，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 + + 40 + 109,4. 简化计算步骤，避免误差积累。,一般来说，计算机处理下列运算的速度为,例：多项式求值：给定的x 求下列n 次多项式的值。,解：1. 用一般算法，即直接求和法；,2. 逐项求和法；,3. 秦九韶方法(即Hornor算法）；,算法的递推性,计算机上使用的算法常采用递推化的形式，,递推化的基本思想是把一个复杂的计算过程,归结为简单过程的多次重复。这种重复在程序,上表现为循环。递推化的优点是简化结构和节,省计算量。,例：用秦九韶方法求多项式,解：,约翰冯诺依曼 （John von Neumann,1903-1957）美藉匈牙利人，1930年接受了普林斯顿大学客座教授的职位，西渡美国。 1931年成为该校终身教授。1933年成为新成立