资源描述：
《算法合集之《用高斯消元法解线性方程组》》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
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+……+a1,nxn=b1a2,1x1+a2,2x2+……+a2,nxn=b2……an,1x1+an,2x2+……+an,nxn=bn下面是n元线性方程组的一般形式：我们可以把它表示为增广矩阵的形式：a1,1a1,2……
3、a1,nb1a2,1a2,2……a2,nb2……an,1an,2……an,nbn先看一个例子2-131425412072-1314-122.5-1.56.52-1314-12-0.8755.25×2×0.5×2.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次消
4、元前的状态第1次消元，第1行的乘数：（i=2,3,…,n）a1,1(1)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,
5、n(k)bk(k)……an,k(k)……an,n(k)bn(k)第k次消元前的增广矩阵：ai,j(k+1)=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的顺序消元的。有：所以每
6、一次消元的主元素都不能为0。如果按照自然顺序消元的过程中出现的ak,k(k)=0，那么消元无法继续进行下去。或者
7、ak,k(k)
8、很小，也会严重影响计算精度。为什么要选主元素例如（假设运算过程中使用单精度实数）：10-101111210-1011-1010-1010解得：x1=0，x2=1这个解与第二个方程差异很大。究其原因，因为消元过程中第一个方程所乘的系数过大，使得上式“吃掉”了下式，所以在结果中根本无法体现下式。但如果调整一下顺序：11210-101111211解得：x1=1，x2=1，这个解基本符合原方程所以每次消元的主元素的绝对
9、值应该尽可能大，使得与主行相乘的乘数尽可能小。选主元素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)………al,k(k)……al,n(k)bl(k)………an,k(k)……an,n(k)bn(k)进行第k次消元时，将ak,k一下各元素（包括ak,k）进行比较，将其中的最大者所在行与第k行交换。无解的情况如果在消元的过程中，增广矩阵出现这样一行：左侧各未知数的系数都为0，而右侧的常数项不为0，则意味着方程组无解。无数组解的情况在消元
10、过程中，出现这样一行：各未知数的系数和常数项都为0。这相当于少了一个方程，也就是接下来的消元过程中，方程的个数少于未知数的个数，方程要么无解，要么有无数组解。下面讨论对于这样的方程，如何得到一
