数值计算方法讲义-第一章预篇

《数值计算方法讲义-第一章预篇》由会员分享，可在线阅读，更多相关《数值计算方法讲义-第一章预篇（28页珍藏版）》请在装配图网上搜索。

1、前言由于计算机的普及，科学计算已成为各学科领域的一项重要工作。学习和掌握数值计算方法的基本原理及应用已成为现代科学工作者不可缺少的一个环节。用计算机解决科学计算问题需经历几个过程：由实际问题建立数学模型，根据数学模型提出求解的数值计算方法，编出程序、上机求出结果。通过以上过程，可以看出，数值计算方法 是计算机、数学和应用科学之间的桥梁，是程序设计和对数值结果进行分析的依据，是用计算机进行科学计算全过程的一个重要环节。目前，数值计算方法已经成为理工科院校（非数学专业）硕士学位研究生的学位课。在农业科学研究中，数值计算方法已经成为不可缺少的有力工具。学生通过本课程的学习，能掌握科学计算中常用的算法

2、，能独立地用学过的算法编程，测试。并能解决工作中遇到的实际问题。本教材同时也适当增加一些只供阅读，而不在课堂教授的内容，这样在规定的课时内可完成基本内容的讲授，又可以作为今后科研的参考书。各章节要点及授课时数本教材的特点：对现有的已知的数学模型建立起相应的一系列数值求解方法，力求设计计算量小、存储量少、精度高，特别是计算机所能接受且执行计算方法，兼顾分析方法的收敛性、稳定性及误差估计。在不失科学性的前提下，尽量做到深入浅出地介绍计算机上常用的数值方法，使学生能用数值计算方法对建立的数学模型实际求解。本教材既坚持介绍数值计算方法基本原理，又兼顾应用学科的特点，这是现有教材所不具备的。使用范围：理

3、工科非数学学科公共专业课教材。本教材主要介绍计算机上常用的各种数值计算方法以及相关的基本概念及理论。内容包括误差分析初步，方程求根，线性方程组的直接解法与迭代法，插值法，最小二乘曲线拟合，数值积分计算，常微分方程数值解法和偏微分方程数值解法。本课程中对主要基本算法的推导、构造原理、收敛性、误差估计进行了讨论。本教材的另一个特色是侧重于计算机应用，各章均有例题及数值算例，并指出应掌握的基本问题，对每一个算法都给出伪代码，以便于学生编制程序的需要，且有适当的书面练习及一些上机计算题。本教材可作为理工科（非计算数学）各专业研究生及大学本科高年级的数值计算方法教材，也可供工程技术人员参考。作者从事硕士

4、研究生学位课数值计算方法教学已经30余年，在多年的教学中发现给农业院校的学生寻找一本合适的教材很难。一方面，和其它理工科院校的学生相比，农业院校的学生数学基础课学得不够，因此需要浅显易懂的教材；另一方面，农业科学的发展，对数学和计算科学提出了很高的要求，因为农业科学的复杂性和不确定性，需要有尽可能多的内容和深度，这样互相矛盾的需求给讲课教师提出了很高的要求，教师要深入的理解数值计算的理念，要有深厚的计算数学理论知识和计算经验才能讲好这门课。在学习了许多国内外教材的基础上，根据农业院校学生的特殊要求，作者于1984年编写了数值计算方法讲稿，每年都有小的改动，在1993年、1999年、2005年和

5、2009年对讲稿进行了几次较大的修改，以适应科学发展需要和农大学生的基础。许多研究生通过学习，在毕业论文中引用了数值计算方法解决应用问题，提高了论文水平，也有许多在职教师和科研人员学习这门课程后，将数值方法引用到科研课题中，取得了较好的成果。目录第一章 预篇 1.1 数值计算方法的研究对象和特点 1.2 误差分析 1.3 算法的概述第二章 非线性方程求根 2.1 二分法 2.2 迭代法的一般原则 2.3 牛顿法(切线法) 2.4 弦截法第三章 解线性方程组的直接法 3.1 Gauss 消去法 3.2 矩阵的三角分解及其在解方程组中的应用 3.3 解对称正定矩阵方程组的平方根解法 3.4 解三对

6、角方程组的追赶法 3.5 向量和矩阵的范数 3.6 方程组的性态、条件数第四章 解线性方程组的迭代法 4.1 Jacobi 迭代法 4.2 Gauss-Seidel 4.3 SQR 方法 4.4 迭代法的收敛性 4.5 共轭梯度法 4.6 最小二乘法第五章 矩阵特征值问题的计算方法 5.1 矩阵特征值问题 5.2 乘幂法和反幂法 5.3 Household方法 5.4 QR方法第六章 函数插值 6.1 Lagrange 插值 6.2 Newton 插值 6.3 等距节点的插值 6.4 Hermite 插值 6.5分段低次多项式插值 6.6 三次样条插值第七章 最佳平方逼近 7.1 正交多项式

7、7.2 切比雪夫多项式 7.3 曲线拟合的最小二乘法第八章 数值积分 8.1 Newton-Cotes 求积公式 8.2 Romberg 求积公式 8.3 Gauss 型求积公式第九章 常微分方程数值解 9.1 Euler 法和改进 Euler 法 9.2 Runge-Kutta 法 9.3 线性多步法 9.4 解二阶常微分方程边值问题的差分法第十章 偏微分方程数值解 10.1 椭圆型方程差分法 10.2 抛物型方程差分法 10.3 双曲型方程差分法 10.4 有限元方法初步第一章 预篇数学是研究数与形的科学。其中研究怎样利用手指、算盘、计算尺、计算器、计算机等工具，来求出数学问题数值解的学问

8、，就是数值计算方法。它是数学中最古老的部分，但只是在计算机出现以后，人们获得了高速度、自动化的计算工具，才为众多浩繁的数值问题的解决展现了光明的前景。从此，科学研究与工程设计的手段，发生了由模型试验向数值计算的巨大转变。近年来，由于计算机的发展，计算性的学科新分支，如计算力学、计算物理、计算化学、计算生物学、计算地质学、计算经济学以及众多工程科学的计算分支纷纷兴起。因为任何具体学科中的计算过程，不论其目的、背景和含义如何，终归是数学的计算过程，数值计算方法是各种计算性学科的联系纽带和共性基础。学习数值计算方法可以知道如何用计算机解决数学问题，特别是我们在微积分和线性代数中没有学过的一些解决问题

9、的方法，还介绍一些用不同的方法解决以前用传统的数学方法解决的问题。我们选择一些现实世界存在的例子，用解析的方法能够解出来，以便将数值方法和解析方法做一个对比。1.1 数值计算方法的起源和意义计算方法是数学的一个古老的分支，虽然数学不仅仅是计算，但推动数学产生和发展的最直接原因还是计算问题。人类社会发展的初期，就常常遇到各种各样的计算问题。一开始没有任何计算工具，最得心应手的就是人类的一双手了。于是人们采取了扳手指头和结绳计数的方法进行计算。随着社会的进一步向前发展，问题越来越复杂，原始的工具不敷使用。人们越来越迫切地希望有更先进的技术和理论来进行计算，于是数学应运而生。可以这么说，记数术是最原

10、始的数学，数学的源头就是计算，计算自古以来就是数学的一个重要组成部分。中国古代数学曾经有过辉煌的成就，它不像古希腊数学那样注重逻辑和推理，而是具有显著的计算性和实用性的特点，从九章算术等中国古典数学名著中就可以看出这一点。早在商代中国就形成了十进制这一方便的计数和运算机制。从最早发明的算筹到后来的算盘以及相应发展起来的珠算方法，是古代中国对世界计算技术的最重要贡献，至今还在中国和其他一些国家都发挥着作用。到了二十世纪四十年代，生产高性能计算工具的技术条件已经成熟。当时适逢第二次世界大战，军事上对高速计算机有迫切的需求。这就迎来了世界上第一台电子计算机的诞生。计算机的问世，从根本上改变了计算工具

11、落后的局面。古老的计算数学借助计算机这一强有力的工具，一下子换发出了青春。随着计算技术的发展，社会需求的急剧增加，计算数学的应用领域越来越广泛，这就使得越来越多的、以前不能设想的、难度和规模日益增大的计算问题得以解决。在这样新的条件下，计算在整个科学技术以至经济生活中的重要性得到前所未有的提高；同时，以原来分散在数学各分支的计算方法为基础的一门新的数学科学开始形成并迅速发展。计算数学和计算机一起已经成为众多领域研究工作中不可或缺的工具和手段。当代计算能力的大幅度提高既来自计算机的进步，也来自计算方法的进步。计算机和计算方法的发展是相辅相成，相互制约和相互促进的。计算方法的发展启发了新的计算机体

12、系结构，而计算机的更新换代也对计算方法提出了新的标准和要求。自计算机诞生以来，经典的计算方法业已经历了一个重新评价、筛选、改造和创新的过程；与此同时，涌现了许多新概念、新课题和许多能够充分发挥计算机潜力、有更大解题能力的新方法；这就构成了现代意义下的计算数学（数值计算方法）。1.2 数值计算方法的研究对象科学计算问题的出发点，往往是研究现实世界中的问题或现象。例如：物理、自然或者社会问题。在一定的假设下，可以将这些实际问题列成方程，也就是数学模型来描述或进行分析。从简单的代数方程到复杂的非线性偏微分方程应有尽有。这些方程一旦建立起来，下一步就是要解方程，以预测这些现象将来朝什么方向发展。为了获

13、取数据，我们也需要做一些实验。如果模型预测的结果和实测数据一致或接近，就认为所建立的模型是合适的，否则就要对所建立的模型加以调整和改进。在求解阶段，最理想的状况是求出方程的解析解，遗憾的是，仅对最简单的模型才能求出解析解。我们通过几个例子来说明在微积分和线性代数中学过的数学模型而在这两门课程中所没有学到可行的解法。例1.1 求解线性方程组AX=b，其中系数矩阵A是的方阵，设n = 20；解：本例的行列式。按照Gramer法则，此方程的解为：。如解n阶方程组，要计算n + 1个n阶行列式的值，每个行列式按Laplace 展开计算，总共需要做（n+1）n! 次乘法运算。本题n=20, 需要进行以上

14、的乘法运算。设用每秒可做一亿次乘法的计算机，一年可以做次乘法。所以在此计算机上用Gramer法则解20阶的线性方程组，需要的时间在万年以上。这当然是没有实际意义的。例1.2 求超越方程 和 的根例1.3 不用计算器，求的近似值。x149123例 1.4 计算定积分 例1.5在7块并排、形状大小相同的试验田上施化肥对水稻产量影响的试验，得到如下表所示的一组数据（单位：kg） 施化肥量 x 15202530354045水稻产量 Y330345365405445450455求施肥和产量的关系。例1.6 研究对象是连续的，我们只能了解到其有限个数据温度的变化，时间是连续的，温度是时间的函数，如何画出温

15、度的曲线图？大量的根据实际问题所建立的模型只能求出近似解，也就是用“逼近”技术求出问题的解。本书的目的就是设计一些算法，对可以用数学模型描述的现实世界的现象求出近似解（数值解）。用计算机解决科学计算问题需经历几个过程：由实际问题建立数学模型，根据数学模型提出求解的数值计算方法，编出程序，上机求出结果。通过以上过程，可以看出：数值计算方法是计算机、数学和应用科学之间的桥梁，是程序设计对数值结果进行分析的依据，是用计算机进行科学计算全过程的一个重要环节。计算机实质上只会做加减乘除等基本运算。研究怎样通过计算机所执行的基本运算，求得各类问题的数值解或近似数值解，就是计算数学的根本课题。数值计算方法的

16、研究对象：数值计算方法主要研究适合于在计算机上使用的计算方法以及与此相关的理论，包括方法的收敛性、稳定性及误差分析。还要根据计算机的特点研究时间最短、需要计算机内存最少的计算方法。1.3 算法 算法的定义：解决问题的一系列有序的步骤。描述算法可以有不同的方式。例如，可以用日常语言和数学语言加以叙述，也可以借助形式语言（算法语言）给出精确的说明，也可以用框图直观地显示算法的全貌。下面举个简单的例子。例1.7：求解二元一次联立方程组这个方程组的行列式解法可表述如下：首先判别是否为零，存在两种可能：（1）如果，则令计算机计算 ，输出计算的结果x1，x2。（2）如果D= 0，则或是无解，或有无穷多组解

17、，这是奇异的情形。下面用框图（也称流程图）来形象地描述上面的算法。开 始输 入D=a11a22-a12a21D=0 Y N输出无解信息输出 x1, x2结 束图 1.1 框图这里我们使用了两种形式的框，一种是矩形框 ，称为叙述框，计算公式就填在这种框内；另一种是棱形框 ，称为判断框，表示算法的判断检查部分。1.4 数值计算中的误差用数值方法解决科学研究或工程技术中的实际问题，一般来说，产生误差是不可避免的，根本不存在绝对的严格和精确。但是我们可以认识误差，从而控制误差，使之局限于最小（或尽量小）的范围内。1.4.1 误差的来源运用数学工具解决实际问题，可能产生的误差主要有以下几类。1描述误差在

18、将实际问题转化为数学模型的过程中，为了使数学模型尽量简单，以便于分析或计算，往往要忽略一些次要的因素，进行合理的简化。这样，实际问题与数学模型之间就产生了误差，这种误差称为描述误差。由于这类误差难于作定量分析，所以在计算方法中，总是假定所研究的数学模型是合理的，对描述误差不作深入的讨论。2观测误差在数学模型中，一般都含有从观测（或实验）得到的数据，如温度、时间、速度、距离、电流、电压等等。但由于仪器本身的精度有限或某些偶然的客观因素会引入一定的误差，这类误差叫做观测误差。通常根据测量工具或仪器本身的精度，可以知道这类误差的上限值，所以无须在计算方法课程中作过多的研究。3截断误差在数值计算中，常

19、用收敛的无穷级数的前几项来代替无穷级数进行计算。如（1.5）当很小时，可以取（1.5）的前两项来近似代替的计算，即 （很小时）（1.6）由泰勒定理可知，这时与的误差是（1.7）在计算中被抛弃了，这类误差叫做截断误差。截断误差的大小，直接影响数值计算的精度，所以它是数值计算中必须十分重视的一类误差。4舍入误差无论用计算机、计算器计算还是笔算，都只能用有限位小数来代替无穷小数或用位数较少的小数来代替位数较多的有限小数，如：p = 3.1415926 x = 8.123456经四舍五入后取含小数点后四位数字的数来表示它们时，便有误差这类误差叫做舍入误差。当然，计算过程中，这类误差往往是有舍有入的，而

20、且单从一次的舍入误差来看也许不算大，但数值计算中，往往要进行成千上万次四则运算，因而就会有成千上万个舍入误差产生，这些误差一经迭加或传递，对精度可能有较大的影响。所以，作数值计算时，对舍入误差应予以足够的重视。显然，上述四类误差都会影响计算结果的准确性，但描述误差和观测误差往往是计算工作者不能独立解决的，是需要与各有关学科的科学工作者共同研究的问题，因此，在计算方法课程中，主要研究截断误差和舍入误差（包括初始数据的误差）对计算结果的影响。1.4.2 绝对误差、相对误差和有效数字在不同的场合下，表示近似数精确度的方法各有不同，下面将介绍数值运算误差的基本概念。1绝对误差与绝对误差限定义1：设x是

21、准确值，x*是x的一个近似值，称 （1.8）是近似值x*的绝对误差，简称为误差。由于准确值x往往是未知的，因此也无法求出绝对误差e(x)是多少，但实际问题往往可以估计出绝对误差的一个上界。定义2：若已知 ，使 （1.9）则称 近似值x* 的绝对误差限，简称为误差限。对一般情况，即有时也表示为绝对误差的大小，在许多情况下还不能完全刻划一个近似值的准确程度，例如测量1000米和1米两个长度，若它们的绝对误差都是1厘米，显然前者的测量比较准确。由此可见，决定一个量的近似值的精确度，除了考虑绝对误差的大小外，还需考虑该量本身的大小，为此引入相对误差的概念。2相对误差和相对误差限定义3：称近似值x*的误

22、差e(x)与准确值x的比值 （1.10）为近似值x*的相对误差，记作，（在实际计算时，（1.10）式中的x通常用近似值x*代替）。类似定义2，有定义4 相对误差的上界，称为相对误差限，即 （1.11）3有效数字众所周知，当准确数x有很多位数时，常常按“四舍五入”的原则去得到x的近似数。例如p = 3.1415926按舍入原则，若取4位小数得p = 3.1416，取5位则有p = 3.14159。用有效数字这个概念来表示一个近似数的准确程度，其定义为定义5：如果 （1.12） 则说x*近似表示x 准确到小数后第n位，并从这第n位起直到最左边的非零数字之间的一切数字都称为有效数字，并把有效数字的位

23、数称为有效位数。由上述定义 有效数位为3位 有效数位为5位 有效数位为4位近似值的有效数字位数越多，近似程度就越好。绝对误差、相对误差及有效数字都是反映误差或近似程度的量，它们相互之间存在某些关系。定义4 描述了绝对误差限与相对误差限的关系，下面的定义6 表明有效数字与绝对误差限的关系。定义6： 若将准确值x 的近似值x*表示成标准形式 （1.13）而其误差限 （1.14）则说近似值x*具有n 位有效数字。这里n 为正整数，m 为整数，每个均为0,1，9中的一个数字，。 例1.8 若x*=3587.64是x 的具有6位有效数字的近似值，求误差限。 解 将x*按（1.13）式写成标准形式 于是，

24、在定义6 中 m=4，n=6 下面讨论有效数字和相对误差限的关系。 定理1.1：若 x* 具有n位有效数字，则其相对误差满足 （1.15）反之，若x*的相对误差满足 （1.16）则近似值x* 至少具有n位有效数字。 证明 若具有n位有效数字，由定义6, 相对误差 由于 所以反之，若（1.16）成立，利用得 根据定义6，x* 至少具有n位有效数字。例1.9：x*=2.71828， ，求相对误差限。解：因为：x*=2.71828=0.271828101，由，n=6，由定理1前一部分，有 例1.10 要使的近似值的相对误差小于0.1%，应取几位有效数字？解：由于，可确定，若相对误差限利用 则有效数字

25、位数n应满足不等式解出n=4，即应有4位有效数字。1.5 数值计算中应该注意的一些原则由上述讨论可知,误差分析在数值计算中是一个很重要又很复杂的问题。因为在数值计算中每一步运算都可能产生误差，而一个科学计算问题的解决，往往要经过成千上万次运算，如果每一步运算都分析误差，显然是不可能的，其实也是不必要的。人们经常通过对误差的某传播规律的分析，指出在数值计算中应该注意的一些原则，有助于鉴别计算结果的可靠性并防止误差危害现象的产生，下面我们给出在数值计算中应该注意的一些原则。1.5.1 要使用数值稳定的算法 所谓算法，就是给定一些数据，按着某种规定的次序进行计算的一个运算序列。它是一个近似的计算过程

26、，我们选择一个算法，主要要求它的计算结果能达到给定的精度。一般而言，在计算过程中初始数据的误差和计算中产生的舍入误差总是存在的，而数值解是逐步求出的，前一步数值解的误差必然要影响到后一步数值解的精度。我们把运算过程中舍入误差增长可以控制的计算公式称为数值稳定的，否则是数值不稳定的。只有稳定的数值方法才可能给出可靠的计算结果，不稳定的数值方法毫无实用价值。下面用一个例子来简单介绍一下稳定性的概念。例1.11：求 （n = 0, 1, 2, , 8）的值。解：由于初值于是可建立递推公式（1.17）若取按 (1.17) 式就可以逐步算得因为在0, 1上被积函数（仅当x = 0时为零），且当mn时，（

27、仅当x = 0时，等号成立），所以In (n = 0, 1, 2, , 8)是恒正的，并有。在上述计算结果中，I4的近似值 是负的，这个结果显然是错的。为什么会这样呢？这就是误差传播所引起的危害。由递推公式（1.13）可看出，In-1的误差扩大了5倍后传给In，因而初值I0的误差对以后各步计算结果的影响，随着n的增大愈来愈严重。这就造成I4的计算结果严重失真。如果改变计算公式，先取一个In的近似值，用下面的公式倒过来计算In-1，In-2，即：（1.18）情况就不同了。我们发现的误差减小到后传给，因而初值的误差对以后各步的计算结果的影响是随着n的增大而愈来愈小。由于误差是逐步衰减的，初值In可

28、以这样确定，不妨设I9 I10，于是由可求得I9 0.017，按公式（1.14）可逐次求得I8 0.019 I7 0.021I6 0.024 I8 0.028I4 0.034 I3 0.043I2 0.058 I1 0.088I0 0.182 显然，这样算出的I0与ln(1.2)的值比较符合。虽然初值I9很粗糙，但因为用公式（1.18）计算时，误差是逐步衰减的，所以计算结果相当可靠。比较以上两个计算方案，显然，前者是一个不稳定的算法，后者是一个稳定算法。对于一个稳定的计算过程，由于舍入误差不增大，因而不具体估计舍入误差也是可用的。而对于一个不稳定的计算过程，如计算步骤太多，就可能出现错误结果。

29、因此，在实际应用中应选用数值稳定的算法，尽量避免使用数值不稳定的算法。1.5.2 要避免两个相似数相减在数值计算中，两个相近的数作减法时有效数字会损失。例如，求：（1.19）之值，当x = 1000，y的准确值为0.01580。若两者直接相减这个结果只有一位有效数字，损失了三位有效数字，从而绝对误差和相对误差都变得很大，严重影响计算结果的精度。若将公式（1.19）处理成，按此公式可求得y = 0.01581，则y有3位有效数字，可见改变计算公式，可以避免两相近数相减引起有效数字损失，而得到较精确的结果。类似地，当e 很小时，当x和y很接近时，采用等号右边的算法，有效数字就不损失。一般地，当时，

30、可用Taylor展开取右端的有限项近似左端。若无法改变算法，直接计算时就要多保留几位有效数字。1.5.3 绝对值太小的数不宜作除数算法语言中已讲述，在机器上若用很小的数作除数会溢出，而且当很小的数稍有一点误差时，对计算结果影响很大。例1.12：如分母变为0.0011，也即分母只有0.0001的变化时商却引起了巨大变化，因此，在计算过程中既要避免两个相近数相减，更要避免再用这个差作除数。1.5.4 采用递推的算法计算机上使用的算法常采用递推化的形式，递推化的基本思想是把一个复杂的计算过程归结为简单过程的多次重复。这种重复在程序上表现为循环。递推化的优点是简化结构和节省计算量。下面用多项式求值问题

31、说明递推化方法。例1.13：设对于给定的x求下列n次多项多的值。（1.16）解：1. 用一般算法，即直接求和法，可知乘法的次数为：；加法次数为：n2. 逐项求和法令，则所以 记： 可以看出前K + 1项部分和等于前K项部分和再加上第K + 1项，因此有 = 1, 2, , n（1.17）初值应取为（1.18）容易看出逐步求和法所用乘法的次数为2n，加法次数为n。当n4后，。3. 秦九韶方法首先将多项式改写为令 则递推公式为： = 1, 2, , n （1.19）此方法称为秦九韶方法,也是多项式求值中常用的方法。此方法的计算量为：乘法n次，加法n次。同1、2相比，秦九韶方法的计算量小，且逻辑结构

32、简单。例1.14：用秦和韶方法求多项式在x = - 0.2的值。解：Ka5-KvK00.008330.00833v0 = a510.041670.04v1 = v0x+a420.166670.15867v2 = v1x+a330.50.46827v3 = v2x+a2410.90635v4 = v3x+a1510.81873v5 = v4x+a0（- 0.2）= 0.818731.6 算法的优劣我们知道，计算机的特点是运算速度快，存贮的信息量大，并能自动完成极其复杂的计算过程。计算机功能虽然很强，但是否可降低对算法的要求呢？许多事实说明，如果算法选择不当，计算机的利用率就得不到充分发挥，有时甚

33、至不能得到满意的解答。一个好的算法，要求有以下几个优点：1计算量小因此，计算量大小是衡量算法优劣的一项重要标准。 而后面将要介绍的高斯消去法求解同样的方程组，乘除法的运算次数不超过3074次，与Gramer法则比较计算量有天壤之别。方程组的阶数增大，计算量的差别还会更大。应当指出，数值方法的计算时间，由计算机速度和数值方法的效率而定。从某种意义上来说，对于减少计算时间，提高数值方法的效率甚至比提高计算机速度更为重要，因为算法研究所需要的代价要小得多。在估计计算量时，我们将区分主次抓住计算过程中费时较多的环节。比如，由于加减操作的机器时间比乘除少得多，对和式可以忽略加法而只统计乘法的次数。又如算

34、式中需要多次计算函数值，每求一次 时，通常需要进行多次加减乘除运算，因此对算式只要统计调用f 的次数就可以了。2存贮量小计算程序所占用的工作单元的数量称为算法的内存量。尽管计算机能贮存大量信息，但计算大型算题时有些微机仍不能使用。因此，尽量节约存贮量有经济价值，是衡量算法质量的又一标准。3逻辑结构简单设计算法时应考虑的另一个因素是逻辑结构问题。虽然计算机能够执行极其复杂的计算方案，但是计算方案的每个细节都需要编程人员制定。因此算法的逻辑结构应尽量简单，才能使编制程度、维修程序和使用程序比较方便。由此可见，虽然计算机是一种强有力的计算工具，但不能因此忽略对算法的研究。应该以计算量大小、存贮量多少

35、、逻辑结构是否简单作为评定算法优劣的标准。 4. 数值稳定 综上所述，我们总结出：1.7 复习几个常用公式微分中值定理和泰勒公式是学习数值计算方法的重要工具，许多数值解法可以直接从泰勒公式中得到，在使用这些方法时，所包含的误差估计也可以直接得到。同学们在微积分中已熟悉这些内容，但我们仍将作一个简略的介绍。1.7.1微分中值定理微分中值定理是反映函数与导数之间联系的重要定理。导数是由极限定义的，而计算机只能进行有限次运算，在计算机上不得不用函数值来进行微分或积分运算，它们是通向微分学的许多重要应用的桥梁。为了使大家能了解中值定理在几何上的直观背景，我们考察下述几何事实：曲线中间，有一点P，在那里

36、，曲线的切线平行于割线。图1.2 图1.3现在就来揭示这一几何事实所包含的数量关系。设曲线的方程为： 换句话说，曲线段是函数f（x）的图像，则曲线在点P(x, f(x)处的切线斜率就是f(x)，而割线的斜率等于 点P处的切线平行于割线，也就是二者斜率相等，于是得到一个公式 可归纳出以下定理。定理1 （Roll中值定理）设函数f(x)在a, b上连续，在（a, b）内可微，且f(a) = f (b)，则存在，使得f(x) = 0。定理2（Lagrange中值定理）设函数f(x)在a, b上连续，在（a, b）内可微，则存在，使得 (1.20)注1.1 若 f(a) = f (b)，则Lagran

37、ge中值定理化为Roll中值定理。注1.2 公式（1.20）称为Lagrange中值公式，它还有其他表示形式，若令则 ，这时，公式（1.20）可以写成 （1.21）1.7.2泰勒（Taylor）公式无论是手算或用其它计算工具去计算函数值，都归结为做有限次的四则运算，由此可见，研究如何用多项式近似地表达一个给定函数的问题是很必要的。一个给定的函数，如果能用多项式近似表达，那么，通过计算多项式的值，就可以得到给定函数的近似值。用多项式近似地表达一个函数，方式很多，我们这里要谈的只是其中一种，我们的问题是：给了一个函数f (x)，要找一个在指定点x = x0（为简单计，以下先设x0 = 0）附近与f

38、 (x)很近似的多项式 (1.22)那么，要找的多项式应满足什么样的条件呢？从几何上看，y = p(x)与y = f (x)代表两条曲线，要想多项式p (x)在点x = 0附近与函数f(x)很近似，就是要曲线y = p (x)与曲线y = f (x)在点(0, f(0)附近很靠近。很明显，首先应该要求曲线y = p (x)与曲线y =f (x)交于点（0, f(0)）（图1.4）也就是要求多项式p (x)满足条件 (1.23)要想曲线y = p(x)与曲线y = f (x)在（0, f(0)）附近靠得更近，应该进而要求它们在点（0, f(0)）处有公共切线（图1.4），也就是要求多项式p (x

39、)同时满足下列两个条件： (1.24)满足这两个条件的多项式p (x)可以有很多。试看图(1.4)曲线y = pi (x)都与曲线y = f (x)在点（0, f(0)）处有公共切线，但与曲线y = f的靠近程度却可以不一样。图1.4要想从中找出与曲线y = f (x)靠得更近的，就要进一步来考察它们的弯曲情况。我们要找的显然是与曲线y = f (x)向同一方向弯曲，这条曲线y = p (x)应该满足条件p(0) = f (0)，即p (x)应同时满足下列三个条件： (1.25)由此可以推想，假如在点x = 0处，p (x)与f (x)的三阶导数，以至更高阶导数都相等，那么在点（0, f (0

40、)）附近，曲线y = p (x)与曲线y = f (x)的靠近程度就会更高。综上所述，所要找的多项式p (x)应满足下列条件： (1.26)现在，根据条件（1.26），我们就可以确定所要找的近似多项式的具体形状了。首先，由（1.22）得到 于是，条件（1.26）就变成 即 代入(1.22)式，就得到： (1.27)这就是我们要找的多项式，这个多项式称为f (x)在x0 = 0这点的泰勒多项式，记为pn (x)。为了进一步研究这个多项式和f (x)究竟差多少，我们必须分析误差项 为推导rn (x)的表达式，我们假定f (x)在点x0 = 0附近有直到n + 1阶的连续导数，注意从rn(x)的定义

41、可见 于是由微积分学基本定理及分部积分法，得 继续实行分部积分，最后利用。便得： (1.28)(1.28)式称为f (x)在点x0 = 0的积分型Taylor余项公式。由(1.23)式，我们还可以导出另一种形式的余项公式：设在0 t x上的最大值为M，最小值为m，不妨设x 0，此时。因此 而 所以上式即 由连续函数的介值定理，应有x, 0 x x，使 即 (1.29)此式为f (x)在x0 = 0点的拉格朗日型余项公式，也是最常用的一种Taylor余项公式。rn(x)通常称为n阶余项，利用rn(x)，我们可以写成： (1.30)(1.30)式称为f (x)在x0 = 0点的Taylor公式。对

42、任意点x0，f (x)在x0点的Taylor公式是： 例1.15 Taylor展开1.8函数计算的误差估计设一元函数f (x)具有二阶导数，自变量x的一个近似值x*，f (x)的近似值为f (x*)，用f (x)在x*点的Teylor展开估计误差，可得 其中x在x与x*这间，如果与有相同数量级，而很小，则可得 （1.31）分别为f (x*)的一个近似误差限与相对误差限。如果f为多元函数，自变量为x1, xn，其近似值为，则类似于一元函数可用多元函数f (x1, x2, , xn)的Taylor展开，取一阶近似的误差限 （1.32）及相对误差限 （1.33）若把（1.33）用到两个或多个数的算术

43、运算中，则可得到近似数及的四则运算误差估计： （1.34） （1.35） （1.36）例1.16 已测得某场地长l的值为l* = 110m，宽d的值为d* = 80m，已知，试求面积S = ld的绝对误差限与相对误差限。解 因S = ld，由（1.2.5）知 其中，从而有 相对误差限为 病态问题与条件数对一个数值问题，往往由于问题本身而使计算结果相对误差很大，这种问题就是病态问题。例如计算函数值f (x)，若x的近似值为x*，其相对误差为，函数值f (x*)的相对误差为，它们相对误差之比的绝对值为 (1.37）Cp称为计算函数值f (x)的条件数，如果Cp很大，将引起函数值f (x*)的相对误

44、差很大，出现这种情况时，就认为问题是病态的。例如，则Cp = n，它表示相对误差可能放大n倍，如n = 10，有f (1) = 1，f (1.02) 1.24，若x = 1，x* = 1.02，则自变量相对误差为2%，而函数值f (1.02)的相对误差为24%，这时就认为问题是病态的。一般情况下若条件数Cp 10，则认为是问题病态，Cp越大病态越严重。第一章 习题1什么是数值计算方法？它与数学科学和计算机的关系如何？2. 数值计算方法的主要研究对象是什么？3什么是算法？如何判断数值算法的优劣？4. 误差为什么是不可避免的？用什么标准来衡量近似值是准确的？5列出科学计算中的误差来源，并说出截断误

45、差与舍入误差的区别。6什么是绝对误差与相对误差？什么是近似数的有效数字？它与绝对误差和相对误差有何关系？7. 什么是数值稳定的算法？如何判断算法稳定？为什么不稳定算法不能使用？8下列各数都是经过四舍五入得到的近似数，试分别指出其绝对误差限、相对误差限和有效数字位数 9求方程的两个根，使它们具有4位有效数字。10计算下列式子，要求具有4位有效数字。（1） （2）11序列中由下列两种递推公式生成（1）（2）采用5位有效数字舍入计算，试分别考察递推计算xn与yn是否稳定。12. 对于 计算定积分： 13判断下列命题的正确性： （1）一个问题的病态性如何，与求解它的算法有关系。（2）解对数据的微小变化

46、高度敏感是病态的。（3）高精度运算可以改善问题的病态性。（4）用一个稳定的算法计算良态问题一定会得到好的近似值。（5）用一个收敛的迭代法计算良态问题一定会得到好的近似值。（6）两个相近数相减必然会使有效数字损失。（7）计算机上将1000个数量级不同的数相加，不管次序如何结果都是一样的。14考虑二次代数方程的求解问题ax2 + bx + c = 0. 求解公式是. 与之等价地有. 对于a = 1, b = -100 000 000 , c = 1应当如何选择算法？15考虑数列xi, i = 1, n, 它的统计平均值定义为它的标准差数学上它等价于作为标准差的两种算法，你如何评价它们的得与失？16

47、. 一个班级第一小组10名同学的期末数学考试成绩为： 85 78 91 73 65 55 80 70 82 73请编程序计算 （1）该组的平均成绩和标准差； （2）将成绩从高到低排序。17. 设 ，试对给定x 设计导数 的求值算法。18. 设计求平方值小于1000的最大整数的算法并编程序计算。19. 一球从100 m 高度落下，每次落地后反弹回原高度的一半，再落下。在球第十次落地时，共经过多少路程？第十次下落多高？请设计算法并编程序计算。20. 找出100到999之间的整数中所有等于它每位数字立方和的数。例如 153=13+53+3321. 求所以满足条件的四位数abcd： 这四位数是11的倍

48、数； a,b，c,d是小于10的互不相同的自然数； b+c=a； bc是完全平方数（例如b=2，c=5，则bc=25，是完全平方数）。22. 已知四位数3025有一个特殊的性质：它的前两位数字30和后两位数字25的和是55，而55的平方刚好等于该数（552=3025）。试编程输出具有这种性质的所有四位数。23. 编程找出四个互不相同的四位数，它们中任意两数之和为偶数，任意三数之和可以被3 整除，而且这四个数的和越小越好。（已知它们的和不大于50）。24. 求完全数：如果一个数（除去本身）等于它的所有约数的和，这个数就称为完全数。 试输出M和N之间完全数。25. 孪生数：如果A的约数之和等于B，

49、B的约数之和等于A，A和B称为孪生数。试找出M和N之间的孪生数。26. 埃及分数：古埃及人有一个非常奇特的习惯，他们喜欢把一个分数表示为若干个分子为1，分母不同的分数的和的形式。例如：7/8=1/2+1/3+1/24。试设计用埃及分数算法求分数，并验证。27. 用19这9个数组成三个三位的平方数，要求每个数字只准使用一次。28. 某班30个人，在开新年联欢会时，全班按学号从1排到30，围成一个圆圈。大家商定从1号开始报数，报到5，出来演个节目，演过节目的同学，不再参加报数。然后接着报数。试编程输出最后演节目的同学的学号。29. 求守形数： 某数的平方其底位与该数本身相同，则称该数为守形数。 求21000中的守形数。 例如：25*25=625 ，625的底位25相同，称25为守形数。30. 设矩阵 请编程序计算 31. 的值可以由下列无穷级数得到： 构造一个算法，求的近似值，。32. 豆子下落问题： 如图所示一个容器，有1000粒豆子从入口一个一个地落下，通过六层隔板落入下面7个格子，豆子经过隔板向左右两个方向的机会相等，编一个程序计算每个格子中豆子的数目。