线性方程组的解法

线性方程组的解法 解线性方程组的迭代法IterativeMethodsforLinearSystemsJacobi迭代和Gauss Seidel迭代迭代法的矩阵表示MatrixformoftheIterativeMethods 1 教育交流ppt 线性方程组的解法在计算数学中占有极其重要的地位 线性方程组的解法大致分为迭代法与直接法两大类 雅可比 Jacobi 迭代法 举例说明雅可比迭代法的基本思路 例4 1 特点 系数矩阵主对角元均不为零 2 教育交流ppt 取迭代初值x1 0 0 x2 0 0 x3 0 0 将方程改写成如下等价形式 据此建立迭代公式 3 教育交流ppt 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 准确解 可以看出 迭代每前进一步 结果就逼近准确解一步迭代过程收敛 4 教育交流ppt 矩阵形式 以上这种迭代方法称雅可比 Jacobi 迭代法 基本思想 将方程组的求解问题转化为重复计算一组彼此独立的线性表达式 5 教育交流ppt i 1 2 n k 0 1 2 i 1 2 n 设有方程组 将第i个方程的第i个变量xi分离出来 据此建立分量形式的雅可比迭代公式 如果 6 教育交流ppt 用矩阵形式来表示雅可比迭代公式 设有方程组 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其中 7 教育交流ppt 于是 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 8 教育交流ppt 9 教育交流ppt 迭代法适用于解大型稀疏方程组 万阶以上的方程组 系数矩阵中零元素占很大比例 而非零元按某种模式分布 背景 电路分析 边值问题的数值解和数学物理方程 问题 1 如何构造迭代格式 2 迭代格式是否收敛 3 收敛速度如何 4 如何进行误差估计 10 教育交流ppt 高斯塞德尔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 上 将这些 11 教育交流ppt i 1 2 n i 1 2 n k 0 1 2 将这些分量利用起来 有可能得到一个收敛更快的迭代公式 具体作法 将分量形式的雅可比迭代公式右端前 i 1 个分量的上标为k换成k 1 即 分量形式的高斯 塞德尔迭代公式 12 教育交流ppt 用矩阵形式来表示高斯 塞德尔迭代公式 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 迭代矩阵 13 教育交流ppt 例 14 教育交流ppt 例 15 教育交流ppt 16 教育交流ppt 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 17 教育交流ppt 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 18 教育交流ppt 从计算结果可以明显看出 Gauss Seidel迭代法比Jacobi迭代法效果好 一般而言 Gauss Seidel迭代法收敛速度比Jacobi迭代法快 但这两种迭代法的收敛范围并不完全重合 而只是部分相交 有的时候Jacobi迭代法可能比Gauss Seidel迭代法收敛速度更快 甚至可以举出Jacobi迭代法收敛而Gauss Seidel迭代法发散的例子 19 教育交流ppt Gauss Seidel迭代法和Jacobi迭代法的异同 Jacobi迭代法 公式简单 每次只需做矩阵和向量的一次乘法 特别适合于并行计算 不足之处 需存放X k 和