第一章 数值分析 绪论.ppt

1、数值分析,任课教师： 赵 茂 先 Office: 信息楼 J13-209 Mobile:E-mail: ,山 东 科 技 大 学 信 息 科 学 与 工 程 学 院,教材： 数值分析 李庆扬、王能超、易大义（华中科技大学出版社，第四版） 参考书： 数值分析 孙志忠、 袁慰平等（东南大学出版社, 第二版） 现代科学与工程计算 孟大志、刘伟（高等教育出版社）,第1章 绪 论,一、数值分析能够做什么？,（应用问题举例）,1 Introduction,今有上禾三秉，中禾二秉，下禾一秉，实三十九斗； 上禾二秉，中禾三秉，下禾一秉，实三十四斗； 上禾一秉，中禾二秉，下禾三秉，实二

2、十六斗。 问上、中、下禾实一秉各几何？ 答曰：上禾一秉九斗四分斗之一。中禾一秉四斗四分斗之一。下禾一秉二斗四分斗之三。-九章算术,1、一个两千年前的例子,这是一个线性方程组求解问题,2、已经测得在某处海洋不同深度处的水温如下： 深度（M） 466 741 950 1422 1634 水温（oC）7.04 4.28 3.40 2.54 2.13 根据这些数据，希望合理地估计出其它深度（如500米，600米，1000米）处的水温,这是一个插值问题,3、人口预测,下面给出的是中国1900年到2000年的人口数， 我们的目标是预测未来的人口数（数据量较大时）,这是一个曲线拟合问题,4、铝制波纹瓦的长度

3、问题,建筑上用的一种铝制波纹瓦是用一种机器将一块平整的铝板压制而成的.,假若要求波纹瓦长4英尺,每个波纹的高度(从中心线)为1英寸,且每个波纹以近似2英寸为一个周期. 求制做一块波纹瓦所需铝板的长度L.,这个问题就是要求由函数f(x)=sin x 给定的曲线从x=0到x=48英寸间的弧长L. 由微积分学我们知道,所求的弧长可表示为:,上述积分称为第二类椭圆积分,它不能用普通方法来计算.,这是一个数值求积问题,二、数值分析的含义、内容与特点,诺贝尔奖得主,计算物理学家 Wilson提出 现代科学研究的三大支柱：,21世纪信息社会的两个主要特征： “计算机无处不在” “数学无处不在”,21世纪信息

4、社会对科技人才的要求： -会用数学解决实际问题 -会用计算机进行科学计算,计算成为第三种科学方法,建立数学模型,选取计算方法,编写上机程序,计算得出结果,科学计算解题过程:,1. 什么是数值分析,数值计算方法是计算数学的一个主要组成部分，它主要研究使用计算机求解各种科学与工程计算问题的数值方法（近似方法）; 对求得的解的精度进行评估以及在计算机上实现求解等。,数值计算方法已经成为计算机处理实际问题的一个重要手段，从宏观天体运动学到微观分子细胞学，从工程系统到社会经济系统，无一能离开数值计算方法。因此，数值计算与计算机模拟被称为“第三种研究科学方法”。,科学计算可视化是目前研究的热门问题，下面的

5、艺术图形是基于科学计算的数据表示的例子:,分形图,混沌图,2. 传统数值分析的主要研究内容,1、数值逼近：插值、函数逼近与计算、拟合、FFT、数 值积分与微分 2、数值代数：方程求根、线性代数方程组的解法、非线 性代数方程组的解法、特征值与特征向量 3、微分方程数值解：ODE、PDE和有限元法 4、最优化方法：无约束优化与有约束优化方法,现代计算方法：融进了机器学习计算、仿生计算、网络计算、以数据为核心的计算和各种普适计算、非线性科学计算等内容。,3. 数值分析的主要特点,借助计算机提供切实可行的数学算法.,通过数值实验证明算法行之有效.,4. 如何学好数值分析,三、算法,描述算法可以有不同的

6、方式。例如，可以用日常语言 和数学语言加以叙述，也可以借助形式语言（算法语言） 给出精确的说明，也可以用框图直观地显示算法的全貌。,定义：由基本运算及运算顺序的规定所构成的 完整的解题步骤，称为算法。,例：求解二元一次联立方程组,用行列式解法：首先判别,（1）如果 ，则令计算机计算,输出计算的结果x1，x2。,（2）如果D= 0，则或是无解，或有无穷多组解。,是否为零，存在两种可能：,令,通过求解过程，可以总结出算法步骤如下：,S2 计算,S3 如果,则输出原方程无解或有无穷多组解的信息;,否则,S1 输入,S4 输出计算的结果,四、算法优劣的判别, 计算量的大小, 存贮量, 逻辑结构,例：用

7、行列式解法求解线性方程组: n阶方程组，要计算n + 1个n阶行列式的值， 总共需要做n! (n - 1) (n + 1) 次乘法运算。,n=20 需要运算多少次？,n=100?,一、误差的来源与分类,从实际问题中抽象出数学模型 模型误差,例:质量为m的物体，在重力作用下,自由下落， 其下落距离s 与时间t 的关系是：,其中 g 为重力加速度。,2 误差来源与误差分析的重要性,通过测量得到模型中参数的值 观测误差,求近似解 方法误差 (截断误差）,例如，当函数 用Taylor多项式,近似代替时，数值方法的截断误差是,（ 在 与0之间）。,四舍五入后,在数值计算方法中，主要研究截断误差和舍入误差

8、 （包括初始数据的误差）对计算结果的影响！,用计算机、计算器和笔算都只能用有限位小数来代替无穷小数或用位数较少的小数来代替位数较多的有限小数，如：,机器字长有限 舍入误差,二、误差分析的重要性,在数值计算中不注意误差分析，用不同正确的方法可能产生不同的结果，甚至有的方法求得的结果是可行的，有的方法求得的结果是错误的。,数值计算在设计算法时首先关心的是由它产生的计算结果的稳定性，而算法的稳定性与舍入误差是否增长密切相关。一个算法如果输入数据有微小扰动（即误差），而在计算过程中舍入误差不增长，则称此算法是数值稳定的，否则称其为数值不稳定。,例：求定积分,的值.,解：直接积分可产生递推公式,若取初值

9、,可得递推公式,按公式就可以逐步算出,注意此公式精确成立，且,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

10、.043 I2 0.058 I1 0.088 I0 0.182,稳定的算法 ！,在我们今后的讨论中，误差将不可回避， 算法的稳定性会是一个非常重要的话题。,注：递推公式(1)的舍入误差以5的幂次增长进行传播，因此是数值不稳定的，而递推公式(2)的舍入误差在一定范围内以0.2的幂次进行传播，随着n的增大，误差逐步减少，因此该算法是数值稳定的。,因此，可以看出数值不稳定的算法是不能使用的，实际计算中对任何输入数据都是数值稳定的算法，称为无条件稳定。而对某些数据数值稳定，对其它数据数值不稳定的算法，称为条件稳定。,一、 绝对误差与绝对误差限,例 :若用以厘米为最小刻度的尺去量桌子的长，大约为1.45

11、米，求1.45米的绝对误差。,1.45米的 绝对误差=？,不知道！,是近似值 的绝对误差,简称为误差。,定义1 设 是准确值，为 的一个近似值，称,3 误差的基本概念,但实际问题往往可以估计出 不超过某个正数 ，即 ，则称 为绝对误差限。有了绝对误差限，就可以知道 的范围为,即 落在 内。,在应用上，常常采用下列写法来刻划 的精度。,为近似值 的相对误差，记作 ，通常取,设 是准确值， 是近似值， 是近似值的误差， 称,一般情况下是不知道 的，怎么办？,相应地，若正数 满足 则称 为 的相对误差限。,二、 相对误差与相对误差限,其中， 是1到9中的一个数字； 是 0到9中一个数字； 为整数，且

12、,若近似值 的误差限是某一位的半个单位,该位到 的左边第一位非零数字共有 位,就说 有 位有效数字。也即，若,三、有效数字,取 作 的近似值， 就有三位有效数字；,取 作 的近似值， 就有五位有效数字。,例如：,注：,（1）例1.2, 1.3。 （2）若一近似数是由原真值经四舍五入得到，则必为有效数。 （3）若 是一个 位有效数字，则 都称为 的准 确数字，即 精确到他的第 位。 （4）若 是一个 位有效数字，则可取 ，这说 明有效位数越多，绝对误差越小。 （5）几个结论：,则 至少具有 位有效数字。,定理1 对于用 式表示的近似数 ，若 具有 位有效数字，则其相对误差限为,反之，若 的相对误

13、差限为,例1.4：,例：用 表示 具有三位有效数字的近似值， 则其相对误差限,设,反之,若 的相对误差的绝对值大于 ，,其中 为整数, 为正整数, 。,若 至多有 位有效数字,即 是有效数字,而 不是有效数字,则 的相对误差的绝对值必大于 ;,定理2,证明：,不是有效数字,反之,若,则,四、数值运算的误差估计,设 是一元函数， 的近似值为 ,以 近似 ，其误差限记作 ，可用Taylor展开,1、函数值的误差（当自变量有误差时）,假定 与 的比值不太大,可忽略 的高阶项,于是可得计算函数的误差限为,当 为多元函数时计算 ,如果,的近似值为 ,则 的近似为,于是函数值 的误差 由Taylor展开,

14、得：,于是误差限为,而 的相对误差限为,(1.3.3),(1.3.4),例1.5: 已测得某场地长 的值为 ,宽 的值为 ,已知 , ，试求 面积 的绝对误差限与相对误差限。,解:,其中,由式(1.3.1)得,于是绝对误差限为,相对误差限为,2、四则运算的误差估计,设 和 分别是准确值 和 的近似值。,（1）加法：令 ，则,（2）减法：令 ，则,（3）乘法：令 ，则,（4）除法：令 ，则,1.要避免两个相近的数相减,在数值计算中，两个相近的数作减法时 有效数字会损失。,y 的准确值为0.01580,4 数值运算中误差分析的方法 与原则（误差的控制）,类似地,(2) 若将原式改写为,则 y =

15、0.01581,(1)直接相减,有3位有效数字！,只有1位有效数字,2. 尽量避免绝对值太小的数作分母,例：,如分母变为0.0011，也即分母只有0.0001的变化时,结果相差这么大!,3. 避免大数吃小数,精确解为, 算法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 + + 40 + 109,4. 简化计算步骤，避免误差积累。,一般来说，计算机处理下列运算的速度为,例：多项式求值：给定的x 求下列n 次多项式的值。,解：1. 用一般算法，即直接求和法；,2. 逐项求和法；,3. 秦九韶方法(即Hornor算法）；,先计算x2, x3, , xn, 再作线性组合，需做 2n-1次乘法和n次加法。,解法一：直接求和法,解法二：逐项求和法,按顺序依次计算每一项的值再求和，需做 n(n+1)/2次乘法和n次加法。,解法三：秦九韶算法（即Ho