第1章 数值分析与科学计算引论

上页下页上页下页1.1.1数学科学与数值分析1.1数值分析的对象、作用与特点数学是科学之母，科学技术离不开数学，它通过建立数学模型与数学产生紧密联系，数学又以各种形式应用于科学技术各领域.数值分析也称计算数学，是数学科学的一个分支,它研究用计算机求解各种数学问题的数值方法及其理论的与软件实现，用计算机求解科学技术问题通常经历以下步骤：第1章数值分析与科学计算引论上页下页①根据实际问题建立数学模型.②由数学模型给出数值计算方法.③根据数值计算方法编制算法程序（数学软件）在计算机上算出结果.第①步建立数学模型是应用数学的任务，而第②,③步就是计算数学的任务，也就是数值分析研究的对象，它涉及数学的各个分支，内容十分广泛.作为“数值分析”课程，只介绍其中最基本、最常用的数值计算方法及其理论，它包括插值与数值逼近，数值微分与积分，线性方程组的数值求解，非线性方程与方程组求解，特征值计算，常微分方程数值解等.上页下页它们都是以数学问题为研究对象，只是不像纯数学那样只研究数学本身的理论，而是把理论与计算紧密结合，着重研究数学问题的数学算法及其理论.与其它数学课程一样，数值分析也是一门内容丰富，研究方法深刻，有自身理论体系的课程，既有纯数学高度抽象性与严密科学性的特点，又有应用广泛性与实际试验高度技术性的特点，是一门与计算机使用密切结合，实用性很强的数学课程.上页下页实际问题模型设计算法设计问题的数值解上机计算程序设计数值分析是计算数学的一个主要部分，方法解决科学研究或工程技术问题，一般按如下途径进行：上页下页(1)绘制某一地区的地形图,用空中航测方法,空中连续拍照.（实际问题）(2)为形成三维地形图,建立了一个大型超定线性方程组.（数学模型）(3)采用最小二乘方法求解该方程组的最小二乘解,然后再整体平滑.（计算方法）例如:(4)编程序,形成一个大型程序,上机进行计算.（上机）上页下页1.1.2计算数学与科学计算几十年来由于计算机及科学技术的快速发展，求解各种数学问题的数值方法也愈来愈多地应用于科学技术各领域，新的计算性交叉学科分支不断涌现，如计算力学，计算物理，计算化学，计算生物学，计算经济学等，统称科学计算，它涉及数学的各个分支，研究它们适合于计算机编程的算法就是计算数学的研究范畴.计算数学是各个计算性学科的共性基础，兼有基础性、应用性和边缘性的数学学科.上页下页科学计算是一门工具性、方法性、边缘性的学科，发展迅速，它与理论研究和科学实验成为现代科学发展的三种主要手段，它们相辅相成又互相独立.在实际应用中导出的数学模型其完备形式往往不能方便地求出精确解，于是只能转化为简化模型求其数值解，如将复杂的非线性模型忽略一些因素而简化为可以求出精确解的线性模型，但这样做往往不能满足近似程度的要求，因此使用数值方法直接求解做较少简化的模型，可以得到满足近似程度要求的结果，使科学计算发挥更大的作用，这正是得益于计算机与计算数学的快速发展.上页下页数值分析也称为计算方法，它与计算工具发展密切相关.在电子计算机出现之前，计算工具只有算盘，算图，算表，算尺和手摇及电动计算机，计算方法只能计算规模较小的问题.计算方法是数学的一个组成部分，很多方法都与当时的数学家名字相联系，如牛顿(Newton)插值公式，方程求根的牛顿法，解线性方程组的高斯(Gauss)消去法，多项式求值的秦九韶算法，计算积分的辛普森(Simpson)公式等.这表明计算方法就是数学的一部分，它没有形成单独的学科分支.只是在计算机出现以后，才使计算方法迅速发展并形成数学学科的一个独立分支——计算数学.1.1.3计算方法与计算机上页下页当代计算能力的大幅度提高既来自于计算机的进步，也来自于计算方法的进步，两者发展相辅相成又互相促进.例如，1955年至1975年的20年间计算机的运算速度提高数千倍，而同一时期解决一定规模的椭圆形偏微分方程计算方法的效率提高约一百万倍，说明计算方法的进步对提高计算能力的贡献更为重要，由于计算规模的不断扩大和计算方法的发展启发了新的计算机体系结构，诞生并发展了并行计算机.而计算机的更新换代也对计算方法提出了新的标准和要求.自计算机诞生以来，经典的计算方法也已经历了一个重新评价、筛选、改造和创新的过程，与此同时涌现了许多新概念、新课题和能发挥计算机解题潜力的新方法，这就构成了现代意义的计算数学.上页下页能用计算机计算的“数值问题”是指输入数据（即问题中的自变量与原始数据）与输出数据（结果）之间函数关系的一个确定而无歧义的描述，输入输出数据可用有限维向量表示.根据这种定义，“数学问题”有的是“数值问题”，如线性方程组求解.也有不是“数值问题”的“数学问题”，如常微分方程1.1.4数值问题与算法22,(0)0,dyxyydx它不是数值问题，因为输出不是数据而是连续函数y=y(x).但只要将连续问题离散化，使输出数据是y(x)在求解区间[a,b]上的离散点xi=a+ih(i=1,2,…,n)上的近似值，就是“数值问题”.数值问题可用各种数值方法求解，这些数值方法就是算法.计算方法就是研究各种“数值问题”的算法.上页下页计算的基本单位称为算法元，它由算子、输入元和输出元组成.算子可以是简单操作，如算术运算(+,-,×,/)、逻辑运算，也可以是宏操作，如向量运算、数组传输、基本初等函数求值等；输入元和输出元可分别视为若干变量或向量.由一个或多个算法元组成一个进程，它是算法元的有限序列，一个数值问题的算法是指按规定顺序执行一个或多个完整的进程.通过它们将输入元变换成一个输出元.面向计算机的算法可分为串行算法和并行算法两类，只有一个进程的算法适合于串行计算机，称为串行算法.有两个以上进程的算法适合于并行计算机，称为并行算法.上页下页对于一个给定的数值问题可以有许多不同的算法，它们都能给出近似答案，但所需的计算量和得到的精确程度可能相差很大.一个面向计算机，有可靠理论分析且计算复杂性好的算法计算一个好算法.理论分析主要是连续系统的离散化及离散型方程的数值问题求解，它包括误差分析、稳定性、收敛性等基本概念，它刻画了算法的可靠性、准确性.计算复杂性包含计算时间复杂性与存储空间复杂性两个方面.在同一规模、同一精度条件下，计算时间少的算法为计算时间复杂性好，而占用内存空间少的算法为存储空间复杂性好，它实际上就是算法中计算量与存储量的分析.上页下页对解同一问题的不同算法其计算复杂性可能差别很大，例如解n阶的线性方程组，若依照克拉默(Cramer)法则用行列式算法，在“线性代数”课程中只介绍解的存在唯一性及有关理论和精确解法，用这些理论和方法还不能在计算机上解上百个未知数的方程组，更不用说求解十几万个未知数的方程组了。上页下页例如，线性方程组的Gramer法则表明：如果n阶线性方程组Ax=b的系数矩阵A非奇异，则此方程组有唯一的解，并且其解可以通过系数表示为：,,,2,1,niddxii其中：Addet，iiAddet，这里Ai是将A的第i列换为b而得到的矩阵。上页下页这一结果把线性方程组的求解问题归结为计算n+1个n阶行列式的问题。而对于n阶行列式的计算，理论上又有著名的Laplace展开定理：ininiiiiAaAaAaAd2211det其中Aij表示元素aij的代数余子式。按照这一定理我们就可以从二阶行列式出发，逐步递推地计算出任意阶行列式的值。这样，理论上我们就有了一种非常漂亮的求解线性方程组的方法。然而我们做一简单的计算就会发现，由于这一方法的运算量大的惊人，以至于完全不能用于实际计算。上页下页设计算k阶行列式所需要的乘法运算的次数为km，则容易推出1kkkmkm，于是，我们有!23)1()2)(1()1(])1()1[(21nnnnnnnnnmnnnnnmnmnnn这样，利用Gramer法则和Laplace展开定理来求解一个n阶线性方程组，所需要的乘法运算的次数要高于)!1(!)1(nnn上页下页它远远超出目前所了解的人类文明历史！然而如果改用下一章将要介绍的消元法，则可在不到一秒钟之内完成这一计算任务。13101536.3100329.436524360010!26172610因此，若在一个“百亿次/秒”次的计算机上求解一个25阶线性方程组，则至少需要亿年，一百亿次/秒秒/小时小时/天天/年计算的总次数上页下页因此要求解这类问题还应根据方程特点，研究适合计算机使用的，满足精度要求，计算时间省有效算法及其相关理论。若用高斯(Gauss)列主元消去法(见第5章)解这个线性方程组则只需做相对较少次数的乘除运算。这表明算法研究的重要性，也说明只提高计算机速度，而不改进和选用好的算法是不行的。上页下页第一，面向计算机，要根据计算机特点提供切实可行的有效算法。即算法只能包括加、减、乘、除运算和逻辑运算，这些运算是计算机能够直接处理的运算。第二，有可靠的理论分析，能任意逼近并达到精确要求，对近似算法要保证收敛性和数值稳定性，还要对误差进行分析。这些都建立在相应数学理论的基础上。综上所述，数值分析是研究数值问题的算法，概括起来有四点：上页下页第三，要有好的计算复杂性，时间复杂性好是指节省时间，空间复杂性好是指节省存储量，这也是建立算法要研究的问题，它关系到算法能否在计算机上实现。第四，要有数值实验，即任何一个算法除了从理论上满足上述三点外，还要通过数值实验证明是行之有效的。上页下页根据“数值分析”课程的特点，学习时我们首先要注意掌握方法的基本原理和思想，要注意方法处理的技巧及其与计算机的结合，要重视误差分析、收敛性及稳定性的基本理论；其次，要通过例子，学习使用各种数值方法解决实际计算问题；最后，为了掌握本课内容，还应做一定数量的理论分析与计算练习。由于本课内容包括了微积分、线性代数、常微分方程的数值方法，大家必须掌握这几门课程的基本内容才能学好这门课程。上页下页1.2.1误差来源与分类1.模型误差:数学模型与实际问题之间出现的误差.在建立数学模型过程中,不可能将所有因素均考虑,它是对被描述的实际问题进行抽象，进行必要的简化，因而是近似的，这就带来了与实际问题的误差。1.2数值计算的误差在运用数学方法解决实际问题的过程中，每一步都可能带来误差.上页下页2.观测误差（数据误差）:测量已知参数时，观测数据带来的误差。数学模型中的已知参数，多数是通过测量得到.而测量过程受工具、方法、观察者的主观因素、不可预料的随机干扰等影响必然带入误差.3.截断误差（方法误差）:在设计算法时，近似处理带来的误差，即近似值与精确值之间的误差。数学模型常难于直接求解，往往要近似替代，简化为易于求解的问题，这种简化带入的误差称为方法误差或截断误差.上页下页例如可微函数f(x)用泰勒(Taylor)多项式()2(0)(0)(0)()(0)1!2!!nnnfffPxfxxxn近似代替，则数值方法的截断误差是(1)1()()()(),0.(1)!nnnnfRxfxPxxxn在与之间4.舍入误差:由于计算机的字长是有限的,每一步运算均需四舍五入，由此产出的误差.例如，用3.14159近似代替π，产生的误差R=π-3.14159=0.0000026…就是舍入误差.上页下页此外，由原始数据或机器中的十进制数转化为二进制数产生的初始误差对数值计算也造成影响，分析初始数据的误差通常也归结为舍入误差.研究计算结果的误差是否满足精度要求就是误差估计问题，在数值分析课程中不分析讨论模型误差和数据误差；本书主要讨论算法的截断误差与舍入误差，而截断误差将结合具体算法讨论.上页下页舍入误差的产生往往带有很大的随机性，讨论比较困难，在问题本身呈病态或算法稳定性不好时，它可能成为计算中误差的主要部分；至于测量误差，我们把它作为初始的舍入误差看待.误差分析是一门比较艰深的专门学科.在数值分析中主要讨论截断误差及舍入误差.但一个训练有素的计算工作者，当发现计算结果与实际不符时，应当能诊断出误差的来源，并采取相应的措