《线性代数方程组的直接法》由会员分享，可在线阅读，更多相关《线性代数方程组的直接法（80页珍藏版）》请在金锄头文库上搜索。
1、*1王 淑 栋办办公室：J13-409电话电话 ：88032786（H）, 15269283087E-mail：数数 值值 分分 析析 （Numerical AnalysisNumerical Analysis ）*2第七章 解线性方程组的直接方法数数 值值 分分 析析 （Numerical AnalysisNumerical Analysis ）AXAX = = b b很多实际问题都可归结为求解线性方程组：*3写成矩阵形式：线性方程组数值解法的分类：直接法：经过有限步算术运算即可求得方程组精 确解的方法（适用于中等规模的n阶线性方程组） Gauss消去法及其变形矩阵的三角分解法迭代法：用某种
2、极限过程去逐步逼近线性方程 组精确解的方法。（适用于高阶线性方程组）Jacobi迭代法 Gauss-Seidel迭代法逐次超松弛法*4*51 Gauss消去法或或 AXAX = = b b消元手续*6举例说明消去法的基本思想：基本思想：用逐次消去未知数的方法把原来方程组AXAX = = b b化为与其等价的三角方程组，然后再用回代法写出方程组的解。事 实上，将方程组化为与其等价的三角方程组的过程就是用行的 初等变换将原来方程组的系数矩阵化为简单形式，然后再求解 。1消元基本思想：通过消元手续将上述方程组化为三角形 方程组进行求解。*7 Guass消去法消元公式消元公式*82. 回代*9回代公式
3、回代公式*10Gauss消去法可执行的前提：【定理 1】 按顺序Gauss消去法所形成的各主元素 的充要条件是 矩阵 的顺序主子式 ，即 *11【推论】如果 的顺序主子式*12【定理 2】如果 的所有顺序主子式都不为零，即则可通过Gauss消去法将前面的方程组约化为三角方程组。*13作业： P197 1，2，7不进行交换两行 的初等变换！*14 矩阵的三角分解借助矩阵理论分析消去法！建立Gauss消去法和矩阵理论间的关系！对于或或 AXAX = = b b在Gauss消元法中，每一步消去过程相当于左乘初等变换矩阵Lk*15*16A 的 LU 分解其中 单位下三角形。 *17【定理3】（矩阵的L
4、U分解）设A为n n矩阵，如果解AX = b用高斯消去法（限制不进行行的交换，即 ）能够完成，则矩阵A可分解为单位下三角矩阵L与上三角矩阵U的乘积，即A = LU且这种分解是唯一的。*18注注： （1 1） L 为单位下三角阵而 U 为一般上三角阵的分解称为Doolittle 分解（2）L 为一般下三角阵而 U 为单位上三角阵的分解称为Crout 分解。*19*20系数矩阵 的三角分解！21 计算量（1）消元过程的计算量：第1步计算乘数mi1(i=1,2,n)，需要n-1次除法运算；计算需要 次乘法和次加、减法。第k步 加、减法次数乘法次数除法次数12n-1111合计22第k步 加、减法次数乘
5、法次数除法次数1232.21nn-1n-11合计(2) 计算b(n)计算量:进行 次乘法和 加、减法；(3) 回代过程的计算量:总计算量：次乘除法和 次加减法较大时乘除法次数：较大时加减法次数：2 Gauss主元素消去法【例4 】用Gauss消去法解方程组选主元素的必要性！要求用具有舍入的10位浮点数进行计算。 精确到10位的精确解为： 【解法1】（高斯消去法）消元：舍去或者 说被“吃”舍去或者说被“吃” 计算解： *23显然,计算解与精确解解相差太大，原因是用很小的数 作除数，使得舍入误差太大，从而计算结果不可靠。【解法2 】 用行变换的高斯消去法消元：计算解:该结果较好。该例子说明，在采用
6、高斯消去法解方程组时，应避免采用绝 对值很小主元素 。对一般系数矩阵，最好保持乘数 ， 因此在高斯消去法中引进选主元素技巧。241、完全主元素消去法 选主元素消元法：为非奇异矩阵，第一步： （1）选主元素：在A中选取绝对值最大的元素作为主元素，即确定 使 （2）交换行列：交换 中第1行和i1行元素，第1列和第j1列元素。注意调换 两未知量，并做记录。交换后 的 元素仍记为 。 （3）第1次消元计算：重复进行上述过程，设已完成第1步至第k-1 步的选主元素、 交换行列和消元计算，使为增广矩阵 。25第k步： （1）选主元素：选取 使 （2）交换行列：交换 中第k行和ik行元素，第k列和第 jk列
7、元素。（3）消元计算：*26 回代求解工作量大。 经过上述过程，方程组约化为 ：缺点：优点：数值稳定改进方法：列主元消去法，且此时其中 是未知数 调换后的顺序，则完全主元素消去法优缺点：完全主元素消去法步骤见P172!27列主元素法考虑依次按列选主元素，然后换行，再进 行消元计算。设已完成第1步第k-1步计算，得到与原方程组等价的方程组 其中 方框内为第k步选主元素区域。2、列主元素消去法28 输入矩阵阶数n，增广矩阵 A(n, n+1); 对于 (1) 按列选主元：选取 l ， 使 (2) 如果 ，交换 A(n, n+1) 的第k行与第l 行元素(3) 消元计算 ： 回代计算*29列主元素消
8、去法步骤见P173!矩阵运算描述列主元素消去法 ！30先换行再消元 ！【定理4】（列主元素的三角分解）如果为非奇异矩阵，则存 在排列矩阵P，使得PA=LU，其中L是单位下三角阵，U是上三角阵。【例5】 用列主元素消去法解方程组我们用4位浮点数进行计算。解 ：消元 ： 舍去或者说被“吃”已知精确解 ：*回代计算解： 高斯选主元消去法的步骤：注：该解若取两位有效数字，则与精确解完全相同。u 优点：数值稳定u 修正方法：消元，回代。高斯-约当（Gauss-Jordam）消去法。u 缺点： 既消元，又回代*323、高斯约当（GaussJordan)消去法高斯消去法始终是消去对角线下方的元素，Gauss
9、Jordan消去法要消去对角线下方和上方的元素。假设G-J消去法已完成第1步第k-1步，得到与原方程组等价的方程组 ，其中第k步计算： （1）按列选主元：即确定ik，使（2）换行：交换 的第k行和第ik行元素（3）消元计算：33（4）计算主行（主元素所在行） 计算解： 上述过程结束后，有*34说明：在解方程组，一般不用 高斯-约当消去法。因为计 算量太大，但是在解多个方程组而它们的系数矩阵相同时，用 此方法，即求系数矩阵的逆矩阵A-1 时，比较合适。设 为非奇异矩阵。如果用列主元G-J消去法将（A, I） 化为（I, T），则 。不用回代，将A化为单位矩阵，则解为常数项列。【定理5】 （高斯约
10、当法求逆矩阵）优点： 缺点：计算量较大，大约是 次乘除法。注：该方法与高等代数中求逆矩阵方法的不同之处是有选主元 ，实际上选主元就是交换两行的位置，仍是初等变换，在一般的 求逆矩阵方法中也有交换两行元素。*35【例6】 用列主元素G-J消去法求 的逆矩阵A-1解：*36所以G-J列主元求逆算法见P176算法3！*37*38作业： P199 12*393 Gauss消去法 的变形1. 直接三角分解法直接从矩阵A的元素得到计算，U元素的递推公式，而不需要任何中间步骤，称之为直接三角分解法。这样，AX=bL(UX)=b LY=b，UX=Y。 不选主元的三角分解 (Doolittle分解法) 通过比较
11、法直接导出L 和 U 的计算公式 。思 路40通过n步可以直接计算定出L，U的元素，其中第r步确定U的 第r行和L的第r列元素。第1步：设第r-1步已确定U的第r-1行和L的第r-1列元素。41第r步：故：故：LU 分解求解线性方程组:*42直接三角分解法解AX = b的计算公式:对于r = 2, 3, , n，(2) 计算U的第r行元素 (3) 计算L的第r 列元素 (r n)(1)*43(4)(5)*44【例7】用直接三角分解法解解：用分解计算公式得：求解：*45*46 选主元的三角分解选主元素三角分解算法见P179!2.平方根法(对称正定矩阵而言) 矩阵的LDR分解【定理6】若n阶矩阵A
12、的所有顺序主子式均不等于零，则矩阵A存在唯一的分解式A =LDR，其中L和R分别是n阶单位下三角阵和单位上三角阵，D是n阶对角元素不为零的对角阵，上述分解也称为A的LDR分解。*47 平方根法如果A为对称矩阵， 且A的所有顺序主子式均不等于零，则A可唯一分解为A=LDLT，其中L是n阶单位下三角阵和D是对角阵。【定理7】（对称矩阵的三角分解定理）*48设A是对称 正定矩阵， 做 LU 分解U =uij=u11uij / uii111u22unn记为A 对称即记 D1/2 =则 仍是下三角阵，且有*49【定理5】（对称正定矩阵的三角分解或Cholesky分解）*50如果A为对称正定矩阵，则存在一
13、个实的非奇异下三角矩阵，使A=LLT ，且当限定的对角元素为正时，这种分解是唯一的。如何确定L呢 ？下面用直接法确定L中元素。*51其中 ，注意到 所以 因此用平方根法解线性代数方程组的算法（1）对矩阵A进行Cholesky分解，即A=LLT，由矩阵乘法：对于 i = 1, 2, n 计算*52（2）求解下三角形方程组 （3）求解LTX = y*53 改进平方根法 其中*54改进平方根法解对称正定方程组的算法 *55令LTX = y，先解下三角形方程组 LDY = b 得解上三角形方程组 LTX = Y 得 *563. 追赶法*57*584 向量和矩阵的范数 1向量范数【定义】设X R n， X 表示定义在Rn上的一个实值函数，称之为X的范数，它具有下列性质：（3）三角不等式：即对任意两个向量X, Y R n，恒有 (1) 非负性：即对一切X R n，X 0, X 0(2) 齐次性：即对任何实数a R，X R n，*59由上可得：设X = (x1, x2, xn)T，则有（1）（2）（3）三个常用的向量范数：范数等价: 设s 和t是Rn上任意两种范数，若存在常数 c1，c2 0 使得: , 则称 s 和t 等价。*60【定理5】(N(x)的连续性)定义在Rn上的向量范数是X分量 的 连续函数。 【定理6】（向量范数的等价性）在Rn上定义
