数值分析课件.ppt

《数值分析课件.ppt》由会员分享，可在线阅读，更多相关《数值分析课件.ppt（57页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、数学学院数学学院&教材教材 数值分析数值分析 李庆扬、王能超、易大义（华李庆扬、王能超、易大义（华中科技大学出版社，中科技大学出版社，第四版第四版）数值分析数值分析 孙志忠、孙志忠、袁慰平等（东南大学袁慰平等（东南大学出版社出版社,第二版）第二版）数值逼近数值逼近 蒋尔雄、赵风光、苏仰峰（复旦大蒋尔雄、赵风光、苏仰峰（复旦大学出版社，第二版）学出版社，第二版）数值分析精品课程网站：数值分析精品课程网站：http:/ 第第1 1章章 绪绪 论论一、数值分析能够做什么？一、数值分析能够做什么？一、数值分析能够做什么？一、数值分析能够做什么？（应用问题举例）（应用问题举例）1 1 Introduct

2、ion1 1、一个两千年前的例子、一个两千年前的例子今有上禾三秉，中禾二秉，下禾一秉，今有上禾三秉，中禾二秉，下禾一秉，实三十九斗；实三十九斗；上禾二秉，中禾三秉，下禾一秉，上禾二秉，中禾三秉，下禾一秉，实三十四斗；实三十四斗；上禾一秉，中禾二秉，下禾三秉，上禾一秉，中禾二秉，下禾三秉，实二十六斗。实二十六斗。问上、中、下禾实一秉各几何？问上、中、下禾实一秉各几何？答曰：上禾一秉九斗四分斗之一。中禾答曰：上禾一秉九斗四分斗之一。中禾一秉四斗四分斗之一。下禾一秉二斗四一秉四斗四分斗之一。下禾一秉二斗四分斗之三。分斗之三。-九章算术九章算术这是一个线性方程组求解问题这是一个线性方程组求解问题 2

3、2、已经测得在某处海洋不同深度处的水温如下：、已经测得在某处海洋不同深度处的水温如下：深度（深度（M M）466 741 950 1422 1634466 741 950 1422 1634水温（水温（o oC C）7.04 4.28 3.40 2.54 2.137.04 4.28 3.40 2.54 2.13根据这些数据，希望合理地估计出其它深度（如根据这些数据，希望合理地估计出其它深度（如500500米，米，600600米，米，10001000米米）处的水温）处的水温这是一个插值问题这是一个插值问题 3 3、人口预测、人口预测 下面给出的是中国下面给出的是中国19001900年到年到200

4、02000年的人口数，年的人口数，我们的目标是预测未来的人口数（数据量较大时）我们的目标是预测未来的人口数（数据量较大时）19505519619606620719708299219809870519901143332000126743这是一个曲线拟合问题这是一个曲线拟合问题 4 4、铝制波纹瓦的长度问题、铝制波纹瓦的长度问题 建筑上用的一种铝制波纹瓦是用一种机建筑上用的一种铝制波纹瓦是用一种机器将一块平整的铝板压制而成的器将一块平整的铝板压制而成的.假若要求波纹瓦长假若要求波纹瓦长4 4英尺英尺,每个波纹的高度每个波纹的高度(从从中心线中心线)为为1 1英寸英寸,且每个波纹以近似且每个波纹以近

5、似2 2英寸英寸为一个周期为一个周期.求制做一块波纹瓦所需铝板的求制做一块波纹瓦所需铝板的长度长度L.L.这个问题就是要求由函数这个问题就是要求由函数f f f f(x x x x)=)=)=)=sin x sin x sin x sin x 给定的曲线给定的曲线从从x x=0=0到到x x=48=48英寸间的弧长英寸间的弧长L.L.由微积分学我们知道由微积分学我们知道,所求的弧长可表示为所求的弧长可表示为:上述积分称为第二类椭圆积分上述积分称为第二类椭圆积分,它不能用普它不能用普通方法来计算通方法来计算.这是一个数值求积问题这是一个数值求积问题 二、数值分析的含义、内容与特点二、数值分析的含

6、义、内容与特点二、数值分析的含义、内容与特点二、数值分析的含义、内容与特点诺贝尔奖得主诺贝尔奖得主,计算物理学家计算物理学家 WilsonWilson提出提出现代科学研究的三大支柱：现代科学研究的三大支柱：理理论论研研究究科科学学实实验验科科学学计计算算21212121世纪信息社会的两个主要特征：世纪信息社会的两个主要特征：世纪信息社会的两个主要特征：世纪信息社会的两个主要特征：“计算机无处不在计算机无处不在计算机无处不在计算机无处不在”“数学无处不在数学无处不在数学无处不在数学无处不在”21212121世纪信息社会对科技人才的要求：世纪信息社会对科技人才的要求：世纪信息社会对科技人才的要求：

7、世纪信息社会对科技人才的要求：-会用数学解决实际问题会用数学解决实际问题会用数学解决实际问题会用数学解决实际问题-会用计算机进行科学计算会用计算机进行科学计算会用计算机进行科学计算会用计算机进行科学计算计算成为第三种科学方法计算成为第三种科学方法科学计算解题过程什么是什么是数值分析？数值分析？数值计算方法是计算数学的一个主要组成部数值计算方法是计算数学的一个主要组成部分，分，它主要研究使用计算机求解各种科学与工它主要研究使用计算机求解各种科学与工程计算问题的数值方法（近似方法）程计算问题的数值方法（近似方法）;对求得对求得的解的精度进行评估以及在计算机上实现求解的解的精度进行评估以及在计算机上

8、实现求解等。等。数值计算方法已经成为计算机处理实际问题数值计算方法已经成为计算机处理实际问题的一个重要手段，从宏观天体运动学到微观分的一个重要手段，从宏观天体运动学到微观分子细胞学，从工程系统到社会经济系统，无一子细胞学，从工程系统到社会经济系统，无一能离开数值计算方法。因此，数值计算与计算能离开数值计算方法。因此，数值计算与计算机模拟被称为机模拟被称为“第三种研究科学方法第三种研究科学方法”。传统数值分析的主要研究内容：传统数值分析的主要研究内容：1 1、数值逼近：数值逼近：插值、函数逼近与计算、拟合、插值、函数逼近与计算、拟合、FFT、数、数 值积分与微分值积分与微分2 2、数值代数：数值

9、代数：方程求根、线性代数方程组的解法、非线方程求根、线性代数方程组的解法、非线 性代数方程组的解法、特征值与特征向量性代数方程组的解法、特征值与特征向量3 3、微分方程数值解：微分方程数值解：ODE、PDE和有限元法和有限元法4 4、最优化方法：最优化方法：无约束优化与有约束优化方法无约束优化与有约束优化方法 现代计算方法：现代计算方法：融进了机器学习计算、仿生计算、融进了机器学习计算、仿生计算、网络计算、以数据为核心的计算和各种普适计算、非线网络计算、以数据为核心的计算和各种普适计算、非线性科学计算等内容。性科学计算等内容。数值分析的主要特点：数值分析的主要特点：借助计算机提供切实可行的数学

10、算法借助计算机提供切实可行的数学算法.想想的精确度的精确度;收敛且稳定收敛且稳定;误差可以分析或估计误差可以分析或估计.所提出的算法必须具有：可靠的理论分析所提出的算法必须具有：可靠的理论分析;理理时间复杂性好时间复杂性好_指节省时间；指节省时间；空间复杂性好空间复杂性好_指节省存储量。指节省存储量。计算复杂性好计算复杂性好 通过数值实验证明算法行之有效通过数值实验证明算法行之有效.如何学好数值分析？如何学好数值分析？三、算法三、算法 描述算法可以有不同的方式。例如，可以用日常语言描述算法可以有不同的方式。例如，可以用日常语言和数学语言加以叙述，也可以借助形式语言（算法语言）和数学语言加以叙述

11、，也可以借助形式语言（算法语言）给出精确的说明，也可以用框图直观地显示算法的全貌。给出精确的说明，也可以用框图直观地显示算法的全貌。定义：由基本运算及运算顺序的规定所构成的定义：由基本运算及运算顺序的规定所构成的 完整的解题步骤，称为完整的解题步骤，称为算法算法算法算法。例：求解二元一次联立方程组例：求解二元一次联立方程组用行列式解法：首先判别用行列式解法：首先判别 （1）如果如果 ，则令计算机计算，则令计算机计算 输出计算的结果输出计算的结果x1，x2。（2）如果如果D D=0 0，则或是无解，或有无穷多组解。，则或是无解，或有无穷多组解。是否为零，存在两种可能：是否为零，存在两种可能：令令

12、通过求解过程，可以总结出算法步骤如下：通过求解过程，可以总结出算法步骤如下：S2 计算计算S3 如果如果则输出原方程无解或有无穷多组解的信息则输出原方程无解或有无穷多组解的信息;否则否则S1 输入输入S4 输出计算的结果输出计算的结果输入输入 D=a11a22-a12a21D=0开始开始输出输出 x1,x2 结结 束束 No输出无解信息输出无解信息Yes四、算法优劣的判别四、算法优劣的判别 计算量的大小计算量的大小 存贮量存贮量 逻辑结构逻辑结构例：用行列式解法求解线性方程组例：用行列式解法求解线性方程组:n阶方程组，要计算阶方程组，要计算n+1个个n n阶行列式的值，阶行列式的值，总共需要做

13、总共需要做n!(n-1)(n+1)次乘法运算。次乘法运算。n=20 需要运需要运算多少次？算多少次？n=100?一、一、误差的来源与分类误差的来源与分类 从实际问题中抽象出数学模型从实际问题中抽象出数学模型 模型误差模型误差例例:质量为质量为m的物体，在重力作用下的物体，在重力作用下,自由下落，自由下落，其下落距离其下落距离s 与时间与时间t 的关系是：的关系是：其中其中 g 为重力加速度。为重力加速度。2 2 误差来源与误差分析的重要性误差来源与误差分析的重要性 通过测量得到模型中参数的值通过测量得到模型中参数的值 观测误差观测误差 求近似解求近似解 方法误差方法误差(截断误差）截断误差）例

14、如，当函数例如，当函数 用用TaylorTaylor多项式多项式 近似代替时，数值方法的截断误差是近似代替时，数值方法的截断误差是（在 与与0 0之间）。之间）。四舍五入后四舍五入后在数值计算方法中，主要研究在数值计算方法中，主要研究截断误差截断误差截断误差截断误差和和舍入误差舍入误差舍入误差舍入误差（包括初始数据的误差）对计算结果的影响！（包括初始数据的误差）对计算结果的影响！用计算机、计算器和笔算都只能用有限位小数来代替无用计算机、计算器和笔算都只能用有限位小数来代替无穷小数或用位数较少的小数来代替位数较多的有限小数，如：穷小数或用位数较少的小数来代替位数较多的有限小数，如：机器字长有限机

15、器字长有限 舍入误差舍入误差二、二、误差分析的重要性误差分析的重要性 在数值计算中不注意误差分析，用不同正确的方在数值计算中不注意误差分析，用不同正确的方法可能产生不同的结果，甚至有的方法求得的结果法可能产生不同的结果，甚至有的方法求得的结果是可行的，有的方法求得的结果是错误的。是可行的，有的方法求得的结果是错误的。计算计算 并估计误差。并估计误差。例例1.11.1:数值计算在设计算法时首先关心的是由它产生的数值计算在设计算法时首先关心的是由它产生的计算结果的稳定性，而算法的稳定性与舍入误差是计算结果的稳定性，而算法的稳定性与舍入误差是否增长密切相关。一个算法如果输入数据有微小扰否增长密切相关

16、。一个算法如果输入数据有微小扰动（即误差），而在计算过程中舍入误差不增长，动（即误差），而在计算过程中舍入误差不增长，则称此算法是则称此算法是数值稳定的数值稳定的，否则称其为，否则称其为数值不稳定。数值不稳定。例：例：求定积分求定积分 的值的值的值的值.解：解：直接积分可产生递推公式直接积分可产生递推公式若取初值若取初值可得递推公式可得递推公式按公式就可以逐步算出按公式就可以逐步算出注意此公式注意此公式精确精确成成立，且立，且What happened?!不稳定的算法不稳定的算法 ！这就是误差传播所引起的危害这就是误差传播所引起的危害这就是误差传播所引起的危害这就是误差传播所引起的危害 !NY

17、BJ蝴蝶效应蝴蝶效应 纽约的一只蝴蝶翅膀一拍，风和日丽的纽约的一只蝴蝶翅膀一拍，风和日丽的北京就刮起台风来了？！北京就刮起台风来了？！这是一个这是一个病态问题病态问题由题设中的递推公式（由题设中的递推公式（1 1）可看出，）可看出，的误差扩大了的误差扩大了5 5倍后传给倍后传给 ，因而初值，因而初值 的误差对以后各步的误差对以后各步这就造成这就造成 的计算结果的计算结果严重失真。严重失真。计算结果的影计算结果的影响，随着响，随着 的增大愈来愈严重。的增大愈来愈严重。要怎么做才能解决这个问要怎么做才能解决这个问要怎么做才能解决这个问要怎么做才能解决这个问题呢题呢题呢题呢?可求得可求得I9 0.0

18、17，按改写后的公式可逐次求得按改写后的公式可逐次求得不妨设不妨设I9 I10，于是由于是由将公式将公式变为变为I8 0.019 I7 0.021I6 0.024 I8 0.028I4 0.034 I3 0.043I2 0.058 I1 0.088I0 0.182 稳定的算法稳定的算法 ！在我们今后的讨论中，在我们今后的讨论中，误差误差将不可回避，将不可回避，算法的算法的稳定性稳定性会是一个非常重要的话题。会是一个非常重要的话题。注：注：递推公式递推公式(1)的舍入误差以的舍入误差以5的幂次增长进的幂次增长进行传播，因此是行传播，因此是数值不稳定的，数值不稳定的，而递推公式而递推公式(2)的舍

19、入误差在一定范围内以的舍入误差在一定范围内以0.2的幂次进行的幂次进行传播，随着传播，随着n的增大，误差逐步减少，因此该的增大，误差逐步减少，因此该算法是算法是数值稳定的数值稳定的。因此，可以看出数值不稳定的算法是不能使因此，可以看出数值不稳定的算法是不能使用的，实际计算中对任何输入数据都是数值稳定用的，实际计算中对任何输入数据都是数值稳定的算法，称为的算法，称为无条件稳定。无条件稳定。而对某些数据数值稳而对某些数据数值稳定，对其它数据数值不稳定的算法，称为定，对其它数据数值不稳定的算法，称为条件稳条件稳定定。一、一、绝对误差与绝对误差限绝对误差与绝对误差限例例 :若用以厘米为最小刻度的尺去量

20、桌子的长，大约若用以厘米为最小刻度的尺去量桌子的长，大约为为1.451.45米，求米，求1.451.45米的绝对误差。米的绝对误差。1.45米的米的绝对误差绝对误差=？不知道！不知道！是近似值是近似值 的的绝对误差绝对误差绝对误差绝对误差,简称为简称为误差误差误差误差。定义定义1 1 设设 是准确值，为是准确值，为 的一个近似值，称的一个近似值，称 3 3 误差的基本概念误差的基本概念 但实际问题往往可以估计出但实际问题往往可以估计出但实际问题往往可以估计出但实际问题往往可以估计出 不超过某不超过某不超过某不超过某个正数个正数个正数个正数 ，即即即即 ，则称，则称，则称，则称 为绝对为绝对为绝

21、对为绝对误差限。有了绝对误差限，就可以知道误差限。有了绝对误差限，就可以知道误差限。有了绝对误差限，就可以知道误差限。有了绝对误差限，就可以知道 的范围为的范围为的范围为的范围为即即即即 落在落在落在落在 内。内。内。内。在应用上，常常采用下列写法来刻划在应用上，常常采用下列写法来刻划在应用上，常常采用下列写法来刻划在应用上，常常采用下列写法来刻划 的精度。的精度。的精度。的精度。为近似值为近似值 的的相对误差相对误差相对误差相对误差，记作，记作 ，通常取通常取 设设 是准确值，是准确值，是近似值，是近似值，是近似值的误差，是近似值的误差，称称 一般情况下是不知道一般情况下是不知道一般情况下是

22、不知道一般情况下是不知道 的，怎么办？的，怎么办？的，怎么办？的，怎么办？相应地，若正数相应地，若正数 满足满足 则称则称 为为 的相对误差限。的相对误差限。二、二、相对误差与相对误差限相对误差与相对误差限有有 位有效数字。位有效数字。则称则称则称则称其中，其中，是是1 1到到9 9中的一个数字；中的一个数字；是是0 0到到9 9中一个数字；中一个数字；为整数，且为整数，且 若近似值若近似值 的误差限是某一位的半个单位的误差限是某一位的半个单位,该位该位到到 的的左边左边第一位非零数字共有第一位非零数字共有 位位,就说就说 有有 位位有效有效数字数字。也即，若也即，若 三、有效数字三、有效数字

23、取取 作作 的近似值，的近似值，就有三位有效数字；就有三位有效数字；取取 作作 的近似值，的近似值，就有五位有效数字。就有五位有效数字。例如：例如：注：注：（1 1）例）例1.2,1.31.2,1.3。（2 2）若一近似数是由原真值经四舍五入得到，则必为有效数。若一近似数是由原真值经四舍五入得到，则必为有效数。若一近似数是由原真值经四舍五入得到，则必为有效数。若一近似数是由原真值经四舍五入得到，则必为有效数。（3 3）若若若若 是一个是一个是一个是一个 位有效数字，则位有效数字，则位有效数字，则位有效数字，则 ，这说明有，这说明有，这说明有，这说明有 效位数越多，绝对误差越小。效位数越多，绝对

24、误差越小。效位数越多，绝对误差越小。效位数越多，绝对误差越小。则则 至少具有至少具有 位有效数字。位有效数字。定理定理1 1 对于用对于用 式表示的近似数式表示的近似数 ，若，若 具有具有 位有位有效效数字，则其相对误差限为数字，则其相对误差限为反之，若反之，若 的相对误差限为的相对误差限为证明：证明：由由(*)式可得式可得:反之反之 即即 至少有至少有 位有效数字位有效数字.当当 有有 位有效数值时位有效数值时:例例例例1.41.4：例：例：例：例：用用 表示表示 具有三位有效数字的近具有三位有效数字的近似值，似值，则其相对误差限则其相对误差限 要使要使 的近似值的相对误差限的近似值的相对误

25、差限小于小于 ,要取几位有效数字要取几位有效数字?四四、数值运算的误差估计数值运算的误差估计设设 是一元函数，是一元函数，的近似值为的近似值为 ,以以 近似近似 ，其误差限记作，其误差限记作 ，可用，可用TaylorTaylor展开展开 介于介于介于介于之间之间之间之间.取绝对值得取绝对值得取绝对值得取绝对值得1 1、函数值的误差（当自变量有误差时）、函数值的误差（当自变量有误差时）假定假定 与与 的比值不太大的比值不太大,可忽略可忽略 的的高阶项高阶项,于是可得计算函数的误差限为于是可得计算函数的误差限为 当当 为多元函数时计算为多元函数时计算 ,如果如果的近似值为的近似值为 ,则则 的近似

26、为的近似为于是函数值于是函数值 的误差的误差 由由TaylorTaylor展开展开,得：得：得：得：于是误差限为于是误差限为于是误差限为于是误差限为而而而而 的相对误差限为的相对误差限为的相对误差限为的相对误差限为(1.3.1)(1.3.1)(1.3.2)(1.3.2)例例例例1.5:1.5:已测得某场地长已测得某场地长已测得某场地长已测得某场地长 的值为的值为的值为的值为 ,宽宽宽宽 的值为的值为的值为的值为 ,已知已知已知已知 ,，试求，试求，试求，试求面积面积面积面积 的绝对误差限与相对误差限。的绝对误差限与相对误差限。的绝对误差限与相对误差限。的绝对误差限与相对误差限。解解解解:其中其

27、中其中其中由式由式由式由式(1.3.1)(1.3.1)得得得得于是绝对误差限为于是绝对误差限为于是绝对误差限为于是绝对误差限为相对误差限为相对误差限为相对误差限为相对误差限为2 2、四则运算的误差估计四则运算的误差估计设设设设 和和和和 分别是准确值分别是准确值分别是准确值分别是准确值 和和和和 的近似值。的近似值。的近似值。的近似值。（1 1）加法：令加法：令加法：令加法：令 ，则，则，则，则（2 2）减法：令减法：令减法：令减法：令 ，则，则，则，则（3 3）乘法：令乘法：令乘法：令乘法：令 ，则，则，则，则（4 4）除法：令除法：令除法：令除法：令 ，则，则，则，则1.要避免两个相近的数

28、相减要避免两个相近的数相减在数值计算中，两个相近的数作减法时在数值计算中，两个相近的数作减法时有效数字会损失。有效数字会损失。例例:求求的值。的值。当当x=1000，y 的准确值为的准确值为0.01580 4 4 数值运算中误差分析的方法数值运算中误差分析的方法 与原则（误差的控制）与原则（误差的控制）类似地类似地(2)若若将将原式原式改写为改写为则则 y=0.01581(1)直接相减直接相减有有3 3位有效数字！位有效数字！只有只有1位有效数字位有效数字2.尽量避免绝对值太小的数作分母尽量避免绝对值太小的数作分母例：例：如分母变为如分母变为0.0011，也即分母只有，也即分母只有0.0001

29、的变化时的变化时结果相差这么结果相差这么结果相差这么结果相差这么大大大大!3.避免大数避免大数吃吃小数小数精确解为精确解为 算法算法1 1：利用求根公式：利用求根公式例：例：例：例：用单精度计算用单精度计算用单精度计算用单精度计算 的根。的根。的根。的根。在计算机内，在计算机内，109存为存为0.1 1010，1存为存为0.1 101。做加法时，两加数的指数先向大指数对齐，再将做加法时，两加数的指数先向大指数对齐，再将浮点部分相加。即浮点部分相加。即1 的指数部分须变为的指数部分须变为1010，则：，则：1=0.0000000001 1010，取单精度时就成为：，取单精度时就成为：109+1=

30、0.10000000 1010+0.00000000 1010=0.10000000 1010?算法算法2 2：先解出先解出再利用再利用注：注：注：注：求和时从小到大相加，可使和的误差减小。求和时从小到大相加，可使和的误差减小。例：例：按从小到大、以及从大到小的顺序分别计算按从小到大、以及从大到小的顺序分别计算1+2+3+40+1094.4.简化计算步骤，避免误差积累。简化计算步骤，避免误差积累。一般来说，计算机处理下列运算的速度为一般来说，计算机处理下列运算的速度为例：例：多项式求值：给定的多项式求值：给定的x x 求下列求下列n n 次多项式的值。次多项式的值。解：解：1.1.用一般算法，

31、即直接求和法；用一般算法，即直接求和法；2.2.逐项求和法；逐项求和法；3.3.秦九韶方法秦九韶方法(即即HornorHornor算法）；算法）；先计算先计算x2,x3,xn,再作线性组合，需做再作线性组合，需做2n-1次次乘法和乘法和n次次加法。加法。解法一：解法一：直接求和法直接求和法解法二：逐项求和法解法二：逐项求和法 按顺序依次计算每一项的值再求和，需做按顺序依次计算每一项的值再求和，需做n(n+1)/2次次乘法和乘法和n次次加法。加法。解法三：秦九韶算法（即解法三：秦九韶算法（即Horner算法）算法）只需做只需做n次次乘法和乘法和n次次加法。且可以递推实现。加法。且可以递推实现。约

32、翰约翰冯冯诺依曼诺依曼（John von Neumann,1903-1957）美藉匈牙利人，）美藉匈牙利人，1930年接受了普林斯顿大学客座教授的职年接受了普林斯顿大学客座教授的职位，西渡美国。位，西渡美国。1931年成为该校终身教授。年成为该校终身教授。1933年成为新成立的普林斯顿高等研究院年成为新成立的普林斯顿高等研究院的终身研究员。的终身研究员。1951年至年至1953 年任美国数年任美国数学会主席。学会主席。冯冯诺依曼是诺依曼是20世纪少有的数学科学世纪少有的数学科学通才，在许多领域都有重要的贡献，被西通才，在许多领域都有重要的贡献，被西方人誉为方人誉为“数学奇才、计算机之父数学奇才、计算机之父”。冯。冯诺依曼对人类的最大贡献是对计算机科学、诺依曼对人类的最大贡献是对计算机科学、计算机技术和数值分析的开拓性工作。计算机技术和数值分析的开拓性工作。