资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,六、三对角阵的三角分解,追赶法,追赶法是适用于三对角线方程组的有效解法。,三对角方程组形式：,AX,=,D,三对角阵的三角分解,其系数阵是三对角阵,将,A,阵分解为,L,阵和,U,阵,三对角阵的三角分解,三对角阵的三角分解算式为,解三对角线方程组的追赶法的步骤,（,1,）将,A,阵按式（,2-89,）分解，得到,L,、,U,阵。,（,2,）向前回代求解,LY,=,D,，得,（,3,）向后回代求解,UX=Y,，得到,（,2-89,）,追,赶,题,7,用追赶法解三对角方程组,解,由,LY,=,D,，得,由,UX,=,Y,，得,七、方程组的逆矩阵解法与矩阵求逆,（一）方程组的逆矩阵解法,对方程 的两端左乘以逆矩阵,A,-1,得,解为,方程组的逆矩阵解法,方程组的逆矩阵解法,（二）矩阵求逆,用计算机求,n,n,阶非奇异方阵,A,的逆矩阵,A,-1,。,式中，,B,1,，,B,2,，,，,B,n,分别为,求,n,n,阶非奇异方阵,A,的逆矩阵,A,-1,，等价于求解具有相同系数阵（被求逆的矩阵）且右端项分别为,的,n,个方程组，即求解下述方程组,最后求得的,A,-1,为,（,2-94,）,方程组的逆矩阵解法,第二节 线性代数方程组的,迭代解法,迭代法,就是用某种极限过程去逐步逼近线性方程组精确解的方法。,迭代法具有需要计算机的存储单元较小，程序设计简单，原始系数矩阵在计算过程中始终不变等优点，但存在收敛性和收敛速度问题。迭代法在解决问题（特别是大型稀疏系数阵问题）时，是一种有效的方法。,雅可比迭代法,高斯,赛德尔迭代法,逐次超松弛法,迭代解法,一、雅可比迭代法,（一）迭代算法,设有,n,阶方程组,可改写为,即,AX,=,B,雅可比迭代法,任一方程可写为,进而写成如下的迭代格式,（,2-97,）,式（,2-97,）就是雅可比迭代算法。,雅可比迭代法,雅可比迭代法,式（,2-97,）展开为,（二）迭代的矩阵形式,方程组,AX,=,B,中的系数矩阵可表示为三个矩阵的代数和矩阵，即,A=D L-U,其中,雅可比迭代法,故式（,2-97,）即为,（,2-99,）,式（,2-99,）就是雅可比迭代的矩阵形式。,其中,雅可比迭代法,题,8,用雅可比迭代法求解下列方程组,解 按式（,2-97,）形式的雅可比算法，有,计算结果见下表：,k,0,1,2,3,4,5,6,7,X,1,0,0.72,0.971,1.057,1.0853,1.0951,1.0983,X,2,0,0.83,1.070,1.1571,1.1853,1.1951,1.1983,X,3,0,0.84,1.150,1.2482,1.2828,1.2941,1.2980,原线性代数方程组的精确解为,二、高斯,赛德尔迭代法,高斯,赛德尔迭代是对雅可比迭代的,一个简单改进,，从而提高了迭代收敛的速度,（一）迭代算法,N,阶方程组可改写为如下形式,高斯,赛德尔迭代法,（,2-100,）,可写成如下的迭代形式,可简写成,式（,2-100,）就是高斯,赛德尔迭代算法,高斯,赛德尔迭代法,，,（二）迭代的矩阵形式,其中,式（,2-101,）是高斯,赛德尔迭代的矩阵形式。,（,2-101,）,高斯,赛德尔迭代法,，,（二）迭代的矩阵形式（书上）,式（,2-100,）可写成,亦即,故,其中,（,2-101,）,式（,2-101,）是高斯,赛德尔迭代的矩阵形式。,高斯,赛德尔迭代法,题,9,用高斯,-,赛德尔迭代法求解下列方程组,解 按式（,2-100,）得到的高斯,赛德尔迭代算法，有,计算结果见下表：,k,0,1,2,3,4,5,6,7,X,1,0,0.72,1.04308,1.09313,1.09913,1.09989,1.09999,1.1,X,2,0,0.902,1.16719,1.19572,1.19947,1.19993,1.19999,1.2,X,3,0,0.1644,1.28205,1.29777,1.29972,1.29996,1.3,1.3,（一）迭代算法,三、逐次超松弛法（或,SOR,法）,逐次超松弛法又是对高斯,赛德尔法的,一个改进,。,高斯,赛德尔迭代算法,逐次超松弛法,这里,r,是用来加速收敛的权因子，称为松弛因子，,r,=1,时，即为赛德尔迭代公式。式（,2-102,）在,r,1,时为超松弛迭代（简称,SOR,），在,r,1,时为松弛迭代。通常取,1,r,2,。,修改为,（,2-102,）,逐次超松弛法,式（,2-102,）还可等价地表示为,（,2-103,）,式（,2102,）和（,2-103,）就是逐次超松弛迭代算法（,r,1,）。,逐次超松弛法,，,（二）迭代的矩阵形式,（,2-104,）,式（,2-104,）是逐次超松弛法的矩阵形式。,直接根据式（,2-103,）写,整理得,逐次超松弛法,（,2-103,）,超松弛因子通常在,1.4,到,1.9,之间。松驰因子的选取对迭代格式的收敛速度影响极大。实际计算时，可以根据系数矩阵的性质，结合经验通过反复计算来确定松驰因子。,使收敛最快的松弛因子称为最佳松弛因子（）。,逐次超松弛法,举例,用,SOR,方法解线性方程组,方程精确解为,X,=,（,-1,，,-1,，,-1,，,-1,）,T,解,:,取,x,(0),=(0,0,0,0),T,取不同的松弛因子，得到的满足误差,10,-5,的迭代次数如下表所示。,逐次超松弛法,松弛因子,迭代次数,松弛因子,迭代次数,1.0,1.1,1.2,1.3,1.4,22,17,12,11,14,1.5,1.6,1.7,1.8,1.9,17,23,33,53,109,本例说明，松弛因子选择的好，会使,SOR,迭代法的收敛大大加速。本例中,1.3,是最佳松弛因子。,逐次超松弛法,四、向量和矩阵的范数的概念,向量,X,的范数 是满足下列条件的,实数,。,迭代法的收敛条件与收敛准则,三个常用的向量范数：,设,X,=(,x,1,x,2,x,n,),T,，则有,列范数,谱范数,行范数,迭代法的收敛条件与收敛准则,矩阵的范数 是定义在,R,n,n,上的,非负的实值函数,，它,满足下列条件的实数。,迭代法的收敛条件与收敛准则,三个常用的矩阵范数：,迭代法的收敛条件与收敛准则,矩阵每一列元素绝对值之和取最大值,矩阵每一行元素绝对值之和取最大值,（一）一般迭代法的收敛准则与收敛条件,对方程组,AX,=,B,，一般（线性）迭代法是按公式,以任意初始向量,X,（,0,）,开始，反复进行计算。当,m,时，迭代向量序列 有时收敛于方程组的精确解，有时则不然。如向量序列 收敛于方程组的精确解，就称该,迭代法收敛,；反之，则谓,不收敛或发散,。,（,2-112,）,定义,迭代法的收敛条件与收敛准则,五、迭代法的收敛条件与收敛准则,收敛准则,收敛准则是指使迭代终止的条件。,通常使用的收敛准则有绝对准则和相对准则两种。,绝对准则,相对准则,或,或,这里 是方程的余差向量，,是给定的控制误差。,迭代法的收敛条件与收敛准则,定理,2,迭代格式（,2-112,）收敛的充分必要条件是迭代矩阵,K,的谱半径,(,K,)1,。,定理,1,若迭代格式（,2-112,）的迭代矩阵,K,的范数小于,1,（即 ），则该格式求出的向量序列 将收敛于方程组的唯一解,a,，且有误差估计式,迭代法收敛定理,以上两定理有较大的理论意义，但实际用起来不甚方便，,为此后面引入更为实用的判别迭代格式收敛的充分条件。,迭代法的收敛条件与收敛准则,定理,1,若线性代数方程组,AX,=,B,的系数阵,A,按行（或列）严格对角占优，即,则雅可比迭代和赛德尔迭代收敛。,定理,2,若线性代数方程组,AX,=,B,的系数阵,A,是实对称正定阵，则赛德尔迭代收敛。,定理,3,对任何系数阵,A,，要使逐次超松弛法收敛，必须选取松弛因子,r,为（,0,，,2,）内的正数，则,SOR,法收敛的必要条件是,(2-117),当,A,是对称正定阵时，满足（,2-117,）的,r,必使,SOR,法收敛。,（二）雅可比、赛德尔及逐次超松弛迭代的收敛条件。,迭代法的收敛条件与收敛准则,
展开阅读全文