1、用高斯消元法解线性方程组北京景山学校 何江舟GPA排名系统（ CTSC2001）高等院校往往采用 GPA来评价学生的学术表现。传统的排名方式是求每一个学生的平均成绩，以平均成绩作为依据进行排名。对于不同的课程，选课学生的平均成绩会受到课程的难易程度等因素的影响，因此这种排名方式不够合理。为此，我们需要对排名系统进行这样的改进：对第 i门课的每一个学生的成绩加上一个特定的修正值 di（ 调整后的成绩不按照百分制），使得经过调整后，该课的平均分等于选该课的所有学生的所有课的平均分。对每一门课都这样调整，使得上述条件对所有课程都满足。你的任务是根据一个年级学生某学年的成绩，通过上述调整，得出他们的排
2、名。简要分析Ai： 选修第 i门课的学生的集合Bj： 第 j个学生选修课程的集合Gi,j： 第 j个学生第 I门课的成绩di： 第 i门课的修正值对于第 p门课，可列出如下关系式：这是关于 di（ i=1,2,n ） 的线性方程，我们可以整理出 n个这样的方程。线性方程组的一般形式a1,1x1+a1,2x2+a 1,nxn=b1a2,1x1+a2,2x2+a 2,nxn=b2an,1x1+an,2x2+a n,nxn=bn下面是 n元线性方程组的一般形式：我们可以把它表示为增广矩阵的形式：a1,1 a1,2 a1,n b1a2,1 a2,2 a2,n b2an,1 an,2 an,n bn先看
3、一个例子2 -1 3 14 2 5 41 2 0 72 -1 3 14 -1 22.5 -1.5 6.52 -1 3 14 -1 2-0.875 5.252 0.52.5得出：x3=5.25/(-0.875)=-6x2=(2-(-1)x3)/4=-1x1=(1-(-1)x2-3x3)/2=9消元过程a1,1(1) a1,2 (1) a1,n (1) b1 (1)a2,1(1) a2,2 (1) a2,n (1) b2 (1)an,1(1) an,2 (1) an,n (1) bn (1)注：用上标 (k)表示第 k次消元前的状态第 1次消元，第 1行的乘数：（ i=2,3,n ）a1,1(1)
4、 a1,2 (1) a1,n (1) b1 (1)a2,2 (2) a2,n (2) b2 (2)an,2 (2) an,n (2) bn (2)得到新的增广矩阵：ai,j(2)=ai,j(1)-mi,1a1,j(1)bi(2)=bi(1)-mi,1b1(1)（ i,j=2,3,n ）第 k次消元，第 k行的乘数：（ i=k+1,k+2,n ）消元过程a1,1(1) a1,2 (1) a1,n (1) b1 (1)a2,2 (2) a2,n (2) b2 (2)ak,k(k) ak,n (k) bk (k)an,k(k) an,n (k) bn (k)第 k次消元前的增广矩阵：ai,j(k+1
5、)=ai,j(k) -mi,kak,j(k)bi(k+1)=bi(k) -mi,kbk(k)增广矩阵的变化：（ i,j=k+1,k+2,n ）第 k步消元的主行第 k步消元的主元素回代过程a1,1(1) a1,2 (1) a1,n (1) b1 (1)a2,2 (2) a2,n (2) b2 (2)an,n (n) bn (n)最后得到的增广矩阵：最终结果的计算：为什么要选主元素前面介绍的消元法都是按照自然顺序，即 x1、 x2、 、 xn的顺序消元的。有：所以每一次消元的主元素都不能为 0。如果按照自然顺序消元的过程中出现的 ak,k(k)=0， 那么消元无法继续进行下去。或者 | ak,k(k) |很小，也会严重影响计算精度。为什么要选主元素例如（假设运算过程中使用单精度实数）：10-10 1 11 1 210-10 1 1-1010 -1010解得： x1=0， x2=1这个解与第二个方程差异很大。究其原因，因为消元过程中第一个方程所乘的系数过大，使得上式 “吃掉 ”了下式，所以在结果中根本无法体现下式。但如果调整一下顺序：1 1 210-10 1 11 1 21 1解得： x1=1， x2=1， 这个解基本符合原方程所以每次消元的主元素的绝对值应该尽可能大，使得与主行相乘的乘数尽可能小。
