高斯消去法详解.ppt

5.2 Gauss消去法 一、消元与回代计算 对线性方程组 对其增广矩阵施行行初等变换: 定义行乘数 且 定义行乘数 What if ? No unique solution exists. What if ? Then we must find the smallest integer k ? i with , and interchange the k-th row with the i-th row. What if we can’t find such k ? No unique solution exists. 定理 若A的所有顺序主子式 /* determinant of leading principal submatrices */ 均不为0，则高斯消元无需换行即可进行到底，得到唯一解。 注：事实上，只要 A 非奇异，即 A?1 存在，则可通过逐次消元及行交换，将方程组化为三角形方程组，求出唯一解。 二、矩阵的三角分解 1.Gauss消去法消元过程的矩阵描述 行变换相 当于左乘 初等矩阵 由于 令 则 显然若令 则有 因此 从而 故 即 且 顺序主元 定义1. 不带行交换的Gauss 消去法的消元过程,产生 一个单位下三角矩阵L和一个上三角矩阵U,即 该过程称之为 由上述分析不难得到 Hey hasn’t GE given me enough headache? Why do I have to know its matrix form??! When you have to solve the system for different with a fixed A. Could you be more specific, please? Factorize A first, then for every you only have to solve two simple triangular systems and . Gauss消去法 可以执行 定理1. 在定理中,可能注意到 可能存在 §2 Matrix Factorization – Matrix Form of G.E. 定理 若A的所有顺序主子式 /* determinant of leading principal submatrices */ 均不为0，则 A 的 LU 分解唯一（其中 L 为单位下三角阵）。 证明：由§1中定理可知，LU 分解存在。下面证明唯一性。 若不唯一，则可设 A = L1U1 = L2U2 ，推出 Upper-triangular Lower-triangular With diagonal entries 1 ? 注： L 为一般下三角阵而 U 为单位上三角阵的分解称为Crout 分解。 实际上只要考虑 A* 的 LU 分解，即 ，则 即是 A 的 Crout 分解。 例：用矩阵的直接三角分解法（LU分解，L为单位下三角阵、U为上三角阵）解方程组 。 二、Gauss消去法的运算量 计算机作乘除运算所耗时间要远远多于加减运算 且在一个算法中，加减运算和乘除运算次数大体相当 故在衡量一个算法的运算量时只需统计乘除的运算次数 乘法次数： 除法次数： 全部回代过程需作乘除法的总次数为 于是Gauss消去法的乘除法运算总的次数为 数级 Gauss消去法乘除法约为2700次 而如果用Cramer法则的乘除法运算次数约为 或 用行列式定义 用行列式性质 ?