迭代法解线性方程组

雅可比(Jacobi)迭代法 程序流程图 高斯-塞德尔(Gauss-Seidel)迭代法 逐次超松弛

迭代法求解线性方程组

学生姓名：张卫斌 专 业：信计 学 号： 完成日期：

西安科技大学计算机科学与技术学院

0901 0908060124 2011-10-21

雅可比(Jacobi)迭代法 程序流程图 高斯-塞德尔(Gauss-Seidel)迭代法 逐次超松弛

实验题目：

学生姓名： 张卫斌 学号： 0908060124 完成日期： 2011-10-21 1 实验目的

1、通过上机计算体会迭代法求解线性方程组的特点，并能和消去法比较； 2、体会上机计算时，终止步骤

（予给的迭代次数），对迭代法

敛散性的意义；

3、体会初始解 x(，松弛因子的选取，对计算结果的影响

2 实验内容和步骤

1． 用雅可比迭代和高斯-塞德尔迭代算法解线性方程组

5x1 2x2 x3 8

2x1 8x2 3x3 21 x 3x 6x 1

23 1

（1）用雅可比（Jacobi）迭代法的算法解上述方程组的程序如下：

#define N 3 // 线性方程组的阶数 #include <iostream.h> #include <math.h> 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;i<N;i++) { sum = 0; for(j=0;j<N;j++) { if(j!=i) { sum = sum + a[i][j] * x0[j]; } }

雅可比(Jacobi)迭代法 程序流程图 高斯-塞德尔(Gauss-Seidel)迭代法 逐次超松弛

x[i] = (b[i] - sum) / a[i][i]; }// 更新迭代向量 c_M++; //迭代次数加1 for(i=0;i<N;i++) { if(fabs(x[i]-x0[i])>current_e) current_e = fabs(x[i]-x0[i]); } //计算当前误差 for(i=0;i<N;i++) x0[i] = x[i]; //更新初始向量

}while(current_e>e&&c_M<M); //判断是否仍未达到精度要求且未达到最大迭代次数

for(i=0;i<N;i++) cout << x[i] << endl; //输出结果 cout << c_M << endl; //输出迭代次数 }

结合雅可比（Jacobi）迭代算法读懂程序，并且选择不同的精度和迭代次数，观察输出结果； （1） 写出高斯-塞德尔(Gauss-Seidel)迭代算法，并简述与雅可比（Jacobi）迭代算法的异同。 （2） 将雅可比（Jacobi）迭代算法的程序改进为高斯-塞德尔(Gauss-Seidel)迭代算法，并在

相同精度下，与雅可比（Jacobi）迭代算法的结果进行比较，写出结论并解释。 2．试用Jacobi迭代、Gauss-Seidel迭代和SOR迭代算法求解如下方程组

4x1 x2 x3 x4 x 4x x x 1234

x1 x2 4x3 x4 x1 x2 x3 4x4

1 1 1 1

（1） 用Jacobi迭代、Gauss-Seidel迭代求解上述方程组，并在相同精度要求下，比较收敛

速度。

（2） 试叙述SOR迭代算法和Gauss-Seidel迭代算法的异同；然后将Gauss-Seidel迭代算

法的程序修改为SOR迭代算法，求解上述方程组（注意通过试算找到较优的松弛因子）。

（3） 在相同精度要求下，比较SOR迭代算法和Gauss-Seidel迭代算法的收敛速度。

3 程序流程图

雅可比(Jacobi)迭代法 程序流程图 高斯-塞德尔(Gauss-Seidel)迭代法 逐次超松弛

4实验结论及结果分析

4.1迭代法的基本原

雅可比(Jacobi)迭代法 程序流程图 高斯-塞德尔(Gauss-Seidel)迭代法 逐次超松弛

(0)Ax bx根据方程组设计出一个迭代公式，然后将任意选取的一个初始向量代入迭

代公式，求出x

(1)

，再以x

(1)

代入同一迭代公式，求出x

(2)

，如此反复进行，得到向量

(k) (k)

{x}{x}收敛时，其极限即为原方程组的解。 序列。当

定理 当方程组的系数矩阵满足按行严格对角占优时，雅可比迭代和高斯-赛德尔迭代算法对任意的初始向量收敛。

2.3.2 雅可比（Jacobi）迭代法的算法描述

设方程组Ax b的系数矩阵对角线元素aii 0(i 1,2,...,n)，M为最大迭代次数，

为容许误差。雅可比（Jacobi）迭代法解方程组的算法描述如下：

(0)(0)(0)T

① 任取初始向量x(0) (x1,x2,...,xn)，令迭代次数k 0.

② k k 1，并且

对i 1,2,...,n，计算

x

(k)

i

n

1

(bi aijx(jk 1)) （1） aiij 1

j i

(k)

③ 如果maxxi

1 i n

xi(k 1) ，则输出x(k)，结束；否则执行④

④ 如果k M，则不收敛，终止程序；否则转② 4.2 高斯-塞德尔(Gauss-Seidel)迭代法的算法描述

在雅可比（Jacobi）迭代法中，如果当新的分量求出后，马上用它来代替旧的分量，则可能会更快地接近方程组的准确解。基于这种设想构造的迭代公式

x

(k)i

i 1n

1(k)

,n,，k 1,2, （2） (bi aijxj aijx(jk 1)) i 1,2

aiij 1j i 1

称为高斯-塞德尔(Gauss-Seidel)迭代法. 算法可相应地从雅可比（Jacobi）迭代法改造得

到。

4.3逐次超松弛(SOR)迭代算法描述

所谓逐次超松弛迭代算法就是，

为了提高精度，可以考虑运用松弛技术，将高斯-塞德尔(Gauss-Seidel)迭代得到的值进一步加工成某种松弛值，迭代公式如下

雅可比(Jacobi)迭代法 程序流程图 高斯-塞德尔(Gauss-Seidel)迭代法 逐次超松弛

i 1n

1 (k)(k)(k 1)

G S迭代:x (b ax ax) iiijjijj aiii 1,2, ,n，k 1,2, （3） j 1j i 1

(k)(k 1) 松弛加速:x(k) x (1 )xiii

其中 为松弛因子（显然当 1时，就是高斯-塞德尔迭代公式）

i(k)通常优于旧值xi(k 1)，由于新值x在将两者加工成松弛值xi(k)时，自然要求松弛因子 1，

以尽量发挥新值的优势，这类迭代就称为逐次超松弛(SOR)迭代法。

使用SOR迭代的关键在于选取合适的松弛因子，松弛因子的取值对收敛速度影响很大，但如何选取最佳松弛因子的问题，至今仍未有效解决，在实际计算时，通常依据系数矩阵的特点，并结合以往的经验选取合适的松弛因子。

5 实验心得体会

在这次数值分析试验中，我明白了雅克比迭代法和高斯-赛德尔迭代法的异同，更深的理解了用迭代法解线性方程组的方法，并且懂得了编写一段代码，我们不仅要考虑它的可行性，更应该考虑它的算法复杂度，运行效率。由此，我们可以看出做一件事要精益求精，多加斟酌 ，并且在数值分析理论课方面更应该多下功夫，扎实基础才是最重要的。

附录（源代码）

#define N 3 // 线性方程组的阶数 #include <iostream.h> #include <math.h> 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;i<N;i++) { sum = 0; for(j=0;j<N;j++) { if(j!=i) { sum = sum + a[i][j] * x0[j]; } }

雅可比(Jacobi)迭代法 程序流程图 高斯-塞德尔(Gauss-Seidel)迭代法 逐次超松弛

x[i] = (b[i] - sum) / a[i][i]; }// 更新迭代向量 c_M++; //迭代次数加1 for(i=0;i<N;i++) { if(fabs(x[i]-x0[i])>current_e) current_e = fabs(x[i]-x0[i]); } //计算当前误差 for(i=0;i<N;i++) x0[i] = x[i]; //更新初始向量

}while(current_e>e&&c_M<M); //判断是否仍未达到精度要求且未达到最大迭代次数

for(i=0;i<N;i++) cout << x[i] << endl; //输出结果 cout << c_M << endl; //输出迭代次数 }