数值分析绪论.pptx

《数值分析绪论.pptx》由会员分享，可在线阅读，更多相关《数值分析绪论.pptx（76页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、应用问题举例应用问题举例第1页/共76页今有上禾三秉，中禾二秉，下禾一秉，实三十九斗；上禾二秉，中禾三秉，下禾一秉，实三十四斗；上禾一秉，中禾二秉，下禾三秉，实二十六斗。问上、中、下禾实一秉各几何？答曰：上禾一秉九斗四分斗之一。中禾一秉四斗四分斗之一。下禾一秉二斗四分斗之三。-九章算术1、一个两千年前的例子第2页/共76页第3页/共76页2 2、天体力学中的、天体力学中的KeplerKepler方程方程x是行星运动的轨道，它是时间t 的函数.第4页/共76页全球定位系统：全球定位系统：在地球的任何在地球的任何一个位置，至一个位置，至少可以同时收少可以同时收到到4 4颗以上卫星颗以上卫星发射的信

2、号发射的信号 3、全球定位系统（全球定位系统（Global Positioning System,Global Positioning System,GPS)GPS)第5页/共76页 表示地球上一个接收点R的当前位置，卫星Si的位置为 ，则得到下列非线性方程组第6页/共76页记为其中，第7页/共76页4 4、已经测得在某处海洋不同深度处的水温如下：、已经测得在某处海洋不同深度处的水温如下：深度（深度（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

3、2.54 2.13根据这些数据，希望合理地估计出其它深度（如根据这些数据，希望合理地估计出其它深度（如500500米，米，600600米，米，10001000米米）处的水温）处的水温第8页/共76页5 5、用比较简单的函数代替复杂的函数、用比较简单的函数代替复杂的函数误差为最小，即距离为最小（在不同的度量意义下）第9页/共76页6 6、人口预测、人口预测 下面给出的是中国下面给出的是中国19001900年到年到20002000年的人口数，年的人口数，我们的目标是预测未来我们的目标是预测未来的人口数（数据量较大的人口数（数据量较大时）时）19505519619606620719708299219

4、809870519901143332000126743第10页/共76页第11页/共76页7 7、铝制波纹瓦的长度问题、铝制波纹瓦的长度问题 建筑上用的一种铝制波纹瓦是用一种机器将一块平整的铝板压制而成的.假若要求波纹瓦长4英尺,每个波纹的高度(从中心线)为1英寸,且每个波纹以近似2英寸为一个周期.求制做一块波纹瓦所需铝板的长度L.第12页/共76页 这个问题就是要求由函数这个问题就是要求由函数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.由微积分学我们知

5、道由微积分学我们知道,所求的弧长可表示为所求的弧长可表示为:上述积分称为第二类椭圆积分,它不能用普通方法来计算.第13页/共76页数值计算方法的意义、内容与方法数值计算方法的意义、内容与方法软件的核心就是算法。软件的核心就是算法。20 20 世纪最伟大的科学技术发明世纪最伟大的科学技术发明-计算机计算机 计算机是对人脑的模拟，它强化了人的思维智能；计算机是对人脑的模拟，它强化了人的思维智能；计算机的发展和应用，已不仅仅是一种科学技术计算机的发展和应用，已不仅仅是一种科学技术现象，而且成了一种政治、军事、经济和社会现象；现象，而且成了一种政治、军事、经济和社会现象；没有软件的支持，超级计算机只是

6、一堆废铁而已；没有软件的支持，超级计算机只是一堆废铁而已；算法犹如乐谱，算法犹如乐谱，软件犹如软件犹如CDCD盘片，盘片，而硬件如同而硬件如同CDCD唱机。唱机。第14页/共76页理论研究科学实验科学计算计算数学诺贝尔奖得主,计算物理学家 Wilson提出 现代科学研究的三大支柱第15页/共76页2121世纪信息社会的两个主要特征：世纪信息社会的两个主要特征：“计算机无处不在计算机无处不在”“数学无处不在数学无处不在”2121世纪信息社会对科技人才的要求：世纪信息社会对科技人才的要求：-会用数学解决实际问题会用数学解决实际问题-会用计算机进行科学计算会用计算机进行科学计算第16页/共76页 科

7、学方法论的巨大变革：如果说伽利略和牛顿在科学发展史上奠定了实验和理论这两大科学方法的支柱，那么由冯.诺依曼研制的现代电子计算机把计算推上了人类科学活动的前沿，使计算成为第三种方法。山山东东科科技技大大学学 信信 息息 学学 院院第17页/共76页建立数学模型选取计算方法编写上机程序计算得出结果科学计算解题过程第18页/共76页数值计算方法是计算数学的一个主要组成部分，“什么是数值计算方法？”山山东东科科技技大大学学 信信 息息 学学 院院它主要研究使用计算机求解各种科学与工程计算问题的数值方法（近似方法）;对求得的解的精度进行评估以及在计算机上实现求解等。数值计算方法已经成为计算机处理实际问题

8、的一个重要手段，从宏观天体运动学到微观分子细胞学，从工程系统到社会经济系统，无一能离开数值计算方法。因此，数值计算与计算机模拟被称为“第三种研究科学方法”。第19页/共76页科学计算科学计算可视化是可视化是目前研究目前研究的热门问的热门问题，下面题，下面的艺术图的艺术图形是基于形是基于科学计算科学计算的数据表的数据表示的例子示的例子山山东东科科技技大大学学 信信 息息 学学 院院第20页/共76页分形图混沌图山山东东科科技技大大学学 信信 息息 学学 院院第21页/共76页一、计算数学的产生和早期发展计算数学是数学的一个古老的分支，虽然数学不仅仅是计算，但推动数学产生和发展的最直接原因还是计算

9、问题计算问题。二、二十世纪计算数学的发展数值代数 最优化计算 数值逼近 计算几何 概率统计计算 蒙特卡罗方法 微分方程的数值解法 微分方程的反演问题 第22页/共76页传统的数值计算的主要研究内容：1、数值逼近 插值与拟合、FFT、数值积分与微分2、数值代数 代数基础、线性代数方程组的解法、非线性代数方程（组）的解法、特征值与特征向量3、微分方程数值解 ODE、PDE和有限元法4、最优化方法 无约束优化与有约束优化方法 现代计算方法：融进了机器学习计算、仿生计算、网络计算、以数据为核心的计算和各种普适计算、非线性科学计算等内容。山山东东科科技技大大学学 信信 息息 学学 院院第23页/共76页

10、数值计算方法的主要特点借助计算机提供切实可行的数学算法.想的精确度;收敛且稳定;误差可以分析或估计.所提出的算法必须具有：可靠的理论分析;理时间复杂性好_指节省时间；空间复杂性好_指节省存储量。计算复杂性好 通过数值实验证明算法行之有效.山山东东科科技技大大学学 信信 息息 学学 院院第24页/共76页F采用“近似替代”方法逼近F采用“构造性”方法F采用“离散化”方法 把求连续变量的问题转化为求离散变量的问题F采用“递推化”方法 复杂的计算归结为简单过程的多次重复，易于用循环结构来实现（迭代法）。F采用各种搜索方法构造数值算法主要手段山山东东科科技技大大学学 信信 息息 学学 院院第25页/共

11、76页如何学好数值计算方法？山山东东科科技技大大学学 信信 息息 学学 院院第26页/共76页 希 望：求近似解，但方法简单可行，行之有效（计算量小，误差小,需存储单元少等）,以计算机为工具，易在计算机上实现。计算机运算:只能进行加，减，乘，除等算术运算和一 些逻辑运算。数值计算方法：把求解数学问题转化为按一定次序只进行 加，减，乘，除等基本运算.设计数值算法的出发点？山山东东科科技技大大学学 信信 息息 学学 院院第27页/共76页威尔金森（James Hardy.Wilkinson，1919-1986）Wilkinson是数值分析和数值计算的开拓者和奠基人。1940 年，开始研究弹道的数学

12、模型与数值计算。1946 年成为Turing 的助手，协助设计 Pilot ACE 计算机。1969年他当选为英国皇家学会院士；1970年工业和应用数学会(s1am)授予他冯诺伊曼奖；1987年他获得美国数学会的chauvenet奖。著名的美国阿尔贡国家实验室曾聘威尔金森为荣誉高级研究员并两次向他授奖。Wilkinson在数值分析研究领域作出了杰出贡献，是数值计算的早期开拓者，其工作加速了数字计算机(在科学计算中)的使用。他研究的主要问题是线性代数方程组和矩阵特征值问题的数值解法，特别是他的向后误差分析法(backward error analysis)的创造性工作奠定了数值分析和数值计算早期

13、的理论基础。1975 年 J.H.Wilkinson成为第五位图灵奖获得者。第28页/共76页&教材 现代科学与工程计算 孟大志 刘伟（高等教育出版社）&参考书目 数值分析 孙志忠 袁慰平等（东南大学出版社,第二版）应用数值方法 使用MATLAB和C语言 Robert J.Schilling&Sandra L.Harris （机械工业出版社）数值分析基础教程 李庆扬 编（高等教育出版社）现代数值分析 李庆扬、易大义、王能超 编著 （高等教育出版社）数值分析与科学计算 Jeffery J.Leader 著，张威，刘志军，李艳红等译，（清华大学出版社)第29页/共76页2 算 法一、算法的概念 描

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

15、-a12a21D=0开始输出 x1,x2 结 束 No输出无解信息Yes第33页/共76页二、算法优劣的判别 计算量的大小 存贮量 逻辑结构例：用行列式解法求解线性方程组:n阶方程组，要计算n+1个n阶行列式的值，总共需要做n!(n-1)(n+1)次乘法运算。n=20 需要运算多少次？n=100?第34页/共76页一、误差的来源与分类 从实际问题中抽象出数学模型 模型误差例:质量为m的物体，在重力作用下,自由下落，其下落距离s 与时间t 的关系是：其中 g 为重力加速度。3 误 差第35页/共76页 通过测量得到模型中参数的值 观测误差 求近似解 方法误差(截断误差）例如，当函数 用Taylo

16、r多项式 近似代替时，数值方法的截断误差是 与0之间。在第36页/共76页机器字长有限 舍入误差 用计算机、计算器和笔算，都只能用有限位=3.1415926 小数来代替无穷小数或用位数较少的小数来代替位数较多的有限小数，如：第37页/共76页四舍五入后在数值计算方法中，主要研究截断误差截断误差和舍入误差舍入误差（包括初始数据的误差）对计算结果的影响！第38页/共76页二、误差的概念1、绝对误差与绝对误差限例:若用以厘米为最小刻度的尺去量桌子的长，大约为1.45米，求1.45米的绝对误差。1.45米的绝对误差=？不知道！是近似值 的绝对误差绝对误差,简称为误差误差。定义：设 是准确值，为 的一个

17、近似值，称 第39页/共76页但实际问题往往可以估计出但实际问题往往可以估计出 不超过某个正数不超过某个正数 ，即即 ，则称，则称 为绝对误差限，有了为绝对误差限，有了绝对误差限绝对误差限就可以知道就可以知道 的范围为的范围为即即 落在落在 内。内。在应用上，常常采用下列写法来刻划在应用上，常常采用下列写法来刻划 的精度。的精度。第40页/共76页2、相对误差与相对误差限定义：设 是准确值，是近似值，是近似值的误差，通常取为近似值 的相对误差相对误差，记作 ，称 一般情况下是不知道一般情况下是不知道 的，怎么办？的，怎么办？第41页/共76页事实上，当 较小时是 的二次方项级,故可忽略不计.相

18、应地，若正数满足 则称 为 的相对误差限。第42页/共76页3、有效数字定义：如果则说 近似表示 准确到小数后第 位，并从这由上述定义第 位起直到最左边的非零数字之间的一切数字都称为有效数字有效数字，并把有效数字的位数称为有效位数有效位数。第43页/共76页定义:若近似值 的误差限是某一位的半个单位,也即，若有 位有效数字。则称则称其中，是1到9中的一个数字；是0到9中一个数字；为整数，且 该位到 的左边第一位非零数字共有 位,就说 有 位有效数字。第44页/共76页取 作 的近似值，就有三位有效数字；取 作 的近似值，就有五位有效数字。例如：注：注：若一近似数是由原真值经四舍五入得到，若一近

19、似数是由原真值经四舍五入得到，则必为有效数则必为有效数.第45页/共76页4、误差限与有效数字的关系 则 至少具有 位有效数字。Th1.1：对于用 式表示的近似数 ，若 具有 位有效数字，则其相对误差限为反之，若 的相对误差限为第46页/共76页Th1.2：设反之,若 的相对误差的绝对值大于 ，其中 为整数,为正整数,。有 位有效数字。则 至多若 至多有 位有效数字,即 是有效数字,而 不是有效数字,则 的相对误差的绝对值必大于 ;第47页/共76页证明：不是有效数字 反之,若 则 不是有效数字，即 至多有 位有效数字.第48页/共76页4 数值运算的误差估计一一、四则运算的误差估计四则运算的

20、误差估计两个近似数两个近似数 与与 ,其误差限分别为其误差限分别为 及及 ,它们进行加减乘除运算得到的误差限分别为它们进行加减乘除运算得到的误差限分别为第49页/共76页二二、函数误差估计函数误差估计当自变量有误差时，计算函数值也会产生误差，其误差限可利用函数的Taylor展开式进行估计。设 是一元函数，的近似值为 ,以 近似 ，其误差限记作 ，可用Taylor展开 介于介于之间之间.取绝对值得取绝对值得第50页/共76页假定 与 的比值不太大,可忽略 的高阶项,于是可得计算函数的误差为 当 为多元函数时计算 ,如果的近似值为 ,则 的近似为于是函数值 的误差 由Taylor展开,得：得：第5

21、1页/共76页于是误差限为于是误差限为而而 的相对误差限为的相对误差限为(1.3.1)(1.3.1)(1.3.2)(1.3.2)第52页/共76页例例:已测得某场地长已测得某场地长 的值为的值为 ,宽宽 的值为的值为 ,已知已知 ,.试求试求面积面积 的绝对误差限与相对误差限的绝对误差限与相对误差限.解解:因因 其中其中由式由式(1.3.1)(1.3.1)得得第53页/共76页而而于是绝对误差限为于是绝对误差限为相对误差限为相对误差限为第54页/共76页5 算法的数值稳定性 数值计算在设计算法时首先关心的是由它产生的计算结果的稳定性，而算法的稳定性与舍入误差是否增长密切相关。一个算法如果输入数

22、据有微小扰动（即误差），而在计算过程中舍入误差不增长，则称此算法是数值稳定的，否则称其为数值不稳定。第55页/共76页例：求定积分 的值的值.解：直接积分可产生递推公式若取初值第56页/共76页可得递推公式按公式就可以逐步算出注意此公式精确成立，且What happened?!不稳定的算法！这就是误差传播所引起的危害这就是误差传播所引起的危害 !第57页/共76页NYBJ蝴蝶效应 纽约的一只蝴蝶翅膀一拍，风和日丽的北京就刮起台风来了？！这是一个病态问题第58页/共76页由题设中的递推公式（1）可看出，的误差扩大了5倍后传给 ，因而初值 的误差对以后各步这就造成 的计算结果严重失真。计算结果的影

23、响，随着 的增大愈来愈严重。要怎么做才能解决这个问要怎么做才能解决这个问题呢题呢?第59页/共76页可求得I9 0.017，按改写后的公式可逐次求得不妨设I9 I10，于是由将公式变为第60页/共76页I8 0.019 I7 0.021I6 0.024 I8 0.028I4 0.034 I3 0.043I2 0.058 I1 0.088I0 0.182 稳定的算法！在我们今后的讨论中，误差将不可回避，算法的稳定性会是一个非常重要的话题。第61页/共76页注：递推公式(1)的舍入误差以5的幂次增长进行传播，因此是数值不稳定的，而递推公式(2)的舍入误差在一定范围内以0.2的幂次进行传播，随着n的

24、增大，误差逐步减少，因此该算法是数值稳定的。因此，可以看出数值不稳定的算法是不能使用的，实际计算中对任何输入数据都是数值稳定的算法，称为无条件稳定。而对某些数据数值稳定，对其它数据数值不稳定的算法，称为条件稳定。第62页/共76页 病态问题和条件数 如果问题的输入数据有微小扰动，就会引起输出结果数据（即解）的很大扰动，称这样的问题为病态问题。相反的情形称为良态问题。对于病态的数学问题，用通常的算法求数值解都是不稳定的。病态和良态是相对的，没有严格的界限，通常用条件数大小来衡量问题的病态程度，条件数越大病态可能越严重。条件数c(x)越大，f(x)的相对误差越大，通常认为时，问题是病态的。第63页

25、/共76页1.要避免两个相近的数相减在数值计算中，两个相近的数作减法时有效数字会损失。例:求的值。当x=1000，y 的准确值为0.01580 6 数值计算中应该注意的一些原则第64页/共76页类似地(2)若将原式改写为则 y=0.01581(1)直接相减有3位有效数字！只有1位有效数字第65页/共76页2.尽量避免绝对值太小的数作分母例：如分母变为0.0011，也即分母只有0.0001的变化时结果相差这么结果相差这么大大!第66页/共76页3.避免大数吃小数精确解为 算法1：利用求根公式例：例：用单精度计算用单精度计算 的根。的根。第67页/共76页在计算机内，109存为0.11010，1存

26、为0.1101。做加法时，两加数的指数先向大指数对齐，再将浮点部分相加。即1 的指数部分须变为1010，则：1=0.0000000001 1010，取单精度时就成为：109+1=0.100000001010+0.00000000 1010=0.10000000 1010第68页/共76页算法2：先解出再利用注：注：求和时从小到大相加，可使和的误差减小。例：按从小到大、以及从大到小的顺序分别计算1+2+3+40+109第69页/共76页4.简化计算步骤，避免误差积累。一般来说，计算机处理下列运算的速度为例：多项式求值：给定的x 求下列n 次多项式的值。解：1.用一般算法，即直接求和法；2.逐项求

27、和法；3.秦九韶方法(即Hornor算法）；第70页/共76页算法的递推性计算机上使用的算法常采用递推化的形式，递推化的基本思想是把一个复杂的计算过程归结为简单过程的多次重复。这种重复在程序上表现为循环。递推化的优点是简化结构和节省计算量。第71页/共76页例：用秦九韶方法求多项式解：Ka5-KvK00.008330.00833v0=a510.041670.04v1=v0 x+a420.166670.15867v2=v1x+a330.50.46827v3=v2x+a2410.90635v4=v3x+a1510.81873v5=v4x+a0第72页/共76页约翰冯诺依曼（John von Neu

28、mann,1903-1957）美藉匈牙利人，1930年接受了普林斯顿大学客座教授的职位，西渡美国。1931年成为该校终身教授。1933年成为新成立的普林斯顿高等研究院的终身研究员。1951年至1953 年任美国数学会主席。冯诺依曼是20世纪少有的数学科学通才，在许多领域都有重要的贡献，被西方人誉为“数学奇才、计算机之父”。冯诺依曼对人类的最大贡献是对计算机科学、计算机技术和数值分析的开拓性工作。第73页/共76页并行计算 一、电子计算机的并行计算分类 传统计算机一般采用Von Neumann结构，每一时刻只有一个进程的算法，即串行算法。并行计算机每一时刻具有2个以上的进程的算法称为并行算法。并

29、行机必须包含2台以上处理机，按指令流是单个还是多个并行算法可分为两类：SIMD算法适用于单指令流多数据流系统；MIMD算法适用于多指令流多数据流系统。按照进程之间是否同步可将并行算法分为:同步算法:是指在k个进程的算法中有些进程的若干算法必须在另一些进程的某些算法之后执行；异步算法:指k个进程间有信息联系但不须同步，它只能在一个具有k台处理机的MIMD系统中实现。第74页/共76页二、并行计算的算法设计 并行算法设计的重要原则是“分而治之”。其基本思想是把问题依次划分为可以独立完成的较小问题，将规模逐次减半的二分技术是并行算法设计的一种基本技术。二分算法的设计原理是反复地将所给计算问题加工成规模减半的同类计算问题而计算。可利用串行算法来改造或设计并行算法，不少数值算法包含了可直接利用的并行性。还可以根据并行算法的特点设计具有新思想的新算法，它的出发点仍然是“分而治之”的原理，符合此原理的区域、算子、系统的分裂方法和技术是设计和实现并行处理的重要手段。此外，异步数值算法基本上是混乱迭代法，是并行算法最富有特色的组成部分之一。第75页/共76页感谢您的观看！第76页/共76页