高斯消元法

高斯消元法（英语：Gaussian Elimination）是线性代数中的一个算法，可以把矩阵转化为行阶梯形矩阵。^[1]高斯消元法可用来为线性方程组求解，求出矩阵的秩，以及求出可逆方阵的逆矩阵。

历史

高斯消元法最早出现在中国数学典籍《九章算术》第八章〈方阵〉中，尽管书中未对其提供正式的证明^[2]。该方法在十八道题目中有所应用，处理的联立方程组数量介于二至五个之间。根据历史记载，此书最早的确切引用可追溯至公元 179 年，但其中部分内容可能早在公元前 150 年左右便已撰写完成^[3]^[4]。到了三世纪，刘徽为其作注解。

根据 Grcar 的研究，透过消元法求解线性方程组的概念在欧亚大陆的多个文化中独立发展，最早可追溯至古代。在欧洲，文艺复兴晚期（16 世纪 50 年代）便已有明确记载该方法的应用。当时，数学家可能已将其视为基础知识，因此未特意加以说明，这也使得我们难以确切还原其详细的发展历程，仅能确定该方法在当时的欧洲多个地区已被广泛使用。

在欧洲，高斯消元法的发展可追溯至艾萨克·牛顿的笔记。 1670 年，牛顿指出，他所知的代数书籍中皆缺少求解联立方程组的相关内容，于是他亲自补充了这一部分。剑桥大学最终于 1707 年出版了这些笔记，书名为《通用算术（英语：Arithmetica Universalis）》，当时牛顿已经离开学术界。该书的内容被广泛仿效，使得（现今所称的）高斯消元法在 18 世纪末成为代数教科书中的标准课程。 1810 年，卡尔·高斯设计了一种用于对称消去的记号，并在 19 世纪被专业计算员采用，以求解最小二乘问题的法方程。然而，直到 1950 年代，由于对该方法历史的误解，这一算法才被命名为“高斯消元法”。

部分学者将“高斯消元法”仅用于指将矩阵化为梯形（阶梯）形式的过程，而将“高斯－约旦消元法”用于指将矩阵进一步化为简化梯形（最简）形式的完整过程。之所以使用这一名称，是因为该方法是高斯消元法的变体，由威廉·乔丹（英语：Wilhelm Jordan (geodesist)）于 1888 年加以描述。然而，同一年克拉森（Clasen）发表的文章中也提出了这种方法，因此乔丹与克拉森很可能是独立发现高斯－约旦消元法的^[5]。

例子

高斯消元法可用来找出下列方程组的解或其解的限制： $\left\{{\begin{matrix}2x+y-z=8\quad (L_{1})\\-3x-y+2z=-11\quad (L_{2})\\-2x+y+2z=-3\quad (L_{3})\\\end{matrix}}\right.$

这个算法的原理是：

首先，要将 $L_{1}$ 以下的等式中的 $x$ 消除，然后再将 $L_{2}$ 以下的等式中的 $y$ 消除。这样可使整个方程组变成一个三角形似的格式。之后再将已得出的答案一个个地代入已被简化的等式中的未知数中，就可求出其余的答案了。

在刚才的例子中，我们将 ${\frac {3}{2}}L_{1}$ 和 $L_{2}$ 相加，就可以将 $L_{2}$ 中的 $x$ 消除了。然后再将 $L_{1}$ 和 $L_{3}$ 相加，就可以将 $L_{3}$ 中的 $x$ 消除。

我们可以这样写：

L_{2}+{\frac {3}{2}}L_{1}\rightarrow L_{2}

L_{3}+L_{1}\rightarrow L_{3}

结果就是：

2x+y-z=8\,

{\frac {1}{2}}y+{\frac {1}{2}}z=1\,

2y+z=5\,

现在将 $-4L_{2}$ 和 $L_{3}$ 相加，就可将 $L_{3}$ 中的 $y$ 消除：

L_{3}+-4L_{2}\rightarrow L_{3}

其结果是：

2x+y-z=8\,

{\frac {1}{2}}y+{\frac {1}{2}}z=1\,

-z=1\,

这样就完成了整个算法的初步，一个三角形的格式（指：变量的格式而言，上例中的变量各为3,2,1个）出现了。

第二步，就是由尾至头地将已知的答案代入其他等式中的未知数。第一个答案就是：

z=-1\quad (L_{3})

然后就可以将 $z$ 代入 $L_{2}$ 中，立即就可得出第二个答案：

y=3\quad (L_{2})

之后，将 $z$ 和 $y$ 代入 $L_{1}$ 之中，最后一个答案就出来了：

x=2\quad (L_{1})

就是这样，这个方程组就被高斯消元法解决了。

这种算法可以用来解决所有线性方程组。即使一个方程组不能被化为一个三角形的格式，高斯消元法仍可找出它的解。例如，如果在第一步化简后， $L_{2}$ 及 $L_{3}$ 中没有出现任何 $y$ ，没有三角形的格式，照着高斯消元法而产生的格式仍是一个行阶梯形矩阵。这情况之下，这个方程组会有超过一个解，当中会有至少一个变量作为答案。每当变量被锁定，就会出现一个解。

通常人或电脑在应用高斯消元法的时候，不会直接写出方程组的等式来消去未知数，反而会使用矩阵来计算。以下就是使用矩阵来计算的例子：

\left[{\begin{array}{ccc|c}2&1&-1&8\\-3&-1&2&-11\\-2&1&2&-3\end{array}}\right]

跟着以上的方法来运算，这个矩阵可以转变为以下的样子：

\left[{\begin{array}{ccc|c}2&1&-1&8\\0&{\frac {1}{2}}&{\frac {1}{2}}&1\\0&0&-1&1\end{array}}\right]

这矩阵叫做“行阶梯形矩阵”。

最后，可以利用同样的算法产生以下的矩阵，便可把所得出的解或其限制简明地表示出来：

\left[{\begin{array}{ccc|c}1&0&0&2\\0&1&0&3\\0&0&1&-1\end{array}}\right]

最后这矩阵叫做“简化行阶梯形矩阵”，亦是高斯-若尔当消元法指定的步骤。^[6]

其他应用

找出逆矩阵

高斯消元法可以用来找出一个可逆矩阵的逆矩阵。设 $A$ 为一个 $n\times n$ 的矩阵，其逆矩阵可被两个分块矩阵表示出来。将一个 $n\times n$ 单位矩阵放在 $A$ 的右手边，形成一个 $n\times 2n$ 的分块矩阵 $B=[A,I]$ 。经过高斯消元法的计算程序后，矩阵 $B$ 的左手边会变成一个单位矩阵 $I$ ，而逆矩阵 $A^{-1}$ 会出现在 $B$ 的右手边。

假如高斯消元法不能将 $A$ 化为三角形的格式，那就代表 $A$ 是一个不可逆的矩阵。

应用上，高斯消元法极少被用来求出逆矩阵。高斯消元法通常只为线性方程组求解。^[7]

计出秩和基底的基本算法

高斯消元法可应用在任何 $m\times n$ 的矩阵 $A$ 。在不可减去某数的情况下，我们都只有跳到下一行。以一个 $6\times 9$ 的矩阵作例，它可能可以变化为一个行阶梯形矩阵：

{\begin{bmatrix}1&*&0&0&*&*&0&*&0\\0&0&1&0&*&*&0&*&0\\0&0&0&1&*&*&0&*&0\\0&0&0&0&0&0&1&*&0\\0&0&0&0&0&0&0&0&1\\0&0&0&0&0&0&0&0&0\end{bmatrix}}

而矩阵中的*是一些数字。这个行阶梯形矩阵 $T$ 会有一些关于 $A$ 的资讯：

$A$ 的秩是5，因为 $T$ 有5行非0的行；
$A$ 的列空间Col(A)，将以 $A$ 的第1、3、4、7和9行为基底，就是那些在矩阵 $T$ 之中拥有主元的行；
矩阵中的*表示了 $A$ 的该行如何写为上述基底的线性组合。

分析

高斯消元法的算法复杂度是O(n³)；这就是说，如果系数矩阵的是n × n，那么高斯消元法所需要的计算量大约与n³成比例。

高斯消元法可以用在电脑中来解决数千条等式及未知数。不过，如果有过百万条等式时，这个算法会十分费时。一些极大的方程组通常会用迭代法来解决。亦有一些方法特地用来解决一些有特别排列的系数的方程组。

高斯消元法可用在任何域中。

高斯消元法对于一些矩阵来说是稳定的。对于普遍的矩阵来说，高斯消元法在应用上通常也是稳定的，不过亦有例外。^[8]

伪代码

高斯消元法的其中一种伪代码：

 i = 1
 j = 1
 while (i ≤ m and j ≤ n) do
   Find pivot in column j, starting in row i    // 从第i行(row)开始，找出第j列(column )中的最大值（i、j值应保持不变）  #台湾与大陆的列、行定义相反。台湾列为row行为column，大陆列为column行为row。
   maxi = i
   for k = i+1 to m do
     if abs(A[k,j]) > abs(A[maxi,j]) then
       maxi = k   // 使用交换法找出最大值（绝对值最大）
     end if
   end for
   if A[maxi,j] ≠ 0 then  // 判定找到的绝对值最大值是否为零：若不为零就进行以下操作；若为零则说明该列第(i+1)列以下（包括第(i+1)列）均为零，不需要再处理，直接跳转至第(j+1)行第(i+1)列
     swap rows i and maxi, but do not change the value of i   // 将第i行与找到的最大值所在行做交换，保持i值不变（i值记录了本次操作的起始行）
     Now A[i,j] will contain the old value of A[maxi,j].
     divide each entry in row i by A[i,j]    // 将交换后的第i列归一化（第i列所有元素分别除以A[i,j]）
     Now A[i,j] will have the value 1.
     for u = i+1 to m do    // 第j行中，第(i+1)列以下（包括第(i+1)列）所有元素都减去A[i,j]，直到第j行的i+1列以後元素均為零
       subtract A[u,j] * row i from row u
       Now A[u,j] will be 0, since A[u,j] - A[i,j] * A[u,j] = A[u,j] - 1 * A[u,j] = 0.
     end for
     i = i + 1   
   end if
   j = j + 1  // 第j行中，第(i+1)列以下（包括第(i+1)列）所有元素均为零。移至第(j+1)行，从第(i+1)列开始重复上述步骤。
 end while

这个算法和之前谈到的有点不同，它由绝对值最大的部分开始做起，这样可以改善算法的稳定性。本算法由左至右地计算，每作出以下三个步骤，才跳到下一行和下一列：

定出每行的绝对值最大的一个非0的数，将第一列的值与该列交换，使得第一列拥有这一行的最大值；
将第一行的数字除以该数，使得该列的第一个数成为1；
对每一列减去第一列乘以每一列的第一个数，使得每一列的第一个数变为0。

所有步骤完成后，这个矩阵会变成一个行阶梯形矩阵，再用代入法就可以求解该方程组。

随着多核处理器的日益普及，现在的程序员可以利用线程级并行高斯消元算法来提高计算的速度。内存共享模式（而不是消息交换模式）的伪代码如下所示：

void parallel(int num_threads,int matrix_dimension)
{
	int i;
	for(i=0; i<num_threads; i++)
		create_thread(&threads[i],i);
	pthread_attr_destroy(&attr); // Free attribute and wait for the other threads
	for(i=0; i<p; i++)
		pthread_join(threads[i],NULL);
}
void *gauss(int thread_id)
{
	int i,k,j;
	for(k=0; k<matrix_dimension-1; k++)
	{
		if(thread_id==(k%num_thread))  //interleaved-row work distribution
		{
			for(j=k+1; j<matrix_dimension; j++)
				M[k][j]=M[k][j]/M[k][k];
			M[k][k]=1;
		}
		barrier(num_thread,&mybarrier);      //wait for other thread finishing this round
		for(i=k+1; i<matrix_dimension; i=i+1)
			if(i%p==thread_id)
			{
				for(j=k+1; j<matrix_dimension; j++)
					M[i][j]=M[i][j]-M[i][j]*M[k][j];
				M[i][k]=0;
			}
		barrier(num_thread,&mybarrier);
	}
	return NULL;
}
void barrier(int num_thread, barrier_t * mybarrier)
{
	pthread_mutex_lock(&(mybarrier->barrier_mutex));
	mybarrier->cur_count++;
	if(mybarrier->cur_count!=num_thread)
		pthread_cond_wait(&(mybarrier->barrier_cond),&(mybarrier->barrier_mutex));
	else
	{
		mybarrier->cur_count=0;
		pthread_cond_broadcast(&(mybarrier->barrier_cond));
	}
	pthread_mutex_unlock(&(mybarrier->barrier_mutex));
}

参考文献

^ Steven J. Leon. Linear Algebra With Applications. 培生教育. 2014: 第13页. ISBN 9781292025148.
^ 第八章方程. 《九章算术》. 150bc. （原始内容存档于2009年4月19日）. 请检查|date=中的日期值 (帮助)
^ Documenta Mathematica, Vol. Extra Volume: Optimization Stories (2012), 9-14. www.emis.de. [2022-12-02].
^ Timothy Gowers; June Barrow-Green; Imre Leader. The Princeton Companion to Mathematics. Princeton University Press. 8 September 2008: 607. ISBN 978-0-691-11880-2.
^ Althoen, Steven C.; McLaughlin, Renate, Gauss–Jordan reduction: a brief history, The American Mathematical Monthly (Mathematical Association of America), 1987, 94 (2): 130–142, ISSN 0002-9890, JSTOR 2322413, doi:10.2307/2322413
^ Steven J. Leon. Linear Algebra With Applications. 培生教育. 2014: 第17页. ISBN 9781292025148.
^ Atkinson, 1989年，第514页
^ Golub and Van Loan, §3.4.6

Atkinson, Kendall A. An Introduction to Numerical Analysis, 第二版, John Wiley & Sons, New York, 1989年 ISBN 978-0-471-50023-0
Golub, Gene H., and Van Loan, Charles F. Matrix computations, 第三版, Johns Hopkins, Baltimore, 1996年 ISBN 978-0-8018-5414-9
Lipschutz, Seymour, and Lipson, Mark. Schaum's Outlines: Linear Algebra, Tata McGraw-hill edition.Delhi 2001年, 第69-80页

参见

外部链接

[1] Steven J. Leon. Linear Algebra With Applications. 培生教育. 2014: 第13页. ISBN 9781292025148.

[2] 第八章方程. 《九章算术》. 150bc. （原始内容存档于2009年4月19日）. 请检查|date=中的日期值 (帮助)

[3] Documenta Mathematica, Vol. Extra Volume: Optimization Stories (2012), 9-14. www.emis.de. [2022-12-02].

[princeton-4] Timothy Gowers; June Barrow-Green; Imre Leader. The Princeton Companion to Mathematics. Princeton University Press. 8 September 2008: 607. ISBN 978-0-691-11880-2.

[5] Althoen, Steven C.; McLaughlin, Renate, Gauss–Jordan reduction: a brief history, The American Mathematical Monthly (Mathematical Association of America), 1987, 94 (2): 130–142, ISSN 0002-9890, JSTOR 2322413, doi:10.2307/2322413

[6] Steven J. Leon. Linear Algebra With Applications. 培生教育. 2014: 第17页. ISBN 9781292025148.

[7] Atkinson, 1989年，第514页

[8] Golub and Van Loan, §3.4.6

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

查论编线性代数的相关概念
重要概念	标量向量向量空间向量子空间线性生成空间线性映射投影线性无关线性组合基标记列空间行空间零空间对偶空间正交特征值特征向量数量积内积空间点乘转置格拉姆-施密特正交化线性方程组克莱姆法则
矩阵	矩阵矩阵乘法矩阵分解行列式子式和余子式矩阵的秩克莱姆法则逆矩阵高斯消元法线性变换分块矩阵
数值线性代数	浮点数数值稳定性基础线性代数程序集稀疏矩阵