数值分析5-2(高斯消去法).ppt

一、高斯消去法 第五章 解线性方程组的直接法 §2 高斯消去法 二、矩阵的三角分解 三、高斯消去法的计算量 四、高斯—约当消去法 一、高斯消去法 1. 高斯消去法的基本思想 举例 用消去法解方程组 （求解过程详见书，请同学们自学） 基本思想：用逐次消去未知数的方法把原来方程组AX=b化为与其等价的三角形方程组，而求解三角形方程组就容易了！ 2. 高斯消去法的一般过程 记 Ax = b 为 A(1)x = b(1)， (1) 消元过程 第一次消元 (记 为 A(2)x = b(2)) …… 第n-1次消元 (记 为 A(n)x = b(n)) (2) 回代过程 高斯消去法的特点：消元和回代不同步！ 3. 使用高斯消去法的条件 使用高斯消去法要求在每步消元时 ， 那么矩阵A满足什么，才能保证这一条件呢？ 引理：约化的主元素 (i=1,2,…,n) 的充 要条件是矩阵A的顺序主子式 推论：如果A的顺序主子式不等于0，则 (k=2,3,…,n) 定理：如果 n 阶矩阵A的所有顺序主子式均 不为零，则可通过高斯消去法（不进行交 换两行的初等变换），将方程组约化为三 角形方程组。 定理：如果A为 n 阶非奇异矩阵，则可通过高斯消去法（及交换两行的初等变换）将方程组 Ax=b 化为三角形方程组。 二、矩阵的三角分解 由矩阵理论可知，对系数矩阵 A 实施行的初 等变换相当于用初等矩阵左乘 A ，即 等价于 其中 行初等变换 行初等变换 初等 矩阵 例 ①*(-2)+③ 则 其中 ①*(-2)+③ 考察高斯消去法过程 ： 等价于 其中 第一次消元 消元时的系数 而且 重复这一过程，共进行 次消元，得 ｎ－1 将上三角矩阵 A(n) 记为 U，则有 其中 Gauss消去法将A分解为两个三角矩阵相乘 定理: (矩阵的LU分解) 设 A 为 n 阶矩阵，如果 A 的顺序主子式 ( i = 1,2,…,n-1)， 则 A 可分解为一个单位下 三角矩阵 L 和一个上三角矩阵 U 的乘积，且 这种分解是唯一的。 注：若A 实现了LU分解，则 Ax = b (LU)x=b Ly = b Ux = y 求解两个三角形方程组! 举例：用系数矩阵的LU分解求下列方程组 解： 系数矩阵为 由高斯消去法， m21=0，m31=2 m32=－1，故 则求解原方程组可转化为如下两个三角形方 程组： 三、高斯消去法的计算量 定理：如果 A 为 n 阶非奇异矩阵，则用高斯 消去法解 Ax = b 所需的乘除法次数及加减法 次数分别为 例如：n=10时，高斯消去法需要430次乘除法，而Cramer法则却需乘法。 四、高斯—约当消去法(Gauss-Jordan) 高斯消去法在消元时始终消去对角线下方的 元素，而高斯——约当消去法则同时消去对 角线上方和下方的元素。 第一次消元 (与高斯消去法不相同) 第二次消元 … 故方程组的解为 高斯——约当消去法的特点： (1) 消元和回代同时进行； (2) 乘除法的次数要比高斯消去法大，所以通常用于同时求解系数矩阵相同的多个方程组或求逆矩阵。 高斯-约当消去法的应用 1.同时求解系数矩阵相同的多个方程组 例 用高斯-约当消去法求解两个方程组 AX=b1 和AX=b2 ，其中 解 增广矩阵为 ①×1/3 消元 ②×3/4 消元