Gauss消去法、 矩阵分解

2 1Gauss消去法 下面通过简单例子导出一般算法 设给定方程组 1 5 2Gauss消去法 矩阵分解 乘以第一个方程 这样方程组 1 其中 显然方程组 2 和原方程组 1 等价 其中 依此方法继续下去 得到 乘以第二个方程 得到 4 其中 从 4 的最后一个方程组得到 再将 代入 4 倒数第二个方程 可得 类似地 得到 我们称将方程组 1 按以上步骤化为等价方程组 4 的过程为解线性方程组的消元过程 从 4 中得出解的过程称为高斯消去法的回代过程 一般情形 1 消元过程 首先消去第一列除之外的所有元素 设 其中 这里取 2 回代过程 若通过消元过程原方程组已化为等价的三角形方程组 且 则逐步回代可得原方程组的解 2 2Gauss主元素消去法 Gauss逐步消去法有如下的缺点 任一主元 就无法做下去 任一绝对值很小时 也不行 舍入误差的影响大 例二元线性方程组 精确解为 下面我们用三位浮点十进制数求解 1 按Gauss逐步消元法 得近似解 完全失去近似意义 2 变换方程的顺序然后消元 得近似解 相当近似 下面我们讨论选主元素的方法 1 列主元消去法 并令为达到最大值的最小行标 可以防止有效数字大量丢失而产生误差 2 全主元消去法 定义 然后进行第步消元过程 此时交换和的行及的列 使主元位置的元素的绝对值具有给出的最大值 注意 因为有列的交换 因此未知量的次序有改变 待求解过程结束后必须还原 多使用列主元消去法 2 3矩阵的三角分解与Gauss消去法的变形 Gauss消去法的实质是将矩阵分解为 其中 单位下三角矩阵 上三角矩阵 事实上 线性方程组 经过步消元过程后 有等价方程组 其中 而和的形式为 1 可以直接验证 其中 则也是对角元等于1的下三角阵 用矩阵依次左乘原给方程组两边 得等价方程组 我们可以计算得到 则 其中 2 Gauss逐步消去法等价于下述过程 2 求解三角形方程组 回代过程 注意上面的全部讨论中要求 其中 证明 其中形如 1 式 我们可以将写成 定理5 10 将 3 写成分块形式为 于是得到 从而 因此 即有分解形式的充分必要条件为的所有顺序主子阵非奇异 形如 2 的分解 那么 既是对角元等于1的上三角阵 又是对角元等于1的下三角阵 即 所以 从而的分解形式是唯一的 证毕 定理5 11 Doolittle分解算法 比较等式两边对应元素可算出 Doolittle分解也可通过令 Crout分解 比较两边对应的元素 得到 例 实际上 进一步可以做分解 其中 分别为单位下 上三角阵 1 对称正定阵的Cholesky分解 首先我们来看一个命题 证明 我们对A做分解 其中 分别为单位下 上三角阵 于是有 由于正定 故有 取 令 即得 证毕 我们将上面的这种分解称为Cholesky分解 下面我们讨论Cholesky分解的算法 比较两边对应的元素 有 以的第二行乘的前两列 即得 又可以解出 由的正定性可知平方根中值为正的 由矩阵乘法解得 例 2解三对角方程组的追赶法 设线性方程组的系数矩阵为三对角矩阵 当的所有顺