数值分析3-计算方法3线性方程组的数值解法

第三章线性方程组的数值解法线性方程组的数值解法有两种 1 迭代法 2 直接法 3 1线性方程组的迭代法设有线性方程组 当 为一大规模线性方程组时 采用迭代法求解不仅可节省内存 还能减少计算量 1 Jacobi迭代法设 将 矩阵分解为 其中 11 22 0 12 1 0 2 1 0 0 210 1 1 1 1 2 2 0于是 假定 0 1 2 则对角阵 非奇异故有 据此 得下述Jacobi迭代公式 记 则有 其中 矩阵 称为Jacobi法迭代矩阵例3 1求解方程组10 1 0 2 2 2 3 7 2 1 10 2 2 3 8 3 1 2 5 3 4 2 将原方程组改为下述等价形式 1 0 1 2 0 2 3 0 72 2 0 1 1 0 2 3 0 83 3 0 1 1 0 2 2 0 84据此 得Jacobi迭代公式取迭代初值 表3 1准确值 1 1 1 2 1 2 3 1 3 2 Gauss Seidel迭代法回看上例Jacobi迭代公式在计算时 用到和进行计算 此时更新的迭代值已经计算出来 而没有被应用 计算时 没有利用更新的迭代值和 为加快迭代收敛速度 做如下改进 仍取初值表3 2 由上例可见 一般而言 Gauss Seidel迭代法的收敛速度高于Jacobi迭代法 但是 这两个方法的收敛范围并不完全重合 只是部分相交 在某些情形下 Jacobi迭代法可能比Gauss Seidel迭代法收敛更快 甚至可能Jacobi迭代法收敛 而Gauss Seidel迭代法却迭代发散 Gauss Seidel迭代法的矩阵表示 1 1 据此 得Gauss Seidel迭代公式 1 1 1 记 1 1 便有 1 其中 矩阵 称为Gauss Seidel法迭代矩阵 3 超松弛迭代法 SOR 以G S迭代法为基础 构造超松弛迭代法 其中 1 1 称为松弛因子 1超松弛法 1低松弛法 1为G S迭代法 例3 2用SOR方法解方程组 41111 4111111 411 4 1 2 3 4 1111该问题的精确解为 1 1 1 1 解 取 0 0 0 0 0 迭代公式为 如果精度要求为 2 10 5取 1 3时 迭代11次的结果为 11 0 9999964 1 0000031 0 9999995 0 999991 4 迭代法的收敛性定理3 1设有方程组 对于任意初始向量 及任意 迭代公式 收敛的充要条件是 1证明 设 为方程 的准确解 即 对任意初值 0 及任意 迭代公式为 1 于是 2 结合定理1 7 即可得证 例3 3考察用迭代法解下列方程组 1 的收敛性 其中 解 矩阵 的特征值分别为 1 0 3082 2 0 1541 0 3245 3 0 1541 0 3245 这里 1 0 3082 1 2 3 0 3592 1此时 1于是 迭代公式 1 对任意初始向量是收敛的 定理3 2 迭代收敛的充分条件 设有迭代公式 如果 系数矩阵 对角占优的线性方程组 称作对角占优的线性方程组 显然 max1 1定理3 3如果线性方程组 是对角占优的 则其Jacobi迭代公式对任意初始向量是收敛的 证明 将方程 改为如下等价形式 1 显然有 1 Jacobi迭代公式为于是由此 记故有 因此 得 所以 Jacobi迭代法收敛 同理 可证明 当线性方程组 是对角占优方程组时 其Gauss Seidel迭代公式收敛 3 2线性方程组的直接解法1 Gauss消元法设有方程组 其中 11 12 1 21 22 2 1 2 为后续讨论方便 记 1 1 原方程为 1 1 1 假定 分别计算 2 3 用乘方程组 1 第一个方程 分别加到第 个 2 3 方程上 由此得与 1 1等价的方程组 记作 2 22 假定 分别计算 3 4 用乘方程组 1 第一个方程 分别加到第 个 2 3 方程上 由此得 3 重复上述消元过程 经过 1次消元 得该方程组为一个上三角方程组 4 回代求解从计算 开始 依次解出 1 1 这个过程称作回代过程 具体公式为 1 2 1 第一次消元记作记作 1 1 2 运算次数 乘除法 1 1 1 1 加法 1 第二次消元记作 2 2 3 运算次数 乘除法 2 1 2 2 加法 1 2 第 1次消元记作 1 1 运算次数 乘除法1 2加法2 1 2 2 1 消元过程总的乘除法次数 1 1 2 3 1 1 3 33 22 5 6消元过程总的加法次数 1 1 2 2 3 1 2 33 3回代过程的乘除法次数和减法次数为 1 2 1 2 2 Gauss主元素消元法Gauss消元法存在的问题 当元素时 消元过程无法进行当元素 但其绝对值很小时 用它做除数 可导致计算过程中舍入误差的放大和某些数据数量级的放大例3 4用4位浮点数 求解下列方程组0 0012 0003 000 1 0003 7124 623 2 000 1 0705 643 1 2 3 1 0002 0003 000 解 Gauss消元法 0 0012 0003 000 1 000 1 0003 7124 623 2 000 2 000 1 0705 643 3 000 0 0012 0003 000 1 000020043005 1002040016006 2003 21 1000 22 2000 0 0012 0003 000 1 000020043005 1002005 000 2 000 32 1 997利用回代过程 得 0 000 0 0998 0 4000 而该方程组舍入到4位有效数字的解为 0 4904 0 05104 0 3675 2 Gauss完全主元消元法在矩阵 中找到绝对值最大的元素 称作主元 将方程组 的第p个方程与第1个方程互换 系数矩阵 的第q列与第1列互换 然后做第1次消元 得等价方程组 1 在矩阵 1中寻找绝对值最大的元素 类似前述步骤 做相应行列互换 将主元移至第2行第2列 然后做第2次消元 依次类推 得 依回代公式 解得 1 2 最后 按变量的原有顺序输出解 1 2 3 Gauss列主元消元法完全主元消元法会改变变量 1 2 的顺序 如果主元仅限于按列选取 则无需改变变量之间的顺序 比如 第1次消元时仅在第1列中选主元 然后将主元所在方程与第1行方程互换 此时变量顺序不被改变 例3 5用4位浮点数 求解下列方程组0 0012 0003 000 1 0003 7124 623 2 000 1 0705 643 1 2 3 1 0002 0003 000解 Gauss列主元消元法 2 000 1 0705 643 3 000 1 0003 7124 623 2 0000 0012 0003 000 1 000 21 0 5000 22 0 0005 2 000 1 0725 643 3 00003 1761 801 0 500002 0013 003 1 002 32 0 6300 2 000 1 0725 643 3 00003 1761 801 0 5000001 868 0 6870解得 0 4900 0 05113 0 3678 该方程组舍入到4位有效数字的解为 0 4904 0 05104 0 3675 4 Doolittle三角分解法定理3 4当 且其顺序主子式 0 1 2 1 矩阵 可做 分解 即 其中 1 211 1 2 1 11 12 1 22 2 由Gauss消元法 得 1 2 2 1 这里 1 2 2 1 显然矩阵 可逆 记 1 于是 1 设有 且 11 12 1 21 22 2 1 2 1 211 1 2 1 11 12 1 22 2 由上式可分别求得系数 2 1 1 1 1 于是方程组 转化为 令 则有 原方程组 的求解转化为下述两个三角方程组的求解 计算量与Gauss消元法相当 5 系数矩阵为对称正定矩阵的线性方程组的平方根方法定理3 5若 为对称正定矩阵 则存在唯一的主对角元素为正的下三角矩阵 使 Cholesky分解 其中 11 21 22 1 2 0 1 2 由 11 21 1 21 22 2 1 2 11 21 22 1 2 11 21 1 22 2 比较两端 1 1 1 1 212 1 1 令 则有 于是由下述两个三角线性方程组求得方程组 的解 计算量约为Doolittle方法的一半 6 三对角线性方程组的追赶法设 的系数矩阵 1 1 2 2 2 1 称 为三对角矩阵定理3 6若三对角矩阵 满足 1 1 2 3 1 则矩阵 是非奇异的 假设 满足定理3 4 则 可做三角分解 其中 1 21 1 1 1 2 1 1 1 1 2 3 1 2 3 于是追 1 1 1 2 3 赶 1 1 2 1 3 3线性方程组的性态和误差分析例3 6设有方程组 1 2 2 1 1 0001 2 2 0001准确解为 1 1 2 1 假定常数项有微小变换 如 1 2 2 1 1 0001 2 2准确解为 1 2 2 0 常数项微小变换