Jacobi-迭代法与Gauss-Seidel迭代法算法比较.doc

Jacobi 迭代法与Gauss-Seidel迭代法算法比较 目录1 引言11.1 Jacobi迭代法21.2 Gauss-Seidel迭代法21.3 逐次超松弛（SOR）迭代法32算法分析33 结论54 附录程序5参考文献8Jacobi 迭代法与Gauss-Seidel迭代法比较1 引言 解线性方程组的方法分为直接法和迭代法，直接法是在没有舍入误差的假设下，能在预定的运算次数内求得精确解，而迭代法是构造一定的递推格式，产生逼近精确值的序列。这两种方法各有优缺点，直接法普遍适用，但要求计算机有较大的存储量，迭代法要求的存储量较小，但必须在收敛性得以保证的情况下才能使用。对于高阶方程组，如一些偏微分方程数值求解中出现的方程组，采用直接法计算代价比较高，迭代法则简单又实用，所以比较受工程人员青睐。迭代法求解方程组就是构造一个无限的向量序列，使它的极限是方程组的解向量。即使计算机过程是精确的，迭代法也不能通过有限次算术运算求得方程组的精确解，而只能逐步逼近它。因此迭代法存在收敛性与精度控制的问题。迭代法是常用于求解大型稀疏线性方程组（系数矩阵阶数较高且0元素较多），特别是某些偏微分方程离散化后得到的大型稀疏方程组的重要方法。设n元线性微分方程组 (1) 的系数矩阵A非奇异，右端向量,因而方程组有唯一的非零解向量。而对于这种线性方程组的近似解，前辈们发展研究了许多种有效的方法，有Jacobi迭代法、GaussSeidel迭代法，逐次超松弛迭代法（SOR法），这几种迭代方法均属一阶线性定常迭代法，即若系数矩阵A分解成两个矩阵N和P的差，即；其中N为可逆矩阵，线性方程组(1)化为：可得到迭代方法的一般公式： （2）其中：，对任取一向量作为方程组的初始近似解，按递推公式产生一个向量序列，.，.，当足够大时，此序列就可以作为线性方程组的近似解。 一阶定常迭代法收敛的充分必要条件是: 迭代矩阵G的谱半径小于1，即；又因为对于任何矩阵范数恒有G，故又可得到收敛的一个充分条件为：G 1。1.1 Jacobi迭代法若D为A的对角素构成的对角矩阵，且对角线元素全不为零。可以将系数矩阵A分解为： 其中，D为系数矩阵A的对角元素构成的对角阵，L为严格下三角阵，U为严格上三角阵。在迭代法一般形式中，取，形成新的迭代公式，其中任取，则Jacobi迭代的迭代公式为： (3)式中: ; , 称为Jacobi迭代矩阵. 其计算公式为: ， （4） 如果迭代矩阵的谱半径，则对于任意迭代初值，Jacobi迭代法收敛；如果GJ1，则Jacobi迭代法收敛；如果方程组的系数矩阵是主对角线按行或按列严格占优阵，则用Jacobi迭代法求解线性方程组必收敛。1.2 Gauss-Seidel迭代法从Jacobi迭代可以看出，用计算时，需要同时保留这两个向量。事实上如果每次获得的分量能够在计算下一个分量时及时更新的话，既节省了存储单元，又能使迭代加速，这就是Gauss-Seidel方法。对于非奇异方程组，若D为A的对角素构成的对角矩阵，且对角线元素全不为零；系数矩阵A的一个分解： (5)在迭代法一般形式中，取，形成新的迭代公式，其中任取，则Gauss-Seidel迭代法的迭代公式为: （6）上式中: 是其右端常数项；为Gauss-Seidel迭代法的迭代矩阵，其计算公式为：， （7）若GS法收敛的充分必要条件是；如果GG0称为松弛因子。在迭代法一般形式中，取, 得到迭代公式 ， （9）其中任取。这就是逐次超松弛迭代法，当=1时该式就是高斯法。SOR法迭代矩阵是整理后得到SOR迭代法的实际计算公式为： ；（10） SOR方法收敛的充分必要条件是；如果GS1，则SOR方法收敛；SOR方法收敛的必要条件是；如果方程组的系数矩阵A是主对角线按行或者列严格占优阵，则用的SOR方法求解必收敛；如果方程组的系数矩阵是正定矩阵，则用的SOR方法求解必收敛。2 算法分析例1 用雅可比迭代法求解下列方程组解 将方程组按雅可比方法写成取初始值按迭代公式进行迭代，其计算结果如表1所示 。表1 01234567 00.720.9711.0571.08531.09511.098300.831.0701.15711.18531.19511.198300.841.1501.24821.28281.29411.2980例2 用高斯塞德尔迭代法求解例1.解 取初始值，按迭代公式进行迭代，其计算结果如下表2表2 0123456700.721.043081.093131.099131.099891.099991.100.9021.167191.195721.199471.199931.199991.201.16441.282051.297771.299721.299961.31.33 结论使用Gauss-Seidel迭代法迭代法，7次就可以求出方程的解，收敛速度要比Jacobi迭代法收敛快(达到同样的精度所需迭代次数少)；但是这个结论,在一定条件下才是对的,甚至有这样的方程组,雅可比方法收敛，而高斯塞德尔迭代法却是发散的.4 附录程序/* 求解线性方程组-Gauss-Seidel迭代法 */#include #include using namespace std;/* 二维数组动态分配模板 */template T* Allocation2D(int m, int n) T *a; a = new T*m; for (int i=0; im; i+)ai = new Tn; return a;/* 一维数组动态分配模板 */template T* Allocation1D(int n) T *a; a = new Tn; return a;/* 求矩阵的一范数 */float matrix_category(float* x, int n)float temp = 0;for(int i=0; in; i+)temp = temp + fabs(xi);return temp;int main()const int MAX = 1000; / 最大迭代次数int i,j,k; / 循环变量int n; / 矩阵阶数float* a; / 增广矩阵float* x_0; / 初始向量float* x_k; / 迭代向量float precision; / 精度coutprecision;/* 动态生成增广矩阵 */coutendln;a = Allocation2D(n, n+1);/* 输入增广矩阵的各值 */coutendl输入增广矩阵的各值：n;for(i=0; in; i+)for(j=0; jaij;/* 生成并初始化初始向量 */x_0 = Allocation1D(n);coutendl输入初始向量:n;for(i=0; ix_0i; /* 生成迭代向量 */x_k = Allocation1D(n);float temp;/* 迭代过程 */for(k=0; kMAX; k+) for(i=0; in; i+)temp = 0;for(j=0; ji; j+)temp = temp + aij * x_kj; x_ki = ain - temp;temp = 0;for(j=i+1; jn; j+)temp = temp + aij * x_0j;x_ki = (x_ki - temp) / aii;/* 求两解向量的差的范数 */for(i=0; in; i+)x_0i = x_ki - x_0i;if(matrix_category(x_0,n) precision)break;elsefor(i=0; in; i+)x_0i = x_ki;/* 输出过程 */if(MAX = k)cout迭代不收敛n; cout迭代次数为：kendl