超松弛迭代法解线性方程组
2013-2014(1)专业课程实践论文
题目:超松弛迭代法解线性方程组
逐次超松弛迭代法是Gauss-Seidel 方法的一种加速方法,世界大型稀疏矩阵方程组的有效方法之一,它具有计算公式简单,程序设计容易,占用计算机内存较少等优点,但需要选择好的加速因子(即最佳松弛因子)
设有方程组Ax =b (1) 其中A ∈R n *n 为非奇异矩阵,且设a ii ≠0(i =1, 2,...., n ),分解A 为
A =D -L -U (2)
设已知第k 次迭代向量x (k ),及第k +1次迭代向量x (k +1)的分量
x j
(k +1)
(j =1, 2,..., i -1),要求计算分量x i (k +1)
(k +1)
首先用Gauss —Seidel 迭代法定义辅助量
x i
1=a ii
i -1⎛
b i -∑x j
j =1⎝
(k +1)
-
j =i +1
∑a ij x j
n
(k )⎫
⎪(i =1, 2,..., n ) (3)
⎪⎭
再把x i
(k +1)
取为x i
x i
(k +1)
(k +1)
某个平均值(即加权平均),即
(k )
=(1-w ) x i
+w x i
(k +1)
=x i
(k )
+w x i
(k +1)
-x i
(k )
) (4)
用式(3)代入式(4)即得到解方程组Ax =b 的逐次超松弛迭代公式
i -1n ⎧(k +1)w ⎛(k )(k +1)(k )⎫ ⎪x =x +b -a x -a x ⎪∑∑i i ij j ij j ⎪i ⎪a j =1j =i ii ⎝⎭ (5) ⎨
⎪(k )(k )(k )(k )T
(k =0, 1, 2...; i =1, 2,... n )x =x , x ,..., x ⎪12n ⎩
()
其中w 为松弛因子,显然,当w =1时,解式(1)的SOR 方法就是Gauss-Seid el
迭代法。
在SOR 方法中,迭代一次主要的运算量是计算一次矩阵与向量的乘法。由式(5)可知,在计算机上应用SOR 方法解方程组时只需一组工作单元,以便存放近似解。
#define N 3 // 线性方程组的阶数 #include #include void main() {
double a[N][N]={5,2,1,2,8,-3,1,-3,-6}, //系数矩阵 b[N]={8,21,1}; //右端常数向量
double x0[N]={1,1,1},x[N]; // 迭代初始向量和迭代向量 double e=1e-5; // 精度要求 int M=5000; //最大迭代次数 int i,j,c_M=0; double sum,current_e;
do{ current_e=0; for(i=0;icurrent_e) current_e = fabs(x[i]-x0[i]); } //计算当前误差 for(i=0;i
}while(current_e>e&&c_M
for(i=0;i
四、算法实现
例1.用超松弛迭代法解方程组
⎧5x 1+2x 2+x 3=8⎪
⎨2x 1+8x 2-3x 3=2 ⎪x -3x -6x =1
23⎩1
解:
将方程组的系数放于a[n][n]中,将等号右端常数放入b[n]中。运行程序,即可
得出结果
例2.用超松弛迭代法解方程组
⎧-4x 1+x 2+x 3=1⎪
⎨x 1-4x 2+x 3=1 ⎪x +x -4x =1
23⎩1
解:
将方程组的系数放于a[n][n]中,将等号右端常数放入b[n]中。运行程序,
即可得出结果