线性方程组的直接解法.ppt

第五章 线性方程组的直接解法 /* Direct Methord for Solving Linear Systems */ 上一页 下一页 返回 第一节 Gauss消去法 第二节 直接三角分解方法 第三节 方程组的性态与误差估计 1 求解 上一页 下一页 返回 2 1 Gauss消去法 一、 高斯顺序消去法 思 路 首先将A化为上三角阵 /* upper-triangular matrix */ ，再回代求解 /* backward substitution */。 = 是一种古老的求解线性方程组的方法, 按自然顺序进 行消元的方法. 上一页 下一页 返回 3 例1 解方程组 解：step1 消元 上一页 下一页 返回 4 Step2 对上三角形方程进行回代求解, 得 下面我们来一般性地讨论求解n阶线性方程组的高 斯顺序消去法. 上一页 下一页 返回 5 消元 Step 1：设 ，计算因子 将增广矩阵/* augmented matrix */ 第 i 行 li1 第1行，得到 与(1)式等价的方程组 上一页 下一页 返回 6 Step 2：一般第 k 次消元 (1k n-1) 上一页 下一页 返回 7 上一页 下一页 返回 8 Step 3：继续上述过程, 且设 aii（i-1）0(i=1,2,n-1),直 到完成第 n-1 次消元, 最后得到与 A(0)x=b(0) 等价的三角 形方程组 A(n-1)x=b(n-1). 将(1)式化为(2)式的过程称为消元过程. 上一页 下一页 返回 9 回代 定理 若A的所有顺序主子式 /* determinant of leading principal submatrices */ 均不为0，则高斯消元无需换行即可进行到底，得 到唯一解。 注注：事实上，只要 A 非奇异，即 A1 存在，则可通过逐次消 元及行交换，将方程组化为三角形方程组，求出唯一解 。 上一页 下一页 返回 10 高斯顺序消去法流程图 F T k=k+1 F T 消元过程 回代过程 上一页 下一页 返回 11 顺序消去法的缺点为当主元akk(k -1)=0时, 消元过程 不能继续进行. 或者当akk (k -1) 0时, 虽然消元过程可以 进行, 但若akk (k -1) 0时, 时, 会出现 很小的数作除数的现象,使舍入误差增大,导致解的严重 失真. 上一页 下一页 返回 12 例：解方程组 /* 精确解为 */ 用Gauss消去法计算： 二、主元素消去法 上一页 下一页 返回 13 由上例可以看出,为提高算法的数值稳定性, 应选取绝对值 尽可能大的元素作主元. 上一页 下一页 返回 按列部分选主元的消去法也称列主元消去法。 14 解： 上一页 下一页 返回 15 一些特殊情况, 主元就在对角线上,不需选主元. 元素满足如下条件的矩阵 即对角线上每一元素的绝对值均大于同行其他各元素绝对 值之和,这样的矩阵称为按行严格对角占优矩阵,简称严格对角 占优矩阵. 例： 性质：严格对角占优矩阵必定非奇异. 上一页 下一页 返回 16 三、高斯-约当消去法 （求矩阵逆） 与 Gauss消去法 的主要区别： 每一步不计算 lik ，而是先将当前主元 akk(k-1) 变为 1; 把 akk(k-1) 所在列的上、下元素全消为0; 这种方法是不是比Gauss 消去法更好? Gauss消去法过程中，消去对角线下方和上方的元素 ，称这种方法为高斯-约当消去法. 上一页 下一页 返回 这种方法不用回代过程了 ，看上去是要好些？ 17 运算量 /* Amount of Computation */ 由于计算机中乘除 /* multiplications / divisions */ 运算的时 间远远超过加减 /* additions / subtractions */ 运算的时间，故 估计某种算法的运算量时，往往只估计乘除的次数，而且通 常以乘除次数的最高次幂为运算量的数量级。 Gauss消去法: Step k：设 ，计算因子 且计算 共进行n 1步 (n k) 次(n k)2 次(n k) 次 (n k) (n k + 2) 次 消元时乘除次数 ： 1 次(n i +1) 次 回代时乘除次数 ： Gauss消去法的总乘除次数为 ，运算量为 级。 上一页 下一页 返回 18 Gauss-Jordan 消去法: 运算量约为 。故通常只用于求逆矩阵，而不用于 解方程组。求逆矩阵即 。 上一页 下一页 返回 19 2 直接三角分解法 一、 LU分解法 /* LU Factorization. */ 就 n=3的情况分析顺序消去法的消元过程. 上一页 下一页 返回 20 可见, 消元过程相当于下述矩阵乘法运算： 由分块乘法可得： 直接计算可得 由(*)式可得 上一页 下一页 返回 21 Step 1: 记M(1) =，则 Step n 1: 其中 M (k)= 以上分析推广到n阶线性方程组可得 上一页 下一页 返回 22 记为 L 单位下三角阵 /* unitary lower-triangular matrix */ 记 U = A 的 LU 分解 /* LU factorization */ 也称 A 的Doolittle分解 上一页 下一页 返回 23 道立特分解法 /* Doolittle Factorization */： LU 分解的紧凑格式 /* compact form */ 根据矩阵乘法法则,先比较等式两边第1行和第1列元素有： 上一页 下一页 返回 24 设已定出U 的第1行到第k-1行的元素 L 的第1列到第k-1列的元素 上一页 下一页 返回 25 (1),(2)两式就是 LU分解的一般计算公式, 其结果与高斯消去法所得 结果完全一样. 避免了中间过程的计算,故称为A的直接分解公式. 上一页 下一页 返回 26 按上图逐框求出矩阵A的LU分解,这种计算方法称为紧凑格式法 。 上一页 下一页 返回 27 定理 若矩阵A非奇异, 则A能分解为LU 的充分必要条件是A的 所有顺序主子式 均不为0. 定理 若非奇异矩阵A有LU 分解,则此分解是唯一的. 上一页 下一页 返回 28 例：利用系数矩阵的 LU分解, 求解方程组 解：LU分解的紧凑格式为 上一页 下一页 返回 29 则求解原方程组等价于求解下面两个方程组Ly=b及Ux=y 上一页 下一页 返回 30 二、三对角方程组追赶法 若A满足Gauss消去法可行的条件，则可用LU分解法求解 其中： 上一页 下一页 返回 31 解方程组Ax=d分为两步，即求解Ly=d和Ux=y，计算公式如下： 上述方法为求解三对角方程组的追赶法，也称Thomas算法. 上一页 下一页 返回 追赶法公式简单，计算量和存储量都小，整个求解过程只 需要5n-4次乘除运算。 32 上一页 下一页 返回 三、平方根法 对称 正定矩阵的分解法 将对称 正定阵 A 做 LU 分解 记为 33 定理 设n阶对称正定矩阵A，则存在唯一的单位下三角阵L及对 角阵D 使得 。 称为矩阵A 的乔累斯基分解 上一页 下一页 返回 定理 设矩阵A对称正定，则存在唯一的对角元为正的下三角阵 L，使得 。 称为对称正定矩 阵A 的乔累斯基分解 利用乔累斯基（Cholesky）分解式来求解Ax=b的方法 也称Cholesky方法或平方根法 34 3 方程组的性态与误差估计 上一页 下一页 返回 一、矩阵的条件数 例，考查以下三个方程组及其准确解 其准确解 其准确解 其准确解 可以看到，后两个方程组与第一个方程组相比，系数矩阵 或右端向量仅有0.0005以下的误差，但准确解却相差很大。对 这样的方程组，无论用多么稳定的算法求解，一旦计算中产生 误差就使解面目全非，所以该方程组的性态很差。 35 上一页 下一页 返回 定义：若方程组Ax=b的系数矩阵A与右端向量b的微小变化（ 小扰动）,将引起解向量x产生巨大变化，则称此方程组为病态 方程组，其系数矩阵A称为病态矩阵，否则称Ax=b为良态方程 组，称A为良态矩阵 . 方程组的病态程度与Ax=b对A和b的扰动的敏感程度有关。 36 求解 时，A 和 的误差对解 有何影响 ？ 设 A 精确， 有误差 ，得到的解为 ，即 绝对误差放大因子 又 相对误差放大因子 上一页 下一页 返回 37 设 精确，A有误差 ，得到的解为 ，即 (只要 A充分小，使得 是关键 的误差放大因子，称为 A的条件数，记为cond (A) , 越 则 A 越病态， 难得准确解。 大 上一页 下一页 返回 38 注: cond (A) 的具体大小与 | | 的取法有关，但相对 大小一致。 cond (A) 取决于A，与解题方法无关。 常用条件数有： cond 1(A)cond (A)cond2 (A) 特别地，若 A 对称，则 条件数的性质： A可逆，则 cond p (A) 1； A可逆， R 则 cond ( A) = cond (A) ； A正交，则 cond 2 (A) =1； A可逆，R正交，则 cond 2 (RA) = cond 2 (AR) = cond2 (A) 。 上一页 下一页 返回 39 精确解为例 计算cond 2(A) 。 A1 = 解：考察 A 的特征根 39206 1 测试病态程度： 给 一个扰动，其相对误差为 此时精确解为 2.0102 200% 上一页 下一页 返回 40 例：Hilbert 阵 cond (H2) = 27cond (H3) 748 cond (H6) = 2.9 106cond (Hn) as n 注：一般判断矩阵是否病态，并不计算A1，而由经验 得出。 行列式的值很大或很小（如某些行、列近似相关 ）； 元素间的数量级相差大，且无规则； 主元消去过程中出现小主元； 特征值相差大数量级。 上一页 下一页 返回 41 二、方程组解的误差估计 定理