3_YQJ_Ch2_1_3方程组Hh.ppt

第2章 线性方程组的解法 ——直接法与迭代法 在自然科学与社会科学的研究中，常常需要求解线性代数方程组，这些方程组的系数矩阵大致分为两种：一种是低阶稠密矩阵（例如：阶数大约为小于等于150），另一种是大型稀疏矩阵（即矩阵阶数高且零元素较多）。 在计算机上求解线性代数方程组 Ax=b 的常用的数值解法： 1、直接法：就是经过有限次算术运算，可求得方程组精确解的方法（若计算过程中没有舍入误差）。但实际计算中由于舍入误差的存在和影响，这种方法也只能求得线性方程组的近似解。 这类方法是解低阶稠密矩阵及大型带状方程组的有效方法。 2、迭代法：就是用某种极限过程去逐步逼近线性方程组精确解的方法，迭代法具有需要计算机的存贮单元较少，程序设计简单，原始系数矩阵在计算机中始终不变等优点，但存在收敛性和收敛速度等问题。 迭代法是解大型稀疏矩阵方程组的重要方法。 高斯消去法的基本思想 将原方程组逐次消去未知元， 变为与之同解的上三角方程组， 再回代求解 。 2.1.1 顺序Gauss消去法 在使用高斯消去法的过程中，仅对方程组做倍加变换，就形成了顺序高斯消去法。 2.1.2 列主元素Gauss消去法 ?定义 使用高斯消去法的过程中，在第 k 次消元前，先对第 k 个增广阵 [ A(k), b(k) ] 做交换二行的变换，把 中绝对值最大的元素换到 (k, k) 位置，再消元。此方法叫列主元素高斯消去法。其算法如下：记 ?注解：此算法中的 称为第 k 个列主元素，它的值总要被换到位置 (k, k) 。 §2.2 直接三角分解法 ?定义 下面的 n×n 矩阵叫做初等下三角矩阵。 求解线性方程组的Doolittle分解法 Crout 分解 例 用矩阵的杜利脱尔（Doolittle）分解解方程组 解：设 2.2.3 三角分解法解带状线性方程组 定义 设矩阵 A = [aij]，如果存在两个正整数 r 和 s，使得当 i -j r 以及 j -i s 时，有 aij=0 ， 则 称 A 是上半带宽为 s，下半带宽为 r 的带状矩阵，线性方程组 Ax =b 称为带状方程组。即，带状矩阵 A 为 2.2.4 追赶法求解三对角线性方程组 设 n 元线性方程组 Ax = b 的系数矩阵为非奇异的 三对角阵 §2.3 矩阵的条件数与病态线性方程组 2.3.1 矩阵的条件数与线性方程组的性态 给定线性方程组 Ax =b，现在考察，系数矩阵 A 和常数列 b 有了微小变化 △A，△b ，它如何影响解向量 x，即，解向量 x 的变化量 △x 何样？ 由于A （或 b）的元素是测量得到的，或者是计算的结果，在前种情况下， A （或 b）常常带有某些观测误差，在后种情况下， A （或 b）包含舍入误差，因此我们处理的实际矩阵是A + △A （或 b+ △b ）。 定义 如果矩阵 A 或常数项 b 的微小变化，引起方程组 Ax =b 的解的巨大变化，则称方程组为“病态”方程组，矩阵 A 称为“病态”矩阵；否则称方程组为“良态”方程组， A 称为“良态矩阵”。 ?误差分析 由此可以看出，量 ||A|| ? ||A-1|| 越小，由A （或 b）的相对误差引起的解的相对误差|| △x || / || x ||就越小 ；量 ||A|| ? ||A-1|| 越大，解的相对误差就可能愈大，所以量 ||A|| ? ||A-1|| 实际上刻划了解对原始数据变化的灵敏程度，即刻划了方程组的“病态”程度。 条件数的性质 cond(A) = || A || ? || A-1 || (1) 对任何可逆阵 A，cond(A) ≥1. (2) A 是可逆阵, k ≠0，则 cond(kA) = cond(A). (3) A 可逆实对称阵，则 cond(A)2 = | l1 | ∕ | ln |. 其中， l1 和ln 分别是 A 的模最大和最小的特征值。 (4) A 正交阵，则有 cond(A)2 = 1。 (5)设A为可逆阵 ，P为正交阵，则有 cond(PA)2 = cond(AP)2 = cond(A)2 2.3.2 关于病态线性方程组的求解问题 1. 病态方程组的判别 (1) 当 |det(A)| 相对很小或 A 的某些行(列)近似线性相关时，方程组可能病态. (2) 用列选主元素消