数值计算简明教程精品文稿.ppt

数数值计算算简明教程明教程数值分析简明教程第1页，本讲稿共101页数值分析简明教程研究算法的意义 尽管计算机的运算速度高，可以承担大运算量的工作，但这并不意味着我们可随意选择 计算机上的算法，相反的，算法的优劣决定着计算效率的高低，能否正确地制定算法也是科学计算成败的关键。第2页，本讲稿共101页数值分析简明教程什么是算法我们所说的“算法”必须是构造性的数值方法，即不但要论证问题的可解性，而且解的构造是通过数值演算过程来完成的。同传统的近似计算方法不同，我们要研究的算法是为电子计算机提供的，解题方案中的每个细节都必须准确的定义，并且要完整地描述整个解题过程。我们所说的“算法”不仅仅是单纯的计算公式，而是指解题方案的准确而完整的描述。计算公式是算法的核心概念。计算机上使用的算法，其计算公式常采用递推化的形式。递推化的基本思想是将一个复杂的计算过程归结为简单过程的多次重复。这种重复在算法上表现为循环，描述是容易的。第3页，本讲稿共101页数值分析简明教程多项式求值的秦九韶算法设要求对给定的求下列多项式的值由于该式有如下嵌套形式：故有如下求该多项式值的秦九韶算法秦九韶算法：秦九韶算法的特点在于，它通过一次式的反复计算，逐步得出高次多项式的值。具体的说，他将一个次多项式的求值问题归结为重复计算个一次式来实现。第4页，本讲稿共101页数值分析简明教程方程求根的二分法 设函数在上连续，且，假定在上有唯一的实根。考察有根区间，取中点将它分为两半。然后进行根的搜索，即检查和是否同号。若确定同号，说明所求的根在的右侧，这时令，否则必在左侧，这时令，于是我们就得到了一个长度压缩了一半的有根区间，对于有根区间施行同样手续可得到新的有根区间，反复如此我们可得到一系列的有根区间：令，则二分过程中可获得一个近似根的序列逐步逼近所求的根。第5页，本讲稿共101页数值分析简明教程误差分析不可忽视在研究算法的同时必须注意误差分析。否则，一个合理的算法也可能得出错误的结果。比如，两个相近的数相减，会造成有效数字的严重损失。两个相差悬殊的数作加减运算会造成“小数”吃“大数”的后果等等。第6页，本讲稿共101页数值分析简明教程误差的来源数值计算中的近似是正常的，计算误差是不可避免的：为要进行数值计算，我们往往把实际问题归结为数学问题，然后建立起合适的数学模型。而这些模型描述的近似必然会产生误差；在数值计算过程中也不可避免的会产生误差，本书主要考察截断误差和舍入误差。第7页，本讲稿共101页数值分析简明教程误差限和有效数字 设以代表数的近似值，误差的绝对值的上界称为近似值的绝对误差限绝对误差限；称为相对误差限相对误差限，如果满足：对于 的近似值（规格化形式）其中，是1-9 之间的自然数，如果误差则称近似值有位有效数字有效数字，或称准确到第位。第8页，本讲稿共101页数值分析简明教程第一章第一章 插值方法插值方法1 问题的提出2 拉格朗日插值公式3 插值余项4 埃特金插值方法5 牛顿插值公式6 埃尔米特插值7 分段插值法8 样条函数9 曲线拟合的最小二乘法第9页，本讲稿共101页数值分析简明教程引言引言 实际问题中碰到的函数是各种各样的。有的表达很复杂，有的甚至给不出数学式子，而只是给出了一些离散数据譬如某些点的函数值和导数值。面对这种情况，一个很自然的想法就是构造某个简单的函数作为要考察的函数的近似。如果要求近似函数取给定的离散数据，则称之为的插值函数。实用上，我们常取结构相对比较简单的代数多项式作为插值函数,这就是所谓的代数插值。本章先讨论代数插值，然后在此基础上进一步研究所谓的样条插值。第10页，本讲稿共101页数值分析简明教程问题的提出问题的提出“温故而知新”。本节将从插值方法的角度重新审视泰勒公式，从而提出所谓的泰勒插值问题，继而在此基础提出拉格朗日插值问题。下述插值问题称作泰勒插值泰勒插值问题：问题问题求作次数多项式，使满足条件，这里为一组已知数据。对于给定函数，设已知导数值则上述插值问题的解就是泰勒多项式：第11页，本讲稿共101页数值分析简明教程拉格朗日插值拉格朗日插值 如果仅仅给出一系列节点上的函数值则插值问题可表述为如下：问题问题求作次数多项式，使满足条件这就是所谓的拉格朗日（拉格朗日（Lagrange）插值）插值。点（它们互不相同）称为插值节点。我们将从最简单的线性插值出发，进而讨论稍微复杂的抛物插值，通过对这两种简单情形进行归纳最后得出拉格朗日公式的一般情形。第12页，本讲稿共101页数值分析简明教程线性插值线性插值问题问题求作一次式，使满足条件从几何图形上看，表示过两点的直线，因此可表为如下对称形式：其中和分别满足条件可见，插值问题的解可以通过插值基函数和的组合得出，且组合系数分别是所给数据。第13页，本讲稿共101页数值分析简明教程拋物插值拋物插值 问题问题求作二次式，使满足条件二次插值的几何解释是用通过三个点的抛物线来近似考察曲线，故称为拋物插值。类似于线性插值，令易知，应满足条件故有，类似的可以构造出。第14页，本讲稿共101页数值分析简明教程拉格朗日插值的一般情形拉格朗日插值的一般情形 仿照前述作法，对于求作次数多项式，使满足条件的问题，我们可构造插值基函数，它们都是次数小于的多项式，且满足条件则有如下拉格朗日插值公式：第15页，本讲稿共101页数值分析简明教程拉格朗日余项定理拉格朗日余项定理 依据的数据表构造出的插值函数，在插值点处计算作为的近似值总有误差，称误差为插值余项。下面给出著名的拉格朗日余项定理拉格朗日余项定理：定理定理设区间含有节点，而在该区间内有连续直到阶导数，且已给，则当时，对于拉格朗日公式确定的成立式中是与有关的点，它包含在由和所界定的范围内，因而。第16页，本讲稿共101页数值分析简明教程误差的事后估计误差的事后估计 下面介绍另一种误差估计方法。考察三个节点，对于给定的插值点，设用和进行线性插值求的一个近似值为，用和进行线性插值求的另一个近似值为，若假设在上变化不大，则有，进一步整理得如下估计式，由此可见，插值结果的误差可由两个结果，的偏差来估计。这种直接利用计算结果估计误差的方法称为事后误差估计事后误差估计法法。第17页，本讲稿共101页数值分析简明教程埃特金插值方法埃特金插值方法 本节介绍的埃特金插值方法埃特金插值方法可以灵活的增加插值节点，且具有所谓的”承袭性”。对于给定插值点，如果除顺序排列的个节点外再增加一个节点进行次插值，则插值结果依赖于给定次数和节点，我们记这一结果为。利用拉格朗日插值公式易知，利用两个次插值与再作线性插值，结果可得到次插值，既有递推公式据此可以通过逐步线性插值生成高次插值。第18页，本讲稿共101页数值分析简明教程具有承袭性的插值公式具有承袭性的插值公式 线性插值公式可以写成如下形式：其中，其修正项的系数，再修正可以进一步得到拋物插值公式其中以上讨论说明，为建立具有承袭性的插值公式，需要引进差商并研究其性质。第19页，本讲稿共101页数值分析简明教程差商及其性质差商及其性质 对给定函数，记表示关于节点的阶差商差商，一般地，阶差商可以递推定义为差商具有明显的承袭性，因而可以从作为零阶差商的函数值出发，逐步生成高阶差商，且有显示表达式：由此可知，改变式中的节点次序，差商值保持不变。这种性质称为差商的对称性对称性。第20页，本讲稿共101页数值分析简明教程差商形式的插值公式差商形式的插值公式再考虑拉格朗日插值问题：问题问题求作次数多项式，使满足条件，利用差商其解亦可表达为如下形式：这种差商形式的插值公式称为牛顿插值公式牛顿插值公式。第21页，本讲稿共101页数值分析简明教程埃尔米特插值埃尔米特插值 在某些问题中，为了保证插值函数能更好密和原来的函数，不但要求“过点”，即两者在节点上有相同的函数值，而且要求“相切”，即在节点上还有相同的导数值，这类插值称作埃尔米特插值埃尔米特插值。问题问题求作三次式，使满足设令式中，易知满足特定的插值条件，从而容易构造出来，它们的表达式分别是：第22页，本讲稿共101页数值分析简明教程高次插值的龙格现象高次插值的龙格现象 对于代数插值来说，插值多项式的次数很高时，逼近效果往往很不理想。例如，考察函数,设将区间分为等份，表示取个等分点作节点的插值多项式，如下图所示，当增大时，在两端会发出激烈的振荡，这就是所谓龙格现龙格现象象。第23页，本讲稿共101页数值分析简明教程分段插值的概念分段插值的概念 所谓分段插值，就是将被插值函数逐段多项式化。一般来说，分段插值方法的处理过程分两步，先将所考察的区间作一分划并在每个子段上构造插值多项式，然后把它们装配在一起，作为整个区间上的插值函数，即称为分段多项式分段多项式。如果函数在分划的每个子段上都是次式，则称为具有分划的分段次式。第24页，本讲稿共101页数值分析简明教程分段线性插值分段线性插值满足条件具有分划的分段一次式在每个子段上都具有如下表达式：其中，而。第25页，本讲稿共101页数值分析简明教程分段三次埃尔米特插值分段三次埃尔米特插值问题问题求作具有分划的分段三次式，使成立解解由于每个子段上的都是三次式，且满足埃尔米特插值条件：所以其中，且有第26页，本讲稿共101页数值分析简明教程样条函数的概念样条函数的概念所谓样条函数，从数学上讲，就是按一定光滑性要求“装配”起来的分段多项式，具体的说，称具有分划的分段次式为次样条函数样条函数，如果它在每个内节点上具有直到阶连续导数。点称为样条函数的节点。特别地，零次样条就是人们熟知的阶梯函数，一次样条则为折线函数。第27页，本讲稿共101页数值分析简明教程三次样条插值三次样条插值 问题问题求作具有分划的三次样条插值，使满足注意到三次样条插值可以看成是一种特殊的分段三次埃尔米特插值，取作为参数，可知，式中，而同前。依据光滑性条件可以导出所满足的代数方程组，它是个三对角方程组。第28页，本讲稿共101页数值分析简明教程第第 2 章章 数值积分数值积分1 机械求积2 牛顿-柯特斯公式3 龙贝格算法4 高斯求积公式5 数值微分第29页，本讲稿共101页数值分析简明教程引言引言 依据微积分基本定理,只要找到被积函数的原函数，便有牛顿-莱伯尼兹公式由于大量的被积函数找不到用初等函数表示的原函数，而实验测量或数值计算给出的通常是一张函数表，所以牛顿-莱伯尼兹公式往往不能直接运用。因此有必要研究积分的数值计算问题。第30页，本讲稿共101页数值分析简明教程数值求积的基本思想数值求积的基本思想 依据积分中值定理，就是说，底为而高为的矩形面积恰恰等于所求曲边梯形的面积。取内若干个节点处的高度，通过加权平均的方法生成平均高度，这类求积公式称机械求积公式机械求积公式：式中称为求积节点求积节点，称为求积系数求积系数，亦称伴随节点的权权。第31页，本讲稿共101页数值分析简明教程代数精度的概念代数精度的概念数值求积方法是近似方法，为保证精度，自然希望所提供求积公式对于“尽可能多”的函数是准确的。如果机械求积公式对均能准确成立，但对不准确，则称机械求积公式具有次代数精度次代数精度。事实上，令求积公式对准确成立，即得可见，在求积公式节点给定的情况下，求积公式的构造问题本质上是个解线性方程组的代数问题。第32页，本讲稿共101页数值分析简明教程插值型的求积公式插值型的求积公式 设已给在节点的函数值，作插值多项式其中由于多项式的求积是容易的，令这样得到的求积公式称为插值型插值型的求积公式，其求积系数为定理定理机械求积公式至少有次代数精度的充分必要条件是它是插值型的。第33页，本讲稿共101页数值分析简明教程牛顿柯特斯公式牛顿柯特斯公式 设分为等份，步长，取等分点构造出的插值型求积公式（其中）称作阶牛顿柯特斯牛顿柯特斯 公式公式。一阶和二阶牛顿柯特斯公式分别是梯形公式梯形公式和辛甫生公式辛甫生公式四阶牛顿柯特斯公式，也称为柯特斯公式柯特斯公式：第34页，本讲稿共101页数值分析简明教程几种低阶求积公式的代数精度几种低阶求积公式的代数精度 阶的牛顿柯特斯公式至少有次代数精度，事实上，二阶的辛甫生公式与四阶的柯特斯公式在精度方面会获得“额外”的好处，它们分别有3 次和5 次代数精度。因此，在几种低阶的牛顿柯特斯公式中，人们更感兴趣的是梯形公式（它最简单、最基本），辛甫生公式和柯特斯公式。第35页，本讲稿共101页数值分析简明教程几种低阶求积公式的余项几种低阶求积公式的余项 利用线性插值的余项公式以及积分中值定理，我们可以得到梯形公式的余项：利用埃尔米特插值的余项公式以及积分中值定理我们可以得到辛甫生公式的余项：另外，我们可以得到如下柯特斯公式的积分余项：第36页，本讲稿共101页数值分析简明教程复化求积公式复化求积公式在使用牛顿柯特斯公式时，通过提高阶的途径并不总能取得满意的效果，为了改善求积公式的精度，一种行之有效的方法是复化求积。将分为等份，步长，分点所谓复化求积公式，就是先用低阶的求积公式求得每个子段上的积分值，然后用作为积分的近似值。复化梯形公式有如下形式：其余项为：第37页，本讲稿共101页数值分析简明教程梯形法的递推化梯形法的递推化实际计算中，由于要事先给出一个合适的步长往往很困难，所以我们往往采用变步长的计算方案，即在步长逐步分半的过程中，反复利用复化求积公式进行计算，直到所求得的积分值满足精度要求为止。设表示复化梯形求得的积分值，其下标是等分数，由此则有递推公式其中，第38页，本讲稿共101页数值分析简明教程 梯形法的加速梯形法的加速 梯形法的算法简单，但精度低，收敛的速度缓慢。如何提高收敛速度以节省计算量呢？由复化梯形公式的截断误差公式可得，整理得，由此可知，这样导出的加速公式是辛甫生公式：第39页，本讲稿共101页数值分析简明教程龙贝格算法龙贝格算法 我们可以在步长逐步分半过程中将粗糙的积分值逐步加工为精度较高的积分值：或者说将收敛缓慢的梯形值序列加工成收敛迅速的积分值序列，这种加速方法称为龙贝格算法龙贝格算法。第40页，本讲稿共101页数值分析简明教程高精度的求积公式高精度的求积公式 不失一般性，设，考虑下列求积公式我们将会看到，适当的选取求积节点可以使上述求积公式具有次代数精度，这种高精度的求积公式称为高斯（高斯（Gauss）公式）公式，高斯公式的求积节点称为高斯点高斯点。第41页，本讲稿共101页数值分析简明教程高斯点的基本特性高斯点的基本特性 尽管高斯点的确定原则上可以化为代数问题，但是由于所归结的方程组是非线性的，而它的求解存在实质性的困难，所以我们要从研究高斯点的基本特性着手解决高斯公式的构造问题。设是求积公式中的高斯点，令则有如下结论：定理定理 节点是高斯点的充分必要条件是多项式与一切次数的多项式正交，即成立第42页，本讲稿共101页数值分析简明教程勒让德多项式勒让德多项式 以高斯点为零点的次多项式称为勒让德勒让德(Legendre)多项式多项式。一般的，勒让德多项式可以依据来求得。第43页，本讲稿共101页数值分析简明教程数值微分的差商公式数值微分的差商公式按照数学分析的定义，导数是差商当时的极限。于是我们可以用差商作为导数的近似值从而获得一种简单的数值微分方法。如果所用的差商分别为向前、向后以及中心差商，那么我们就可分别建立如下的三种数值微分法其中第三种方法称为中点方法中点方法。第44页，本讲稿共101页数值分析简明教程中点方法的加速中点方法的加速由于中点法的余项展开式具有下列形式：其中系数与步长无关，由此，我们可以在步长分半的过程中将中点法加速，即有如下方法：第45页，本讲稿共101页数值分析简明教程插值型的求导公式插值型的求导公式 设已知在节点的函数值，利用所给定数据作次插值多项式，并取的值作为的近似值，这样建立的数值公式统称为插值型求导公式。应当指出，即使与处处相差不多，与在某些点仍然可能出入很大。一般的，我们只用它求取某个节点上的导数值，这是我们才有某种意义下比较准确的余项公式来保证导数值的精度。第46页，本讲稿共101页数值分析简明教程第三章第三章 常微分方程的差分方法常微分方程的差分方法1 欧拉方法2 改进的欧拉方法3 龙格-库塔方法4 亚当姆斯方法5 收敛性与稳定性6 方程组与高阶方程的情形7 边值问题第47页，本讲稿共101页数值分析简明教程引言引言科学技术当中常常需要求解常微分方程的定解问题。这类问题的最简单的形式，是本章着重要考察的一阶方程的初值问题：本章中我们假定右函数适当光滑以保证初值问题解的存在唯一。虽然求解常微分方程有各种各样的解析方法，但求解从实际问题中归结出来的微分方程要靠数值解法。差分法是一类重要的数值方法，这类方法是要寻求离散节点上的近似解，相邻节点间距称为步长步长。初值问题的各种差分方法都采用“步进式”，即求解过程顺着节点排列的次序一步一步地向前推进。描述这类算法，只要给出从已知信息计算的递推公式，这类计算格式统称为差分格差分格 式式。第48页，本讲稿共101页数值分析简明教程欧拉格式欧拉格式 微分方程的本质特征是方程中含有导数项，这也是它难于求解的症结所在。数值解法的第一步就是设法消除其导数值，这项手续称为离散化。离散化。实现离散化的基本途径就用差商代替导数。譬如，若在点列出方程，并用差商代替，结果有设用的近似值代入上式右端，记所求结果为，这样导出的计算公式就是众所周知的欧拉（欧拉（Euler）格式）格式，若初值是已知的，则依据上式即可逐步算出数值解。第49页，本讲稿共101页数值分析简明教程欧拉格式的精度欧拉格式的精度 为简化分析，人们常在为准确即的前提下估计误差，这种误差称为局部截断误差局部截断误差。如果一种数值方法的局部截断误差为，则称它的的精度是阶的，或称之为阶方法。由此我们可知欧拉格式仅为一阶方法。第50页，本讲稿共101页数值分析简明教程隐式欧拉格式隐式欧拉格式设改用后差商替代方程中的导数项，再离散化，即可导出下列格式该格式右端含有未知的，它实际上是个关于的函数方程。故称该格式隐式欧拉格式隐式欧拉格式。隐式欧拉格式也是一阶方法，精度与欧拉格式相当。第51页，本讲稿共101页数值分析简明教程两步欧拉格式两步欧拉格式设改用中心差商替代方程中的导数项，再离散化，即可导出下列格式无论是显式欧拉格式还是隐式欧拉格式，它们都是单步法，其特点是计算时只用到前一步的信息，而该格式却调用了前面两步的信息，两步欧拉格式两步欧拉格式因此而得名。两步欧拉格式具有更高的精度，它是二阶方法。第52页，本讲稿共101页数值分析简明教程梯形公式梯形公式设将方程的两端从到求积分，即得，显然，只要能近似的算出其中的积分项，我们就可以得到计算的差分格式。若我们用梯形法计算积分项：再离散化，即可得如下计算公式与梯形求积公式相呼应的这一差分格式称为梯形格式梯形格式。第53页，本讲稿共101页数值分析简明教程改进的欧拉格式改进的欧拉格式先用欧拉法求得一个初步的近似值，记为，称之为预报值，然后用它替代梯形法右端的再直接计算，得到校正值，这样建立的预报校正系统称为改进的欧拉格式改进的欧拉格式：预报校正它有下列平均化形式：实践表明，改进的欧拉格式明显改善了精度。第54页，本讲稿共101页数值分析简明教程龙格龙格-库塔法的设计思想库塔法的设计思想 考察差商，根据微分中值定理，存在点，利用所给方程得我们称为区间上的平均斜率，这样只要对平均斜率提供一种算法，相应地我们便导出一种计算格式。龙格库塔（RungeKutta）方法设计思想就是设法在内多预报几个点的斜率值，然后把它们加权平均作为平均斜率，以期望构造出更高精度的计算格式。第55页，本讲稿共101页数值分析简明教程二阶龙格二阶龙格-库塔方法库塔方法随意考察区间内一点，用两个点的斜率的加权平均代替平均斜率，于是我们就得到如下计算格式：其中有两个待定参数，适当选取它们的值，就可使上述格式有较高的精度。若，该格式是二阶的，故统称满足这一条件的一族格式为二阶龙格库塔格式二阶龙格库塔格式。特别地，当时，上述格式即为改进的欧拉格式改进的欧拉格式，如果取，则上述格式称为变形的欧拉格式，亦称为中点格式中点格式。第56页，本讲稿共101页数值分析简明教程三阶龙格三阶龙格-库塔方法库塔方法 为了进一步提高精度，我们可以考虑用三个点的斜率值加权平均得出平均斜率的近似值，其中，于是就可以构造所谓的三阶龙格库塔格式三阶龙格库塔格式，下列库塔格式库塔格式是其中的一种：第57页，本讲稿共101页数值分析简明教程四阶龙格四阶龙格-库塔方法库塔方法继续上述过程，我们可以导出四阶龙格库塔格式四阶龙格库塔格式，下列经典格式是其中的一种：值得注意的是，龙格库塔法的推导基于泰勒展开法，因而它要求解具有较好的光滑性。如果解的光滑性差，则该方法得到的解反而不好。第58页，本讲稿共101页数值分析简明教程变步长的龙格变步长的龙格-库塔方法库塔方法 同积分的数值计算一样，微分方程的数值解法也需要选择步长。同样，我们可以采取步长加倍或折半的办法选择步长，即通过检查步长折半前后的两种计算结果的偏差：来判断选取的步长是否合适，具体可以分为两种情况来处理：对于给定精度，若，则反复将步长折半进行计算直到为止，取步长折半后的“新值”作为结果；相反的，反复将步长加倍直到，取步长加倍前的“老值”作为结果。这种通过步长加倍或折半的手续处理步长的方法称为变步长方变步长方法法。第59页，本讲稿共101页数值分析简明教程亚当姆斯格式亚当姆斯格式 亚当姆斯（Adams)方法的设计思想是充分利用计算之前已得到一系列节点上的斜率值来减少计算量。譬如，我们可以用两点的斜率的加权平均作为区间上的平均斜率，于是可设计出如下二阶亚当姆斯格式：类似的，可导出如下三阶和四阶亚当姆斯格式：第60页，本讲稿共101页数值分析简明教程隐式亚当姆斯格式隐式亚当姆斯格式 同样，我们也可导出如下隐式的二阶、三阶和四阶亚当姆斯格式：第61页，本讲稿共101页数值分析简明教程亚当姆斯预报亚当姆斯预报-校正系统校正系统仿照改进的欧拉格式的构造方法，将显式和隐式两种亚当姆斯格式相匹配，可构成下列亚当姆斯预报校正系统亚当姆斯预报校正系统：预报校正第62页，本讲稿共101页数值分析简明教程改进的亚当姆斯预报改进的亚当姆斯预报-校正系统校正系统我们可以方便地估计出亚当姆斯预报校正系统的截断误差，从而依据这种估计将该系统就可改进为如下精度更高的计算方案：预报改进校正改进第63页，本讲稿共101页数值分析简明教程收敛性问题收敛性问题在用差分格式求解微分方程时我们要考虑差分格式的收敛性。我们称差分格式是收敛的，如果对任意固定的，数值解当（同时）时趋于准确解。以下我们研究欧拉方法的收敛性。我们记，记为关于的李普希兹常数，经反复递推，可得其中为常数。若初始是准确的，即，则当时，有。这说明欧拉方法是收敛收敛的。第64页，本讲稿共101页数值分析简明教程稳定性问题稳定性问题关于收敛性的讨论有个前提，即必须假定差分方法的每一步计算都是准确的。然而实际计算中往往由于有舍入误差等原因而产生扰动，而这些扰动有可能“淹没”真解，所以我们还要考虑稳定性问题。我们称差分方法是稳定稳定的，如果在节点值上大小为的扰动于以后各节点值上产生的偏差值均不超过。稳定性比较复杂。为简化讨论，我们仅考察下列模型方程可以验证，对于该模型方程，欧拉格式是条件稳定条件稳定的，而隐式欧拉格式是恒稳定恒稳定的。第65页，本讲稿共101页数值分析简明教程一阶方程组一阶方程组前面我们研究了单个方程的差分方法，只要把和理解为向量，所提供的各种算法即可推广应用到一阶方程组的情形。譬如，对于方程组令，以表示节点上的近似解，则其改进的欧拉格式具有形式：预报校正第66页，本讲稿共101页数值分析简明教程化高阶方程为一阶方程组化高阶方程为一阶方程组关于高阶微分方程（或方程组）的初值问题，原则上总可以归结为一阶方程组来求解。譬如，对于下列二阶方程的初值问题若引进新的变量，即可化为一阶方程组的初值问题从而可以运用前面介绍的各种算法求解。第67页，本讲稿共101页数值分析简明教程 边值问题边值问题考察下列二阶线性方程的边值问题我们令并将求解区间等分，步长，记为在上的取值，则上述边值问题可以离散化为下列差分方程：第68页，本讲稿共101页数值分析简明教程第4章 方程求根的迭代法 1 迭代过程的收敛性2 迭代过程的加速3 牛顿法4 弦截法第69页，本讲稿共101页数值分析简明教程引言 引论中曾介绍过求解函数方程的二分法。这是电子计算机上的一种常用算法,其基本思想是逐步收缩有根区间，最后得出所求的根。本章的主要内容就是介绍方程求根的迭代法。第70页，本讲稿共101页数值分析简明教程迭代法的设计思想 迭代法是一种逐次逼近法，这种方法使用某个固定公式所谓迭代公式反复校正根的近似值，使之逐步精确化，直至满足精度要求的结果。迭代法的求根过程分成两步，第一步先提供根的某个猜测值，即所谓迭代初值，然后将迭代初值逐步加工成满足精度要求的根。迭代法的设计思想是，将隐式方程归结为计算一组显式公式，也就是说，迭代过程实质上是一个逐步显式化的过程。第71页，本讲稿共101页数值分析简明教程迭代过程的局部收敛性 在实际应用迭代法时，通常首先在根的邻近考察。称一种迭代过程在根邻近收敛，如果存在邻域，使迭代过程对于任意初值均收敛，这种在根的邻近所具有的收敛性被称为局部收敛性局部收敛性。定理定理设在的根邻近有连续导数，且成立则迭代过程在邻近具有局部收敛性。第72页，本讲稿共101页数值分析简明教程迭代过程的收敛速度 一种迭代法要具有实用价值，不但要肯定它是收敛的，还要求它收敛的比较快。所谓迭代过程的收敛速度，是指在接近收敛时迭代误差的下降速度，具体地说，如果迭代误差当时成立(常数)则称迭代过程是阶收敛收敛的。特别地，时称线性收敛线性收敛，时称平方收敛平方收敛。第73页，本讲稿共101页数值分析简明教程迭代公式的加工 设是根的某个近似值，用迭代公式校正一次得假设在所考察的范围内改变不大，其估计值为，则有据此可导出如下加速公式：其一步分为两个环节：迭代:改进:第74页，本讲稿共101页数值分析简明教程埃特金算法 前面加速方案有个缺点是其中含有导数的有关信息而不便于实际应用。设将迭代值再迭代一次，可得据此构造出不含导数信息的加速公式：迭代:迭代:改进:这一加速方法称为埃特金算法埃特金算法。第75页，本讲稿共101页数值分析简明教程牛顿迭代法 对于方程，设已知它的近似根，则函数在点附近可用一阶泰勒多项式来近似，若取的根作为新的近似根，记，则有如下著名的牛顿公式牛顿公式：相应的迭代函数是：第76页，本讲稿共101页数值分析简明教程开方公式 对于给定正数应用牛顿迭代法解二次方程可导出求开方值的计算公式设是的某个近似值，则自然也是一个近似值，上式表明，它们两者的算术平均值将是更好的近似值。定理定理开方公式对于任意给定的初值均为平方收敛。第77页，本讲稿共101页数值分析简明教程牛顿下山法 一般地说，牛顿法的收敛性依赖于初值的选取，如果偏离较远，则牛顿法可能发散。为了防止发散，通常对迭代过程再附加一项要求，即保证函数值单调下降：满足这项要求的算法称为下山法下山法。牛顿下山法牛顿下山法采用以下迭代公式：其中称为下山因子。第78页，本讲稿共101页数值分析简明教程弦截法 用差商替代牛顿公式中的导数可得到以下离散化形式：从几何图形上看，上面的公式求得的实际上是弦线与轴的交点，因此称这种方法为弦截法弦截法。改用差商代替牛顿法中的导数有以下快速弦截法迭代公式：第79页，本讲稿共101页数值分析简明教程第5章 线性方程组的迭代法1 迭代公式的建立2 向量和矩阵的范数3 迭代过程的收敛性第80页，本讲稿共101页数值分析简明教程引言 前几章研究过的几个课题，无论是插值公式与求积公式的建立，还是常微分方程差分格式的构造，其基本思想都是将其转化为代数问题来处理，最后归结为解线性方程组。工程技术的科学计算中，线性方程组也会经常遇到。因此，线性方程组的解法在数值分析中占有极其重要的地位。线性方程组的解法大致分为直接法和迭代法两大类。本章将先介绍迭代法，这类算法一个突出优点就是算法简单，因而编制程序比较容易。但是迭代法也有缺点,它要求方程组的系数矩阵具有某种特殊性质，以保证迭代过程的收敛性。发散的迭代过程是没有实用价值的。第81页，本讲稿共101页数值分析简明教程雅可比迭代公式 解线性方程组迭代法的基本思想是将联立方程组的求解归结为重复计算一组彼此独立的线性表达式，这就使问题得到了简化。考察一般形式的线性方程组，从上式中分离出变量，将它改写成，即得到解方程组的雅可比迭代公式雅可比迭代公式:，第82页，本讲稿共101页数值分析简明教程高斯塞德尔迭代公式 在迭代的每一步设定计算顺序并且，在计算迭代值充分利用它前面的新信息，这样设计出来的迭代公式，称为高斯高斯塞德尔迭代公式塞德尔迭代公式。第83页，本讲稿共101页数值分析简明教程超松弛法 松弛法实质是高斯塞德尔迭代的一种加速方法。它将前一步的结果与高斯塞德尔迭代值适当加权平均：迭代加速式中系数称为松弛因子。为保证迭代收敛，要求。由于迭代值通常比精确，所以加大它的比重，取松弛因子，这种方法称为超松弛法超松弛法。第84页，本讲稿共101页数值分析简明教程迭代公式的矩阵表示 考察线性方程组，设将系数矩阵分裂为 其中为对角阵，和分别为严格下三角和严格上三角阵。如果将所给方程改写为据此建立的迭代公式即为雅可比迭代公式。如果改写为据此建立的迭代公式即为高斯塞德尔迭代公式。第85页，本讲稿共101页数值分析简明教程向量的范数 为了研究迭代过程的收敛性，需要对向量”大小“引入某种度量。任给向量，其范数范数记为，它是一个实数，且满足：(1)对任意向量,当且仅当时,(2)对任意实数及任意向量,(3)对于任意向量与,有其中性质(3)被称为向量范数的三角不等式。第86页，本讲稿共101页数值分析简明教程矩阵的范数 对给定的阶方阵，我们将比值的上确界称为的范数范数，记为。由定义知，对任意向量，有。矩阵范数具有以下基本性质：(1)对任意方阵，当且仅当时(2)对任意实数和任意方阵，有(3)对任意两个同阶方阵和，有第87页，本讲稿共101页数值分析简明教程迭代收敛的充分条件 定理定理对给定的方阵，若，则矩阵为非奇异。设将方程组改写成的形式，据此建立迭代公式定理定理若迭代矩阵满足，则上迭代公式对任意初值均收敛。第88页，本讲稿共101页数值分析简明教程对角占优方程 称阶方阵是对角占优的，如果其主对角线元素的绝对值大于同行其它元素绝对值之和：若线性方程祖的系数矩阵为对角占优阵，则称这个线性方程组为对角占优方程组。定理定理对角占优方程组的雅可比迭代公式和高斯塞德尔迭代公式均收敛。第89页，本讲稿共101页数值分析简明教程第6章 线性方程组的直接法1 消去法2 追赶法3 平方根法4 误差分析第90页，本讲稿共101页数值分析简明教程引言 求解线性方程组的另一类重要方法是直接法。直接法利用一系列递推公式计算有限步能直接得到方程组的精确解。当然，实际计算结果仍有误差，譬如舍入误差。舍入误差的积累有时甚至会严重影响解的精度。求解线性方程组最基本的一种直接法是消去法。这是一个众所周知的古老方法，但用在现代电子计算机上仍然十分有效。第91页，本讲稿共101页数值分析简明教程约当消去法 消去法的基本思想是，通过将一个方程乘或除以某个常数，以及将两个方程相加减这两种手续，逐步减少方程中的变元的数目，最终使每个方程仅含一个变元，从而得出所求的解。所谓约当消去法约当消去法，其特点是，它的每一步仅在一个方程中保留某个变元，而从其它的各个方程中消去该变元，这样经过反复消元后，所给方程组中的每个方程最终被加工成仅含一个变元的形式，从而得出所求的解。第92页，本讲稿共101页数值分析简明教程高斯消去法 高斯消去法高斯消去法是约当消去法的一种改进。高斯消去法的求解过程分为消元过程和回代过程两个环节。消元过程将所给的方程组加工成上三角方程组。所归结的方程成组再通过回代过程得出它的解。高斯消去法由于添加了回代的过程，算法结构稍复杂，但这种算法的改进明显减少了计算量。第93页，本讲稿共101页数值分析简明教程选主元素 我们在高斯消去法的消元过程中检查方程组中变元的各系数，从中挑选出最大者，称之为第步的主元素。设主元素在第个方程，即若不等于，则我们先将第个方程与第个互易位置，使新的成为主元素，这一手续称为选主元素选主元素。第94页，本讲稿共101页数值分析简明教程三对角方程组 我们曾碰到下列形式的方程组我们用矩阵记号将方程组简记作，这里系数矩阵就是所谓的三对角阵，方程组就是所谓三对角方程组三对角方程组。三对角方程组可用追赶法追赶法来求解。第95页，本讲稿共101页数值分析简明教程追赶法的计算公式 解三对角方程组的追赶法追赶法分“追”和“赶”两个环节：(1)追的过程（消元过程）按顺序计算系数和；(2)赶的过程（回代过程）按逆序求出解。其具体计算公式分别为：第96页，本讲稿共101页数值分析简明教程追赶法的代数基础 定理定理 设三对角矩阵为对角占优，则它可唯一分解成下二对角阵和单位上二对角阵的乘积：事实上，追赶法的求解过程就是将系数矩阵分解两个简单的二对角矩阵，从而归结为求解两个简单方程组的过程。上述定理也表明，追赶法的原理和高斯消去法相同，但考虑到方程组的特点，计算时会把大量零元素撇开，从而大大节省计算量。第97页，本讲稿共101页数值分析简明教程平方根法 线性方程组求解的难易程度取决于系数矩阵的特征，当是三角阵时，方程组的求解特别方便。对称正定方程组就可归结为两个三角方程组和来求解，由于矩阵分解的过程中含有开方运算，故称此求解方法为平方根法平方根法，其具体求解过程分两步：(1)由顺序计算：(2)由逆序计算：第98页，本讲稿共101页数值分析简明教程改进的平方根法 运用平方根法计算量较大，为了避免开方运算，改用单位三角阵作为分解阵，于是对称正定方程组就可归结为两个三角方程组和来求解，其中为对角阵，称这种求解方法为改进的平方根法改进的平方根法，亦称为乔累斯基方法乔累斯基方法，其计算公式分别为和第99页，本讲稿共101页数值分析简明教程方程组的病态 考察方程组和上述方程组尽管只是右端项有微小扰动，但解大不相同：一个是，一个是。这类方程组称为病态病态的。方程组的病态程度可由系数矩阵的条件数条件数来刻画，条件数愈大，扰动对解的影响愈大。第100页，本讲稿共101页数值分析简明教程精度分析 求得方程组的一个近似解以后，自然希望判断其精度。检验精度的一个简单办法是，将近似解再代回到原方程组去求出余量，一般来说，如果很小，就认为解是相当准确的。定理定理设是方程组的近似解，其精确解为，为的余量，则有如下估计式：上述定理表明，用余量大小检验近似解精度的方法对于病态方程组是不可靠的。第101页，本讲稿共101页