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

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

目录

TOC\o"1-3"\h\uHYPERLINK\l_Toc257481引言 PAGEREF_Toc257481
HYPERLINK\l_Toc297841.1Jacobi迭代法 PAGEREF_Toc297842
HYPERLINK\l_Toc231271.2Gauss-Seidel迭代法 PAGEREF_Toc231272
HYPERLINK\l_Toc62481.3逐次超松弛（SOR）迭代法 PAGEREF_Toc62483
HYPERLINK\l_Toc159312算法分析 PAGEREF_Toc159313
HYPERLINK\l_Toc235863结论 PAGEREF_Toc235865
HYPERLINK\l_Toc15304附录程序 PAGEREF_Toc15305
HYPERLINK\l_Toc10423参考文献 PAGEREF_Toc104238

第PAGE\*MERGEFORMAT8页

Jacobi迭代法与Gauss-Seidel迭代法比较
1引言
解线性方程组的方法分为直接法和迭代法，直接法是在没有舍入误差的假设下，能在预定的运算次数内求得精确解，而迭代法是构造一定的递推格式，产生逼近精确值的序列。这两种方法各有优缺点，直接法普遍适用，但要求计算机有较大的存储量，迭代法要求的存储量较小，但必须在收敛性得以保证的情况下才能使用。对于高阶方程组，如一些偏微分方程数值求解中出现的方程组，采用直接法计算代价比较高，迭代法则简单又实用，所以比较受工程人员青睐。
迭代法求解方程组就是构造一个无限的向量序列，使它的极限是方程组的解向量。即使计算机过程是精确的，迭代法也不能通过有限次算术运算求得方程组的精确解，而只能逐步逼近它。因此迭代法存在收敛性与精度控制的问题。
迭代法是常用于求解大型稀疏线性方程组（系数矩阵阶数较高且0元素较多），特别是某些偏微分方程离散化后得到的大型稀疏方程组的重要方法。设n元线性微分方程组
(1)
的系数矩阵A非奇异，右端向量,因而方程组有唯一的非零解向量。而对于这种线性方程组的近似解，前辈们发展研究了许多种有效的方法，有Jacobi迭代法、Gauss—Seidel迭代法，逐次超松弛迭代法（SOR法），这几种迭代方法均属一阶线性定常迭代法，即若系数矩阵A分解成两个矩阵N和P的差，即；其中N为可逆矩阵，线性方程组(1)化为：

可得到迭代方法的一般公式：
（2）
其中：，，对任取一向量作为方程组的初始近似解，按递推公式产生一个向量序列，，...，，...，当足够大时，此序列就可以作为线性方程组的近似解。
一阶定常迭代法收敛的充分必要条件是:迭代矩阵G的谱半径小于1，即；又因为对于任何矩阵范数恒有‖G‖，故又可得到收敛的一个充分条件为：‖G‖<1。
1.1Jacobi迭代法
若D为A的对角素构成的对角矩阵，且对角线元素全不为零。可以将系数矩阵A分解为：
其中，D为系数矩阵A的对角元素构成的对角阵，L为严格下三角阵，U为严格上三角阵。在迭代法一般形式中，取，，形成新的迭代公式
，
其中任取，则Jacobi迭代的迭代公式为：
(3)
式中:;,称为Jacobi迭代矩阵.其计算公式为:
，（4）
如果迭代矩阵的谱半径，则对于任意迭代初值，Jacobi迭代法收敛；如果‖GJ‖<1，则Jacobi迭代法收敛；如果方程组的系数矩阵是主对角线按行或按列严格占优阵，则用Jacobi迭代法求解线性方程组必收敛。
1.2Gauss-Seidel迭代法
从Jacobi迭代可以看出，用计算时，需要同时保留这两个向量。事实上如果每次获得的分量能够在计算下一个分量时及时更新的话，既节省了存储单元，又能使迭代加速，这就是Gauss-Seidel方法。对于非奇异方程组，若D为A的对角素构成的对角矩阵，且对角线元素全不为零；系数矩阵A的一个分解：
(5)
在迭代法一般形式中，取，，形成新的迭代公式
，
其中任取，则Gauss-Seidel迭代法的迭代公式为:（6）
上式中:是其右端常数项；为Gauss-Seidel迭代法的迭代矩阵，其计算公式为：
，（7）
若GS法收敛的充分必要条件是；如果‖GG‖<1,则GS法收敛；如果线性方程组的系数矩阵A为主对角线按行或按列严格占优阵，或者为正定矩阵，则对于任意初值用GS法求解必收敛。
1.3逐次超松弛（SOR）迭代法
一般而言，因Jacobi迭代收敛速度不够快，所以在工程中用的并不是太多。并且在Jacobi迭代收敛速度很慢的情况下，通常Gauss-Seidel迭代法也不会太