求解线性方程组的不同高斯消去法

1学院：精仪学院专业：光学工程姓名：张荣香学号：1011202039求解线性方程组的不同高斯消去法线性代数是代数学的一个重要组成部分，广泛应用于现代科学的许多分支，其核心问题之一就是线性方程组的求解问题。线性方程组的求解从理论上可分为两类：直接法和间接法（迭代法）。直接法是经过有限步算术运算得到方程组精确解的方法（不考虑计算过程中的舍入误差），常见的方法有Gauss消去法和LU分解法。直接法在实际计算时有舍入误差的存在和影响。迭代法是采用某种极限过程，用线性代数方程组的近似解逐步逼近精确解的方法，迭代法中常用的方法有简单迭代法、Jacobi迭代法、Gauss-Seidel迭代法和SOR迭代法。本文主要对顺序高斯消去法、选主元高斯消去法进行分析比较。1、顺序高斯消去法1.1基本原理用顺序高斯消去法求解线性方程组的基本思想是在逐步消元的过程中，把方程组的系数矩阵化为上三角矩阵，从而将原方程组约化为容易求解的等价三角方程组，然后进行回代求解。设有如下方程组m21n21mnm2m12n22211n1211bbbxxxaaaaaaaaa简记为：bAx将原方程组记为)1()1(bxA，其中)()()1()1(ijijaaA，bb)1(第一步（k=1）：若011a，则可以计算乘数)1(11)1(11/aamii（mi,,3,2）用1im乘方程组第一个方程加到第i个方程，则原方程组同解方程组为)2()2(2)1(1n21(2)mn)2(2(2)2n)2(22(1)1n)1(12)1(1100mmbbbxxxaaaaaaa简记为：)2()2(bxA，其中，)1(11)1()2(jiijijamaa（mi,,3,2；nj,,3,2）2)1(11)1()2(bmbbiii（mi,,3,2）第二步：设经过k-1次消元后的同解方程组为)()()2(2)1(1n21(k)mn)((k)kn(k)kk(2)2n(2)2k)2(22(1)1n(1)1k)1(12)1(11kmkkkmkbbbbxxxaaaaaaaaaaa设0)(kkka，计算乘数)()(/kkkkikikaam（mki,,1）用ikm乘上面方程组第k个方程加到第i个方程，可以消去kx元，得到同解方程组)1()1(kkbxA其中，)()()1(kkjikkijkijamaa（mki,,1；nkj,,1）)()()1(kkikkikibmbb（mki,,1）重复上述过程可以将方程组化为等价的简单方程组)1()1(ssbxA，),1min(nms，其中)1(sA为上梯形阵。当nm时，与原方程组等价的方程组为)()(nnbxA，即)()2(2)1(1n21(n)nn(2)2n)2(22(1)1n)1(12)1(11000nnbbbxxxaaaaaa由上述方程组很快可以求出：)1,,2,1(,/)(/)(1)()()()(nnkaxabxabxkkknkjjkkjkkknnnnnn1.2求解实例(1)7251013-94144-3211312433-00124321xxxx(2)211110121-18xx【Matlab程序】3clear;MatrixA=[2100-3;-3-4-1213;123-4;4149-13];MatrixB=[10;5;-2;7];%MatrixA=[1e-181;11];%MatrixB=[1;2];Lent=length(MatrixB);MatrixX=zeros(Lent,1);fori=1:Lent-1forj=i+1:Lentfork=i+1:LentMatrixA(j,k)=MatrixA(j,k)-MatrixA(i,k)*(MatrixA(j,i)/MatrixA(i,i));endMatrixB(j)=MatrixB(j)-MatrixB(i)*(MatrixA(j,i)/MatrixA(i,i))MatrixA(j,i)=0endendMatrixX(Lent)=MatrixB(Lent)/MatrixA(Lent,Lent);fori=Lent-1:-1:1Sum=0;forj=i+1:LentSum=Sum+MatrixA(i,j)*MatrixX(j);endMatrixX(i)=(MatrixB(i)-Sum)/MatrixA(i,i);endMatrixX【求解结果及分析】（1）消元后的A消元后的b结果x2.000010.00000-3.000010.00001011.0000-12.00008.500020.0000200-0.2727-0.1818-1.54553000-4.0000-16.00004（2）消元后的A消元后的b结果x1.0e+018*1.0e+018*0.00000.00000.000000-1.0000-1.00001这个解不满足原方程组（2），解是错误的。这是因为主元素)1(11a很小，用其作除数，会导致其他元素数量级的严重增长和舍入误差的扩散，从而导致结果错误。2、选主元高斯消去法2.1基本原理顺序高斯消去法在消元的过程中，可能出现0)(kkka的情况，这时消去法将无法进行；即使主元素)(kkka很小，用其作除数，会导致其他元素数量级的严重增长和舍入误差的扩散(如上例中（2）)。4因此，为了减少误差，每次消元选取系数矩阵（或某列）中绝对值最大的元素作为主元素，这就是全（列）主元高斯消去法。列主元高斯消去法的基本思想：依次按列选主元素，然后换行使之变到主元素位置上，再进行消元计算。在第k步消元时①先选取列主元：0)()(maxkiknikkkiaak；②如果kik，则交换第k行和第ki行；③消元。列主元高斯消去法比顺序高斯消去法要多一些比较运算，但比顺序高斯消去法稳定。全主元高斯消去法是k步消元时选)(kA中绝对值最大的元素为主元，即①先选取全主元：0)(,)(maxkijnjikkjiaakk；②如果kik，则交换第k行和第ki行；如果kjk，则交换第k列和第kj列；③消元。列交换改变了ix的顺序，须记录交换次序，解完后再换回来。全主元高斯消去法具有很好的稳定性，但选全主元比较费时，故在实际计算中很少使用，目前使用较多的是列主元消去法。2.2求解实例利用列主元高斯消去法求解上述两个方程组。【Matlab程序】clear;MatrixA=[2100-3;-3-4-1213;123-4;4149-13];MatrixB=[10;5;-2;7];%MatrixA=[1e-181;11];%MatrixB=[1;2];Lent=length(MatrixB);MatrixX=zeros(Lent,1);MatrixC=zeros(1,Lent);d1=0;fori=1:Lent-1Max=abs(MatrixA(i,i));s=i;forj=i+1:Lentif(Maxabs(MatrixA(j,i)))Max=abs(MatrixA(j,i));s=j;endendif(s~=i)fork=i:LentMatrixC(k)=MatrixA(i,k);MatrixA(i,k)=MatrixA(s,k);MatrixA(s,k)=MatrixC(k);endd1=MatrixB(i);5MatrixB(i)=MatrixB(s);MatrixB(s)=d1;endforj=i+1:Lentfork=i+1:LentMatrixA(j,k)=MatrixA(j,k)-MatrixA(i,k)*(MatrixA(j,i)/MatrixA(i,i));endMatrixB(j)=MatrixB(j)-MatrixB(i)*(MatrixA(j,i)/MatrixA(i,i))MatrixA(j,i)=0endendMatrixX(Lent)=MatrixB(Lent)/MatrixA(Lent,Lent);fori=Lent-1:-1:1Sum=0;forj=i+1:LentSum=Sum+MatrixA(i,j)*MatrixX(j);endMatrixX(i)=(MatrixB(i)-Sum)/MatrixA(i,i);endMatrixX【求解结果及分析】（1）消元后的A消元后的b结果x4.000014.00009.0000-13.00007.00001.000006.5000-5.25003.250010.25002.000000-2.07692.00001.76923.0000000-0.4444-1.77784.0000此结果和利用顺序高斯消去法得到的结果一样，可见对于方程组（1）两种方法同样有效，并且由计算结果可得知列主元高斯消去法的计算结果要更加精确。（2）消元后的A消元后的b结果x11210111此结果和利用顺序高斯消元法得到的结果不同。这个结果是正确的，可见用高斯消去法解方程组时，小主元可能导致计算失败，因为用绝对值很小的数作除数，乘数很大，引起约化中间结果数量级严重增长，再舍入就使得计算结果不可靠了，故应避免采用绝对值很小的主元素，以便减少计算过程中舍入误差对计算解的影响。以上两例的求解结果说明列主元高斯消去法比顺序高斯消去法稳定。