《绪论计算方法》PPT课件.ppt

第0章 绪论,运用数学方法解决科学研究或工程技术问题，一般按如下途径进行：,实际问题,模型设计,算法设计,程序设计,上机计算,问题的解,其中算法设计是计算方法课程的主要内容.,结束,1,计算方法又称数值分析、数值计算方法，是研究并解决数学问题的数值近似解方法，是在计算机上使用的解数学问题的方法。它是计算数学的重要组成部分。,0.1 数值计算方法与算法,结束,2,0.1.1 计算方法的任务 计算方法课程研究常见的基本数学问题的数值解法.包含了数值代数(线性方程组的解法、非线性方程的解法、矩阵求逆、矩阵特征值计算等)、数值逼近、数值微分与数值积分、常微分方程及偏微分方程的数值解法等.,算法 进行科学计算，需要构造确定型数值算法，确定型算法可定义为：从给定的已知量出发，按指定的运算顺序，经过有限次的四则运算及逻辑运算，可求出给定问题的数值解的完整的计算步骤。,结束,3,0.1.2 算法的效率 算法的计算量简化为该算法所需要的乘法和除法运算的总次数。计算量越小，计算效率就越高。,0.1.3 算法的表述形式 算法的表述形式是多种多样的.1 用数学公式和文字说明描述，这种方式符合人们的理解习惯，和算法的推证相衔接，易于学习接受，但离上机应用距离较大.,2 用框图描述，这种方式描述计算过程流向清楚，易于编制程序，详略难以掌握.,3 算法描述语言，它是表述算法的一种通用语言。有特定的表述程序和语句。可以很容易地转化为某种计算机语言，同时也具有一定的可读性。,4 算法程序，即用计算机语言描述的算法，它是面对计算机的算法。我们以后讨论的算法，都有现成的程序文本和软件可资利用.但从学习算法的角度看，这种描述方式并不有利.,结束,4,0.1.4 算法的基本特点 1 算法常表现为一个无穷过程的截断：,例1 计算 sin x的值，,根据sin x 的无穷级数,(0.1),这是一个无穷级数，我们只能在适当的地方“截断”，使计算量不太大，而精度又能满足要求.,如计算 sin 0.5，取n=3,结束,5,据泰勒余项公式，它的误差应为,(0.2),可见结果是相当精确的.实际上结果的六位数字都是正确的.,2 算法常表现为一个连续过程的离散化,例2 计算积分值.,将0，1分为4等分，分别计算4个小曲边梯形的面积的近似值，然后加起来作为积分的近似值(如图1-1).记被积函数为 f(x)，即,结束,6,计算有：I0.697 024，与精确值0.693 147比较，可知结果不够精确，如进一步细分区间，精度可以提高.,迭代是指某一简单算法的多次重复，后一次使用前一次的结果.这种形式易于在计算程序中实现，在程序中表现为“循环”过程.,例3 多项式求值.,结束,7,3 算法常表现为“迭代”形式.,用tk表示xk，uk表示(0.3)式前k+1项之和.作为初值令：(0.4),(0.3),对k=1,2,n，反复执行：(0.5),显然Pn(x)=un，而(0.5)式是一种简单算法的多次循环.,令 k=1,2,n(0.6),结束,对此问题还有一种更好的迭代算法.,8,这两种算法都是将n次多项式化为n个一次多项式来计算，这种化繁为简的方法在数值分析中经常使用.,下面估计一下以上两种算法的计算量：第一法：执行n次(0.5)式，每次2次乘法，一次加法，共计2n次乘法，n次加法；,第二法：执行n次(0.6)式，每次1次乘法，一次加法，共计n次乘法，n次加法.,显然第二种方法运算量小，它是我国宋代数学家秦九韶最先提出的，被称为“秦九韶算法”.,结束,9,显然Pn(x)=vn.,0.2.1 误差的来源,1 模型误差(原始误差)在建立数学模型时，往往要忽视很多次要因素，把模型“简单化”，“理想化”，这时模型就与真实背景有了差距，即带入了误差.,2 测量误差 数学模型中的已知参数，多数是通过测量得到.而测量过程受工具、方法、观察者的主观因素、不可预料的随机干扰等影响必然带入误差.,结束,10,0.2 误差与有效数字,在运用数学方法解决实际问题的过程中，每一步都可能带来误差.,误差分析是一门比较艰深的专门学科.在数值分析中主要讨论截断误差及舍入误差.但一个训练有素的计算工作者，当发现计算结果与实际不符时，应当能诊断出误差的来源，并采取相应的措施加以改进，直至建议对模型进行修改.,结束,11,4 舍入误差 计算机只能处理有限数位的小数运算，初始参数或中间结果都必须进行四舍五入运算，这必然产生舍入误差.,3 截断误差 数学模型常难于直接求解，往往要近似替代，简化为易于求解的问题，这种简化带入误差称为方法误差或截断误差.,定义0.1 设x*是准确值，x是它的一个近似值，称e=x-x*为近似值x的绝对误差，简称误差.即：,误差一般无法准确计算，只能根据测量或计算情况估计出它的绝对值的一个上限，这个上界称为近似值x的误差限，记为,|e|=x-x*，其意义是：x-x*x+在工程中常记为：x*=x.,如 l=10.20.05mm，R=1500100,结束,12,0.2.2 绝对误差与绝对误差限,误差是有量纲的量，量纲同x，它可正可负.,绝对误差e=精确值x*-近似值x,绝对误差不能完全刻画近似值的精度.如测量百米跑道产生10cm的误差与测量一个课桌长度产生1cm的误差，我们不能简单地认为后者更精确，还应考虑被测值的大小.下面给出定义：,0.2.3 相对误差与相对误差限,定义 0.2 误差与精确值的比值 称为x的相对误差，记作er.,相对误差是无量纲的量，常用百分比表示，它也可正可负.相对误差也常不能准确计算，而是用相对误差限来估计.,相对误差限：,实际上由于x*不知道，用上式无法确定r，常用x代x*作分母，此时：,结束,14,以后我们就用 表示相对误差限.,例4 在刚才测量的例子中，若测得跑道长为1000.1m，课桌长为1201cm，则,定义 0.3,结束,15,0.2.4 有效数字,显然后者比前者相对误差大.,定义 0.4,结束,16,如：=3.14159265 则3.14和3.1416分别有3位和5位有效数字.而3.143相对于也只能有3位有效数字,如a=0.034537，则近似数0.0345有3位有效数字又如近似数c=30.4和d=30.40分别有3位和4位有效数字,如计算机上得到方程x3-x-1=0的一个正根为1.32472，保留4位有效数字的结果为1.325，保留5位有效数字的结果为1.3247.相对误差与有效数位的关系十分密切.定性地讲，相对误差越小，有效数位越多，反之亦正确.,结束,17,0.3 设计算法时应注意的原则,当参与运算的数值带有误差时，结果也必然带有误差，问题是结果的误差与原始误差相比是否扩大.,1)对函数f(x)的计算:设x是x*的近似值，则结果误差,用泰勒展式分析,忽略第二项高阶无穷小之后，可得函数f(x)的误差限估计式,结束,18,0.3.1数值运算时误差的传播,2）四则运算中误差的传播:,其中(0.7)取等号,是因为作为多元函数,加减法的一次函数，泰勒展开没有二次余项。,结束,例6：若电压V=220 5V，电阻R=300 10，求电流I并计算其误差限及相对误差限。解：,19,所以,结束,1）避免相近数相减 由公式(0.7),20,0.3.2 算法中应避免的问题,当x1和x2十分相近时，x1-x2接近零，,结束,将很大，所以,和,从直观上看，相近数相减会造成有效数位的减少，有时，通过改变算法可以避免相近数相减.,大很多，即相对误差将显著扩大.,将比,例7:解方程x 2-18 x+1=0，假定用4位浮点计算.解:用公式解法,可见第二个根只有两位有效数字,精度较差.若第二个根改为用韦达定理计算,可得较好结果。,21,结束,如,等等,都可以得到比直接计算好的结果。,可改为,如,可改为,若,则,这时,将比,扩大很多。,3)防止小数被大数“吃掉”在大量数据的累加运算中，由于加法必须进行对位，有可能出现小数被大数“吃掉”.,22,2)避免除法中除数的数量级远小于被除数 由公式(1.13),结束,如用六位浮点数计算某市的工业总产值，原始数据是各企业的工业产值，当加法进行到一定程度，部分和超过100亿元（0.11011），再加产值不足10万元的小企业产值，将再也加不进去.而这部分企业可能为数不少，合计产值相当大.这种情况应将小数先分别加成大数，然后相加，结果才比较正确.这个例子告诉我们，在计算机数系中，加法的交换律和结合律可能不成立，这是在大规模数据处理时应注意的问题.,23,4)注意运算步骤的简化减少算术运算的次数以减少误差的积累效应：时参加运算的数字精度应尽量保持一致，否则那些较高精度的量的精度没有太大意义。,24,结束,0.4 范数,内积定义：设两个n维向量,令,称x,y为向量x与y的内积。它是向量的一种运算。,向量x与y都是列向量时，内积也可写成：x,y=xTy,范数是在广义长度意义下，对函数、向量、矩阵等元素“长度”的度量定义。,结束,25,定义1 x和y是Rn中的任意向量，向量范数是定义在Rn上的实值函数,它满足:,容易看出，实数的绝对值，复数的模，三维向量的模都满足以上三条，n维向量的范数概念是它们的自然推广.,设向量x=(x1,x2,xn)T,(1)x 0，并且，当且仅当x=0时,x=0;（非负性）,(2)k x=|k|x，k是一个实数;（齐次性）,0.4.1 向量范数,(3)x+y x+y，（三角不等式）,1）向量范数定义,其中,经常使用的三种范数为,称为向量X的Lp范数.,容易验证,它们都满足三个条件.例8 x=(1,0.5,0,-0.3)T,求解:,结束,27,2)不同向量范数的关系,在Rn空间上的任意向量范数等价.即对任意给定的两种范数,有下列关系:m M 其中的m,M是正的常数,表示向量或矩阵的范数.,或,3)向量的极限,定义 如果 称向量序列x(k)收敛于向量x.,定理 向量序列x(k)收敛于向量x的充要条件是:,例9 求向量序列x(k)量的极限向量x.,解:,结束,29,从向量范数出发,可以定义矩阵的范数.定义 设A是nn矩阵,定义,0.4.2 矩阵范数,为矩阵A的范数.这样定义的范数有如下性质:,(1)A0,当且仅当A是零矩阵时,A=0（非负性）(2)kA=|k|A（齐次性）,1）矩阵范数定义,结束,30,(3)两个同阶方阵A,B,有A+BA+B(三角不等式)(4)A,B都是nn矩阵,有ABAB(5)A是nn矩阵,x是n维向量,有AxAx(相容性),（1 是ATA的最大特征值）,列范数,2-范数(谱),行范数,2）常用矩阵范数,与向量范数的等价性质类似，矩阵范数之间也是等价的.,结束,31,当向量或矩阵的任一种范数趋于零时，其它各种范数也趋于零。因此讨论向量和矩阵序列的收敛性时，可不指明使用的何种范数；证明时，也只要就某一种范数证明就行了.,还有一种范数：F范数,它是向量2-范数的直接推广,结束,32,定义 设n阶方阵A的特征值为j(j=1,2,n),则称为A的谱半径.,0.4.3 谱半径,证:设i是A的任一特征值,xi为对应的特征向量 Axi=ixi两边取范数,用矩阵范数性质(5)有|i|x iAx i 因为 x i 0,所以x i0所以|i|A i=1,2,n,所以(A)=max|i|A.,定理 方阵谱半径和方阵范数有如下关系:,结束,例,求A1,A2,A,AF，(A).,33,解:显然A1=4,A=4,结束,这里，我们指出，对于实对称矩阵A，有,34,