数值分析第1章绪论.ppt

《数值分析第1章绪论.ppt》由会员分享，可在线阅读，更多相关《数值分析第1章绪论.ppt（77页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、山山东东科科技技大大学学信信息息科科学学与与工工程程学学院院数值分析数值分析 能够做什么？11 IntroductionIntroduction应用问题举例应用问题举例今有上禾三秉，中禾二秉，下禾一秉，今有上禾三秉，中禾二秉，下禾一秉，实三十九斗；实三十九斗；上禾二秉，中禾三秉，下禾一秉，上禾二秉，中禾三秉，下禾一秉，实三十四斗；实三十四斗；上禾一秉，中禾二秉，下禾三秉，上禾一秉，中禾二秉，下禾三秉，实二十六斗。实二十六斗。问上、中、下禾实一秉各几何？问上、中、下禾实一秉各几何？答曰：上禾一秉九斗四分斗之一。中禾答曰：上禾一秉九斗四分斗之一。中禾一秉四斗四分斗之一。下禾一秉二斗四一秉四斗四分斗

2、之一。下禾一秉二斗四分斗之三。分斗之三。-九章算术九章算术1 1、一个两千年前的例子、一个两千年前的例子2 2、天体力学中的、天体力学中的KeplerKepler方程方程x是行星运动的轨道，它是时间是行星运动的轨道，它是时间t 的的函数函数.全球定位系统：全球定位系统：在地球的任何一在地球的任何一个位置，至少可个位置，至少可以同时收到以同时收到4 4颗颗以上卫星发射的以上卫星发射的信号信号 3、全球定位系统（全球定位系统（Global Positioning System,GPS)Global Positioning System,GPS)表示地球上表示地球上一个接收点一个接收点R R的当前位

3、的当前位置，卫星置，卫星S Si i的位置为的位置为 ，则得，则得到下列非线性方程组到下列非线性方程组记为记为其中，其中，4 4、已经测得在某处海洋不同深度处的水温如下：、已经测得在某处海洋不同深度处的水温如下：深度（深度（M M）466 741 950 1422 1634 466 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米米）处的水温）处的

4、水温5 5、用比较简单的函数代替复杂的函数、用比较简单的函数代替复杂的函数误差为最小，即距离为最小误差为最小，即距离为最小（在不同的度量意义下）（在不同的度量意义下）6 6、人口预测、人口预测 下面给出的是中国下面给出的是中国19001900年到年到20002000年的人口数，年的人口数，我们的目标是预测未来我们的目标是预测未来的人口数（数据量较大的人口数（数据量较大时）时）7 7、铝制波纹瓦的长度问题、铝制波纹瓦的长度问题 建筑上用的一种铝制波纹瓦是用一种机建筑上用的一种铝制波纹瓦是用一种机器将一块平整的铝板压制而成的器将一块平整的铝板压制而成的.假若要求波纹瓦长假若要求波纹瓦长4 4英尺英

5、尺,每个波纹的高度每个波纹的高度(从从中心线中心线)为为1 1英寸英寸,且每个波纹以近似且每个波纹以近似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、通方法来计算.数值计算方法的意义、内容与方法数值计算方法的意义、内容与方法软件的核心就是算法。软件的核心就是算法。软件的核心就是算法。软件的核心就是算法。20 20 世纪最伟大的科学技术发明世纪最伟大的科学技术发明世纪最伟大的科学技术发明世纪最伟大的科学技术发明-计算机计算机计算机计算机 计算机是对人脑的模拟，它强化了人的思维智能；计算机是对人脑的模拟，它强化了人的思维智能；计算机是对人脑的模拟，它强化了人的思维智能；计算机是对人脑的模拟，它强化了人的思维智能；计算机的发展和应用，已不仅仅是一种科学技术计算机的发展和应用，已不仅仅是一种科学技术计算机的发展和应用，已不仅仅是一种科学技术计算机的

7、发展和应用，已不仅仅是一种科学技术现象，而且成了一种政治、军事、经济和社会现象；现象，而且成了一种政治、军事、经济和社会现象；现象，而且成了一种政治、军事、经济和社会现象；现象，而且成了一种政治、军事、经济和社会现象；没有软件的支持，超级计算机只是一堆废铁而已；没有软件的支持，超级计算机只是一堆废铁而已；没有软件的支持，超级计算机只是一堆废铁而已；没有软件的支持，超级计算机只是一堆废铁而已；算法犹如乐谱，算法犹如乐谱，算法犹如乐谱，算法犹如乐谱，软件犹如软件犹如软件犹如软件犹如CDCD盘片，盘片，盘片，盘片，而硬件如同而硬件如同而硬件如同而硬件如同CDCD唱机。唱机。唱机。唱机。理理论论研研究

8、究科科学学实实验验科科学学计计算算诺贝尔奖得主诺贝尔奖得主,计算物理学家计算物理学家 WilsonWilson提出提出 现代科学研究的三大支柱现代科学研究的三大支柱21212121世纪信息社会的两个主要特征：世纪信息社会的两个主要特征：世纪信息社会的两个主要特征：世纪信息社会的两个主要特征：“计算机无处不在计算机无处不在计算机无处不在计算机无处不在”“数学无处不在数学无处不在数学无处不在数学无处不在”21212121世纪信息社会对科技人才的要求：世纪信息社会对科技人才的要求：世纪信息社会对科技人才的要求：世纪信息社会对科技人才的要求：-会用数学解决实际问题会用数学解决实际问题会用数学解决实际问

9、题会用数学解决实际问题-会用计算机进行科学计算会用计算机进行科学计算会用计算机进行科学计算会用计算机进行科学计算 科学方法论的巨大变革科学方法论的巨大变革：如果说如果说伽伽利略和牛顿利略和牛顿在科学发展史上奠定了实验在科学发展史上奠定了实验和理论这两大科学方法的支柱，那么由和理论这两大科学方法的支柱，那么由冯冯.诺依曼诺依曼研制的现代电子计算机把计算研制的现代电子计算机把计算推上了人类科学活动的前沿，使计算成推上了人类科学活动的前沿，使计算成为为第三种方法第三种方法。山山东东科科技技大大学学 信信 息息 学学 院院科学计算解题过程数值计算方法是计算数学的一个主要组成部分，数值计算方法是计算数学

10、的一个主要组成部分，“什么是什么是数值计算方法？数值计算方法？”山山山山东东东东科科科科技技技技大大大大学学学学 信信信信 息息息息 学学学学 院院院院它主要研究使用计算机求解各种科学与工程计算它主要研究使用计算机求解各种科学与工程计算问题的数值方法（近似方法）问题的数值方法（近似方法）;对求得的解的精对求得的解的精度进行评估以及在计算机上实现求解等。度进行评估以及在计算机上实现求解等。数值计算方法已经成为计算机处理实际问题的数值计算方法已经成为计算机处理实际问题的一个重要手段，从宏观天体运动学到微观分子细一个重要手段，从宏观天体运动学到微观分子细胞学，从工程系统到社会经济系统，无一能离开胞学

11、，从工程系统到社会经济系统，无一能离开数值计算方法。因此，数值计算与计算机模拟被数值计算方法。因此，数值计算与计算机模拟被称为称为“第三种研究科学方法第三种研究科学方法”。科学计算科学计算科学计算科学计算可视化是可视化是可视化是可视化是目前研究目前研究目前研究目前研究的热门问的热门问的热门问的热门问题，下面题，下面题，下面题，下面的艺术图的艺术图的艺术图的艺术图形是基于形是基于形是基于形是基于科学计算科学计算科学计算科学计算的数据表的数据表的数据表的数据表示的例子示的例子示的例子示的例子山山山山东东东东科科科科技技技技大大大大学学学学 信信信信 息息息息 学学学学 院院院院分形图分形图混沌图混

12、沌图山山东东科科技技大大学学 信信 息息 学学 院院一、一、计算数学的产生和早期发展计算数学的产生和早期发展计算数学是数学的一个古老的分支，虽然数学不仅仅计算数学是数学的一个古老的分支，虽然数学不仅仅是计算，但推动数学产生和发展的最直接原因还是是计算，但推动数学产生和发展的最直接原因还是计算问题计算问题计算问题计算问题。二、二、二十世纪计算数学的发展二十世纪计算数学的发展数值代数数值代数 最优化计算最优化计算 数值逼近数值逼近 计算几何计算几何 概率统计计算概率统计计算 蒙特卡罗方法蒙特卡罗方法 微分方程的数值解法微分方程的数值解法 微分方程的反演问题微分方程的反演问题 传统的数值计算的主要研

13、究内容：传统的数值计算的主要研究内容：1、数值逼近数值逼近 插值与拟合、插值与拟合、FFT、数值积分与微分、数值积分与微分2、数值代数、数值代数 代数基础、线性代数方程组的解法、非线性代数方代数基础、线性代数方程组的解法、非线性代数方程（组）的解法、特征值与特征向量程（组）的解法、特征值与特征向量3、微分方程数值解、微分方程数值解 ODE、PDE和有限元法和有限元法4、最优化方法、最优化方法 无约束优化与有约束优化方法无约束优化与有约束优化方法 现代计算方法：现代计算方法：融进了机器学习计算、仿生计融进了机器学习计算、仿生计算、网络计算、以数据为核心的计算和各种普适计算、网络计算、以数据为核心

14、的计算和各种普适计算、非线性科学计算等内容。算、非线性科学计算等内容。山山东东科科技技大大学学 信信 息息 学学 院院数值计算方法的主要特点数值计算方法的主要特点借助计算机提供切实可行的数学算法借助计算机提供切实可行的数学算法.想想的精确度的精确度;收敛且稳定收敛且稳定;误差可以分析或估计误差可以分析或估计.所提出的算法必须具有：可靠的理论分析所提出的算法必须具有：可靠的理论分析;理理时间复杂性好时间复杂性好_指节省时间；指节省时间；空间复杂性好空间复杂性好_指节省存储量。指节省存储量。计算复杂性好计算复杂性好 通过数值实验证明算法行之有效通过数值实验证明算法行之有效.山山东东科科技技大大学学

15、 信信 息息 学学 院院F采用采用“近似替代近似替代”方法方法逼近逼近F采用采用“构造性构造性”方法方法F采用采用“离散化离散化”方法方法 把求连续变量的问题转化为求离散变量的问题把求连续变量的问题转化为求离散变量的问题F采用采用“递推化递推化”方法方法 复杂的计算归结为简单过程的多次重复，易复杂的计算归结为简单过程的多次重复，易于用循环结构来实现（迭代法）。于用循环结构来实现（迭代法）。F采用各种采用各种搜索搜索方法方法构造数值算法主要手段构造数值算法主要手段山山东东科科技技大大学学 信信 息息 学学 院院如何学好数值计算方法？如何学好数值计算方法？山山东东科科技技大大学学 信信 息息 学学

16、 院院 希希 望：望：求近似解，但方法简单可行，行之有效求近似解，但方法简单可行，行之有效 （计算量小，误差小（计算量小，误差小,需存储单元少等）需存储单元少等）,以计算机为工具，易在计算机上实现。以计算机为工具，易在计算机上实现。计算机运算计算机运算:只能进行加，减，乘，除等算术运算和一只能进行加，减，乘，除等算术运算和一 些逻辑运算。些逻辑运算。数值计算方法：数值计算方法：把求解数学问题转化为按一定次序只进行把求解数学问题转化为按一定次序只进行 加，减，乘，除等基本运算加，减，乘，除等基本运算.设计数值算法的出发点？设计数值算法的出发点？山山东东科科技技大大学学 信信 息息 学学 院院威尔

17、金森威尔金森（James Hardy.Wilkinson，1919-1986）Wilkinson是数值分析和数值计算的是数值分析和数值计算的开拓者和奠基人开拓者和奠基人。1940 年，开始研究弹道的数年，开始研究弹道的数学模型与数值计算。学模型与数值计算。1946 年成为年成为Turing 的助手，的助手，协助设计协助设计 Pilot ACE 计算机。计算机。1969年他当选为英年他当选为英国皇家学会院士；国皇家学会院士；1970年工业和应用数学会年工业和应用数学会(s1am)授予他冯授予他冯诺伊曼奖；诺伊曼奖；1987年他获得美国年他获得美国数学会的数学会的chauvenet奖。著名的美国阿

18、尔贡国家奖。著名的美国阿尔贡国家实验室曾聘威尔金森为荣誉高级研究员并两次向实验室曾聘威尔金森为荣誉高级研究员并两次向他授奖。他授奖。Wilkinson在数值分析研究领域作出了杰出贡献，是数值计算在数值分析研究领域作出了杰出贡献，是数值计算的早期开拓者，其工作加速了数字计算机的早期开拓者，其工作加速了数字计算机(在科学计算中在科学计算中)的的使用。他研究的主要问题是线性代数方程组和矩阵特征值问题使用。他研究的主要问题是线性代数方程组和矩阵特征值问题的数值解法，特别是他的向后误差分析法的数值解法，特别是他的向后误差分析法(backward error analysis)的创造性工作奠定了数值分析和

19、数值计算早期的理论的创造性工作奠定了数值分析和数值计算早期的理论基础。基础。1975 年年 J.H.Wilkinson成为第五位图灵奖获得者。成为第五位图灵奖获得者。&教材教材 现代科学与工程计算现代科学与工程计算 孟大志孟大志 刘伟（高等教育出版社）刘伟（高等教育出版社）&参考书目参考书目 数值分析数值分析 孙志忠孙志忠 袁慰平等（东南大学出版社袁慰平等（东南大学出版社,第二版）第二版）应用应用数值方法数值方法 使用使用MATLAB和和C语言语言 Robert J.Schilling&Sandra L.Harris （机械工业出版社）机械工业出版社）数值分析基础教程数值分析基础教程 李庆扬李

20、庆扬 编编 （高等教育出版社）（高等教育出版社）现代数值分析现代数值分析 李庆扬、易大义、王能超李庆扬、易大义、王能超 编著编著 （高等教育出版社）（高等教育出版社）数值分析与科学计算数值分析与科学计算 Jeffery J.Leader 著，张威，刘志军，李艳著，张威，刘志军，李艳红等译，（清华大学出版社红等译，（清华大学出版社)2 算算 法法一、算法的概念一、算法的概念 描述算法可以有不同的方式。例如，可以用日常语言描述算法可以有不同的方式。例如，可以用日常语言和数学语言加以叙述，也可以借助形式语言（算法语言）和数学语言加以叙述，也可以借助形式语言（算法语言）给出精确的说明，也可以用框图直观

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

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

23、0 需要运需要运算多少次？算多少次？n=100?一、一、误差的来源与分类误差的来源与分类 从实际问题中抽象出数学模型从实际问题中抽象出数学模型 模型误差模型误差例例:质量为质量为m的物体，在重力作用下的物体，在重力作用下,自由下落，自由下落，其下落距离其下落距离s 与时间与时间t 的关系是：的关系是：其中其中 g 为重力加速度。为重力加速度。3 误误 差差 通过测量得到模型中参数的值通过测量得到模型中参数的值 观测误差观测误差 求近似解求近似解 方法误差方法误差(截断误差）截断误差）例如，当函数例如，当函数 用用TaylorTaylor多项式多项式 近似代替时，数值方法的截断误差是近似代替时，

24、数值方法的截断误差是 与与0 0之间。之间。在在机器字长有限机器字长有限 舍入误差舍入误差 用计算机、计算器和笔算，都只能用有限位用计算机、计算器和笔算，都只能用有限位=3.1415926 小数来代替无穷小数或用位数较少的小数来小数来代替无穷小数或用位数较少的小数来代替位数较多的有限小数，如：代替位数较多的有限小数，如：四舍五入后在数值计算方法中，主要研究在数值计算方法中，主要研究截断误差截断误差截断误差截断误差和和舍入误差舍入误差舍入误差舍入误差（包括初始数据的误差）对计算结果的影响！（包括初始数据的误差）对计算结果的影响！二、二、误差的概念误差的概念1、绝对误差与绝对误差限、绝对误差与绝对

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

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

27、情况下是不知道一般情况下是不知道一般情况下是不知道一般情况下是不知道 的，怎么办？的，怎么办？的，怎么办？的，怎么办？事实上，当事实上，当 较小时较小时是是 的二次方项级的二次方项级,故可忽略不计故可忽略不计.相应地，若正数相应地，若正数满足满足 则称则称 为为 的相对误差限。的相对误差限。3、有效数字有效数字定义：定义：如果如果则说则说 近似表示近似表示 准确到小数后第准确到小数后第 位，并从这位，并从这由上述定义由上述定义第第 位起直到最左边的非零数字之间的一切数字都位起直到最左边的非零数字之间的一切数字都称为称为有效数字有效数字有效数字有效数字，并把有效数字的位数称为并把有效数字的位数称

28、为有效位数有效位数有效位数有效位数。定义定义:若近似值若近似值 的误差限是某一位的半个单位的误差限是某一位的半个单位,也即，若也即，若有有 位有效数字。位有效数字。则称则称则称则称其中，其中，是是1 1到到9 9中的一个数字；中的一个数字；是是0 0到到9 9中一个数字；中一个数字；为整数，且为整数，且 该位该位到到 的的左边左边第一位非零数字共有第一位非零数字共有 位位,就说就说 有有 位位有效数字有效数字。取取 作作 的近似值，的近似值，就有三位有效数字；就有三位有效数字；取取 作作 的近似值，的近似值，就有五位有效数字。就有五位有效数字。例如：例如：注：注：若一近似数是由原真值经四舍五入

29、得到，若一近似数是由原真值经四舍五入得到，若一近似数是由原真值经四舍五入得到，若一近似数是由原真值经四舍五入得到，则必为有效数则必为有效数则必为有效数则必为有效数.4、误差限与、误差限与有效数字的关系有效数字的关系 则则 至少具有至少具有 位有效数字。位有效数字。Th1.1Th1.1：对于用对于用 式表示的近似数式表示的近似数 ，若，若 具有具有 位有效位有效数字，则其相对误差限为数字，则其相对误差限为反之，若反之，若 的相对误差限为的相对误差限为Th1.2Th1.2：设设反之反之,若若 的相对误差的绝对值大于的相对误差的绝对值大于 ，其中其中 为整数为整数,为正整数为正整数,。有有 位有效数

30、字。位有效数字。则则 至多至多若若 至多有至多有 位有效数字位有效数字,即即 是有效数字是有效数字,而而 不是有效数字不是有效数字,则则 的相对误差的绝对值必大于的相对误差的绝对值必大于 ;证明：证明：不是有效数字不是有效数字 反之反之,若若 则则 不是有效数字，不是有效数字，即即 至多有至多有 位有效数位有效数字字.4 数值运算的误差估计数值运算的误差估计一一、四则运算的误差估计四则运算的误差估计两个近似数两个近似数两个近似数两个近似数 与与与与 ,其误差限分别为其误差限分别为其误差限分别为其误差限分别为 及及及及 ,它们进行加减乘除运算得到的误差限分别为它们进行加减乘除运算得到的误差限分别

31、为它们进行加减乘除运算得到的误差限分别为它们进行加减乘除运算得到的误差限分别为二二、函数误差估计函数误差估计当自变量有误差时，计算函数值也会产生误差，其当自变量有误差时，计算函数值也会产生误差，其误差限可利用函数的误差限可利用函数的TaylorTaylor展开式进行估计。展开式进行估计。设设 是一元函数，是一元函数，的近似值为的近似值为 ,以以 近似近似 ，其误差限记作，其误差限记作 ，可用，可用TaylorTaylor展开展开 介于介于介于介于之间之间之间之间.取绝对值得取绝对值得取绝对值得取绝对值得假定假定 与与 的比值不太大的比值不太大,可忽略可忽略 的的高阶项高阶项,于是可得计算函数的

32、误差为于是可得计算函数的误差为 当当 为多元函数时计算为多元函数时计算 ,如果如果的近似值为的近似值为 ,则则 的近似为的近似为于是函数值于是函数值 的误差的误差 由由TaylorTaylor展开展开,得：得：得：得：于是误差限为于是误差限为于是误差限为于是误差限为而而而而 的相对误差限为的相对误差限为的相对误差限为的相对误差限为(1.3.1)(1.3.1)(1.3.2)(1.3.2)例例例例:已测得某场地长已测得某场地长已测得某场地长已测得某场地长 的值为的值为的值为的值为 ,宽宽宽宽 的值为的值为的值为的值为 ,已知已知已知已知 ,.试求试求试求试求面积面积面积面积 的绝对误差限与相对误差

33、限的绝对误差限与相对误差限的绝对误差限与相对误差限的绝对误差限与相对误差限.解解解解:因因因因 其中其中其中其中由式由式由式由式(1.3.1)(1.3.1)得得得得而而而而于是绝对误差限为于是绝对误差限为于是绝对误差限为于是绝对误差限为相对误差限为相对误差限为相对误差限为相对误差限为5 算法的数值稳定性算法的数值稳定性 数值计算在设计算法时首先关心的是由它产数值计算在设计算法时首先关心的是由它产生的计算结果的稳定性，而算法的稳定性与舍生的计算结果的稳定性，而算法的稳定性与舍入误差是否增长密切相关。一个算法如果输入入误差是否增长密切相关。一个算法如果输入数据有微小扰动（即误差），而在计算过程中数

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

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

36、求得不妨设不妨设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)的舍入误差在一定范围内以的舍入误差在一定范围内以0.2

37、的幂次进行的幂次进行传播，随着传播，随着n的增大，误差逐步减少，因此该的增大，误差逐步减少，因此该算法是算法是数值稳定的数值稳定的。因此，可以看出数值不稳定的算法是不能使因此，可以看出数值不稳定的算法是不能使用的，实际计算中对任何输入数据都是数值稳定用的，实际计算中对任何输入数据都是数值稳定的算法，称为的算法，称为无条件稳定。无条件稳定。而对某些数据数值稳而对某些数据数值稳定，对其它数据数值不稳定的算法，称为定，对其它数据数值不稳定的算法，称为条件稳条件稳定定。病态问题和条件数病态问题和条件数 如果问题的输入数据有微小扰动，就会引起输出结果数据如果问题的输入数据有微小扰动，就会引起输出结果数据

38、（即解）的很大扰动，称这样的问题为（即解）的很大扰动，称这样的问题为病态问题病态问题。相反的情形相反的情形称为称为良态问题良态问题。对于病态的数学问题，用通常的算法求数值解。对于病态的数学问题，用通常的算法求数值解都是都是不稳定的。不稳定的。病态和良态是病态和良态是相对的相对的，没有严格的界限，通常用条件数大小没有严格的界限，通常用条件数大小来衡量问题的病态程度，条件数越大病态可能越严重。来衡量问题的病态程度，条件数越大病态可能越严重。条件数条件数c(x)越大，越大，f(x)的相对误差越大，通常认为的相对误差越大，通常认为时，问题是时，问题是病态的。病态的。1.要避免两个相近的数相减要避免两个

39、相近的数相减在数值计算中，两个相近的数作减法时在数值计算中，两个相近的数作减法时有效数字会损失。有效数字会损失。例例:求求的值。的值。当当x=1000，y 的准确值为的准确值为0.01580 6 数值计算中应该注意的一些原则数值计算中应该注意的一些原则类似地类似地(2)若若将将原式原式改写为改写为则则 y=0.01581(1)直接相减直接相减有有3 3位有效数字！位有效数字！只有只有1位有效数字位有效数字2.尽量避免绝对值太小的数作分母尽量避免绝对值太小的数作分母例：例：如分母变为如分母变为0.0011，也即分母只有，也即分母只有0.0001的变化时的变化时结果相差这么结果相差这么结果相差这么

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

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

42、求和法；逐项求和法；3.3.秦九韶方法秦九韶方法(即即HornorHornor算法）；算法）；算法的递推性算法的递推性计算机上使用的算法常采用计算机上使用的算法常采用递推化递推化的形式，的形式，递推化的基本思想是递推化的基本思想是把一个复杂的计算过程把一个复杂的计算过程归结为简单过程的多次重复。这种重复在程序归结为简单过程的多次重复。这种重复在程序上表现为循环。递推化的优点是简化结构和节上表现为循环。递推化的优点是简化结构和节省计算量省计算量。例：例：用秦九韶方法求多项用秦九韶方法求多项式式解：解：Ka5-KvK00.008330.00833v0=a510.041670.04v1=v0 x+a

43、420.166670.15867v2=v1x+a330.50.46827v3=v2x+a2410.90635v4=v3x+a1510.81873v5=v4x+a0约翰约翰冯冯诺依曼诺依曼（John von Neumann,1903-1957）美藉匈牙利人，）美藉匈牙利人，1930年接受了普林斯顿大学客座教授的职年接受了普林斯顿大学客座教授的职位，西渡美国。位，西渡美国。1931年成为该校终身教授。年成为该校终身教授。1933年成为新成立的普林斯顿高等研究院年成为新成立的普林斯顿高等研究院的终身研究员。的终身研究员。1951年至年至1953 年任美国数年任美国数学会主席。学会主席。冯冯诺依曼是诺

44、依曼是20世纪少有的数学科学世纪少有的数学科学通才，在许多领域都有重要的贡献，被西通才，在许多领域都有重要的贡献，被西方人誉为方人誉为“数学奇才、计算机之父数学奇才、计算机之父”。冯。冯诺依曼对人类的最大贡献是对计算机科学、诺依曼对人类的最大贡献是对计算机科学、计算机技术和数值分析的开拓性工作。计算机技术和数值分析的开拓性工作。并行计算并行计算 一、一、电子计算机的并行计算分类电子计算机的并行计算分类 传统计算机一般采用传统计算机一般采用Von Neumann结构，每一时刻结构，每一时刻只有一个进程的算法，即只有一个进程的算法，即串行算法。串行算法。并行计算机每一时刻具有并行计算机每一时刻具有

45、2个以上个以上的进程的算法称为的进程的算法称为并行算法。并行机必须包含并行算法。并行机必须包含2台以上台以上处理机，按指令流是处理机，按指令流是单个还是多个并行算法可分为两类：单个还是多个并行算法可分为两类：SIMD算法算法适用于单指令流多数据流系统；适用于单指令流多数据流系统；MIMD算法算法适用于多指令流多数据流系统适用于多指令流多数据流系统。按照进程之间是否同步可将并行算法分为按照进程之间是否同步可将并行算法分为:同步算法同步算法:是指在是指在k个进程的算法中有些进程的若干算个进程的算法中有些进程的若干算法必须在另一些进程的某些算法之后执行；法必须在另一些进程的某些算法之后执行；异步算法

46、异步算法:指指k个进程间有信息联系但不须同步，它只个进程间有信息联系但不须同步，它只能在一个具有能在一个具有k台处理机的台处理机的MIMD系统中实现。系统中实现。二、并行计算的算法设计二、并行计算的算法设计 并行算法设计的重要原则是并行算法设计的重要原则是“分而治之分而治之”。其基本思其基本思想想是把问题依次划分为可以独立完成的较小问题，将规模是把问题依次划分为可以独立完成的较小问题，将规模逐逐次减半次减半的二分技术是并行算法设计的一种基本技术。的二分技术是并行算法设计的一种基本技术。二分算法的设计原理是反复地将所给计算问题加工成二分算法的设计原理是反复地将所给计算问题加工成规模减半的同类计算

47、问题而计算。可利用串行算法来改造规模减半的同类计算问题而计算。可利用串行算法来改造或设计并行算法，不少数值算法包含了可直接利用的并行或设计并行算法，不少数值算法包含了可直接利用的并行性。还可以根据并行算法的特点设计具有新思想的新算法，性。还可以根据并行算法的特点设计具有新思想的新算法，它的出发点仍然是它的出发点仍然是“分而治之分而治之”的原理，符合此原理的区的原理，符合此原理的区域、算子、系统的分裂方法和技术是设计和实现并行处理域、算子、系统的分裂方法和技术是设计和实现并行处理的重要手段。的重要手段。此外，异步数值算法基本上是此外，异步数值算法基本上是混乱迭代法混乱迭代法，是并行算，是并行算法最富有特色的组成部分之一。法最富有特色的组成部分之一。