第3章线性方程组的数值解法1.ppt

科学和工程计算 第3章 解线性方程组的直接方法 上述消元过程除第一个方程不变以外, 第2—第 n 个方程全消去了变量 ?1，而系数 和常数项全得到新值： 回代过程算法 高斯主元素消去法 高斯—若当消去法 Gauss消去法的矩阵表示 LU形式 直接计算 A 的 LU 分解(例) 一般计算公式 LU 分解求解线性方程组 i+1行 i+1行 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 . 定理 若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 分解。 计算量与 Gauss 消去法同. * Direct Method for Solving Linear Systems 其中 简记作 求解 解线性方程组的两类方法： 迭代法：从解的某个近似值出发，通过构造一个无穷序列去逼近精确解的方法。（一般有限步内得不到精确解） 直接法: 经过有限次运算后可求得方程组精确解的方法(不计舍入误差!) Gauss 消去法 一、Gauss 消去法计算过程 相当于第i个方程-第一个方程×数→新的第i方程—同解！第一方程不动！ 其中 系数矩阵与常数项： 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. 定理6 若A的所有顺序主子式 /* determinant of leading principal submatrices */ 均不为0，则高斯消元无需换行即可进行到底，得到唯一解。 注：事实上，只要 A 非奇异，即 A?1 存在，则可通过逐次消元及行交换，将方程组化为三角形方程组，求出唯一解。 消去第一列的 n-1 个系数要计算n*(n-1） 个乘法。 Gauss消去法乘法计算量 例1. 用Gauss消去法解线性方程组(用3位十进制浮点数计算） 解: 本方程组的精度较高的解为 用Gauss消去法求解(用3位十进制浮点数计算) 9999 回代后得到 与精确解相比,该结果相当糟糕 究其原因,在求行乘数时用了很小的数0.0001作除数 主元 如果在求解时将1,2行交换,即 0.9999 回代后得到 这是一个相当不错的结果 每一步消去过程相当于左乘初等变换矩阵Lk