高斯-赛德尔迭代法的算法及程序设计

题目：高斯-赛德尔迭代法的算法及程序设计摘要本文通过理论与实例对线性方程组的解法、收敛性及误差分析进行了探讨.在对线性方程组数值解法的讨论下用到了高斯-赛德尔迭代法，进一步研究和总结了高斯-赛德尔迭代法的理论与应用，使我们在分析问题与编辑程序时能更好的把握对高斯-赛德尔迭代法的应用。关键词Gauss-Seidel迭代法；收敛性；误差分析；流程图；Mathematica编程目录第一章高斯-赛德尔迭代法...............................................1§1.1高斯-赛德尔迭代法的提出.......................................1§1.1.1高斯-赛德尔迭代法的思想理论.............................1§1.1.2高斯-赛德尔迭代法的定义及表达形式.......................2§1.2高斯-赛德尔迭代法的收敛性.....................................1§1.3高斯-赛德尔迭代法的误差分析...................................1第二章高斯-赛德尔迭代法的程序设计.....................................1§2.1高斯-赛德尔迭代法在上机中的应用...............................1§2.1.1高斯-赛德尔迭代法的流程图...............................1§2.1.2高斯-赛德尔迭代法的源程序...............................1参考文献...............................................错误!未定义书签。附录...................................................错误!未定义书签。1第一章高斯-赛德尔迭代法考虑线性方程组Axb其中A为非奇异矩阵，对于由工程技术中产生的大型稀疏矩阵方程组（A的阶数n很大但零元素很多）,利用迭代法求解线性方程组Axb是合适的.在计算机内存和运算两方面，迭代法通常都可利用A中有大量零元素的特点.本章将介绍迭代法中的高斯-赛德尔法的思想理论、收敛性及误差分析.§1.1高斯-赛德尔迭代法的提出§1.1.1高斯-赛德尔迭代法的思想理论在研究雅可比迭代法时，计算1kix时，已得(1)(1)(1)121,,,kkkixxx（这些分别为121,,,ixxx的第k+1次近似），Gauss-Seidel迭代法认为在计算时启用新值，从而产生1(1)(1)()111()inkkkiiijjijjjjiiixbaxaxa.具体原理如下图所示构造迭代(1)()00kkxBxfx产生向量序列(0)(1)()kxxxxBxfAxb2图1.1基本迭代原理§1.1.2高斯-赛德尔迭代法的定义及表达形式定义1.1我们注意到在雅可比迭代法中并没有对新算出的分量11kx，12kx，，11kix进行充分利用．不妨设想，在迭代收敛的条件下，我们把(1)()()()11211331111(1)()()()22112332222(1)()()()1122,111()1(1(kkkknnkkkknnkkkknnnnnnnnxaxaxaxbaxaxaxaxbaxaxaxaxba式中第一个方程算出的11kx立即投入到第二个方程中，代替()1kx进行计算，当12kx算出后代替()2kx马上投入到第三个方程中计算，依次进行下去，这样也许会得到更好的收敛效果．根据这种思路建立的一种新的迭代格式，我们称为高斯-赛德尔（Gauss-Seidel）迭代公式，高斯=赛德尔迭代法的分量形式：(1)()()()11211331111(1)(1)()()22112332222(1)(1)(1)(1)1122,111()1(1(kkkknnkkkknnkkkknnnnnnnnxaxaxaxbaxaxaxaxbaxaxaxaxba高斯-赛德尔迭代法的矩阵形式：(1)(),(0,1,2,)kkxBxfk其中1()BDLU，1()fDLbB称为高斯-赛德尔迭代矩阵，f称为高斯-赛德尔迭代常量..§1.2高斯-赛德尔迭代法的收敛性根据上节所述，高斯-赛德尔迭代法的迭代格式为3(1)(),(0,1,2,)kkxBxfk（1-1）其中1()BDLU，1()fDLb.本节要讨论的问题就是任意选取初始值(0)x，利用迭代格式(1-1)得到的向量序列()kx是否一定收敛，如果收敛的话需要满足什么条件？下面我们给出一般迭代收敛的条件:定理1.2简单迭代法(1-1)收敛的充分必要条件是迭代矩阵B的谱半径()1B．定理1.3若迭代矩阵B的某种范数1B则（1-2-1）确定的迭代法对任意初值(0)X均收敛于方程组xBxf的唯一解*x。特殊线性方程组迭代法的收敛性定理：定理1.4设对于方程组Axb,若系数矩阵A是严格对角占优矩阵，则（1）A非奇异.（2）Gauss-Seidel迭代法收敛.定理1.5若系数矩阵A对称正定，则Gauss-Seidel迭代公式收敛.例1.1已知方程组1231231232211221xxxxxxxxx，用Gauss-Seidel迭代法解此方程组的收敛性.方程组的系数矩阵122111221A，所以有111D，010220L，022010U11100022()110012210GBDLU=02223222det()023002GIB，得1230,24故()21B，因此Gauss-Seidel迭代法不收敛.§1.3高斯-赛德尔迭代法的误差分析科学计算的主要过程是：对给定的实际问题建立数学模型，通过已获得的有关基本数据，建立近似数值方法，设计算法编制程序，最后上机进行数值计算得到数值结果.其大致过程如下图：图1.2误差分析表定义1.2假设某一量的标准值为x近似解为*x，则x与*x之差叫做近似解x的绝对误差（简称误差），记为()x，即*()xxx定义1.3绝对误差与准确值之比*()(),0ixxxxxxx称为*x的相对误差.定理1.6设*x是方程组Axb的同解方程xBxf的准确解，若迭代公式(1)()kkxBxf中迭代矩阵B的某种范数1qB，则有1）)1()(*)(1kkkXXqqXX2）)0()1(*)(1XXqqXXKk模型误差否是验证结果的正确性与合理性结束得到数值结果上机计算舍入误差设置算法编制程序科学计算方法数学模型实际问题截断误差观测误差截断误差5第二章高斯-赛德尔迭代法的程序设计第二章高斯-赛德尔迭代法的程序设计20世纪50年代是用数字计算机求解电力系统潮流问题的开始阶段，人们普通采用以节点导纳矩阵为基础的高斯-赛德尔迭代法.此方法原理简单，占用内存量较小，编程容易实现，特别是对于配网潮流有其独特优势.但是此算法也有着其致命缺点那就是收敛速度比较慢，尤其是随着电力系统的发展。网络中的节点增多，这个问题将会更加突出.本章将研究高斯-赛德尔迭代法的流程图及程序应用.§2.1高斯-赛德尔迭代法在上机中的应用§2.1.1高斯-赛德尔迭代法的流程图在实际应用中，有时需解决的问题中运算很复杂且运算量也很大，这时我们就需要借助计算机的帮助解决实际问题，即利用高斯-赛德尔迭代法在C语言中的编程实现.高斯-赛德尔迭代法在计算机中的主要实现过程如下图所示图2.3高斯-赛德尔迭代法流程图是输入n,系数矩阵A，矩阵B，精度，循环次数Max，输出精度控制prefor(z=0,zn,z++)[][]*[,][]saizxizj是[][]*[,][1]saizxizj始终误差zi?输出结果否6§2.1.2高斯-赛德尔迭代法在计算机中的应用在C语言环境中解线性方程组的问题需要进行程序编辑，如果解决每一个线性方程组都需要重新编辑程序,就没体现计算机语言的简便性，所以需要一个程序使其对大多数问题都适用.例2.1设方程组Axb的系数矩阵的对角线元素(1,2,,)in，M为迭代次数容许的最大值，为容许误差。1取初始向量令k=0.2对i=1,2,…,n计算3如果则输出结束；否则执行44如果则不收敛，终止程序；否则，转2源程序：#includestdio.h#includemath.h#defineN600voidmain(){inti;doublex[4];doublec[4][5]={10,-1,2,0,-11,0,8,-1,3,-11,2,-1,10,0,6,-1,3,-1,11,25};voidGaussSeidel(double*,int,double[]);GaussSeidel(c[0],4,x);for(i=0;i=3;i++)printf(x[%d]=%f\n,i,x[i]);}voidGaussSeidel(double*a,intn,doublex[]){inti,j,k=1;doubled,dx,eps;for(i=0;i=3;i++)while(1){eps=0;for(i=0;i=3;i++){d=0;for(j=0;j=4;j++){if(j==i)continue;d+=*(a+i*(n+1)+j)*x[j];}7dx=(*(a+i*(n+1)+n)-d)/(*(a+i*(n+1)+i));eps+=fabs(dx-x[i]);x[i]=dx;}if(eps1e-6){printf(迭代次数是:%d\n,k);return;}if(kN){printf(迭代发散n\n);return;}}}输出结果结果分析：从输出结果可以看出此方程组的迭代次数为1，此时能得到精确结果是x[0]=-1.467391,x[1]=-2.358696,x[2]=0.657609,x[3]=2.842391从结果和原有知识可以知道其系数矩阵是严格对角占优的。所以此迭代解法有很好的收敛性.8参考文献[1]贺俐、陈桂兴.计算方法[M].武汉水利电力大学出版社.1998-8-1[2]袁慰平等.计算方法与实习[M].东南大学出版社.2000-7-1[3]徐士良.数值方法与计算机实现[M].清华大学出版社.2006-2-1[4]李炳钊.数值分析基础[M].上海:同济大学出版,1998.[5]张光澄.实用数值分析[M].四川:四川大学出版,2004.[6]刘春凤.应用数值分析[M].北京:冶金工业出版社,20059附录C语言编程源程序#includestdio.h#includestring.h#includemath.h#includestdlib.h#defineN3main(){inti,j,k,s;floata[N][N]={0},L[N][N]={0},U[N][N]={0},sigma1,sigma2;for(i=0;iN;i++){L[i][i]=1;}for(i=0;iN;i++){printf(请输入矩阵第%d行元素：\n,i+1);for(j=0;jN;j++)scanf(%f,&a[i][j]);}for(i=0;iN;i++){U[0][i]=a[0][i];L[i][0]=a[i][0]/U[0][0];}for(k=1;kN;k++){for(j=k;jN;j++){sigma1