Jacobi-迭代法与Gauss-Seidel迭代法算法比较.doc
- 文档编号:18836177
- 上传时间:2024-01-03
- 格式:DOC
- 页数:10
- 大小:180.54KB
Jacobi-迭代法与Gauss-Seidel迭代法算法比较.doc
《Jacobi-迭代法与Gauss-Seidel迭代法算法比较.doc》由会员分享,可在线阅读,更多相关《Jacobi-迭代法与Gauss-Seidel迭代法算法比较.doc(10页珍藏版)》请在冰点文库上搜索。
Jacobi迭代法与Gauss-Seidel迭代法算法比较
目录
1引言 1
1.1Jacobi迭代法 2
1.2Gauss-Seidel迭代法 2
1.3逐次超松弛(SOR)迭代法 3
2算法分析 3
3结论 5
4附录程序 5
参考文献 8
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迭代法也不会太快。
可以对Gauss-Seidel迭代公式做适度修改,提高收敛速度,这就是逐次超松弛迭代法。
设线性方程组的系数矩阵A满足,。
可将系数矩阵A分解为
(8)
其中实常数>0称为松弛因子。
在迭代法一般形式中,取
得到迭代公式
,(9)
其中任取。
这就是逐次超松弛迭代法,当=1时该式就是高斯法。
SOR法迭代矩阵是
整理后得到SOR迭代法的实际计算公式为:
;(10)
SOR方法收敛的充分必要条件是;如果‖GS‖<1,则SOR方法收敛;SOR方法收敛的必要条件是;如果方程组的系数矩阵A是主对角线按行或者列严格占优阵,则用的SOR方法求解必收敛;如果方程组的系数矩阵是正定矩阵,则用的SOR方法求解必收敛。
2算法分析
例1用雅可比迭代法求解下列方程组
解将方程组按雅可比方法写成
取初始值按迭代公式
进行迭代,其计算结果如表1所示。
表1
0
1
2
3
4
5
6
7
0
0.72
0.971
1.057
1.0853
1.0951
1.0983
…
0
0.83
1.070
1.1571
1.1853
1.1951
1.1983
…
0
0.84
1.150
1.2482
1.2828
1.2941
1.2980
…
例2用高斯——塞德尔迭代法求解例1.
解取初始值,按迭代公式
进行迭代,其计算结果如下表2
表2
0
1
2
3
4
5
6
7
0
0.72
1.04308
1.09313
1.09913
1.09989
1.09999
1.1
0
0.902
1.16719
1.19572
1.19947
1.19993
1.19999
1.2
0
1.1644
1.28205
1.29777
1.29972
1.29996
1.3
1.3
3结论
使用Gauss-Seidel迭代法迭代法,7次就可以求出方程的解,收敛速度要比Jacobi迭代法收敛快(达到同样的精度所需迭代次数少);但是这个结论,在一定条件下才是对的,甚至有这样的方程组,雅可比方法收敛,而高斯—塞德尔迭代法却是发散的.
4附录程序
/*求解线性方程组--Gauss-Seidel迭代法*/
#include
#include
usingnamespacestd;
/*二维数组动态分配模板*/
template
T**Allocation2D(intm,intn)
{
T**a;
a=newT*[m];
for(inti=0;i { a[i]=newT[n]; } returna; } /*一维数组动态分配模板*/ template T*Allocation1D(intn) { T*a; a=newT[n]; returna; } /*求矩阵的一范数*/ floatmatrix_category(float*x,intn) { floattemp=0; for(inti=0;i { temp=temp+fabs(x[i]); } returntemp; } intmain() { constintMAX=1000;//最大迭代次数 inti,j,k;//循环变量 intn;//矩阵阶数 float**a;//增广矩阵 float*x_0;//初始向量 float*x_k;//迭代向量 floatprecision;//精度 cout<<"输入精度e: "; cin>>precision; /*动态生成增广矩阵*/ cout< "; cin>>n; a=Allocation2D /*输入增广矩阵的各值*/ cout< \n"; for(i=0;i { for(j=0;j { cin>>a[i][j]; } } /*生成并初始化初始向量*/ x_0=Allocation1D cout< \n"; for(i=0;i { cin>>x_0[i]; } /*生成迭代向量*/ x_k=Allocation1D floattemp; /*迭代过程*/ for(k=0;k { for(i=0;i { temp=0; for(j=0;j { temp=temp+a[i][j]*x_k[j]; } x_k[i]=a[i][n]-temp; temp=0; for(j=i+1;j { temp=temp+a[i][j]*x_0[j]; } x_k[i]=(x_k[i]-temp)/a[i][i]; } /*求两解向量的差的范数*/ for(i=0;i { x_0[i]=x_k[i]-x_0[i]; } if(matrix_category(x_0,n) { break; } else { for(i=0;i { x_0[i]=x_k[i]; } } } /*输出过程*/ if(MAX==k) { cout<<"迭代不收敛\n"; } cout<<"迭代次数为: "< cout<<"解向量为: \n"; for(i=0;i { cout<<"x"< "< } return0; } 参考文献 [1]颜庆津.数值分析[M].北京: 航空航天大学出版社,1999. [2]黎建玲,简金宝,李群宏.数值分析与实验[M].北京: 科学出版社,2012. [3]宋叶志.MATLAB数值分析与应用[M].北京: 机械工业出版社,2013. 第8页共7页
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- Jacobi 迭代法 Gauss Seidel 算法 比较