数值分析--第1章绪论.doc

第一章 绪论上世纪中叶诞生的计算机给科学、工程技术和人类的社会生活带来一场新的革命。它使科学计算平行于理论分析和实验研究，成为人类探索未知科学领域和进行大型工程设计的第三种方法和手段。在独创性工作的先行性研究中，科学计算更有突出的作用。在今天，熟练地运用电子计算机进行科学计算，已成为科学工作者的一项基本技能。然而，科学计算并不是计算机本身的自然产物，而是数学与计算机结合的结果，它的核心内容是以现代化的计算机及数学软件为工具，以数学模型为基础进行模拟研究。近年来，它同时也成为数学科学本身发展的源泉和途径之一。1 数值分析的研究对象与特点数值分析是计算数学的一个主要部分，计算数学是数学科学的一个分支，它研究用计算机求解各种数学问题的数值计算方法及其理论与软件实现。一般地说，用计算机解决科学计算问题，首先需要针对实际问题提炼出相应的数学模型，然后为解决数学模型设计出数值计算方法，经过程序设计之后上机计算，求出数值结果，再由实验来检验。概括为实际问题数学模型计算方法程序设计计算结果由实际问题的提出到上机求得问题的解答的整个过程都可看作是应用数学的任务。如果细分的话，由实际问题应用有关科学知识和数学理论建立数学模型这一过程，通常作为应用数学的任务，而根据数学模型提出求解的数值计算方法直到编出程序上机计算出结果，这一过程则是计算数学的任务，即数值分析研究的对象。因此，数值分析是寻求数学问题近似解的方法、过程及其理论的一个数学分支。它以纯数学作为基础，但却不完全像纯数学那样只研究数学本身的理论，而是着重研究数学问题求解的数值方法及与此有关的理论，包括方法的收敛性，稳定性及误差分析；还要根据计算机的特点研究计算时间最省（或计算费用最省）的计算方法。有的方法在理论上虽然还不够完善与严密，但通过对比分析，实际计算和实践检验等手段，被证明是行之有效的方法也可采用。因此数值分析既有纯数学高度抽象性与严密科学性的特点，又有应用的广泛性与实际试验的高度技术性的特点，是一门与使用计算机密切结合的实用性很强的数学课程。在电子计算机成为数值计算机的主要工具以后，则要求研究适合计算机使用的，满足精确要求，计算时间省的有效算法及其相关的理论。在实现这些算法时往往还要根据计算机的容量、字长、速度等指标，研究具体的求解步骤和程序设计技巧。有的方法在理论上虽还不够严格，但通过实际计算、对比分析等手段，证明是行之有效的方法，也应采用。这些就是数值分析具有的特点，概括起来有四点：第一，面向计算机，要根据计算机特点提供切实可行的有效算法。即算法只能包括加、减、乘、除运算和逻辑运算，这些运算是计算机能直接处理的运算。.第二，有可靠的理论分析，能任意逼近并达到精确要求，对近似算法要保证收敛性和数值稳定性，还要对误差进行分析。这些都建立在相应数学理论的基础上。第三，要有好的计算复杂性，时间复杂性好是指节省时间，空间复杂性好是指节省存储量，这也是建立算法要研究的问题，他关系到算法能否在计算机上实现。第四，要有数值试验，即任何一个算法除了从理论上要满足上述三点外，还要通过数值试验证明是行之有效的。根据“数值分析”课程的特点，学习是我们首先要注意掌握方法的基本原理和思想，要注意方法处理的技巧及其与计算机的结合，要重视误差分析、收敛性及稳定性的基本理论；其次，要通过例子，学习使用各种数值方法解决实际计算问题；最后，为了掌握本课的内容，还应作一定数量的理论分析与计算练习。由于本课内容包括了微积分、代数、常微分方程的数值方法，读者必须掌握这几门课的基本内容才能学好这门课。2 数值计算的误差2.1 误差来源与分类我们算出数学模型的近似解和一个物理量的真的值往往不相等，它们之差称为误差。用电子计算机进行解决实际问题的数值计算，误差是不可避免的。引起数值结果中的误差的原因是多方面，通常来自固有误差和计算误差，如下面所示：模型误差观测误差误差来源计算误差固有误差截断误差舍入误差模型误差：用数学方法解决实际问题，首先必须建立该问题的数学模型。即把实际问题经过抽象，忽略一些次要的因素，简化成一个确定的数学问题。数学模型只是对实际问题的一种近似、一种粗糙的描述，因而它与实际问题或客观现象之间必然存在误差，这种误差称为“模型误差”。这样的误差常常是可以忽略不计的。例如在经典力学问题中，我们常常忽略相对论效应。但是，如果这种误差不可忽略，说明数学模型选择得不好。那么不论数值计算多么精确，其结果都将存在不可忽略的误差。观测误差：数学问题中总包含一些参量（或物理量，如电压、电流、温度、长度等），它们的值（输入数据）往往是由观测得到的。而观测的误差是难以避免的，由此产生的误差称为“观测误差”。由于观测误差通常具有随机的性质，所以想用分析的方法来估计它们的影响常常是一件非常困难的事。由于固有误差的产生往往涉及各专业知识及实验手段，所以它不是数值分析所研究的内容。截断误差：数值计算的本质就是用有限的过程、离散的数据来近似（刻画）无限的过程、连续的量。这样对一些具有连续量、无限计算量的数学问题的求解的过程中，我们不得不对一些连续的量进行有限的离散化近似，不得截去无限的计算过程，只进行有限次的计算。如求一个收敛的无穷级数之和，必须截去该级数后面的无穷多项，而用前面有限项的部分来近似代替，于是产生了有限过程代替无限过程的误差，称为“截断误差”，这是计算方法本身所出现的误差，所以也称为“方法误差”。例如，当很小时，可以用作为近似值。由交错级数判敛的莱布尼兹（Leibniz）准则，它的截断误差的绝对值不超过。有限过程代替无限过程的误差和计算量取决于其方法的收敛性及收敛速度。舍入误差：计算中遇到的数据可能位数很多或是无穷小数，如受机器字长的限制，无穷小数和位数很多的数必须舍入成一定的位数（机器字长）。舍入方法：a) 舍入机。采用四舍五入的办法，如将舍为；b) 截断机。采用截尾的办法。如在八位字长的截断机里取成。这样产生的误差称为“舍入误差”。少量的舍入误差是微不足道的，但在计算机是作了成千上万次运算后，舍入误差的累积有时可能是十分惊人的。它取决于方法的稳定性。如果方法能够累积大量的误差，此算法是不稳定的，反之为稳定算法。如算法1：。显然是不稳定的；算法2：， 研究计算结果的误差是否满足精度要求就是误差估计问题，本书主要讨论算法的截断误差与舍入误差，而截断误差将结合具体算法讨论。为分析数值运算的舍入误差，先要对误差基本概念做简单介绍。2.2 绝对误差与相对误差定义1 设为准确值，为的一个近似值，称为近似值的绝对误差，简称误差。注意这样定义的误差可正可负，当绝对误差为正时近似值偏大，叫强（赢）近似值；当绝对误差为负时近似值偏小，叫弱（亏）近似值。通常我们不能算出准确值，当然也不能算出误差的准确值，只能根据测量工具或计算情况估计出误差的绝对值不超过某正数，也就是误差绝对值的一个上界。叫做近似值的误差限，它总是正数。一般情形，即。这个不等式有时也表示为。我们把近似值的误差与准确值的比值称为近似值的相对误差，记作。在实际计算中，由于真值总是不知道的，通常取作为的相对误差，条件是较小，此时是的平方项级，故可忽略不计。相对误差也可正可负，它的绝对值上界叫做相对误差限，记作，即。注1：1）绝对误差是有量纲的量，它与所研究问题的背景有关，因此我们不能单单从绝对误差值的大小来判断计算结果的精度，还必须考虑到实际问题的应用背景；2）通过引入相对误差，我们可比较不同算法，不同应用问题的计算精度，这一点是无法通过比较绝对误差做到的，因为不同值的东西，在量上是无法比较的。正如我们不能通过比较两个商品的使用价值来判定商品的真贵，只能通过抽象的价值。2.3 有效数字有效数字是近似值的一种表示法，它既能表示近似值的大小，又能表示其精确程度。定义2 若近似值的误差限是某一位的半个单位，该位到的第一位非零数字共有位，则称近似值有位有效数字。在科学记数法中，将近似值写成规格化形式为 (1-1)其中为整数，为0到9之间的整数。按照定义2，近似值有位有效数字当且仅当 (1-2)因此在相同的情形下，越大则误差越小，亦即一个近似值的有效位数越多其误差限越小。例1 按四舍五入原则写出下列各数具有5位有效数字的近似数：187.9325,0.03785551,8.000033, 2.7182818。按定义，上述各数具有5位有效数字的近似数分别是：187.93, 0.037856, 8.0000, 2.7183。注意：的5位有效数字的近似数是8.0000而不是8，因为8只有1位有效数字。例2 重力常数，如果以为单位，；若以为单位，它们都具有3位有效数字，因为按第一种写法，按第二种写法，他们虽然写法不同，但都具有3位有效数字。至于绝对误差限，由于单位不同结果也不同，而相对误差都是例2说明有效位数与小数点后有多少位数有关。然而，从(2-2)可以得到具有位有效数字的近似数，其绝对误差限为，在相同的情况下，越大则越小，故有效位数越多，绝对误差限越小。关于一个近似数的有效位数与其相对误差的关系，有下面的定理定理1.1 设近似数具有规格化形式(1-1)，(1) 若具有位有效数字，则其相对误差限为 (1-3)(2) 如果 (1-4)则至少具有位有效数字。证明 由(1-1)可得到当有位有效数字时即证(1)。反之，由即说明具有位有效数字，(2)得证。定理说明，有效位数越多，相对误差限越少。例3 要使的近似值的相对误差限小于0.1%，要取几位有效数字？设取位有效数字，由定理1.1，。由于，知，故只要取，就有即只要对的近似值取4位有效数字，其相对误差就小于0.1%。此时由开方表得。3 数值计算中误差的传播3.1 基本运算中的误差估计数值运算中误差传播情况比较复杂，估计起来比较困难。本节所讨论的运算是四则运算与一些常用函数的计算。由微分学，当自变量改变（误差）很小时，函数的微分作为函数的改变量的主要线性部分可以近似函数的改变量，故可以利用微分运算公式可导出误差运算公式。设数值计算中求得的解与参量（原始数据）有关，记为参量的误差必然引起解的误差。设的近似值分别为，相应的解为假设在点可微，则当数据误差较小时，解的绝对误差为 (1-5)其相对误差为 (1-6)注2：函数值的绝对误差等于函数的全微分，自变量的微分即为自变量的误差；函数值的相对误差等于函数的对数的全微分。将式(1-5)及(1-6)中的和分别换成误差限和，求和的各项变成绝对值。特别地，由式(1-5)及(1-6)可得和、差、积、商之误差及相对误差公式 (1-7) (1-8)由以上的式(1-7)及(1-8)可得出 (1-9)因此，和、差的误差限不超过各数的误差限之和，积、商的相对误差限不超过各数的相对误差限之和。例4 设，求的相对误差与的相对误差之间的关系。解 由式(1-9)得所以的相对误差是的相对误差的倍，特别地，的相对误差是的相对误差的一半。例5 设，的相对误差为，求的绝对误差。解 由于 ，即，所以例6 已测得某场地长为的值为宽的值为已知，试求面积的绝对误差与相对误差。解 因由(1-5)知其中，而于是绝对误差限相对误差限3.2 误差定性分析数值运算中的误差分析是一个很重要而复杂的问题，上节讨论了不精确数据运算结果的误差限，他只适用于简单情形，然而一个工程或科学计算问题往往要运算千万次，由于每步运算都有误差，如果每步都做误差分析是不可能的，也不科学，因为误差积累有正有负，绝对值有大有小，都按最坏情况估计误差限得到的结果比实际误差大得多，这种保守的误差估计不反映实际误差积累。考虑到误差分布的随机性，有人用概率统计方法，将数据和运算中的舍入误差视为适合某种分布的随机变量，然后确定计算结果的误差分布，这样得到的误差估计更能接近实际，这种方法称为概率分析法。20世纪60年代以后对舍入误差分析提出了一些新的方法，较重要的有以下两种：1.向后误差分析法是把新算出的量由某个公式表达，它仅含基本的算术运算，如假定是前面已算出的量或原始数据，新算出量若的摄动为，使得由浮点运算得出结果为则可根据的界由摄动理论估计最后舍入误差的界，威克逊（Wilkinson）将这种方法应用于数值代数（矩阵运算）的误差分析，取得较好的效果。2.区间分析法是把参加运算的数都看成区间量根据区间运算规则求得最后结果的近似值及误差限。例如，的近似数为由于则若计算（*为运算符号），由,则为所求近似值，而则为误差限。上面简略介绍了误差分析的几种方法，但都不是十分有效的，目前尚无有效的方法对误差作出定量估计。为了确保数值计算结果的正确性，首先需对数值计算问题作出定性分析，为此本节讨论以下三个问题。3.3 病态问题与条件数对一个数值问题本身如果输入数据又微小扰动（即误差），引入输出数据（即问题解）相对误差很大，这就是病态问题，例如计算函数值时，若有扰动，其相对误差为，函数值的相对误差为。相对误差比值 (1-10)称为计算函数值问题的条件数。自变量相对误差一般不会太大，如果条件数很大，将引起函数值相对误差很大，出现这种情况的问题就是病态问题。例如，则有，他表示相对误差可能放大倍。如，有，若取自变量相对误差为2%，函数值相对误差为24%，这是问题可以认为是病态的。一般情况条件数就认为是病态的，越大病态越严重。其他计算问题也要分析是否病态。例如解线性方程组，如果输入数据有微小误差引起解的巨大误差，就认为是病态方程组，我们将在第5章用矩阵的条件数来分析这种现象。3.4 算法的数值稳定性数值运算的误差分析是个很重要而复杂的问题，对于一个工程或科学计算问题往往要运算千万次，由于几乎每一步运算都会产生误差，如果每步都做误差分析是不可能的，也不科学，因为误差累积有正有负，绝对值有大有小，很可能有一部分相互抵消。如果每一步都按最坏情况估计误差不反映实际情况。近年来，虽然发展起来一些新的误差估计办法，如概论统计法，事后误差估计法及区间分析法等等。但这些方法目前也仅仅在特定的一些问题上取得了较为满意的结果，还正在发展中。对于计算步骤较多的算法，一般不宜采用上述的一些定量估计的办法。而是采用定性分析的办法，即讨论算法的数值稳定性。定义3 一个算法如果输入数据有误差，而在计算过程中舍入误差得到控制，则称此算法是数值稳定的，否则称此算法是不稳定的。在一种算法中，如果某一步有了绝对值为的误差，而以后各步计算都准确地进行，仅由所引起的误差的绝对值，始终不超过，就说算法是稳定的。对于数值稳定性的算法，不用做具体的误差估计，就认为其结果是可靠的。而数值不稳定的算法尽量不要使用。例7 计算并估计误差。由分部积分可得计算的递推公式 (1-11)若计算出，代入(1-11)，可逐次求出的值。要算出就要先计算，若用泰勒多项式展开部分和，并取，用4位小数计算，则得，截断误差。计算过程中小数点后第5位的数字按四舍五入原则舍入，由此产生的舍入误差这里先不讨论。当初始值取为时，用(1-11)递推的计算公式为（A） 。计算结果见表1-1的列。用近似产生的误差就是初始误差，它对后面计算结果是有影响的。表1-1(用(A)算)(用(B)算) (用(A)算)(用(B)算)012340.63210.36790.26420.20740.17040.63210.36790.26430.20730.1708567890.1480 0.1120 0.2160 -0.7280 7.552 0.14550.12680.11210.10350.0684从表中可以看到出现负值，这与一切0相矛盾。实际上，有积分估值得 (1-12)因此，当较大时，用近似显然是不正确的。这里的计算公式与每步计算都是正确的，那么是什么原因使计算结果错误呢？主要就是初值有误差，由此引起以后各步计算的误差满足关系 容易推得，由此看出：误差导致第步的误差扩大倍，当较大时，误差将淹没真值，因此用近似显然是不正确的，这种递推公式不宜采用。例如，若，则。这就说明完全不能近似了。它表明公式(A)是数值不稳定的。我们现在换一种计算方法。由(1-12)取，有我们粗略取，然后将公式(1-11)倒过来算，即由算出公式为（B） 计算结果见表1-1的列。我们发现与的误差不超过。记，则，比缩小了倍，因此，尽管较大，但由于误差逐步缩小，故可用近似。反之，当用方案(A)计算时，尽管初值相当准确，由于误差传播是逐步扩大的，因而计算结果不可靠。此例说明，数值不稳定的算法是不能使用的。在例7中，算法(B)使数值稳定的，而算法(A)是不稳定的。数值不稳定现象属于误差危害现象，如何防止误差危害下面将进一步讨论。4 数值计算中应注意的几个问题数值计算中首先要分清问题是否病态和算法是否数值稳定，计算时还应尽量避免误差危害，防止有效数字的损失，下面给出若干原则：1 要避免除数绝对值远远小于被除数绝对值的除法。因为故当时，舍入误差可能增大很多。例8 线性方程组的准确解为现在四位浮点十进制数（仿机器实际计算）下用消去法求解，上述方程写成若用除第一方程减第二方程，则出现用小的数除大的数，得到由此解出显然严重失真。若反过来用第二个方程消去第一个方程中含的项，则避免了大数被小数除，得到由此求的相当好的近似解。2 要避免两相近数相减。两数之差的相对误差为当与很接近时，的相对误差会很大，有效数字位数将严重丢失。例如，都具有五位有效数字，但只有两位有效数字。这说明必须尽量避免出现这类运算。最好是改变计算方法，防止这种现象产生。先举例说明。例9 求的根。解 ，只有一位有效数字。若改用具有3位有效数字。例10 计算（用四位数学用