线性代数方程组的解法

第五章线性代数方程组的解法5.1预备知识1a

求解线性方程组

其中

且。2a

利用法则求解时存在的困难是：当方程组的阶数很大时，计算量为常用计算方法:

(1)直接解法：它是一类精确方法，即若不考虑计算过程中的舍入误差，那么通过有限步运算可以获得方程解的精确结果.Gauss逐步（顺序）消去法、Gauss主元素法、矩阵分解法等；3a(2)迭代解法：所谓迭代方法，就是构造某种极限过程去逐步逼近方程组的解.经典迭代法有：

迭代法、迭代法、逐次超松弛（SOR）迭代法等；4a5.1.1

向量空间及相关概念和记号

1向量的范数5a例:设求根据定义:6a范数的等价性例如：7a设为中的一个给定向量序列若对则称向量序列收敛于向量命题:当时这是因为2向量序列的收敛问题8a利用向量范数的等价性及向量范数的连续性,容易得到定理5.2的证明9a对于上的任何向量范数,我们可以定义矩阵范数.1.矩阵的范数5.1.2矩阵的一些相关概念及记号10a定理5.3

矩阵的从属范数具有下列基本性质：1），当且仅当时，2)4)时5)、

定理5.3中的性质1),2)和3)是一般范数所满足的基本性质，性质4)、5)被称为相容性条件，一般矩阵范数并不一定满足该条件.11a三种从属范数计算：（1）矩阵的1-范数（列和范数）:（3）矩阵的2-范数:其中:的最大特征值（2）矩阵的-范数（行和范数）:12a解：按定义例已知矩阵求13a矩阵范数的等价定理：对、，存在常数和，使得：几种常用范数的等价关系：14a2.谱半径：此时若为对称阵，（因为）15a关于矩阵的谱半径与矩阵的范数之间有如下关系.16a定义5.3称矩阵序列是收敛的，如果存在，使得此时称为矩阵序列的极限记为矩阵序列的充分必要条件为3.矩阵级数的收敛性17a18a

该定理将被应用于解方程组的扰动分析和Gauss消去法的舍入误差分析.19a4矩阵的条件数

20a21a5几种特殊矩阵

且至少有一个使不等式严格成立，则称矩阵为按行对角占优矩阵。若严格不等式均成立，则称为按行严格对角占优矩阵.类似地，可以给出矩阵为按列（严格）对角占优矩阵的定义.22a证明我们只证按行严格对角占优的情形，这时有从而矛盾23a24a§5.2Gauss消去法、矩阵分解25a2.1Gauss消去法下面通过简单例子导出一般算法。设给定方程组(1)26a乘以第一个方程，这样方程组（1）

(2)化为其中：显然方程组（2）和原方程组（1）等价若，则以第个方程减去

(1)27a

得到(3)其中依此方法继续下去，得到以（2）的第个方程减去(2)28a（4）从（4）的最后一个方程组得到其中29a再将代入（4）倒数第二个方程，可得：类似地，得到：我们称将方程组（1）按以上步骤化为等价方程组（4）的过程为解线性方程组的消元过程

从（4）中得出解的过程称为高斯消去法的回代过程

（4）30a一般情形对于一般的阶线性代数方程组

即1.消元过程首先消去第一列除之外的所有元素，

31a设总可由消元过程得到系数矩阵为上三角阵的线性代数方程组，其第步的结果为32a其中这里取2.回代过程若通过消元过程原方程组已化为等价的三角形方程组33a且,则逐步回代可得原方程组的解34aGauss逐步消去法有如下的缺点：任一主元，就无法做下去任一绝对值很小时,也不行（舍入误差的影响大）2.2Gauss主元素消去法下面我们讨论列主元消去法.假设Gauss消去法的消元过程进行到第步，35a设36a并令为达到最大值的最小行标，

则交换和中的第行和第行，再进行消元过程的第步.这时每个乘子

都满足

可以防止有效数字大量丢失而产生误差.37a例用列主元消去法解如下方程组

解对增广矩阵按列选主元再进行高斯消元

38a39a回代求解得40a%magauss2.mfunctionx=magauss2(A,b,flag)%用途：列主元Gauss消去法解线性方程组Ax=b%格式：x=magauss(A,b,flag),A为系数矩阵,b为右端项,若flag=0,%则不显示中间过程，否则显示中间过程,默认为0,x为解向量ifnargin<3,flag=0;endn=length(b);fork=1:(n-1)

%选主元[ap,p]=max(abs(A(k:n,k)));p=p+k-1;ifp>kt=A(k,:);A(k,:)=A(p,:);A(p,:)=t;t=b(k);b(k)=b(p);b(p)=t;end41a

%消元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);ifflag~=0,Ab=[A,b],endend%回代x=zeros(n,1);x(n)=b(n)/A(n,n);fork=n-1:-1:1x(k)=(b(k)-A(k,k+1:n)*x(k+1:n))/A(k,k);end42a全主元消去法定义此时交换和的行及A的列，使主元位置的元素的绝对值具有给出的最大值，

然后进行第步消元过程

注意：因为有列的交换，因此未知量的次序有改变，待消元过程结束时必须还原.多使用列主元消去法.43aGauss消去法的实质是将矩阵分解为其中--单位下三角矩阵，--上三角矩阵.事实上，线性方程组经过步消元过程后，有等价方程组其中：，而和的形式为：2.3矩阵的三角分解与Gauss消去法的变形44a（1）可以直接验证，

45a46a其中47a乘积是下三角阵，且对角元全部等于1

则也是对角元等于1的下三角阵

用矩阵依次左乘原给方程组两边，得等价方程组则其中48a由于为上三角阵，记

,于是得到(2)49aGauss逐步消去法等价于下述过程：2.求解三角形方程组（回代过程）.(注意上面的全部讨论中要求)50a比较等式两边对应元素算出Doolittle分解51aDoolittle分解计算顺序为…

…

…

…

第一层第二层第三层52aCrout分解：比较两边对应的元素，得53a其中

、分别为单位下、上三角阵例实际上，进一步可以做分解54a首先我们来看一个命题:证明:我们对A做分解其中

、分别为单位下、上三角阵又由于则当为对称正定矩阵时，

A存在三角分解其中为下三角矩阵

1.对称正定阵的Cholesky分解55a于是有由于正定，故有取令即得证毕我们将上面的这种分解称为Cholesky分解.下面我们讨论Cholesky分解的算法.

56a比较两边对应的元素，有：因正定，就有，故以的第二行乘的前两列57a即得又可以解出一般地，对有由的正定性可知平方根中值为正的58a由矩阵乘法解得例59a设线性方程组的系数矩阵为三对角矩阵当的所有顺序主子矩阵非奇异时可作如下分解2解三对角方程组的追赶法60a追赶法：（1）