[理学]3 解线性方程组的直接法.ppt

第3章 解线性方程组的直接法 §3.1 高斯消元法 思路 消元 回代 用高斯消去法解方程组 求解 例：单精度解方程组 ? 全主元消去法 用列主元消去法解方程组 ? 高斯-约当消去法 高斯—约当消去法的演变过程 ? 例：用高斯—约当消去法与主元素相结合求解下列方程组的根 ? 例：用高斯—约当消去法求矩阵A 的逆矩阵 §3.2 三角分解法 定理 ? Doolittle分解法 —— LU 分解的紧凑格式 ? 例：用Doolittle分解求解方程组 * 求解 预备知识 关于未知量x1，x2，……，xn的线性方程组可表示为： 其中aij，bi为方程组的系数 写成矩阵形式，Ax=b 称A为系数矩阵，x=(x1,x2,……,xn)T为解向量， b=(b1,b2,……,bn)T为常数向量。当detA=D≠0时，由线性代数 的克莱姆法则，方程Ax=b 的解存在且唯一。其中： Di是将A的第i列元素以b代替的矩阵的行列式的值。 用克莱姆法则运算： n=30，需要进行2.38×1035次运算 解： 例 ? 高斯消元法： 首先将A化为上三角阵，再回代求解 = 高斯消元法解方程得两个步骤：消去和迭代 高斯消元法的工具 对线性方程组 而言 施以以下变换 对换某两个方程的次序 对某个方程的两边乘一个不为零的数 把某一个方程两边同乘一个常数后加到另一个方程的两边 从矩阵变换的角度看，其作用相当于方程组得增广矩阵 施以以下变换 对换(A,b)的某两行 (A,b)中的某行乘以一个不为零的数 把(A,b)某一行乘一个常数后加到另一行 高斯消去法就是通过以上变换，把(A,b)转化为等价的上三角形式，然后回代求解 记 Step 1：设 ，计算因子 将增广矩阵第 i 行 ? mi1 ? 第1行，得到 其中 Step k：设 ，计算因子 且计算 共进行 ？ 步 n ? 1 若A的所有顺序主子式 均不为0，则高斯消元无需换行即可进行到底，得到唯一解。 定理3-1 注：事实上，只要 A 非奇异，即 A?1 存在，则可通过逐次消元及行交换，将方程组化为三角形方程组，求出唯一解。 例 取小数点后4位时(A,b)做高斯消去法 做回代过程有： /* 精确解为 和 */ 8个 8个 用高斯消去法计算： 8个 小主元 可能导致计算失败。 每一步选绝对值最大的元素为主元素，保证 Step k: ① 选取 ② If ik ? k then 交换第 k 行与第 ik 行; If jk ? k then 交换第 k 列与第 jk 列; ③ 消元 注：列交换改变了 xi 的顺序，须记录交换次序，解完后再换回来。 ? 列主元消去法 省去换列的步骤，每次仅选一列中最大的元。 例 对(A,b)做选主元及消去过程 解 由同解方程 ，回代过程有： 例： ? 注：列主元法没有全主元法稳定。 例 注意：这两个方程组在数学上严格等价。 ? ? 标度化列主元消去法 对每一行计算　　　　　 。为省时间，si 只在初始时计算一次。以后每一步考虑子列 中　 最大的 aik 为主元。 注：稳定性介于列主元法和全主元法之间。 与 Gaussian Elimination 的主要区别： ? 每步不计算 mik ，而是先将当前主元 akk(k) 变为 1; ? 把 akk(k) 所在列的上、下元素全消为0; 因此，高斯消去法是将系数矩阵化为上三角矩阵，再进行回代求解；高斯—约当消去法是将系数矩阵转化为对角矩阵，再进行回代求解。 ? 对于系数增广矩阵 ? 第一步，将a11变为1; ? 第二步，将a22变为1; ? 将除a11外的第一列的元素变为0; ? 将除a22外的第二列的元素变为0; ? 对于第k步来讲 ? 第k步，将akk变为1; ? 将除akk外的第k列的元素变为0; ? 经过n步运算后，变为下面的形式 ? 此时增广矩阵对应的方程组为 ? 解：其对应的增广矩阵变化情况如下： 对应方程组为： 优点：不用换行、换列，不用回代，精度高 缺点：循环语句比较难组织 ? 解： 于是得 ? 高斯消元法的矩阵形式 Step 1: 记 L1 = ，则 Step n ? 1: 其中 Lk = 记为 L 单位下三角阵 记 U = A 的 LU 分解 若A的所有顺序主子式