线性代数方程组的解法

1、湘潭大学数学与计算科学学院,1,第五章 线性代数方程组的解法,5.1 预备知识,湘潭大学数学与计算科学学院,2,求解线性方程组,湘潭大学数学与计算科学学院,3,利用 法则求解时存在的困难是：当方程 组的阶数 很大时，计算量为,常用计算方法:,(1) 直接解法：它是一类精确方法，即若不考虑计算过程中的舍入误差，那么通过有限步运算可以获得方程解的精确结果.,湘潭大学数学与计算科学学院,4,(2) 迭代解法：所谓迭代方法，就是构造某种极限过程去逐步逼近方程组的解.,经典迭代法有：,湘潭大学数学与计算科学学院,5,5.1.1 向量空间及相关概念和记号,1 向量的范数,湘潭大学数学与计算科学学院,6,根

2、据定义:,湘潭大学数学与计算科学学院,7,范数的等价性,例如：,湘潭大学数学与计算科学学院,8,向量序列,若对,则称向量序列 收敛于向量,这是因为,2 向量序列的收敛问题,湘潭大学数学与计算科学学院,9,利用向量范数的等价性及向量范数的连续性, 容易得到定理5.2的证明,湘潭大学数学与计算科学学院,10,对于 上的任何向量范数,我们可以定义矩阵范数.,1. 矩阵的范数,5.1.2 矩阵的一些相关概念及记号,湘潭大学数学与计算科学学院,11,定理5.3 矩阵的从属范数具有下列基本性质：,1） ，当且仅当 时，,2),定理5.3中的性质 1), 2) 和 3)是一般范数所满足的基本性质，性质 4)

3、、5) 被称为相容性条件，一般矩阵范数并不一定满足该条件.,湘潭大学数学与计算科学学院,12,三种从属范数计算：,（1）矩阵的1-范数（列和范数）:,（3）矩阵的2-范数:,其中 : 的最大特征值,（2）矩阵的 -范数（行和范数）:,湘潭大学数学与计算科学学院,13,解：,按定义,湘潭大学数学与计算科学学院,14,矩阵范数的等价定理：,几种常用范数的等价关系：,湘潭大学数学与计算科学学院,15,2. 谱半径：,此时,若 为对称阵，,（ 因为 ）,湘潭大学数学与计算科学学院,16,关于矩阵的谱半径与矩阵的范数之间有如下关系.,湘潭大学数学与计算科学学院,17,定义5.3,称矩阵序列 是收敛的，,

4、如果存在 ，使得,此时称 为矩阵序列 的极限,记为,3. 矩阵级数的收敛性,湘潭大学数学与计算科学学院,18,湘潭大学数学与计算科学学院,19,该定理将被应用于解方程组的扰动分析和gauss消去法的舍入误差分析.,湘潭大学数学与计算科学学院,20,4 矩阵的条件数,湘潭大学数学与计算科学学院,21,湘潭大学数学与计算科学学院,22,5 几种特殊矩阵,且至少有一 个使不等式严格成立，则称矩阵,为按行对角占优矩阵。若 严格不等,式均成立，则称 为按行严格对角占优矩阵.,类似地，可以给出矩阵 为按列（严格）对角 占优矩阵的定义.,湘潭大学数学与计算科学学院,23,证明 我们只证按行严格对角占优的情形

5、，这时有,从而,矛盾,湘潭大学数学与计算科学学院,24,湘潭大学数学与计算科学学院,25,5.2 gauss消去法、矩阵分解,湘潭大学数学与计算科学学院,26,2.1 gauss消去法,下面通过简单例子导出一般算法。,设给定方程组,(1),湘潭大学数学与计算科学学院,27,乘以第一个方程，这样方程组（1）,其中：,显然方程组（2）和原方程组（1）等价,(1),湘潭大学数学与计算科学学院,28,其中,依此方法继续下去，得到,湘潭大学数学与计算科学学院,29,（4）,从（4）的最后一个方程组得到,其中,湘潭大学数学与计算科学学院,30,再将,代入（4）倒数第二个方程，可得：,类似地，得到：,我们称

6、将方程组（1）按以上步骤化为等价方程组 （4）的过程为解线性方程组的消元过程,从（4）中得出解的过程称为高斯消去法的回代过程,（4）,湘潭大学数学与计算科学学院,31,一般情形,1. 消元过程,首先消去第一列除 之外的所有元素，,湘潭大学数学与计算科学学院,32,设,湘潭大学数学与计算科学学院,33,其中,这里取,2. 回代过程,若通过消元过程原方程组已化为等价的三角形 方程组,湘潭大学数学与计算科学学院,34,且 , 则逐步回代可得原方程组的解,湘潭大学数学与计算科学学院,35,gauss逐步消去法有如下的缺点：,任一主元 ，就无法做下去,任一 绝对值很小时,也不行（舍入误差的影响大）,2.

7、2 gauss主元素消去法,下面我们讨论列主元消去法.,设,湘潭大学数学与计算科学学院,37,并令 为达到最大值 的最小行标 ，,可以防止有效数字大量丢失而产生误差.,湘潭大学数学与计算科学学院,38,例 用列主元消去法解如下方程组,解 对增广矩阵按列选主元再进行高斯消元,湘潭大学数学与计算科学学院,39,湘潭大学数学与计算科学学院,40,回代求解得,湘潭大学数学与计算科学学院,41,%magauss2.m function x=magauss2(a,b,flag) %用途：列主元gauss消去法解线性方程组ax=b %格式：x=magauss(a,b,flag), a为系数矩阵, b为右端项

8、, 若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

9、); 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）

10、,可以直接验证 ，,湘潭大学数学与计算科学学院,46,湘潭大学数学与计算科学学院,47,其中,湘潭大学数学与计算科学学院,48,则 也是对角元等于1的下三角阵,用矩阵 依次左乘原给方程组 两边，得等价方程组,则,其中,湘潭大学数学与计算科学学院,49,(2),湘潭大学数学与计算科学学院,50,gauss逐步消去法等价于下述过程：,2. 求解三角形方程组 （回代过程）.,(注意上面的全部讨论中要求 ),湘潭大学数学与计算科学学院,51,比较等式两边对应元素算出,doolittle分解,湘潭大学数学与计算科学学院,52,doolittle分解计算顺序为,第一层,第二层,第三层,湘潭大学数学与计算科

11、学学院,53,crout分解：,比较两边对应的元素，得,湘潭大学数学与计算科学学院,54,其中,、 分别为单位下、上三角阵,例,实际上，进一步可以做分解,湘潭大学数学与计算科学学院,55,首先我们来看一个命题:,证明:,我们对a做分解,其中,、 分别为单位下、上三角阵,1. 对称正定阵的cholesky分解,湘潭大学数学与计算科学学院,56,于是有,由于 正定， 故有,取,令,即得,证毕,我们将上面的这种分解称为cholesky分解.,下面我们讨论cholesky分解的算法.,湘潭大学数学与计算科学学院,57,比较两边对应的元素，有：,以 的第二行乘 的前两列,湘潭大学数学与计算科学学院,58,即得,又可以解出,由 的正定性可知平方根中值 为正的,湘潭大学数学与计算科学学院,59,由矩阵乘法解得,例,湘潭大学数学与计算科学学院,60,设线性方程组 的系数矩阵 为三对角矩阵,当 的所有顺序主子矩阵非奇异时可作如下分解,2 解三对角