(完整word版)Jacobi迭代法与Gauss-Seidel迭代法算法比较

迭代法与Gauss-Seidel迭代法算法比

较

(完整word版)Jacobi迭代法与Gauss-Seidel迭代法算法比较

目录

1 引言 ...................................................................................................................................... 1

1。1 Jacobi迭代法 ....................................................................................................... 2 1.2 Gauss—Seidel迭代法 ........................................................................................... 2 1.3 逐次超松弛（SOR）迭代法.................................................................................. 3 2算法分析 ............................................................................................................................... 4 3 结论 ...................................................................................................................................... 5 4 附录程序 .............................................................................................................................. 5 参考文献 ................................................................................................................................... 9

(完整word版)Jacobi迭代法与Gauss-Seidel迭代法算法比较

Jacobi 迭代法与Gauss-Seidel迭代法比较

1 引言

解线性方程组的方法分为直接法和迭代法，直接法是在没有舍入误差的假设下,能在预定的运算次数内求得精确解，而迭代法是构造一定的递推格式,产生逼近精确值的序列。这两种方法各有优缺点，直接法普遍适用，但要求计算机有较大的存储量，迭代法要求的存储量较小，但必须在收敛性得以保证的情况下才能使用。对于高阶方程组，如一些偏微分方程数值求解中出现的方程组，采用直接法计算代价比较高,迭代法则简单又实用，所以比较受工程人员青睐。

迭代法求解方程组就是构造一个无限的向量序列，使它的极限是方程组的解向量.即使计算机过程是精确的，迭代法也不能通过有限次算术运算求得方程组的精确解，而只能逐步逼近它。因此迭代法存在收敛性与精度控制的问题.

迭代法是常用于求解大型稀疏线性方程组（系数矩阵阶数较高且0元素较多），特别是某些偏微分方程离散化后得到的大型稀疏方程组的重要方法。设n元线性微分方程组

Axb （1)

的系数矩阵A非奇异,右端向量b0,因而方程组有唯一的非零解向量。而对于这种线性方程组的近似解，前辈们发展研究了许多种有效的方法,有Jacobi迭代法、Gauss—Seidel迭代法，逐次超松弛迭代法（SOR法），这几种迭代方法均属一阶线性定常迭代法，即若系数矩阵A分解成两个矩阵N和P的差，即ANP；其中N为可逆矩阵,线性方程组(1)化为:

（NP)xb NxPxb

xN1PxN1b

可得到迭代方法的一般公式：

（k)d （2） x(k1)Gx其中:GN-1P，dN1b，对任取一向量x(0)作为方程组的初始近似解，按递推公式产生一个向量序列x(1)，

x(2)，...,x(k），...，当k足够大时，此序列就可以作为线性方程组的近似解。

第 1 页 共 7页

(完整word版)Jacobi迭代法与Gauss-Seidel迭代法算法比较 一阶定常迭代法收敛的充分必要条件是: 迭代矩阵G的谱半径小于1，即（G）1；又因为对于任何矩阵范数恒有（G）‖G‖，故又可得到收敛的一个充分条件为：‖G‖< 1。 1。1 Jacobi迭代法 若D为A的对角素构成的对角矩阵，且对角线元素全不为零.可以将系数矩阵A分解为：

ADLU 其中,D为系数矩阵A的对角元素构成的对角阵，L为严格下三角阵,U为严格上三角阵。在迭代法一般形式中，取ND，P(LU)，形成新的迭代公式 x(k1)D1(LU)x(k)D1b，k0,1,... 其中x(0)任取，则Jacobi迭代的迭代公式为： x(k1)GJx(k)dJ （3) 式中: dJD1b; GJD1(LU), 称GJ为Jacobi迭代矩阵. 其计算公式为: xi(k1)n1(k)biaiixj，i1,2,...,naiij1ji (4） 如果迭代矩阵GJ的谱半径（G）1,则对于任意迭代初值x(0)，Jacobi迭代法收敛;如果‖GJ‖〈1，则Jacobi迭代法收敛；如果方程组的系数矩阵是主对角线按行或按列严格占优阵，则用Jacobi迭代法求解线性方程组必收敛。 1。2 Gauss—Seidel迭代法 从Jacobi迭代可以看出，用x(k)计算x(k1)时，需要同时保留这两个向量.事实上如果每次获得的分量能够在计算下一个分量时及时更新的话，既节省了存储单元，又能使迭代加速，这就是Gauss-Seidel方法。对于非奇异方程组，若D为A的对角素构成的对角矩阵，且对角线元素全不为零；系数矩阵A的一个分解： ADLU （5) 在迭代法一般形式中，取NDL，PU,形成新的迭代公式 x(k1)(DL)1Ux(k)(DL)1b，k0,1,... （k1)其中x(0)任取，则Gauss—Seidel迭代法的迭代公式为： xGGx(k)f （6) 第 2 页 共 7页

(完整word版)Jacobi迭代法与Gauss-Seidel迭代法算法比较 上式中： f(DL)1b是其右端常数项；GG(DL)1U为Gauss-Seidel迭代法的迭代矩阵，其计算公式为: xi(k1)i1n1(k1)(k)biaijxjaijxj，i1,2,3,...n k0,1,2,... （7) aiij1ji1若GS法收敛的充分必要条件是（GG)1;如果‖GG‖<1,则GS法收敛；如果线性方程组的系数矩阵A为主对角线按行或按列严格占优阵，或者为正定矩阵，则对于任意初值x(0)用GS法求解必收敛。 1。3 逐次超松弛（SOR）迭代法 一般而言，因Jacobi迭代收敛速度不够快，所以在工程中用的并不是太多.并且在Jacobi迭代收敛速度很慢的情况下，通常Gauss—Seidel迭代法也不会太快。可以对Gauss-Seidel迭代公式做适度修改，提高收敛速度,这就是逐次超松弛迭代法。 设线性方程组的系数矩阵A满足aii0,i1,2,...n。可将系数矩阵A分解为 A1DL(11)DU (8) 其中实常数>0称为松弛因子。在迭代法一般形式中，取 N得到迭代公式 1DL， P((11)DU) x(k1)(1DL)1((11)DU)x(k)(1DL)1b，k0,1,... （9） 其中x(0)任取。这就是逐次超松弛迭代法，当=1时该式就是高斯法。SOR法迭代矩阵是GS(1DL)1((11)DU) 整理后得到SOR迭代法的实际计算公式为： xi(k1)ni1aij(k1)1(k)aij(k)bixj(1)xixj i1,2,...,n；k0,1,...(10) aiiaiiji1aiij11；如果‖GS‖〈1，则SOR方法收敛；SOR方法收敛的必要 SOR方法收敛的充分必要条件是（Gs）条件是02；如果方程组的系数矩阵A是主对角线按行或者列严格占优阵,则用01的SOR方法求解必收敛；如果方程组的系数矩阵是正定矩阵，则用02的SOR方法求解必收敛。

第 3 页 共 7页

(完整word版)Jacobi迭代法与Gauss-Seidel迭代法算法比较

2 算法分析

例1 用雅可比迭代法求解下列方程组

10x1x22x37.2x110x22x38.3x1x25x34.2

解 将方程组按雅可比方法写成

x10.1x20.2x30.72x20.1x0.2x130.83x30.2x10.2x20.84

取初始值

x0x00T,T1,x2,x030,0,0按迭代公式

xk10.1xkk120.2x30.72xk1k20.1x0.2xk30.831xk130.2xkk10.2x20.84

进行迭代，其计算结果如表1所示 。 表1 k 0 1 2 3 4 5 6 7 xk1 0 0。0.971 1.051。0853 1.0951 1.0983 … 72 7 xk2 0 0。1.070 1.151.1853 1。1。… 83 71 1951 1983 xk3 0 0。1。1.241。2828 1.2941 1。… 84 150 82 2980 例2 用高斯——塞德尔迭代法求解例1.

x0x0,x0,0T0,0,0,T解 取初始值

12x3，按迭代公式 第 4 页 共 7页

(完整word版)Jacobi迭代法与Gauss-Seidel迭代法算法比较

kx1k10.1x20.2x3k0.72k1k10.2x3k0.83x20.1x1xk10.2xk10.2xk10.84123

进行迭代，其计算结果如下表2

表2

k 0 0 1 0.72 2 1.04308 kx2 3 1.09313 1.19572 1。29777 4 1。09913 1.19947 1。29972 5 1。09989 1.19993 1。29996 6 1。09999 1.19999 1。3 7 1。1 1.2 x1k 0 0.902 1。16719 1.28205 x3k 0 1。1644 1。3

3 结论

使用Gauss-Seidel迭代法迭代法，7次就可以求出方程的解,收敛速度要比Jacobi迭代法收敛快（达到同样的精度所需迭代次数少);但是这个结论，在一定条件下才是对的,甚至有这样的方程组，雅可比方法收敛，而高斯—塞德尔迭代法却是发散的.

4 附录程序

/* 求解线性方程组--Gauss-Seidel迭代法 ＊/

＃include using namespace std；

/＊ 二维数组动态分配模板 */

第 5 页 共 7页

(完整word版)Jacobi迭代法与Gauss-Seidel迭代法算法比较

template 〈class T>

T*＊ Allocation2D（int m, int n） ｛

T *＊a;

a = new T*[m］；

for （int i=0； i｝

return a；

}

/＊ 一维数组动态分配模板 */ template T* Allocation1D(int n) {

T ＊a；

a = new T［n］； return a; ｝

/* 求矩阵的一范数 ＊/

float matrix_category（float＊ x, int n） ｛ float temp = 0;

for(int i=0； i〈n; i++） { temp = temp + fabs(x［i]);

}

return temp;

｝

int main(） { const int MAX = 1000； // 最大迭代次数 int i,j，k; // 循环变量

int n; // 矩阵阶数

第 6 页 共 7页

(完整word版)Jacobi迭代法与Gauss-Seidel迭代法算法比较

float** a; // 增广矩阵 float＊ x_0; // 初始向量 float* x_k； // 迭代向量 float precision； // 精度 cout<〈\"输入精度e:”； cin>>precision;

/＊ 动态生成增广矩阵 */

cout<n；

a = Allocation2D〈float>（n, n+1)； /* 输入增广矩阵的各值 ＊/

cout〈>a［i］[j];

｝

｝

/* 生成并初始化初始向量 */ x_0 = Allocation1D〈float>(n);

cout<〈endl<〈\"输入初始向量：\\n”； for(i=0; i〈n; i++） {

cin〉>x_0［i］;

｝ /* 生成迭代向量 ＊/ x_k = Allocation1D〈float〉（n）; float temp； /* 迭代过程 ＊/

for(k=0; k｛

第 7 页 共 7页

(完整word版)Jacobi迭代法与Gauss-Seidel迭代法算法比较

for（i=0; i〈n; i++） { temp = 0;

for（j=0； j〈i; j++） {

temp = temp + a[i]［j］ ＊ x_k[j］;

}

x_k［i］ = a[i][n] - temp； temp = 0；

for(j=i+1； jx_k［i］ = (x_k[i] - temp） / a[i］［i]；

}

/* 求两解向量的差的范数 */ for(i=0； i｝

if（matrix_category(x_0,n） 〈 precision) { break;

｝ else ｛ for（i=0； i〈n; i++） ｛ x_0［i］ = x_k[i]; ｝

}

}

/＊ 输出过程 ＊/ if（MAX == k)

第 8 页 共 7页

(完整word版)Jacobi迭代法与Gauss-Seidel迭代法算法比较

｛

cout<<”迭代不收敛\\n”；

} cout<〈”迭代次数为：\"〈cout<<\"解向量为:\\n”； for(i=0； i〈n； i++） {

cout<〈”x”<}

return 0; }

参考文献

[1]颜庆津. 数值分析[M］. 北京：航空航天大学出版社，1999.

［2]黎建玲，简金宝，李群宏。数值分析与实验［M]。北京：科学出版社，2012．［3］宋叶志．MATLAB数值分析与应用[M]．北京：机械工业出版社,2013．

第 9 页 共 7页