线性方程组的解法.ppt

线性方程组的解法 解线性方程组的迭代法IterativeMethodsforLinearSystemsJacobi迭代和Gauss Seidel迭代迭代法的矩阵表示MatrixformoftheIterativeMethods 线性方程组的解法在计算数学中占有极其重要的地位 线性方程组的解法大致分为迭代法与直接法两大类 雅可比 Jacobi 迭代法 举例说明雅可比迭代法的基本思路 例4 1 特点 系数矩阵主对角元均不为零 取迭代初值x1 0 0 x2 0 0 x3 0 0 将方程改写成如下等价形式 据此建立迭代公式 x 0 000 x 1 0 77780 80000 8667 x 2 0 96300 96440 9778 x 3 0 99290 99350 9952 x 4 0 99870 99880 9991 x1 1 0000 x2 1 0000 x3 1 0000 准确解 可以看出 迭代每前进一步 结果就逼近准确解一步迭代过程收敛 矩阵形式 以上这种迭代方法称雅可比 Jacobi 迭代法 基本思想 将方程组的求解问题转化为重复计算一组彼此独立的线性表达式 i 1 2 n k 0 1 2 i 1 2 n 设有方程组 将第i个方程的第i个变量xi分离出来 据此建立分量形式的雅可比迭代公式 如果 用矩阵形式来表示雅可比迭代公式 设有方程组 AX b其中A aij n为非奇异矩阵 X x1 x2 xn T b b1 b2 bn T 唯一解为X x1 x2 xn T将A分解为 A U D L其中 于是 U D L X b得X D U L X D b据此得矩阵形式的雅可比迭代公式X k 1 D U L X k D b记B D U L f D b有B 迭代矩阵 任取X 0 迭代计算产生向量序列 若 则迭代过程收敛 x 是方程组Ax b的解 X 1 X 2 X k 迭代法适用于解大型稀疏方程组 万阶以上的方程组 系数矩阵中零元素占很大比例 而非零元按某种模式分布 背景 电路分析 边值问题的数值解和数学物理方程 问题 1 如何构造迭代格式 2 迭代格式是否收敛 3 收敛速度如何 4 如何进行误差估计 高斯塞德尔Gauss Seidel迭代法 Gauss Seidel迭代法是通过对Jacobi迭代法稍加改进得到的 Jacobi迭代法的每一步迭代新值x k 1 x1 k 1 x2 k 1 xn k 1 T都是用前一步的旧值x k x1 k x2 k xn k T的全部分量计算出来的 那么在计算第i个分量xi k 1 时 已经计算出x1 k 1 x2 k 1 xi 1 k 1 i 1 个分量 这些分量新值没用在计算xi k 1 上 将这些 i 1 2 n i 1 2 n k 0 1 2 将这些分量利用起来 有可能得到一个收敛更快的迭代公式 具体作法 将分量形式的雅可比迭代公式右端前 i 1 个分量的上标为k换成k 1 即 分量形式的高斯 塞德尔迭代公式 用矩阵形式来表示高斯 塞德尔迭代公式 DX k 1 b LX k 1 UX k 即 D L X k 1 UX k b如果 D L 存在 则X k 1 D L UX k D L b记B D L f D L b则 矩阵形式的高斯 塞德尔迭代公式 B 迭代矩阵 例 例 Jacobi迭代算法 A 9 1 1 110 1 1 115 b 7 8 13 x 0 0 0 er 1 k 0 whileer 0 00005er 0 k k 1 fori 1 3s 0 t x i x i 0 forj 1 3s s A i j x j endx i t y i b i s A i i er max abs x i y i er endx y x end 0 77780 80000 86670 96300 96440 97190 99290 99350 99520 99870 99880 99910 99980 99980 99981 00001 00001 00001 00001 00001 0000 Gauss Seidel迭代算法 A 9 1 1 110 1 1 115 b 7 8 13 x 0 0 0 er 1 k 0 whileer 0 00005er 0 k k 1 fori 1 3s 0 t x i x i 0 forj 1 3s s A i j x j endx i b i s A i i er max abs x i t er endx end 0 77780 87780 97700 98390 99610 99870 99940 99980 99991 00001 00001 00001 00001 00001 0000 从计算结果可以明显看出 Gauss Seidel迭代法比Jacobi迭代法效果好 一般而言 Gauss Seidel迭代法收敛速度比Jacobi迭代法快 但这两种迭代法的收敛范围并不完全重合 而只是部分相交 有的时候Jacobi迭代法可能比Gauss Seidel迭代法收敛速度更快 甚至可以举出Jacobi迭代法收敛而Gauss Seidel迭代法发散的例子 Gauss Seidel迭代法和Jacobi迭代法的异同 Jacobi迭代法 公式简单 每次只需做矩阵和向量的一次乘法 特别适合于并行计算 不足之处 需存放X k 和X k 1 两个存储空间 Gauss Seidel迭代法 只需一个向量存储空间 一旦计算出了xj k 1 立即存入xj k 的位置 可节约一套存储单元 有时起到加速收敛的作用 是一种典型的串行算法 每次迭代中必须依次计算解的各个分量 超松驰 SOR 迭代法 超松驰迭代法是迭代方法的一种加速方法 其计算公式简单 但需要选择合适的松驰因子 以保证迭代过程有较快的收敛速度 设有方程组AX b其中A aij n为非奇异矩阵 X x1 x2 xn T b b1 b2 bn T 记X k 为第k步迭代近似值 则r k b AX k 表示近似解X k 的残余误差 引进如下形式的加速迭代公式 X k 1 X k w b AX w称作松驰因子 其分量形式为选择适当的松驰因子 可期望获得较快的收敛速度 如果在计算分量xi k 1 时 考虑利用已经计算出来的分量x1 k 1 x2 k 1 xi 1 k 1 又可得到一个新的迭代公式特别当aii 0时 将上面迭代公式应用于方程组 i 1 2 n 由此得下列超松驰 SOR 迭代公式 i 1 2 n k 0 1 2 3 当w 1时 称超松驰法 当w 1时 称低松驰法 当w 1时 就是Gauss Seidel迭代公式 所以超松驰 SOR 迭代法可以看成是Gauss Seidel迭代法的加速 而Gauss Seidel迭代法是超松驰方法的特例 定理4 8若A是对称正定矩阵 则当0 w 2时SOR迭代法解方程组Ax b是收敛的 定理4 9若A是严格对角占优矩阵 则当0 w 1时SOR迭代法解方程组Ax b是收敛的 例4 3用SOR方法解方程组 w 1 4 w input input w A 2 10 12 1 0 12 b 1 0 1 8 x 1 1 1 er 1 k 0 whileer 0 0005er 0 k k 1 fori 1 3s 0 t x i x i 0 forj 1 3s s A i j x j endx i 1 w t w b i s A i i er max abs x i t er endendk k 10 x 1 19991 39991 5999 1 2 只需k 6 块迭代法简介设A Rn n x Rn b Rn将方程组Ax b中系数矩阵A分块 其中 Aii Rni ni Aij Rni nj xi Rni bi Rni 将A分解 A DB LB UB Jacobi块迭代DBx k 1 LB UB x k b i 1 2 r 2 Gauss Seidel块迭代DBx k 1 LBx k 1 UBx k b i 1 2 r 迭代法的收敛性Convergenceofiterativemethod迭代矩阵谱半径Spectralradius对角占优矩阵diagonallydominantmatrix 原始方程 Ax b 迭代格式 x k 1 Bx k f 定理4 1 迭代法基本定理 迭代法x k 1 Bx k f收敛的充要条件是 B 1 迭代法有着算法简单 程序设计容易以及可节省计算机存贮单元等优点 但是迭代法也存在着收敛性和收敛速度等方面的问题 因此弄清楚迭代法在什么样的条件下收敛是至关重要的 证对任何n阶矩阵B都存在非奇矩阵P使B P 1JP其中 J为B的Jordan标准型 其中 Ji为Jordan块 其中 i是矩阵B的特征值 由B P 1JP Bk P 1JP P 1JP P 1JP P 1JkP 迭代法x k 1 Bx k f收敛 i 1 2 r 例线性方程组Ax b 分别取系数矩阵为 试分析Jacobi迭代法和Seidel迭代法的敛散性 1 2 A2 2 1 1 1 1 1 1 1 2 两种迭代法之间没有直接联系对矩阵A1 求A1x b的Jacobi迭代法收敛 而Gauss Seidel迭代法发散 对矩阵A2 求A2x b的Jacobi迭代法发散 而Gauss Seidel迭代法收敛 证由 k B k 1 得 k B k 1 k 1 2 3 所以 定理4 2 迭代收敛的充分条件 设有迭代公式x k 1 Bx k f 如果 B 1 则对任意初始向量x 0 和任意f 迭代公式收敛 k B k 0 B 1 定义4 1A aij n n 如果则称A为严格对角占优阵 例4 1 定理4 3若Ax b的系数矩阵A是严格对角占优矩阵 则Jacobi迭代和Seidel迭代均收敛 证由于矩阵A严格对角占优 由A矩阵构造Jacobi迭代矩阵BJ D 1 D A 第i行绝对值求和 所以 例4 2试对下列方程组建立收敛的迭代公式 解通过观察可发现这个方程组的系数矩阵不是对角占优的 但经行交换后可得下列等价形式 此等价形式的系数矩阵是严格对角占优阵 据此建立的雅可比迭代公式和高斯 塞德尔迭代公式收敛 收敛速度 称R B ln B 为迭代法的渐进收敛速度简称收敛速度