用高斯消元法和列主元消去法求解线性代数方程组
（X*是方程组的精确解）
1 高斯消去法
1.1 基本思想及计算过程
高斯（Gauss）消去法是解线性方程组最常用的方法之一，它的基本思想是通过逐步消元，把方程组化为系数矩阵为三角形矩阵的同解方程组，然后用回代法解此三角形方程组得原方程组的解。
为便于叙述，先以一个三阶线性方程组为例来说明高斯消去法的基本思想。
(?)?2x1?3x2?4x3?6?(??) ?3x1?5x2?2x3?5?4x?3x?30x?32(III)23?1把方程（I）乘（?32）后加到方程（II）上去，把方程（I）乘（?42）后加到方程（III）上
去，即可消去方程（II）、（III）中的x1，得同解方程组
?2x1?3x2?4x3?6??0.5x2?4x3??4??3x?22x?2023?将方程（II）乘（
(?)(??)
(III)3）后加于方程（III），得同解方程组： 0.5?2x1?3x2?4x3?6??0.5x2?4x3??4??2x3??4?由回代公式（3.5）得x3 = 2，x2 = 8，x1 = -13。
(?)(??)
(III)下面考察一般形式的线性方程组的解法，为叙述问题方便，将bi写成ai, n+1，i = 1, 2,…,n。
?a11x1?a12x2?a13x3???a1nxn?a1,n?1??a21x1?a22x2?a23x3???a2nxn?a2,n?1 ?
?????an1x1?an2x2?an3x3???annxn?an,n?1?
如果a11 ? 0，将第一个方程中x1的系数化为1，得
(1)(1)(1)x1?a12x2???a1nxn?a1,n?1
(0)aij （1-1）
其中a(1)1j?a(0)11(0)， j = 1, …, n + 1（记aij?aij，i = 1, 2, …, n; j = 1, 2, …, n + 1）
从其它n –1个方程中消x1，使它变成如下形式
(1)1))?x1?a12x2???a1(nxn?a1(,1n?1?(1)(1)(1)a22x2???a2?nxn?a2,n?1 ?
??(1)(1)(1)?ax???ax?an22nnnn,n?1? （1-2）
其中a(1)ij?aij?mi1?a(1)iji?2,?,n，mi1?1)ai(1a11j?2,3,?,n?1
由方程（1-1）到（1-2）的过程中，元素a11起着重要的作用，特别地，把a11称为主元素。
如果（1-2）中a22?0，则以a22为主元素，又可以把方程组（1-2）化为：
(1))(1)?x1?a12x2? ? ?a1(1nxn?a1,n?1?(2)(2)(2)x2?a23x3???a2? nxn?a2,n?1?(2)(2)(3) a33x3???a3?nxn?a3,n?1 ???(2)(2)(2)? anx???ax?a33nnnn,n?1?(1)(1) （1-3）
针对（1-3） 继续消元，重复同样的手段，第k步所要加工的方程组是：
(1)(1))(1)?x1?a12x2?a13x3 ?? ?a1(1nxn?a1,n?1?(2)(2)(2)x2?a23x3 ?? ? a2?nxn?a2,n?1????(k?1)(k?1)(k?1) xk?1?akx???ax?a? ?1kknnk?1,n?1
?(k?1)(k?1)(k?1) ax???ax?akkknnnk,n?1????(k?1)(k?1)(k?1)? ax???ax?ankknnnn,n?1?(k?1)?0，第k步先使上述方程组中第k个方程中xk的系数化为1： 设akk(k)(k)(k)xk?ak,k?1xk??aknxn?ak,n?1
然后再从其它（n - k）个方程中消xk，消元公式为：
(k?1)?(k)akjj?k,k?1,?,n?1?akj?(k?1)akk??(k)(k?1)(k?1)(k) (1-4) ?aij?aij?aik?akj??j?k?1,?,n?1??i?k?1,?n
按照上述步骤进行n次后，将原方程组加工成下列形式：
(1)(1)(1)(1)?x1?a12x2?a13x3???a1nxn?a1,n?1?(2)(2)(2)x2?a23x3???a2?nxn ?a2,n?1?
???(n?1)(n?1)x?ax ?an?1nnnn?1,n?1?(n)?xn ?an,n?1?回代公式为：
(n)?xn?an,n?1? ?(k)x?akk,n?1???
j?k?1(k)xj?akjnk?n?1,?,1 （1-5）
综上所述，高斯消去法分为消元过程与回代过程，消元过程将所给方程组加工成上三角
形方程组，再经回代过程求解。
由于计算时不涉及xi, i = 1, 2, …, n，所以在存贮时可将方程组AX = b，写成增广矩阵（A,
b）存贮。
下面，我们统计一下高斯消去法的工作量；在（1-4）第一个式子中，每执行一次需要
n?(n?k)次除法，在（1-5）第二个式子中，每执行一次需要[n?(k?1)]?(n?k)次除
法。因此在消元过程中，共需要
??(n?k?1)?(n?k)?(n?k?1)?k?1nn??(n?k?1)2?k?11n(n?1)(2n?1)6
次乘作法。此外，回代过程共有
?(n?k)?2(n?1)
k?1nn次乘法。汇总在一起，高斯消去法的计算量为：
n2n3n(n?3n?1)??n2? 333次乘除法。
1.2 基于Matlab的程序代码
function x=gauss6(A,b) %x=gauss6(A,b) 正消 n=length(A); a=[A,b]; for k=1:n-1 for i=k+1:n l(i,k)=a(i,k)/a(k,k); a(i,k+1:n+1)=a(i,k+1:n+1)-l(i,k).*a(k,k+1:n+1); end end %回代 if a(n,n)==0 return end x(n)=a(n,n+1)/a(n,n); for i=n-1:-1:1 x(i)=(a(i,n+1)-sum(a(i,i+1:n).*x(i+1:n)))/a(i,i); end 1.3 运行结果图
2 列主元消去法
2.1基本思想及计算过程
前述的消去过程中，未知量是按其出现于方程组中的自然顺序消去的，所以又叫顺序消
去法。实际上已经发现顺序消去法有很大的缺点。设用作除数的akk元过程中可能出现akk(k?1)(k?1)为主元素，首先，消
(k?1)为零的情况，此时消元过程亦无法进行下去；其次如果主元素akk很小，由于舍入误差和有效位数消失等因素，其本身常常有较大的相对误差，用其作除数，会导致其它元素数量级的严重增长和舍入误差的扩散，使得所求的解误差过大，以致失真。
在消元过程中适当选取主元素是十分必要的。误差分析的理论和计算实践均表明：顺序
消元法在系数矩阵A为对称正定时，可以保证此过程对舍入误差的数值稳定性，对一般的矩阵则必须引入选取主元素的技巧，方能得到满意的结果。
在列主元消去法中，未知数仍然是顺序地消去的，但是把各方程中要消去的那个未知数
的系数按绝对值最大值作为主元素，然后用顺序消去法的公式求解。
2.2 基于Matlab的程序代码
作业一 高斯消元法和列主元消元法
