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

Jacobi

迭代法与Gauss-Seidel迭代

法算法比较

目录

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

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

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

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

x-1?1(k?1)（k)?Gx?d （2）

(0)其中：G?NP，d?Nb，对任取一向量x生一个向量序列x，x近似解。

(1)(2)作为方程组的初始近似解，按递推公式产

，...，x(k），...，当k足够大时，此序列就可以作为线性方程组的

?1； 一阶定常迭代法收敛的充分必要条件是: 迭代矩阵G的谱半径小于1，即?（G）又因为对于任何矩阵范数恒有?（G）?‖G‖，故又可得到收敛的一个充分条件为：‖G‖< 1。

第 1 页 共 7页

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?Db; GJ??D?1(L?U), 称GJ为Jacobi迭代矩阵. 其计算公式为: ?1xi(k?1)??n1?(k)???bi??aiixj?，i?1,2,...,naii?j?1?j?i?? （4） (0) 如果迭代矩阵GJ的谱半径?（G）?1，则对于任意迭代初值x，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,... 其中x(0)任取，则Gauss-Seidel迭代法的迭代公式为: x?1（k?1) ?GGx(k)?f （6）?1上式中: f?(D?L)b是其右端常数项；GG??(D?L)U为Gauss-Seidel迭代法的迭代矩阵，其计算公式为： xi(k?1)i?1n?1?(k?1)(k)?，i?1,2,3,...n k?0,1,2,.. . （7） ??bi??aijxj?aijxj???aii?j?1j?i?1?若GS法收敛的充分必要条件是?（GG)?1；如果‖GG‖<1,则GS法收敛；如果线性方程组的系数矩阵A为主对角线按行或按列严格占优阵，或者为正定矩阵，则对于任意初值x

(0)用GS法求解必收敛。 第 2 页 共 7页

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)??(其中x(0)1?D?L)?1((1?1?)D?U)x(k)?(1?D?L)?1b，k?0,1,... （9） 任取。这就是逐次超松弛迭代法，当?=1时该式就是高斯法。SOR法迭代矩阵是GS??(1?D?L)?1((1?1?)D?U) 整理后得到SOR迭代法的实际计算公式为： xi(k?1)n?i?1aij(k?1)1(k)aijbi? ?????xj?(1?)xi??xj(k)?? i?1,2,...,n；k?0,1,...（10）?aii?j?i?1aii?j?1aii SOR方法收敛的充分必要条件是?（Gs）?1；如果‖GS‖<1，则SOR方法收敛；SOR方法收敛的必要条件是0???2；如果方程组的系数矩阵A是主对角线按行或者列严格占优阵，则用0???1的SOR方法求解必收敛；如果方程组的系数矩阵是正定矩阵，则用0???2的SOR方法求解必收敛。 2 算法分析

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

?10x1?x2?2x3?7.2???x1?10x2?2x3?8.3??x?x?5x?4.223?1

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

第 3 页 共 7页

?0?x取初始值

?x1?0.1x2?0.2x3?0.72???0.2x3?0.83?x2?0.1x1?x3?0.2x1?0.2x2?0.84??

TT?0???x1?0?,x2,x3?0????0,0,0,?按迭代公式

?k??x1?k?1??0.1x2?0.2x3?k??0.72???k?1??k??0.2x3?k??0.83?x2?0.1x1??k?1??k??k?x?0.2x?0.2x?0.84312?? 进行迭代，其计算结果如表1所示 。 表1 k ?k??k??k?0 0 0 0 1 0.72 0.83 0.84 2 0.971 1.070 1.150 3 1.057 1.1571 1.2482 4 1.0853 1.1853 1.2828 5 1.0951 1.1951 1.2941 6 1.0983 1.1983 1.2980 7 … … … x1x2x3 例2 用高斯——塞德尔迭代法求解例1.

?0??0??0??0?????0,0,0,?x?x,x,x123解 取初始值

TT，按迭代公式

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

?k??x1?k?1??0.1x2?0.2x3?k??0.72??k?1??k?1??k?x?0.1x?0.2x?0.83?213?x?k?1??0.2x?k?1??0.2x?k?1??0.8412?3

k ?k?0 0 0 0 1 0.72 0.902 2 1.04308 1.16719

表2 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 1.3 x1?k?x2 x3?k?

1.1644 1.28205 第 4 页 共 7页

3 结论

使用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; 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

int main() { const int MAX = 1000; // 最大迭代次数 int i,j,k; // 循环变量 int n; // 矩阵阶数

第 5 页 共 7页

float** a; // 增广矩阵 float* x_0; // 初始向量 float* x_k; // 迭代向量 float precision; // 精度 cout<<\输入精度e:\cin>>precision; /* 动态生成增广矩阵 */ cout<>n; a = Allocation2D(n, n+1); /* 输入增广矩阵的各值 */ cout<>a[i][j]; } } /* 生成并初始化初始向量 */ x_0 = Allocation1D(n); cout<>x_0[i]; } /* 生成迭代向量 */ x_k = Allocation1D(n); float temp; /* 迭代过程 */ for(k=0; k

第 6 页 共 7页

for(i=0; i

return 0; }

第 7 页 共 7页

参考文献

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

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

第 8 页 共 7页

本文来源：https://www.bwwdw.com/article/y7nh.html