线性代数方程组的解法

单击此处编辑母版标题样式,湘潭大学数学与计算科学学院,*,上一页,下一页,湘潭大学数学与计算科学学院,1,第五章,线性代数方程组的解法,5.1,预备知识,湘潭大学数学与计算科学学院,2,求解线性方程组,其中,且,。,湘潭大学数学与计算科学学院,3,利用 法则求解时存在的困难是：当方程,组的阶数 很大时，计算量为,常用计算方法,:,(1),直接解法：,它是一类精确方法，即若不考虑计算过程中的,舍入误差,，那么通过有限步运算可以获得方程解的,精确结果,.,Gauss,逐步（顺序）消去法、,Gauss,主元素法、矩阵分解法等；,湘潭大学数学与计算科学学院,4,(2),迭代解法,：所谓迭代方法，就是构造某种,极限过程,去逐步,逼近,方程组的解,.,经典迭代法有,：,迭代法、 迭代法、,逐次超松弛（,SOR,）迭代法等；,湘潭大学数学与计算科学学院,5,5.1.1,向量空间及相关概念和记号,1,向量的范数,湘潭大学数学与计算科学学院,6,例,:,设,求,根据定义,:,湘潭大学数学与计算科学学院,7,范数的等价性,例如：,湘潭大学数学与计算科学学院,8,设,为,中的一个给定,向量序列,若对,则称向量序列,收敛,于向量,命题,:,当,时,这是因为,2,向量序列的收敛问题,湘潭大学数学与计算科学学院,9,利用向量范数的等价性及向量范数的连续性,容易得到定理,5.2,的证明,湘潭大学数学与计算科学学院,10,对于 上的任何,向量范数,我们可以定义,矩阵范数,.,1.,矩阵的范数,5.1.2,矩阵的一些相关概念及记号,湘潭大学数学与计算科学学院,11,定理,5.3,矩阵的,从属范数,具有下列,基本性质,：,1,） ，当且仅当 时，,2),4),时,5),、,定理,5.3,中的性质,1), 2),和,3),是一般范数所满足的基本性质，性质,4),、,5),被称为,相容性条件,，一般矩阵范数并不一定满足该条件,.,湘潭大学数学与计算科学学院,12,三种从属范数计算：,（,1,）矩阵的,1-,范数（,列和范数,）,:,（,3,）矩阵的,2-,范数,:,其中,:,的最大特征值,（,2,）矩阵的,-,范数（,行和范数,）,:,湘潭大学数学与计算科学学院,13,解：,按定义,例 已知矩阵,求,湘潭大学数学与计算科学学院,14,矩阵范数的,等价定理,：,对 、 ，存在常数 和 ，使得：,几种常用范数的等价关系：,湘潭大学数学与计算科学学院,15,2.,谱半径：,此时,若 为,对称阵,，,（ 因为 ）,湘潭大学数学与计算科学学院,16,关于矩阵的,谱半径,与,矩阵的范数,之间有如下,关系,.,湘潭大学数学与计算科学学院,17,定义,5.3,称,矩阵序列,是,收敛,的，,如果,存在,，使得,此时称 为矩阵序列 的极限,记为,矩阵序列 的,充分必要条件,为,3.,矩阵级数的收敛性,湘潭大学数学与计算科学学院,18,湘潭大学数学与计算科学学院,19,该定理将被应用于解方程组的扰动分析和,Gauss,消去法的舍入误差分析,.,湘潭大学数学与计算科学学院,20,4,矩阵的条件数,湘潭大学数学与计算科学学院,21,湘潭大学数学与计算科学学院,22,5,几种特殊矩阵,且至少有一 个使不等式严格成立，则称矩阵,为,按行对角占优矩阵,。若 严格不等,式均成立，则称 为,按行严格对角占优矩阵,.,类似地，可以给出矩阵 为,按列（严格）对角,占优矩阵,的定义,.,湘潭大学数学与计算科学学院,23,证明,我们只证按行严格对角占优的情形，这时有,从而,矛盾,湘潭大学数学与计算科学学院,24,湘潭大学数学与计算科学学院,25,5.2 Gauss,消去法、矩阵分解,湘潭大学数学与计算科学学院,26,2.1 Gauss,消去法,下面通过简单例子导出一般算法。,设给定方程组,(1),湘潭大学数学与计算科学学院,27,乘以第一个方程，这样方程组（,1,）,(2),化为,其中：,显然方程组（,2,）和原方程组（,1,）等价,若,，则以第,个方程减去,(1),湘潭大学数学与计算科学学院,28,得到,(3),其中,依此方法继续下去，得到,以（,2,）的第,个方程,减去,(2),湘潭大学数学与计算科学学院,29,（,4,）,从（,4,）的最后一个方程组得到,其中,湘潭大学数学与计算科学学院,30,再将,代入（,4,）倒数第二个方程，可得：,类似地，得到：,我们称将方程组（,1,）按以上步骤化为等价方程组,（,4,）的过程为解线性方程组的,消元过程,从（,4,）中得出解的过程称为高斯消去法的,回代过程,（,4,）,湘潭大学数学与计算科学学院,31,一般情形,对于一般的,阶线性代数方程组,即,1.,消元过程,首先消去第一列除 之外的所有元素，,湘潭大学数学与计算科学学院,32,设,总可由消元过程得到系数矩阵为上三角阵的线性代数,方程组，其第,步的结果为,湘潭大学数学与计算科学学院,33,其中,这里取,2.,回代过程,若通过消元过程原方程组已化为等价的三角形,方程组,湘潭大学数学与计算科学学院,34,且,则逐步回代可得原方程组的解,湘潭大学数学与计算科学学院,35,Gauss,逐步消去法有如下的缺点,：,任一主元 ，就无法做下去,任一 绝对值很小时,也不行（舍入误差的影响大）,2.2 Gauss,主元素,消去法,下面我们讨论,列主元消去法,.,假设,Gauss,消去法的消元过程进行到,第 步，,设,湘潭大学数学与计算科学学院,37,并令 为达到最大值 的最小行标 ，,则交换 和 中的第 行和第 行，,再进行消元过程的第 步,.,这时每个乘子,都满足,可以防止有效数字大量丢失而产生误差,.,湘潭大学数学与计算科学学院,38,例,用列主元消去法解如下方程组,解,对增广矩阵按列选主元再进行高斯消元,湘潭大学数学与计算科学学院,39,湘潭大学数学与计算科学学院,40,回代求解得,湘潭大学数学与计算科学学院,41,%magauss2.m,function x=magauss2(A,b,flag),%,用途：列主元,Gauss,消去法解线性方程组,Ax=b,%,格式：,x=magauss(A,b,flag), A,为系数矩阵, b,为右端项,若,flag=0,%,则不显示中间过程，否则显示中间过程,默认为,0, x,为解向量,if nargink,t=A(k,:); A(k,:)=A(p,:); A(p,:)=t;,t=b(k); b(k)=b(p); b(p)=t;,end,湘潭大学数学与计算科学学院,42,%,消元,m=A(k+1:n,k)/A(k,k);,A(k+1:n,k+1:n)=A(k+1:n,k+1:n)-m*A(k,k+1:n);,b(k+1:n)=b(k+1:n)-m*b(k);,A(k+1:n,k)=zeros(n-k,1);,if flag=0, Ab=A,b, end,end,%,回代,x=zeros(n,1);,x(n)=b(n)/A(n,n);,for k=n-1:-1:1,x(k)=(b(k)-A(k,k+1:n)*x(k+1:n)/A(k,k);,end,湘潭大学数学与计算科学学院,43,全主元消去法,定义,此时交换 和 的行及,A,的列，使主元位置的元素,的绝对值具有给出的最大值 ，,然后进行第 步消元过程,注意：因为有列的交换，因此未知量的次序有改变，待消元过程结束时必须还原,.,多使用列主元消去法,.,湘潭大学数学与计算科学学院,44,Gauss,消去法的实质是将矩阵 分解为,其中,-,单位下三角矩阵，,-,上三角矩阵,.,事实上，线性方程组,经过 步消元过程后，有等价方程组,其中： ，而 和 的形式为：,2.3,矩阵的三角分解与,Gauss,消去法的变形,湘潭大学数学与计算科学学院,45,（,1,）,可以直接验证 ，,湘潭大学数学与计算科学学院,46,湘潭大学数学与计算科学学院,47,其中,湘潭大学数学与计算科学学院,48,乘积,是下三角阵，且对角元全部等于,1,则 也是对角元等于,1,的下三角阵,用矩阵 依次左乘原给方程组,两边，得等价方程组,则,其中,湘潭大学数学与计算科学学院,49,由于 为上三角阵，记,于是得到,(2),湘潭大学数学与计算科学学院,50,Gauss,逐步消去法等价于下述过程：,2.,求解三角形方程组 （回代过程）,.,(,注意上面的全部讨论中要求,),湘潭大学数学与计算科学学院,51,比较等式两边对应元素算出,Doolittle,分解,湘潭大学数学与计算科学学院,52,Doolittle,分解计算顺序为,第一层,第二层,第三层,湘潭大学数学与计算科学学院,53,Crout,分解：,比较两边对应的元素，得,湘潭大学数学与计算科学学院,54,其中,、 分别为单位下、上三角阵,例,实际上，进一步可以做分解,湘潭大学数学与计算科学学院,55,首先我们来看一个命题,:,证明,:,我们对,A,做分解,其中,、 分别为单位下、上三角阵,又由于,则,当 为对称正定矩阵时，,A,存在三角分解,其中,为下三角矩阵,1.,对称正定阵的,Cholesky,分解,湘潭大学数学与计算科学学院,56,于是有,由于 正定， 故有,取,令,即得,证毕,我们将上面的这种分解称为,Cholesky,分解,.,下面我们讨论,Cholesky,分解的算法,.,湘潭大学数学与计算科学学院,57,比较两边对应的元素，有：,因 正定，就有,，故,以 的第二行乘 的前两列,湘潭大学数学与计算科学学院,58,即得,又可以解出,一般地，对,有,由 的正定性可知平方根中值 为正的,湘潭大学数学与计算科学学院,59,由矩阵乘法解得,例,湘潭大学数学与计算科学学院,60,设线性方程组 的系数矩阵 为三对角矩阵,当 的所有顺序主子矩阵非奇异时可作如下分解,2,解三对角方程组的追赶法,湘潭大学数学与计算科学学院,61,追赶法：,（,1,） 分解（,Doolittle,分解）,对 计算,湘潭大学数学与计算科学学院,62,（,2,）解 （,“,追,”,过程）,对 计算,（,3,）解 （,“,赶,”,过程）,对于 计算,湘潭大学数学与计算科学学院,63,同样可以作,Crout,分解：,对 计算,湘潭大学数学与计算科学学院,64,湘潭大学数学与计算科学学院,65,