线性方程组的迭代法.ppt

数值分析 第6章方程与方程组的迭代解法 基本迭代法 迭代法的收敛性 6 2解线性方程组的迭代法 超松弛迭代法 6 2线性方程组的迭代法 在用直接法解线性方程组时要对系数矩阵不断变换 如果方程组的阶数很高 则运算量将会很大 并且大量占用计算机资源 因此对线性方程组 要求找寻更经济 适用的数值解法 1 如果能将线性方程组 1 变换为 2 显然 1 式和 2 式同解 我们称 1 2 等价 对线性方程组 2 采用以下步骤 依此类推 3 这种方式就称为迭代法 以上过程称为迭代过程 迭代法产生一个序列 如果其极限存在 即 则称迭代法收敛 否则称为发散 一 简单迭代法 基本迭代法 设线性方程组 1 的一般形式为 依此类推 线性方程组 1 可化为 4 5 对 4 作迭代过程 则 5 式转化为矩阵形式 6 令 故迭代过程 6 化为 等价线性方程组为 7 称 5 式和 7 式为解线性方程组 1 的Jacobi迭代法 J法 例1 用Jacobi迭代法求解方程组 误差不超过1e 4 解 依此类推 得方程组满足精度的解为x12 迭代次数为12次 x4 3 02411 94780 9205d 0 1573x5 3 00031 98401 0010d 0 0914x6 2 99382 00001 0038d 0 0175x7 2 99902 00261 0031d 0 0059x8 3 00022 00060 9998d 0 0040 x9 3 00031 99990 9997d 7 3612e 004x10 3 00001 99990 9999d 2 8918e 004x11 3 00002 00001 0000d 1 7669e 004x12 3 00002 00001 0000d 3 0647e 005 分析Jacobi迭代法 5 的迭代过程 将 5 式细化 考虑迭代式 7 即 将上式改为 8 9 上式称为Gauss Seidel迭代法 简称G S法 利用 8 式展开Gauss Seidel迭代法也可表示成 例2 用Gauss Seidel迭代法求解例1 解 x1 2 50002 09091 2273d 3 4825x2 2 97732 02891 0041d 0 5305x3 3 00981 99680 9959d 0 0465x4 2 99981 99971 0002d 0 0112x5 2 99982 00011 0001d 3 9735e 004x6 3 00002 00001 0000d 1 9555e 004x7 3 00002 00001 0000d 1 1576e 005 通过迭代 至第7步得到满足精度的解x7 从例1和例2可以看出 Gauss Seidel迭代法的收敛速度比Jacobi迭代法要高 二 迭代法的收敛性 设解线性方程组的迭代格式 10 11 将 10 与 11 相减 得 则 因此迭代法收敛的充要条件 可转变为 定理1 迭代格式 10 收敛的充要条件为 12 根据矩阵与其Jordan标准形及特征值的关系 可知 即 因此 定理2 迭代格式 10 收敛的充要条件为 13 又因为矩阵的谱半径不超过其任一种算子范数 即 于是又可得到 定理3 14 且 证明 只证 14 式 所以 14 即 14 可以用来估计迭代法的精度 理论上只要 在计算时 迭代终止的条件可以用上式判别 例3 判别下列方程组用J法和G S法求解是否收敛 解 1 求Jacobi法的迭代矩阵 因此不能用定理3 只能用定理2判断 所以 即Jaobi迭代法收敛 2 求Gauss Seidel法的迭代矩阵 同样用定理2判断 所以Gauss Seidel迭代法发散 在例1和例2中 G S法收敛速度比J法要高 但例3却说明G S法发散时而J法却收敛 因此 不能说G S法比J法更好 另外 给出系数矩阵对角占优线性方程组的一个结论 定理4 证 1 对于Jacobi迭代法 其迭代矩阵为 根据定理3 Jacobi迭代法收敛 2 对于G S迭代法 其迭代矩阵为 不能使用定理3 而用定理2 即 从而 因此 由于 可得 矛盾 由定理2 G S迭代法收敛 3解线性方程组的超松弛迭代法 超松弛迭代法 简称SOR方法 是高斯 塞德尔方法的一种加速方法 是解大型稀疏矩阵方程组的有效方法之一 设有方程组其中为非奇异矩阵 且设 0 1 2 n 设已知第次迭代向量 及第k 1次迭代向量的分量 要求计算分量 首先用迭代法定义辅助量 再把取为与某个平均值 即加权平均 即 超松弛迭代公式 其中称为松弛因子 或写为 显然 当 1时 SOR方法就是高斯 塞德尔迭代法 当时 称为低松弛法 当时 称为高松弛法 例11 用SOR方法解方程组 它的精确解为 解 取 迭代公式为 取 第11次迭代结果为 0 46 10 5 下面我们写出SOR迭代公式的矩阵形式 迭代公式亦可写为 用分解式A D L U 则 即 显然对任何一个值 非奇异 由设于是 这就是说 设SOR方法迭代公式为 其中 矩阵为SOR方法的迭代矩阵 这说明SOR方法相当于对方程组 应用一般迭代法 于是关于一般迭代法的理论可得到下述定理 定理设有线性方程组Ax b 且 0 i 1 2 n 则解方程组的SOR方法收敛的充要条件是 定理设解Ax b O i 1 2 n 的SOR方法收敛 则 下面研究对于一般方程组 O i 1 2 n 松弛因子在什么范围内取值 SOR方法才可能收敛 现给出SOR方法收敛的必要条件 证明由设SOR方法收敛 设的特征值为 则 而 所以 即 定理如果A为对称正定矩阵 且 则解Ax b的SOR方法收敛 证明在上述假定下 若能证明 那么定理得证 其中为的任一特征值 事实上 设y为对应的的特征向量 即 亦即 为了找出的表达式 考虑数量积 则 显然 记 由于A AT 所以U LT 所以 当O 2时 有 从而 即的任一特征值满足 故SOR方法收敛 注意当O 2时 可以证明