第五章 解线性方程组的直接方法-1.pptVIP

* 上三角阵， 算法1第 步需要作 次除法， 次乘法， 因此，本算法(从第1步到第 步消元计算总的计算量) 当 时，总共大约需要 次乘法运算. 数 称为约化的主元素. 算法2(回代算法) 设 其中 为非奇异 本算法计算 的解. 对于 (1) 大约需要 次乘法(对相当大的 ). * (2) 对于 (3) 这个算法需要 乘除法运算. 高斯消去法对于某些简单的矩阵可能会失败， 由此，需要对算法1进行修改， 例如 在什么条件下才能保证 首先需要研究原来的矩阵 * 定理6 约化的主元素 的充要条件 是矩阵 的顺序主子式 即 （2.12） 证明 显然，当 时，定理6成立. 现设定理6充分性对 是成立的，求证定理6充分性对 亦成立. 首先利用归纳法证明定理6的充分性. * 设 可用高斯消去法将 约化到 ， 且有 于是由归纳法假设有 即 * （2.13） 由设 定理6充分性对 亦成立. 显然，由假设 利用(2.13)式， 则有 利用(2.13)式亦可 推出 * 推论 如果 的顺序主子式 则 * 于是对(2.1)施行第一次消元后化为(2.7)， 5.2.2 矩阵的三角分解 下面借助矩阵理论进一步对消去法作些分析，从而建 立高斯消去法与矩阵因式分解的关系. 设(2.1)的系数矩阵 的各顺序主子式均不为零. 由于对 施行行的初等变换相当于用初等矩阵左乘 ， 这时 化为 化为 ， 即 * 其中 一般第 步消元， 化为 , 化为 ， 相当于 其中 * 重复这过程，最后得到 （2.14） 记上三角矩阵 为 ，由(2.14)得到 * 其中 为单位下三角矩阵. 这就是说，高斯消去法实质上产生了一个将 分解为 两个三角形矩阵相乘的因式分解，于是得到如下重要定理， 它在解方程组的直接法中起着重要作用. * 定理7 设 为 阶矩阵， 如果 的 顺序主子式 则 可分解为一个单位 下三角矩阵 和一个上三角矩阵 的乘积， 证明 现在在 为非奇异矩阵的假定下证明唯一性， 设 其中 为单位下三角矩阵， 为上三角矩阵. (矩阵的LU分解) 且这种分解是 唯一的. 根据以上高斯消去法的矩阵分析，存在性已得证， * 上式右边为上三角矩阵，左边为单位下三角矩阵， 例2 由高斯消去法， 由于 存在，故 从而上式两边都必须等于单位矩阵， 唯一性得证. 故 对于例1，系数矩阵 故 * * 例3 5.3 高斯主元素消去法 由高斯消去法知道，在消元过程中可能出现 即使主元素 但很小时，用其作除数，会导致其他元素数量级的严重增长和舍入误差的扩散，最后也使得计算解不可靠. 这时消去法将无法进行； 求解方程组 * 用4位浮点数进行计算. 精确解舍入到4位有效数字为 解法1 用高斯消去法 * 计算解为 显然计算解是一个很坏的结果，不能作为方程组的近似解. 其原因是我们在消元计算时用了小主元 0.001，使得约化后的方程组元素数量级大大增长，经再舍入使得在计算(3,3)元素时发生了严重的相消情况，因此经消元后得到的三角形方程组就不准确了. * 解法2 交换行，避免绝对值小的主元作除数. * 得计算解为 这个例子告诉我们，在采用高斯消去法解方程组时， 小主元可能产生麻烦，故应避免采用绝对值小的主元素 对一般矩阵来说，最好每一步选取系数矩阵(或消元后 的低阶矩阵)中绝对值最大的元素作为主元素，以使高斯消 去法具有较好的数值稳定性. 这就是全主元素消去法. 在选主元时要花费较多机器时间，目前主要使用的是 列主元消去法. * 本节主要介绍列主元消去法，并假定(2.1)的 为非奇异的. * 5.3.1 列主元素消去法 设方程组(2.1)的增广矩阵为 首先在 的第一列中选取绝对值最大的元素作为主元素， 例如 * 重复上述过程， 设已完成第 步的选主元素，交换两行 然后交换 的第1行与第 行，