数值分析的第一章

1第一章绪论数学是研究数与形的科学。其中研究怎样利用手指、算盘、算尺、计算器、计算机等工具，来求出数学问题数值解答的学问，就是计算方法，或称计算数学。它是数学中最古老的部分，但只是在电子计算机出现以后，人们获得了高速度、自动化的计算工具，才为众多浩繁的数值问题的解决展现了光明的前景。从此，科学研究与工程设计的手段，发生了由模型试验向数值计算的巨大转变。在农业科学研究中，数值计算方法已经成为不可缺少的有力工具。我校开设数值计算方法课已有二十几年的历史，许多研究生通过学习，在毕业论文中引用了数值计算方法解决应用问题，提高了论文水平，也有许多在职教师和科研人员学习这门课程后，将数值方法引用到科研课题中，取得了较好的结果。本讲义旨在为农业院校高年级学生、研究生提供一本学习数值计算方法的入门工具。§1数值计算方法的意义、内容与方法由计算机解决科学计算问题需经历几个过程：由实际问题建立数学模型，根据数学模型提出求解的数值计算方法，编出程序，上机求出结果。通过以上过程，可以看出：数值计算方法是计算机、数学和应用科学之间的桥梁，是程序设计对数值结果进行分析的依据，是用计算机进行科学计算全过程的一个重要环节。数值计算方法的研究对象就是构造计算机能用的算法。§2算法一、算法的概念计算机实质上只会做加减乘除等基本运算。研究怎样通过计算机所执行的基本运算，求得各类问题的数值解或近似数值解，就是计算数学的根本课题。由基本运算及运算顺序的规定所构成的完整的解析步骤，称为算法．．。描述算法可以有不同的方式。例如，可以用日常语言和数学语言加以叙述，也可以借助形式语言（算法语言）给出精确的说明，也可以用框图直观地显示算法的全貌。下面举个简单的例子。例：求解二元一次联立方程组22221211212111bxaxabxaxa这个方程组的行列式解法可表述如下：首先判别12212211aaaaD是否为零，存在两种可能：（1）如果0D，则令计算机计算2Dababx1222211Dababx2111122然后输出计算的结果x1，x2。（2）如果D=0，则或是无解，或有无穷多组解，这是奇异的情形。下面用框图（也称流程图）来形象地描述上面的算法。YN框图这里我们使用了两种形式的框，一种是矩形框，称为叙述框，计算公式就填在这种框内；另一种是棱形框，称为判断框，表示算法的判断检查部分。二、算法的优劣我们知道，计算机的特点是运算速度快，存贮的信息量大，并能自动完成极其复杂的计算过程。计算机功能虽然很强，但是否可降低对算法的要求呢？许多事实说明，如果算法选开始输入2122211211,,,,,bbaaaaD=a11a22-a12a21D=0DababxDababx/)(/)(21111221222211输出x1,x2结束输出无解信息3择不当，计算机的利用率就得不到充分发挥，有时甚至不能得到满意的解答。一个好的算法，要求有以下几个优点：1．计算量小例如求解线性方程组，原则上可以用行列式解法。如解n阶方程组，要计算n+1个n阶行列式的值，总共需要做n!(n-1)(n+1)次乘法运算。设n=20，采用每秒一亿次的计算机，要连续计算三十万年才能完成。这当然是没有实际意义的。因此，计算量大小是衡量算法优劣的一项重要标准。在估计计算量时，我们将区分主次抓住计算过程中费时较多的环节。比如，由于加减操作的机器时间比乘除少得多，对和式KKbaS可以忽略加法而只统计乘法的次数。又如算式)(KKKxfaS中需要多次计算函数值)(kxf，每求一次)(kxf时，通常需要进行多次加减乘除运算，因此对算式)(KKKxfaS只要统计调用f的次数就可以了。2．存贮量小计算程序所占用的工作单元的数量称为算法的内存量。尽管计算机能贮存大量信息，但计算大型算题时有些微机仍不能使用。因此，尽量节约存贮量有经济价值，是衡量算法质量的又一标准。3．逻辑结构简单设计算法时应考虑的另一个因素是逻辑结构问题。虽然计算机能够执行极其复杂的计算方案，但是计算方案的每个细节都需要编程人员制定。因此算法的逻辑结构应尽量简单，才能使编制程度、维修程序和使用程序比较方便。由此可见，虽然计算机是一种强有力的计算工具，但不能因此忽略对算法的研究。应该以计算量大小、存贮量多少、逻辑结构是否简单作为评定算法优劣的标准。§3数值计算中的误差用数值方法解决科学研究或工程技术中的实际问题，一般来说，产生误差是不可避免的，根本不存在绝对的严格和精确。但是我们可以认识误差，从而控制误差，使之局限于最小（或尽量小）的范围内。一、误差的来源运用数学工具解决实际问题，可能产生的误差主要有以下几类。1．描述误差在将实际问题转化为数学模型的过程中，为了使数学模型尽量简单，以便于分析或计算，往往要忽略一些次要的因素，进行合理的简化。这样，实际问题与数学模型之间就产生了误差，这种误差称为描述误差。由于这类误差难于作定量分析，所以在计算方法中，总是假定所研究的数学模型是合理的，对描述误差不作深入的讨论。2．观测误差在数学模型中，一般都含有从观测（或实验）得到的数据，如温度、时间、速度、距离、电流、电压等等。但由于仪器本身的精度有限或某些偶然的客观因素会引入一定的误差，这类误差叫做观测误差。通常根据测量工具或仪器本身的精度，可以知道这类误差的上限值，所以无须在计算方法课程中作过多的研究。43．截断误差在数值计算中，常用收敛的无穷级数的前几项来代替无穷级数进行计算。如!!212nxxxenx（1.5）当x很小时，可以取（1.5）的前两项来近似代替xe的计算，即xex1（x很小时）（1.6）由泰勒定理可知，这时xxE1)(与xe的误差是)10(2)(2xxexxEe（1.7）在计算中被抛弃了，这类误差叫做截断误差。截断误差的大小，直接影响数值计算的精度，所以它是数值计算中必须十分重视的一类误差。4．舍入误差无论用计算机、计算器计算还是笔算，都只能用有限位小数来代替无穷小数或用位数较少的小数来代替位数较多的有限小数，如：=3.1415926…3333.031x=8.123456经四舍五入后取含小数点后四位数字的数来表示它们时，便有误差0000074.01416.31000033.0333.0312000044.01235.83x这类误差叫作舍入误差。当然，计算过程中，这类误差往往是有舍有入的，而且单从一次的舍入误差来看也许不算大，但数值计算中，往往要进行成千上万次四则运算，因而就会有成千上万个舍入误差产生，这些误差一经迭加或传递，对精度可能有较大的影响。所以，作数值计算时，对舍入误差应予以足够的重视。显然，上述四类误差都会影响计算结果的准确性，但描述误差和观测误差往往是计算工作者不能独立解决的，是需要与各有关学科的科学工作者共同研究的问题，因此，在计算方法课程中，主要研究截断误差和舍入误差（包括初始数据的误差）对计算结果的影响。二、绝对误差、相对误差和有效数字在不同的场合下，表示近似数精确度的方法各有不同，下面将介绍数值运算误差的基本概念。1．绝对误差与绝对误差限定义1：设x是准确值x*的近似值，称xxe*是近似值x的绝对误差。由于x*一般不知道，所以e也不得而知，但实际问题往往可以估计出e不超过某个正5数，即*xx，则称为绝对误差限，有了绝对误差限就可以知道x*范围为xxx*即x*落在],[xx内。在应用上，常常采用下列写法来刻划x*的精度。xx*绝对误差的大小，在许多情况下还不能完全刻划一个近似值的准确程度，例如测量1000米和1米两个长度，若它们的绝对误差都是1厘米，显然前者的测量比较准确。由此可见，决定一个量的近似值的精确度，除了考虑绝对误差的大小外，还需考虑该量本身的大小，为此引入相对误差的概念。2．相对误差和相对误差限定义2：设x*是准确值，x是近似值，称***xxxxe为近似值x的相对误差，相应地，若正数r，满足rxxx**则称r为x的相对误差限。3．有效数字众所周知，当准确数x*有很多位数时，常常按“四舍五入”的原则去得到x*的近似数。例如=3.1415926…按舍入原则，若取4位小数得=3.1416，取5位和则有=3.14159。定义3：若x是准确数x*的近似数Kxx1021*那么我们就说，用近似数x表示x*时，准确到非零数之间的一切数字都叫做有效数字，并把有效数字的位数叫做有效数位，它反映了x近似x*的精确程度。由上述定义410211416.35102114159.30015926.014.3有效数位为3位0000074.01416.3有效数位为5位0000926.01415.3有效数位为4位§4数值计算中应该注意的一些原则由上述讨论可知,误差分析在数值计算中是一个很重要又很复杂的问题。因为在数值计算中每一步运算都可能产生误差，而一个科学计算问题的解决，往往要经过成千上万次运算，如果每一步运算都分析误差，显然是不可能的，其实也是不必要的。人们经常通过对误差的某传播规律的分析，指出在数值计算中应该注意的一些原则，有助于鉴别计算结果的可靠性并防止误差危害现象的产生，下面我们给出在数值计算中应该注意的一些原则。1．要使用数值稳定的算法6所谓算法，就是给定一些数据，按着某种规定的次序进行计算的一个运算序列。它是一个近似的计算过程，我们选择一个算法，主要要求它的计算结果能达到给定的精度。一般而言，在计算过程中初始数据的误差和计算中产生的舍入误差总是存在的，而数值解是逐步求出的，前一步数值解的误差必然要影响到后一步数值解的精度。我们把运算过程中舍入误差不增长的计算公式称为数值稳定的，否则是数值不稳定的。只有稳定的数值方法才可能给出可靠的计算结果，不稳定的数值方法毫无实用价值。例：求10dx5xxInn（n=0,1,2,…,8）的值。解：由于nxxxxIInnnnn1dxdn5551011011初值)2.1ln(5ln6lndx51100xI于是可建立递推公式)8,,2,1(,51)2.1ln(10nInIInn（1.8）若取182.0)2.1ln(0I按(1.8)式就可以逐步算得09.05101II05.052112II083.053123II165.054134II因为在[0,1]上被积函数05xxn（仅当x=0时为零），且当mn时，55xxxxmn（仅当x=0时，等号成立），所以In(n=0,1,2,…,8)是恒正的，并有08210IIII。在上述计算结果中，I4的近似值是负的，这个结果显然是错的。为什么会这样呢？这就是误差传播所引起的危害。由递推公式（1.8）可看出，In-1的误差扩大了5倍后传给In，因而初值I0的误差对以后各步计算结果的影响，随着n的增大愈来愈严重。这就造成I4的计算结果严重失真。如果改变计算公式，先取一个In的近似值，用下面的公式（1.9）倒过来计算In-1，In-2，…即：7)1,,1,(51511nnKIKIKk（1.9）情况就不同了。我们发现kI的误差减小到51后传给1kI，因而初值的误差对以后各步的计算结果的影响是随着n的增大而愈来愈小。由于误差是逐步衰减的，初值In可以这样确定，不妨设I9I10，于是由10951501II可求得I90.017，按公式（1.9）可逐次求得I80.019I70.021I60.024I80.028I40.034I30.043I20.058I10.088I00.182显然，这样算出的I0与ln(1.2)的值比较符合。虽然初值I9很粗糙，但因为用公式（1.9）计算时，误差是逐步衰减的，所以计算结果相当可靠。比较以上两个计算方案，显然，前者是一个不稳定的算法，后者是一个稳定算法。对于一个稳定的计算过程，由于舍入误差不