算法帝国的重要成员——初等行变换算法

焦华

（贵州商学院，贵阳 550014）

0 引言

“算法”其实早已深入到人类社会及人类生活的各个方面，只是大多数人对此一无所知而已。小到十字路口的交通红绿灯和地铁站里的无人自动售票机，大到沪深股市每天几千亿甚至上万亿资金股票的交易及载人航天的探月工程，都与算法分不开。算法对人类社会影响的深度、广度、远度，远远超出了一般人的想象及认知[1]P26。

随着大数据时代的到来以及人工智能研究与应用的再度复苏，智能机器人、智能家电、无人驾驶飞机和汽车等话题越来越受到人们的关注。而这一切都与“算法”息息相关！甚至有专家提出“算法”将统治世界、算法帝国已经形成！[1]P58

从古老的欧几里得算法、割圆术算法到后来的搜索算法、排序算法等，“算法”已从数学概念转变为计算机概念。数学的研究一直是计算机数值算法丰饶的源泉。在“算法”热得发紫的今天，我们重新审视一下算法帝国从古到今的重要成员，初等行变换算法应当入列。这是因为初等行变换算法是线性代数中贯穿始终的算法。而线性代数是自然科学、社会科学、工程技术、经济与管理等领域应用非常广泛的数学学科[4]。

在线性代数中，初等行变换是指三种基本的变换：交换矩阵的某两行；矩阵的某一行乘以一个非零的数；把矩阵某一行的倍数加到另一行。定义这三种基本变换的想法应当来源于对线性方程组的研究。理论上已证明可将任一矩阵通过初等行变换化为行阶梯形，进一步化为行最简形。（如果再进行初等列变换，可化为标准形。）初等行变换算法是以上具体步骤的描述，且已变成了计算机程序，我们也就可用MATLAB来解决线性代数问题。以下是初等行变换算法在线性代数各分支中的应用[2]P65。

1 初等行变换算法在矩阵中的应用

在计算矩阵的逆矩阵时，有两种常用方法：伴随矩阵法和初等行变换法，相比较而言，初等行变换法更简洁。（当然从定义出发的待定系数法也算一种方法，只是太繁琐了。）

实例1证明 A可逆，并求A-1。

解：这里只给出初等行变换法，(A,E)→(E,A-1)，当把左边的A变成了E，右边的E也就变成了A-1。

从而得到A可逆，且

用MATLAB验算如下：（可看出结果是一致的）[3]P15-17

>>A=[0-2 1;1 3-2;-2 3 0];

>>inv（A）

ans=

6.00003.00001.0000

4.0000 2.00001.0000

9.0000 4.00002.0000

>>A^-1

ans=

6.0000 3.00001.0000

4.00002.00001.0000

9.0000 4.00002.0000

利用初等行变换法求矩阵秩的方法：通过初等行变换把矩阵变成它的行阶梯形，行阶梯形矩阵中的非0行的行数即是该矩阵的秩。

实例2设矩阵其中λ为参数，求矩阵A的秩。

解：对A作初等行变换，得：

当λ=3时，r(A)=2；当λ≠3时，r(A)=3。[2]P76-78

求向量组的极大无关组的方法：以向量组中各向量作为列向量组成矩阵后，只允许作初等行变换将此矩阵化为行阶梯形矩阵，（如果问题需要，可进一步化为行最简形矩阵。）之后可直接写出所求向量组的极大无关组。这种方法的理论依据是：初等行变换不改变矩阵列向量之间的线性关系；即矩阵行的初等变换将保持列向量间的线性相关性或线性无关性。

实 例3求 向 量 组α1=(1 ,1,1)T，α2=(1 ,1,0)T，α3=(1 ,0,0)T，α4=(1 ,2,-3)T的一个极大无关组，并将其余向量用此极大无关组线性表示。[2]P104-105

解：由于问题需要将其余向量用极大组线性表示，因此初等行变换的目标不局限于行阶梯形矩阵，而需进一步化为行最简形矩阵。

向量组的秩为3，α1，α2，α3是向量组的一个极大无关组，且 α4=-3α1+5α2-α3。

2 初等行变换算法在线性方程组中的应用

线性方程组的初等变换是指这三种变换：交换某两个方程的位置；某方程的两边同时乘以一个非零的数；把某一个方程的适当倍数加到另一个方程上。线性方程组经过初等变换会将它变成另一个同解的方程组，高斯消去法的目标就是通过初等变换将原有的线性方程组化为阶梯形方程组、进一步化为最简形方程组，最终得到方程组的解。高斯消去法的产生是基于逐步消去（减少）未知量的思想。线性方程组与它的增广矩阵一一对应，高斯消去法的过程也就与初等行变换法的过程一一对应。在人类的认知历程中，应当先有高斯消去法，之后才有初等行变换法。后者是前者从方程组到矩阵的映像，但后者更具备广泛的应用性！20世纪计算机的出现比数学家高斯所处的19世纪晚1个世纪，初等行变换算法是高斯消去法思想结合计算机编程的发扬光大！相比较其他算法而言，比如克莱姆法则，初等行变换算法时间复杂度小。尤其是线性方程组规模庞大时，比如方程个数及未知量个数都是几千个或几万个时，其优势更加明显。[2]P84-85

线性方程组是线性代数的核心，是各分支的汇流处，是有广泛的应用背景的。

实例1有大米、黄豆、玉米、小麦各一袋共38元，若购大米3袋，黄豆5袋，玉米4袋，小麦2袋共需120元；若购大米4袋，黄豆3袋，玉米1袋，小麦1袋共需84元，若购大米2袋，黄豆4袋，玉米2袋，小麦4袋共需122元，问大米、黄豆、玉米、小麦每袋各多少元？

解：设大米、黄豆、玉米、小麦每袋各为x1,x2,x3,x4元，则：

可用克莱姆法则求解，但要计算5个4阶行列式的值，运算量大。克莱姆法则只具备理论价值。也可用消元法和代入法相结合的初等方法求解。这种方法灵活大，但不适宜计算机编程计算，这里采用初等行变换算法。

将线性方程组对应的增广矩阵用初等行变换化为行阶梯形、行最简形：

答：大米每袋10元、黄豆每袋8元、玉米每袋5元、小麦每袋15元。

用MATLAB验算如下：[3]P17-19

>>A=[1 1 1 1;3 5 4 2;4 3 1 1;2 4 2 4];

>>b=[38;120;84;122];

>>x=A

x=

10.0000

8.0000

5.0000

15.0000

>>det（A）

ans=

-22

若已知答案（大米每袋10元、黄豆每袋8元、玉米每袋5元、小麦每袋15元）去构造问题：（显然是修改原题的某些数据，用红色标注。）

1、有大米、黄豆、玉米、小麦各1袋共38元，若购大米3袋，黄豆1袋，玉米2袋，小麦2袋共需78元；若购大米2袋，黄豆3袋，玉米1袋，小麦1袋共需64元，若购大米4袋，黄豆2袋，玉米4袋，小麦2袋共需106元，问大米、黄豆、玉米、小麦每袋各多少元？

用MATLAB验算如下：[3]P16

>>A=[1 1 1 1;3 1 2 2;2 3 1 1;4 2 4 2];

>>b=[38;78;64;106];

>>x=A

x=

10

8

5

15

可以看出构造问题的解与原问题的解是一样的，构造时要注意必须得到4个独立的线性方程，从而得到唯一解。

下面的实例是对无穷多解的讨论，用初等行变换算法求解。

实例2求齐次线性方程组的基础解系及通解。[2]P118

解：

实例3设矩阵X满足方程AX=BT，求X。

解：这是一个解不是向量而是矩阵的矩阵方程，用初等行变换算法求解。[2]P71-72

从而得到:

用MATLAB验算如下：[3]P16-18

>>A=[1 1 2;2 2 3;4 3 3];

>>B=[1 0 0;2 1 1;-1 2 2];

>>X=AB'

X=

34-7

-6-814

23-4

>>X=inv（A）*B'

X=

34-7

-6-814

23-4

3 初等行变换算法在行列式中的应用

行列式的计算有两种常用的算法：“三角化”算法与降阶算法。由于三角形行列式的值等于它的主对角线元素的乘积，因此“三角化”算法的目标就是通过行列式的初等行变换及初等列变换（对应矩阵）将原行列式化为上三角行列式。需要注意的有两点：1、不局限于初等行变换，允许进行初等列变换，更加方便灵活。2、第一种初等行变换（交换两行）行列式要变号；第二种初等行变换（某行乘以某非0数）行列式就要除以该非0数；第三种初等行变换（某行适当的倍数加到另一行）行列式的值不变。这三种变换结果实质是行列式的三条性质。可以看出，“三角化”算法是初等行变换算法在行列式中的应用推广。

实例1计算

解：从第4行起，后面一行减去前面一行，达到最大限度的化繁为简，这里只采用初等行变换，过程如下：

实例2计算

解：其实可以初等行变换及初等列变换一起结合使用，但在此仅采用初等行变换，这是为了更好地突出本文的主题思想。

用MATLAB验算如下：[3]P19

>>D=[3 1-1 2;-5 1 3-4;2 0 1-1;1-5 3-3];

>>det（D）

ans=

40

综上所述，初等行变换算法的确是线性代数中贯穿始终的算法。由于是成熟算法，我们没有用高级语言写出代码，只是在实例中用MATLAB验算结果。马云说：“人算不如天算，天算是什么？天算就是云计算。”。现代人们可通过电脑或手机等方式接入云数据中心，体验到每秒10万亿次以上的云计算能力！明天很美好，未来有无限可能，古老的数学也将焕发出勃勃生机！[4]

[1]（美）克里斯托弗·斯坦纳.算法帝国[M].人民邮电出版社，2014.

[2]吴赣昌.线性代数（经管类第四版）[M].中国人民大学出版社，2011.

[3]于润伟.MATLAB基础及应用（第三版）[M].机械工业出版社，2011.

[4]焦华.用计算机软件辅助数学教学是大数据时代的需要[J].科技展望，2017（08）：177-178.