用高斯消元法求解线性代数方程组

用高斯消元法求解线性代数方程组12341115-413-2823113-21041513-21719xxxx1111X（X*是方程组的精确解）1高斯消去法1.1基本思想及计算过程高斯（Gauss）消去法是解线性方程组最常用的方法之一，它的基本思想是通过逐步消元，把方程组化为系数矩阵为三角形矩阵的同解方程组，然后用回代法解此三角形方程组得原方程组的解。为便于叙述，先以一个三阶线性方程组为例来说明高斯消去法的基本思想。III)(323034)(5253)(6432321321321xxxxxxxxx把方程（I）乘（23）后加到方程（II）上去，把方程（I）乘（24）后加到方程（III）上去，即可消去方程（II）、（III）中的x1，得同解方程组III)(20223)(445.0)(64323232321xxxxxxx将方程（II）乘（5.03）后加于方程（III），得同解方程组：III)(42)(445.0)(6432332321xxxxxx由回代公式（3.5）得x3=2，x2=8，x1=-13。下面考察一般形式的线性方程组的解法，为叙述问题方便，将bi写成ai,n+1，i=1,2,…,n。1,3322111,223232221211,11313212111nnnnnnnnnnnnnnaxaxaxaxaaxaxaxaxaaxaxaxaxa（1-1）如果a110，将第一个方程中x1的系数化为1，得)1(1,1)1(12)1(121nnnaxaxax其中)0(11)0()1(1aaaijj，j=1,…,n+1（记ijijaa)0(，i=1,2,…,n;j=1,2,…,n+1）从其它n–1个方程中消x1，使它变成如下形式)1(1,)1(2)1(2)1(1,2)1(22)1(22)1(1,1)1(12)1(121nnnnnnnnnnnnaxaxaaxaxaaxaxax（1-2）其中niamaaijiijij,,2)1(1)1(，1,,3,211)1(11njaamii由方程（1-1）到（1-2）的过程中，元素11a起着重要的作用，特别地，把11a称为主元素。如果（1-2）中0)1(22a，则以)1(22a为主元素，又可以把方程组（1-2）化为：)2(1,)2(3)2(3)3(1,3)2(33)2(33)2(1,2)2(23)2(232)1(1,1)1(12)1(121nnnnnnnnnnnnnnnaxaxaaxaxaaxaxaxaxaxax（1-3）针对（1-3）继续消元，重复同样的手段，第k步所要加工的方程组是：)1(1,)1()1()1(1,)1()1()1(1,1)1()1(11)2(1,2)2(23)2(232)1(1,1)1(13)1(132)1(121knnnknnkknkknknknnkkkkknknkknkkkknnnnnnaxaxaaxaxaaxaxaxaxaxaxaxaxaxax设0)1(kkka，第k步先使上述方程组中第k个方程中xk的系数化为1：)(1,)()(1,knknkknkkkkkaxaxax然后再从其它（n-k）个方程中消xk，消元公式为：nkinkjaaaankkjaaakkjkikkijkijkkkkkjkkj,11,,11,,1,)()1()1()()1()1()((1-4)按照上述步骤进行n次后，将原方程组加工成下列形式：)(1,)1(1,1)1(1)2(1,2)2(23)2(232)1(1,1)1(13)1(132)1(121nnnnnnnnnnnnnnnnnnaxaxaxaxaxaxaxaxaxax回代公式为：1,,11)()(1,)(1,nkxaaxaxnkjjkkjknkknnnn（1-5）综上所述，高斯消去法分为消元过程与回代过程，消元过程将所给方程组加工成上三角形方程组，再经回代过程求解。由于计算时不涉及xi,i=1,2,…,n，所以在存贮时可将方程组AX=b，写成增广矩阵（A,b）存贮。下面，我们统计一下高斯消去法的工作量；在（1-4）第一个式子中，每执行一次需要)(knn次除法，在（1-5）第二个式子中，每执行一次需要)()]1([knkn次除法。因此在消元过程中，共需要)12)(1(61)1()1()()1(121nnnknknknknnknk次乘作法。此外，回代过程共有)1(2)(1nnknnk次乘法。汇总在一起，高斯消去法的计算量为：33)13(3232nnnnnn次乘除法。1.2基于VC的C语言程序#includestdio.h#definen4/*n为方程组系数矩阵的阶数*/intGauss(floata[n][n],floatb[n]){inti,j,k,flag=1;floatt;for(i=0;in-1;i++){if(a[i][i]==0){flag=0;break;}else{for(j=i+1;jn;j++)/*消元过程*/{t=-a[j][i]/a[i][i];b[j]=b[j]+t*b[i];for(k=i;kn;k++)a[j][k]=a[j][k]+t*a[i][k];}}}return(flag);}voidzg_matric(floata[n][n],floatb[n])/*输出增广矩阵*/{inti,j;for(i=0;in;i++){for(j=0;jn;j++)printf(%10f,a[i][j]);printf(%10f,b[i]);printf(\n);}printf(\n);}voidmain(){staticfloata[n][n]={{11,1,5,-4},{-2,8,2,3},{3,-2,10,4},{1,3,-2,17}};floatb[n]={13,11,15,19};floatx[n]={0,0,0,0};inti,j,flag;zg_matric(a,b);flag=Gauss(a,b);zg_matric(a,b);if(flag==0)/*无解*/printf(Gaussmethoddosenotrun.);else/*回带过程开始*/{x[n-1]=b[n-1]/a[n-1][n-1];for(i=n-2;i=0;i--){x[i]=b[i];for(j=i+1;jn;j++)x[i]=x[i]-a[i][j]*x[j];x[i]=x[i]/a[i][i];}for(i=0;in;i++)/*输出方程组的解*/printf(x%d=%11.7f\n,i+1,x[i]);}}1.3运行结果图