超松弛迭代法
2012-2013(1)专业课程实践论文
超松弛迭代法
姓名,吕永杰,0818180119,R 数学08-1班
一、 算法理论
逐次超松弛迭代法是Gauss-Seidel 方法的一种加速方法,世界大型稀疏矩阵方程组的有效方法之一,它具有计算公式简单,程序设计容易,占用计算机内存较少等优点,但需要选择好的加速因子(即最佳松弛因子)。
设有方程组Ax=b, …………(1) 其中A ∈错误!未找到引用源。为非奇异矩阵,且设错误!未找到引用源。(i=1,2,……,n), 分解A 为 错误!未找到引用源。。………….. (2)
设已知第k 次迭代向量错误!未找到引用源。, 及第k+1次迭代向量错误!未找到引用源。的分量错误!未找到引用源。(j=1,2,……,i-1), 要求计算分量错误!未找到引用源。.
首先用Gauss —Seidel 迭代法定义辅助量
错误!未找到引用源。=错误!未找到引用源。(错误!未找到引用源。 (i=1,2,……n) ……………………..(3) 再把错误!未找到引用源。取为错误!未找到引用源。某个平均值(即加权平均),即
错误!未找到引用源。=(1-错误!未找到引用源。) 错误!未找到引用源。+错误!未找到引用源。=错误!未找到引用源。+错误!未找到引用源。(错误!未找到引用源。) ……………………….. (4)
用式(3)代入式(4)即得到解方程组Ax=b的逐次超松弛迭代公式 错误!未找到引用源。, ……………… (5)
其中错误!未找到引用源。为松弛因子,或写为 错误!未找到引用源。 ……………….. (6)
显然,当错误!未找到引用源。=1时,解式(1)的SOR 方法就是Gauss-Seid el 迭代法。
在SOR 方法中,迭代一次主要的运算量是计算一次矩阵与向量的乘法。由式(5)可知,在计算机上应用SOR 方法解方程组时只需一组工作单元,以便存放近似解.
二, 算法框图
三、 算法程序
#include #include using namespace std;
float *one_array_malloc(int n); //一维数组分配 float **two_array_malloc(int m,int n); //二维数组分配 float matrix_category(float* x,int n);
int main() {
const int MAX=100;//最大迭代次数 int n,i,j,k; float** a;
float* x_0; //初始向量 float* x_k; //迭代向量 float precision; //精度 float w; //松弛因子 cout>precision;
cout>n;
a=two_array_malloc(n,n+1);
cout
for(j=0;j
cin>>a[i][j]; } }
x_0=one_array_malloc(n);
cout
cin>>x_0[i]; }
x_k=one_array_malloc(n);
cout>w; float temp; //迭代过程
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]; x_k[i]=(1-w)*x_0[i]+w*x_k[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
cout
cout
return 0; }
float *one_array_malloc(int n) //一维数组分配 {
float *a;
a=(float *)malloc(sizeof(float)*n); return a; }
float **two_array_malloc(int m,int n) //二维数组分配 {
float **a; int i;
a=(float **)malloc(m*sizeof(float *)); for (i=0;i
a[i]=(float *)malloc(n*sizeof(float)); }
return a; }
float matrix_category(float* x,int n) { int i;
float temp=0; for(i=0;i
temp=temp+fabs(x[i]); }
return temp; }
四、 算法实现
例1 . 用SOR 方法解方程组
错误!未找到引用源。=错误!未找到引用源。
精确解:错误!未找到引用源。=(0.5,1,-0.5),要求精度为5*错误!未找到引用源。,且错误!未找到引用源。为1.03,确定其迭代次数, 解向量。
例2. 用SOR 方法解方程组
错误!未找到引用源。=错误!未找到引用源。 其初始向量为0,精度为错误!未找到引用源。,松弛因子1.3,求其迭代次数及
解向量。