超松弛迭代法解线性方程组

2013-2014（1）专业课程实践论文题目：超松弛迭代法解线性方程组一、算法理论逐次超松弛迭代法是Gauss-Seidel方法的一种加速方法，世界大型稀疏矩阵方程组的有效方法之一，它具有计算公式简单，程序设计容易，占用计算机内存较少等优点，但需要选择好的加速因子（即最佳松弛因子）设有方程组bAx（1）其中nnRA*为非奇异矩阵，且设niaii,....,2,10，分解A为ULDA（2）设已知第k次迭代向量kx，及第1k次迭代向量1kx的分量1,...,2,11ijxkj，要求计算分量1kix首先用Gauss—Seidel迭代法定义辅助量nixaxbaxijnijkjijkjiiiki,...,2,1111111(3)再把1kix取为1kix某个平均值（即加权平均），即kikikikikikixxwxxwxwx111)1(（4）用式（3）代入式（4）即得到解方程组bAx的逐次超松弛迭代公式nikxxxxxaxabawxxTknkkkijnijkjijkjijiiikiki,...2,1...;2,1,0,...,,211111(5)其中w为松弛因子，显然，当1w时，解式（1）的SOR方法就是Gauss-Seidel迭代法。在SOR方法中，迭代一次主要的运算量是计算一次矩阵与向量的乘法。由式（5）可知，在计算机上应用SOR方法解方程组时只需一组工作单元，以便存放近似解。二、算法框图定义f(x)输入x0e1e2NK=1f(x)e1x1=x0-x0/f¡¯(x0)︱X1-x2︳e2?K=N?输出迭代失败标志输出奇异标志输出x1x0=x1K=k=1YESYESYESNONO开始结束三、算法程序#defineN3//线性方程组的阶数#includeiostream.h#includemath.hvoidmain(){doublea[N][N]={5,2,1,2,8,-3,1,-3,-6},//系数矩阵b[N]={8,21,1};//右端常数向量doublex0[N]={1,1,1},x[N];//迭代初始向量和迭代向量doublee=1e-5;//精度要求intM=5000;//最大迭代次数inti,j,c_M=0;doublesum,current_e;do{current_e=0;for(i=0;iN;i++){sum=0;for(j=0;jN;j++){if(j!=i){sum=sum+a[i][j]*x0[j];}}x[i]=(b[i]-sum)/a[i][i];}//更新迭代向量c_M++;//迭代次数加1for(i=0;iN;i++){if(fabs(x[i]-x0[i])current_e)current_e=fabs(x[i]-x0[i]);}//计算当前误差for(i=0;iN;i++)x0[i]=x[i];//更新初始向量}while(current_ee&&c_MM);//判断是否仍未达到精度要求且未达到最大迭代次数for(i=0;iN;i++)coutx[i]endl;//输出结果coutc_Mendl;//输出迭代次数}四、算法实现例1．用超松弛迭代法解方程组1632382825321321321xxxxxxxxx解：将方程组的系数放于a[n][n]中，将等号右端常数放入b[n]中。运行程序，即可得出结果例2．用超松弛迭代法解方程组141414321321321xxxxxxxxx解：将方程组的系数放于a[n][n]中，将等号右端常数放入b[n]中。运行程序，即可得出结果