数值分析课件

数学学院教材数值分析李庆扬、王能超、易大义（华中科技大学出版社，第四版）数值分析孙志忠、袁慰平等（东南大学出版社,第二版）数值逼近蒋尔雄、赵风光、苏仰峰（复旦大学出版社，第二版）数值分析精品课程网站：第1章绪论一、数值分析能够做什么？（应用问题举例）§1Introduction263234323923zyxzyxzyx1、一个两千年前的例子今有上禾三秉，中禾二秉，下禾一秉，实三十九斗；上禾二秉，中禾三秉，下禾一秉，实三十四斗；上禾一秉，中禾二秉，下禾三秉，实二十六斗。问上、中、下禾实一秉各几何？答曰：上禾一秉九斗四分斗之一。中禾一秉四斗四分斗之一。下禾一秉二斗四分斗之三。-------《九章算术》nnnnnnaaaaaaaaa212222111211bxAnnbbbxxx2121——这是一个线性方程组求解问题2、已经测得在某处海洋不同深度处的水温如下：深度（M）46674195014221634水温（oC）7.044.283.402.542.13根据这些数据，希望合理地估计出其它深度（如500米，600米，1000米…）处的水温——这是一个插值问题3、人口预测下面给出的是中国1900年到2000年的人口数，我们的目标是预测未来的人口数（数据量较大时）19505519619606620719708299219809870519901143332000126743432231ttty——这是一个曲线拟合问题4、铝制波纹瓦的长度问题建筑上用的一种铝制波纹瓦是用一种机器将一块平整的铝板压制而成的.假若要求波纹瓦长4英尺,每个波纹的高度(从中心线)为1英寸,且每个波纹以近似2π英寸为一个周期.求制做一块波纹瓦所需铝板的长度L.这个问题就是要求由函数f(x)=sinx给定的曲线从x=0到x=48英寸间的弧长L.由微积分学我们知道,所求的弧长可表示为:dxxdxxfL48024802')(cos1))((1上述积分称为第二类椭圆积分,它不能用普通方法来计算.——这是一个数值求积问题二、数值分析的含义、内容与特点诺贝尔奖得主,计算物理学家Wilson提出现代科学研究的三大支柱：理论研究科学实验科学计算计算数学21世纪信息社会的两个主要特征：“计算机无处不在”“数学无处不在”21世纪信息社会对科技人才的要求：--会用数学解决实际问题--会用计算机进行科学计算——计算成为第三种科学方法建立数学模型选取计算方法编写上机程序计算得出结果科学计算解题过程什么是数值分析？数值计算方法是计算数学的一个主要组成部分，它主要研究使用计算机求解各种科学与工程计算问题的数值方法（近似方法）;对求得的解的精度进行评估以及在计算机上实现求解等。数值计算方法已经成为计算机处理实际问题的一个重要手段，从宏观天体运动学到微观分子细胞学，从工程系统到社会经济系统，无一能离开数值计算方法。因此，数值计算与计算机模拟被称为“第三种研究科学方法”。传统数值分析的主要研究内容：1、数值逼近：插值、函数逼近与计算、拟合、FFT、数值积分与微分2、数值代数：方程求根、线性代数方程组的解法、非线性代数方程组的解法、特征值与特征向量3、微分方程数值解：ODE、PDE和有限元法4、最优化方法：无约束优化与有约束优化方法现代计算方法：融进了机器学习计算、仿生计算、网络计算、以数据为核心的计算和各种普适计算、非线性科学计算等内容。数值分析的主要特点：借助计算机提供切实可行的数学算法.想的精确度;收敛且稳定;误差可以分析或估计.所提出的算法必须具有：可靠的理论分析;理时间复杂性好__指节省时间；空间复杂性好__指节省存储量。计算复杂性好通过数值实验证明算法行之有效.如何学好数值分析？三、算法描述算法可以有不同的方式。例如，可以用日常语言和数学语言加以叙述，也可以借助形式语言（算法语言）给出精确的说明，也可以用框图直观地显示算法的全貌。定义：由基本运算及运算顺序的规定所构成的完整的解题步骤，称为算法。例：求解二元一次联立方程组22221211212111bxaxabxaxa用行列式解法：首先判别12212211aaaaD（1）如果，则令计算机计算0D,1222211DababxDababx2111122输出计算的结果x1，x2。（2）如果D=0，则或是无解，或有无穷多组解。是否为零，存在两种可能：12212211Daaaa令通过求解过程，可以总结出算法步骤如下：S2计算12212211DaaaaS3如果0D则输出原方程无解或有无穷多组解的信息;否则0DD1212112babaxD2121221babaxS1输入2122211211,,,,,bbaaaaS4输出计算的结果21,xx输入2122211211,,,,,bbaaaaD=a11a22-a12a21D=0开始DababxDababx/)(/)(21111221222211输出x1,x2结束No输出无解信息Yes四、算法优劣的判别计算量的大小存贮量逻辑结构例：用行列式解法求解线性方程组:n阶方程组，要计算n+1个n阶行列式的值，总共需要做n!(n-1)(n+1)次乘法运算。n=20需要运算多少次？n=100?一、误差的来源与分类从实际问题中抽象出数学模型——模型误差例:质量为m的物体，在重力作用下,自由下落，其下落距离s与时间t的关系是：mgdtsdm22其中g为重力加速度。§2误差来源与误差分析的重要性通过测量得到模型中参数的值——观测误差求近似解——方法误差(截断误差）例如，当函数用Taylor多项式fx()200001!2!!nnnfffPxfxxxn近似代替时，数值方法的截断误差是(1)1(1)!nnnnfRxfxPxxn（在与0之间）。x四舍五入后……0000074.01416.31000033.0333.0312在数值计算方法中，主要研究截断误差和舍入误差（包括初始数据的误差）对计算结果的影响！10.3333...3用计算机、计算器和笔算都只能用有限位小数来代替无穷小数或用位数较少的小数来代替位数较多的有限小数，如：机器字长有限——舍入误差二、误差分析的重要性在数值计算中不注意误差分析，用不同正确的方法可能产生不同的结果，甚至有的方法求得的结果是可行的，有的方法求得的结果是错误的。计算并估计误差。例1.1:110(0,1,)nxnIexedxn数值计算在设计算法时首先关心的是由它产生的计算结果的稳定性，而算法的稳定性与舍入误差是否增长密切相关。一个算法如果输入数据有微小扰动（即误差），而在计算过程中舍入误差不增长，则称此算法是数值稳定的，否则称其为数值不稳定。例：求定积分10(0,1,2,,8)5nnxIdxnx的值.解：直接积分可产生递推公式若取初值)2.1ln(5ln6lndx51100xI11105515(1)5nnnxIxdxIxn可得递推公式)8,,2,1(,51)2.1ln(10nInIInn按公式就可以逐步算出100150.09(0.182)III05.052112II083.053123II165.054134II025.155145II952.456156II注意此公式精确成立，且Whathappened?!不稳定的算法！这就是误差传播所引起的危害!0nINYBJ蝴蝶效应——纽约的一只蝴蝶翅膀一拍，风和日丽的北京就刮起台风来了？！这是一个病态问题由题设中的递推公式（1）可看出，的误差扩大了1nI5倍后传给，因而初值的误差对以后各步nI0I这就造成的计算结果严重失真。4I计算结果的影响，随着的增大愈来愈严重。n要怎么做才能解决这个问题呢?可求得I90.017，按改写后的公式可逐次求得不妨设I9I10，于是由10951501II)1,,1,(51511nnkIkIkknIInn151将公式变为I80.019I70.021I60.024I80.028I40.034I30.043I20.058I10.088I00.182稳定的算法！在我们今后的讨论中，误差将不可回避，算法的稳定性会是一个非常重要的话题。注：递推公式(1)的舍入误差以5的幂次增长进行传播，因此是数值不稳定的，而递推公式(2)的舍入误差在一定范围内以0.2的幂次进行传播，随着n的增大，误差逐步减少，因此该算法是数值稳定的。因此，可以看出数值不稳定的算法是不能使用的，实际计算中对任何输入数据都是数值稳定的算法，称为无条件稳定。而对某些数据数值稳定，对其它数据数值不稳定的算法，称为条件稳定。一、绝对误差与绝对误差限**()exxx例:若用以厘米为最小刻度的尺去量桌子的长，大约为1.45米，求1.45米的绝对误差。1.45米的绝对误差=？不知道！是近似值的绝对误差,简称为误差。x定义1设是准确值，为的一个近似值，称x*xx*x§3误差的基本概念****()()xxxxx**()xxx但实际问题往往可以估计出不超过某个正数，即，则称为绝对误差限。有了绝对误差限，就可以知道的范围为*ex**()xxx*()xx即落在内。在应用上，常常采用下列写法来刻划的精度。****(),()xxxxx*x*()x为近似值的相对误差，记作，通常取*()rex*x设是准确值，是近似值，是近似值的误差，称x*x*()ex**()exxxxx一般情况下是不知道的，怎么办？*****()()rexxxexxx相应地，若正数满足则称为的相对误差限。*()rx***()rxxxx*x*()rx二、相对误差与相对误差限*1112101010mnnxaaa*11102mnxx有位有效数字。n则称*x其中，是1到9中的一个数字；是0到9中一个数字；为整数，且1a2naam若近似值的误差限是某一位的半个单位,该位到的左边第一位非零数字共有位,就说有位有效数字。也即，若*x*xn*xn(*)三、有效数字取作的近似值，就有三位有效数字；*3.14x*x取作的近似值，就有五位有效数字。*3.1416x*x例如：注：（1）例1.2,1.3。（2）若一近似数是由原真值经四舍五入得到，则必为有效数。（3）若是一个位有效数字，则，这说明有效位数越多，绝对误差越小。*11102mn*xn则至少具有位有效数字。*xn定理1对于用式表示的近似数，若具有位有效数字，则其相对误差限为**xn*x1*11()102nrxa反之，若的相对误差限为*x1*11()102(1)nrxa证明：由(*)式可得:反之***()rxxxx11110210mnma11102mn111102na***()rxxxx1111(1)10102(1)mnaa即至少有位有效数字.*xn*1110(1)10mmaxa当有位有效数值时:*xn例1.4：例：用表示具有三位有效数字的近似值，则其相对误差限*2.72xe1*(31)21111()1010102224nrxa要使的近似值的相对误差限小于,要取几位有效数字?200.1%1*11()102nrxa4n得111024n0.1%四、数值运算的误差估计设是一元函数，的近似值为,以近似，其误差限记作，可