0方法绪论(精品)

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,绪论,计算方法,一、计算方法的研究内容,计算方法，又称为数值计算，是现代数学的重要分支。然而它又是一门古典的数学分支，主要用于近似计算求近似值。如：,实际上，以前的简单数学用表如平方表、开方表，三角函数表，以及现在计算机中的函数计算、所有程序中的基本函数的计算，都是用此方法（包括计算器）。,求,e,x,的近似值。,求函数的近似值,：,对任意的,x,e,x,的计算相当困难，因此常用：,2.求方程近似解,迭代法：将上述方程化为等价形式：,可以某一较大的,k,对应的,x,k,作为方程根的近似值，显然当,k,时，,x,k,1,为准确根。三次，四次方程的求解可类似设计算法求解。,求准确解较难，可设计算法，求近似解。,计算方法的研究内容（续1）,3.求微分近似值,进而可求微分方程近似解,求积分近似值等。,4.节省计算量，提高计算速度:,如要计算多项式：,若先算各项然后相加，需做十次乘法运算和四次加法运算。,则只需做四次乘法和四次加法（节省计算量问题后面还会谈到）。,计算方法的研究内容（续2）,关于节省计算量，提高计算速度，一般情况下，设：,若要计算,p,(,x,)|,x=,，,可用如下的递推公式计算：,这实际上是秦九韶算法，我国古代,祖冲之，秦九韶（宋代），杨辉,等在计算方面都作出了相当大的贡献，国外称此算法为,Hornor,算法,，比,秦九韵算法,至少晚五个世纪，秦九韶是四川安岳县人，2000年8月报道在安岳为他塑像建馆。,计算方法的研究内容（续3）,计算方法,的发展及重要性,随着科学技术的发展，提出了大量复杂的数值计算问题，在实际解决这些计算问题的长期过程中，形成了计算方法这门学科，专门研究各种数学问题的数值解法（近似解法），包括方法的构造和求解过程的误差分析，是一门内容丰富，有自身理论体系的实用性很强的学科。,在生产和科学研究中遇到的大量复杂计算问题不是人工手算（如以前的算盘，计算尺及计算器等简单的计算工具）所能胜任的，如求解由几十个方程构成的线性方程组等。,上述几个简单的数学问题要得到精确解是很困难甚至是不可能的，很多类似的问题都只能利用计算方法求其近似解，近似解与精确解之间的差称为误差，误差在一定范围内近似解有效，超过此范围近似解就失去了意义。,计算方法,的发展及重要性（续1）,1946年,第一台计算机的诞生，是计算数学史以至人类文明史的一个里程碑，它使人类获得了高速度，自动化的计算工具。随着计算机性能的不断提高，极大地促进了计算方法这门学科在理论和应用上的快速发展，我们都知道计算机只能做加减乘除四则运算，而计算方法中的各种算法都可直接用于计算机编程作数值计算。因此近年来人们越来越认识到计算方法的学习与研究离不开计算机，只有与计算机相结合才能构造出好的算法，如,并行算法,等。反之，要利用计算机做科学计算，做数据处理，做定量分析，首先要掌握计算数学和计算技术。当代许多实践证明，计算方法正在日趋明显地成为数学与计算机科学的交叉性学科，是,Compuiting,学科,的九大主干课之一，,其方法和技术已渗透到自然科学和社会科学的各个领域中，研究工作和工程设计更加离不开数值计算，它将许多领域的科学研究工作由定性阶段迅速推向定量阶段，科学计算方法实际上已发展成为与科学理论，科学实验相并的第三种科学方法。,随着科学技术的不断发展和计算方法的广泛应用，掌握好计算方法的基本理论和方法对计算机使用者来说是非常必要的。只有掌握好了各类数学问题的数值计算方法，才能更好地使用计算机，才能更有效地解决实践中各种科学计算问题，今天的计算方法就是,研究能在计算机上使用的，各种数学问题的数值计算方法及相关理论，主要为计算机的计算服务，是程序设计的工具,。,计算方法,的发展及重要性（续2）,二、,数值,计算的任务,将计算机不能直接计算的运算，化成能在计算机上执行,的运算。,这是一个连续变量问题，必须通过离散化方法，将定积分离散成求运算和（将微分方程离散成差分方程），采用如下的复化梯形求积分式计算：,如计算定积分：,数值,计算的任务（续1）,计算机上不能直接执行的运算较多，常见的开方运算超越函数运算，极限，微分，积分等运算都不能直接在计算机上运算，必须将它们化成能在计算机上执行的等价运算或近似等价运算，例如前面曾提到的指数函数,e,x,的运算，可以化为近似计算（有限运算去近似无限过程）等等。,微分运算,y,(,x,)，,可以,化为近似运算：,把一个连续型问题运用离散化方法将其化为一个离散型问题，在计算方法中对处理连续型问题是很关键的一步。离散化也是计算方法中基本的概念与方法之一。,2.针对数值问题研究可在计算机上执行且行之有效的算法,例如要求解线性方程组：,虽然在线性代数中已作了较多的研究，但是由于没有考虑以计算机为工具进行计算的特点，即近似计算和计算复杂性和可执行性等，因而可能会出现线性代数中介绍的方法不能直接应用或在实际计算中出现一些意想不到的问题等。比如若用线性代数中介绍的,克莱姆（,Crammer,）,法则,求解上述线性方程组：,数值计算的任务（续2）,由于每个行列式包含,n,!,乘积，而计算每个乘积需做,n,-1,次乘法，因此,Crammer,法则,的乘除法次数为,A,n,=(,n,+1),n,!(,n,-1)+,n,。,要完成这么多次乘除法，即使是用国产大型,银河,I,型,计算机，计算速度为,1亿次/每秒,，也需,30万年,！现在已有,银河,II,型机。10亿次/每秒,，那么也需,3万年,，可见,Crammer,法则因计算量太大而在计算机上不适此例说明构造一个好的算法是多么重要，同时也说明节省计算量的重要性，因此，必须研究以计算机为工具解线性方程组的新数值方法。,数值,计算的任务（续3）,而,D,k,是将,D,中第,k,列(,a,1,k,，,a,2,k,a,nk,),T,换为方程组右端项（,b,1,b,2,b,n,）,T,后得到的行列式。按,Crammer,法则,，首先要计算上述,n,+1,个行列式。然后再做,n,次除法。,3.进行误差分析，即用研究数值问题的性态和稳定性,由于数值方法是解数值问题的系列计算公式，所以数值方法是否有效，不但与方法本身的好坏有关，而且与数值问题本身的好坏也有关，因此，研究数值方法时，不但需要研究数值方法的好坏，即数值稳定性问题，而且还需要研究数值问题本身的好坏，即数值问题的性态，以及它们的判别问题，由于这两个问题是计算方法中偏于理论的问题，不重点研究，只作概念性介绍。,数值计算的任务（续4）,三、的特点,数值计算,的一个明显,特点,是与计算机的使用密切结合，具有实际试验的高度技术性，因此除注意学习基本理论知识外，必须注意程序编制和上机计算等环节的学习与实践。,数值计算,的绝大部分方法都具有近似性，而其理论又具有严密的科学性，方法的近似值正是建立在理论的严密性基础上，根据计算方法的这一,特点,。因此不仅要求掌握和使用算法，还要重视必要的误差分析，以保证计算结果的可靠性。,计算方法的特点（续）,数值计算,还具有应用性强的,特点,，计算方法的绝大部分方法如求微分方程近似解，求积分近似值，求解超越方程，解线性方程组等都具有较强的实用性，而插值法，最小二乘法，样条函数等也都是工程技术领域中常用的，有实际应用价值的方法。,数值计算,的另一,特点,是内容多而杂，涉及到的数学公式多，得到的算法也都是由一组公式表示，而要记住这些公式比较难，手算是为了熟悉计算公式，手算的例题虽然都较为简单，但是它的计算过程和步骤与计算机按程序计算的过程和步骤一样，因此，虽然强调程序设计的重要性却难以具体介绍各公式所对应的程序的设计而要求手算完成各种算法的练习。,数值计算,还具有应用性强的特点,插值用于数码相机增加图像的分辩率：,如果要将一幅数码图像放大，也就是使,其具有更多的像素，而多出来的像素原本,是不存在的,需要根据周围像素的色值计算,出来，这个计算的过程即为,插值,。,插值方法的最新应用：,像素越高，可以冲印的照片尺寸越大，,四、算法设计,用计算机进行数值计算的核心是算法设计，算法是对解题方案的准确描述，通常是指有步骤地完成数值问题的过程，且应具备以下,四个特性,：,目的性：,有明确的目的，给出输入输出的明确规定,与要求；,2.确定性：,必须准确给出每一步的操作（不一定是运算）,定义，不允许有岐义；,3.可执行性：,算法中的每个操作都是可执行的；,4.有穷性：,算法必须在有限步内能够结束解题过程因此，,算法不仅包含着解题的数值方法，并且还包含,着解题的思想，步骤，目的及数据的输入与输,出要求。,算法设计（续）,算法设计的,主要目的,是：,1.选择或研制计算精度高的数值方法，即可,靠性好的数值方法；,2.尽可能提高数值方法的计算速度和少占存,贮空间，即计算复杂性好；,3.为程序设计做好准备等。,遵循上述原则可以防止误差积累，防止误差危害,的发生。,4.具有较好的数值稳定性，这可以控制误差的传,播，给出可靠的计算结果.,算法设计举例,以求解二次方程,ax,2,+,bx,+c=,0,为例，进行算法设计介绍。,首先应选择或设计算法，求解二次方程的数值方法主要有两种，直接法（求根公式）和迭代法（后面将介绍），这里选用较熟悉的求根公式。,数值方法选定后应考虑数值方法中求解公式的细节，对求根公式应考虑：,(,1).当,d,=,b,2,4,ac,大于零或小于零时，应选用不同的公式；,(2).当,d,0,且 时会出现两个近似数相减而影响有效数字的位数问题。,在算法设计中尽可能地考虑好这些细节问题的处理方法，才能设计出行之有效地的算法。,(,3).若|,a|,较|,b,|,和|,c|,相对小很多时可能会出现舍入误差增大的 问题。,三种算法结构,而在计算机上可执行的计算机程序则是由算法及基本语法规则构成。,1）按顺序执行操作的顺序结构；,2）带逻辑判断条件，当条件成立则执行某些操作，当条 件不成立则执行另外一些操作的分枝结构；,3）循环结构带控制条件，当条件成立时重复执行循环体 内操体，条件不成立时退出循环体。,一个解决实际问题的算法往往是由计算机可执行的基本操作（加、减，乘，除、判断，置数以及调用内部函数等）按照顺序，分枝，循环这三种基本结构组成。,算法描述可以用自然语言及框图二种形式，本课程选用自然语言描述算法。,五、为什么要学数值计算方法,1.,前面提到的重要性：计算方法作为应用计算机,解决各种计算问题的基础；,2.,后续课程中以及论文和许多实际问题中有不少,计算问题需解决；,3.,因为计算方法的重要性以及为避免编程的麻烦，,目前有大量 的计算程序和软件可以直接使用，,但是：,（1）学过计算方法基本理论和方法与没有学过，在认识和处理具体的问题时会有很大差异，懂基本方法和基本理论才能做到心中有数，会分析计算结果；,为什么要学数值计算方法（续）,（4）更重要的是结合实际问题，设计专用算法。,（2）仅仅会使用现成的程序和软件是远远不够的，一旦出现问题则难以解决；,（3）通常需要结合各种问题的具体需求而对程序和软件作修改，达到灵活应用的目的。,六、数值计算的若干原则,因为几乎每一步运算都有误差，而实际问,题 往往需要进行千百万次计算，所以每步运算,即分 析误差几乎是不可能的。也是不必要的，,例如，运算过程中产生的误差有时会累积起来，,有时又会相互抵消，而任何数值方法只有运用它,在计算机上很快算出可靠结果时，才能显示出,它的实用价值，评价一个数值方法的好坏，应考,虑以下,几点原则,：,误差分析是计算方法中一个既重要复杂的问题。,数值计算的若干原则（续）,遵循上述原则可以防止误差积累，防止误差危害的发生。,1.,计算量小，这不仅会使计算速度快而且能减小误差积累；,2.,计算过程简单，有规律，便于编程；,3.,需要存贮的原始数据及需要记录的中间结果较少，这样可以少占用计算机的存贮单元和工作单元；,4.,具有较好的数值稳定性，这可以控制误差的传播，给出 可靠的计算结果。,绪