高斯消元法 也被叫做加减消元法，是线性代数中一个重要算法，可以把矩阵转化为行阶梯形矩阵。高斯消元法可用来方程组求解，求出矩阵的秩，计算行列式，以及求出可逆方阵的逆矩阵。

高斯消元

高斯消元是一种求解线性方程组的方法。所谓线性方程组，是由 $M$ 个 $N$ 元一次方程共同构成的。

线性方程组的所有系数可以写成一个 $M$ 行 $N$ 列的“系数矩阵”，再加上每个方程等号右侧的常数，可以写成一个 $M$ 行 $N+1$ 列的“增广矩阵” ，例如：

$$\left\{\begin{matrix} x_1+2x_2-x_3=-6\\ 2x_1+x_2-3x_3=-9\\ -x_1-x_2+2x_3=7 \end{matrix}\right. \Longrightarrow \begin{bmatrix} \begin{array}{lcr|r} 1 & 2 & -1 & -6 \\ 2 & 1 & -3 & -9 \\ -1 & -1 & 2 & 7 \end{array} \end{bmatrix}$$

消元法理论的核心-"初等行变换"

求解方程组的步骤可以概括成对“增广矩阵”的三类操作：

• 1.交换两行位置。（两方程互换，解不变；）
• 2.给某一行乘一个非零的数。（一方程乘以非零数 𝑘 ，解不变；）
• 3.把一行乘以非零的数，加到另一行。（一方程乘以数 𝑘 加上另一方程，解不变。）

对矩阵的这 $3$ 个操作就是“初等行变换”。

对矩阵初等行变换本质就是解方程消元的过程。

通过初等行变换把增广矩阵变为简化阶梯形矩阵形矩阵求解算法就是高斯消元法。

普通的高斯消元法，通过矩阵“初等行变换”，将矩阵转化为“阶梯型矩阵”（其系数矩阵被称为“上三角矩阵”），再从下往上带回方程组，得到每个未知量的解。

例如上述方程，通过变换得到“阶梯形矩阵”：

$$\begin{bmatrix} \begin{array}{lcr|r} 1 & 2 & -1 & -6 \\ 2 & 1 & -3 & -9 \\ -1 & -1 & 2 & 7 \end{array} \end{bmatrix} \Longrightarrow \begin{bmatrix} \begin{array}{lcr|r} 1 & 2 & -1 & -6 \\ 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 3 \end{array} \end{bmatrix}$$

再从下往上依次带回，得到“简化阶梯矩阵” （系数矩阵部分就是一个“对角矩阵”）

$$\begin{bmatrix} \begin{array}{lcr|r} 1 & 2 & -1 & -6 \\ 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 3 \end{array} \end{bmatrix} \Longrightarrow \begin{bmatrix} \begin{array}{lcr|r} 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & -2 \\ 0 & 0 & 1 & 3 \end{array} \end{bmatrix}$$

代码相对比较繁琐，实际对于第 $i$ 行对角位置 $(i,i)$ , 其中 $1\sim i-1$ 列都是 $0$ ，可以直接消掉 $1\sim i-1$ 行第 $i$ 列所有系数(不会影响前面对角线的值)，从而直接得到“对角矩阵”，这就是高斯-约旦消元法，改进了高斯消元法。

高斯-约旦消元法过程

依次从 $1$ 行处理到 第 $n$ 行 ，当前行记为 $r$

1. 选主元：依次枚举主元所在的列 $col:1 \to n$

2. 找主元最大的行：从当前行到最后一行，找到当前列绝对值最大的元素所在行 ，即当前行是 $r$, 枚举行 $i:r \to n$ , 寻找最大的 $a_{i,col}$ 所在的行，记为 $max$ 行；

3. 交换行：将当前行与最大行交换，即 交换第 r 行与第 max 行；

4. 归一化：将当前行除以主元，使主元变为 $1$ （这一步也可以最后再做，代码简洁，保证精度）

5. 消元：用当前行消去所有其他行（包括上面的行）的主元列元素 ，即枚举所有行 $i: 1 \to n ,i \ne r$ ,将第 $r$ 行乘以 $-\frac{a_{i,col}}{a_{r,col}}$ ，加入第 $j$ 列中。

6. 重复：对每一列重复上述过程

下面以前面方程组为例，模拟高斯-约旦消元法，注意归一化处理在最后一步做。

$$\begin{bmatrix} 1 & 2 & -1 & -6 \\ 2 & 1 & -3 & -9 \\ -1 & -1 & 2 & 7 \end{bmatrix} \underrightarrow{swap(r_1,r_2)} \begin{bmatrix} 2 & 1 & -3 & -9 \\ 1 & 2 & -1 & -6 \\ -1 & -1 & 2 & 7 \end{bmatrix}$$$$\underrightarrow{r_2-\frac{1}{2}r_1,r_3+\frac{1}{2}r_1} \begin{bmatrix} 2 & 1 & -3 & -9 \\ 0 & \frac{3}{2} & \frac{1}{2} & -\frac{3}{2} \\ 0 & -\frac{1}{2} & \frac{1}{2} & \frac{5}{2} \end{bmatrix} \underrightarrow{r_1-\frac{2}{3}r_2,r_3+\frac{1}{3}r_2} \begin{bmatrix} 2 & 0 & -\frac{10}{3} & -8 \\ 0 & \frac{3}{2} & \frac{1}{2} & -\frac{3}{2} \\ 0 & 0 & \frac{2}{3} & 2 \end{bmatrix}$$$$\underrightarrow{r_1+5r_3,r_2-\frac{3}{4}r_3} \begin{bmatrix} 2 & 0 & 0 & 2 \\ 0 & \frac{3}{2} & 0 & -3 \\ 0 & 0 & \frac{2}{3} & 2 \end{bmatrix} \Longrightarrow \begin{bmatrix} 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & -2 \\ 0 & 0 & 1 & 3 \end{bmatrix}$$

特殊情况 - 自由元

在高斯消元法过程中，当前主元这一列全是 $0$ 的情况，即 $j \in [1,n],a_{j,i}=0$ , 此时 $a_{j,i}*x_i$ ，无论 $x_i$ 取任何值，$x_i$ 对答案没有影响，也就是 $x_i$ 自由元。自由元的出现，方程可能无解，或者无穷组解，需要单独判断。

消元后，可能会出现 $0=d$ 的特殊情况，下面就其特殊性进行分类讨论。

若 $d$ 非零，说明方程之间有矛盾，即系数都为 $0$ ，常数不为 $0$ ，方程组无解。

若 $d=0$ ，系数全为 $0$ ，常数也为 $0$ ，有 $k$ 行是这种情形，说明自由元有 $k$ 个，可以取任意值，方程组有任意多组解。

若所有行系数不全为 $0$ ，即主元有 $n$ 个，说明方程组有唯一解。

模板题1：P3389 【模板】高斯消元法

使用高斯-约旦消元法，代码比较简洁。

时间复杂度 $O(n^3)$ , 空间复杂度 $O(n^2)$

• UPDATE 2025-12-8 : 代码进一步优化

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=110;
const double eps=1e-9;
int n;
double a[N][N];
//高斯约旦消元法
int guass()
{
    int r=1;   //当前处理行 r-1也就是当前矩阵的秩
    for(int col=1;col<=n;col++)  //依次处理矩阵主元所在的列
    {
        //第一步，寻找主元绝对值最大的行
        int max=r;
        for(int i=r+1;i<=n;i++)
            if(fabs(a[max][col])<fabs(a[i][col]))max=i;
        
        if(fabs(a[max][col])<eps)continue;  //存在自由元

        //第二步，将主元 最大的行 换到当前行中
        swap(a[r],a[max]);

        //第三步，利用当前行 将其他所有行 主元所在的列清空 （归一化处理最后再做）
        for(int i=1;i<=n;i++)
        {
            if(i==r)continue;
            double rate=a[i][col]/a[r][col];
            for(int j=col;j<=n+1;j++)
                a[i][j]-=rate*a[r][j];
        }
        r++;   //正常进行换到下一行
    }
    if(r<=n)return 0;   //唯一解 r-1 应该等于 n
    return 1;    // 矩阵的秩 r-1 =n ,存在唯一解  
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n+1;j++)cin>>a[i][j];
    
    if(guass()==0)cout<<"No Solution";  //存在自由元
    else
        for(int i=1;i<=n;i++)
            cout<< fixed << setprecision(2) << a[i][n+1]/a[i][i]<<"\n";  //最后再做归一化处理
    
    
    return 0;
}

模板题2：[SDOI2006]线性方程组

这道题需要详细讨论方程是否存在唯一解、无解、无穷解的情况。

先利用高斯-约旦消元法，将矩阵转换为“简化行阶梯矩阵”，接下来检测系数全为 $0$ 的行，如果第 $n+1$ 列常数出现非零，那么方程组不可能成立，即无解。

• UPDATE 2025-12-8 : 之前参考代码忽略了自由元所在的其他列也是可以当主元的，被 hack 掉了。这个版本消除了此漏洞，并且将所有 $0$ 行换到了最下面。结束后 $r-1$ 就是矩阵的秩。

#include<bits/stdc++.h>
using namespace std;
const int N=110;
double a[N][N],ans[N],eps=1e-9;
int n;
bool b[N];
int gauss()
{
    int r=1;  //当前处理的行 r-1 就是有效主元个数
	for(int col=1;col<=n;col++) //主元所在的列为 col
	{
        //第一步，寻找主元最大的行
		int max=r;
		for(int i=r+1;i<=n;i++)
			if( fabs(a[max][col])<fabs(a[i][col]))max=i;
			
		if(fabs(a[max][col])<eps)
            continue;  //存在自由元，r 不会变大
       
        // 第二步，将最大的一行换到当前处理行
		swap(a[r],a[max]);  
		
        // 第三步，将其他行 col 列清 0
		for(int i=1;i<=n;i++)
		{
			if(r==i)continue;   //跳过本身这一行
			double rate=a[i][col]/a[r][col];
			for(int j=col;j<=n+1;j++)
				a[i][j]-=rate*a[r][j];
		}
        r++;
	}
    // 如果存在自由元 ，从 r 到 n 行系数应该全部为 0 
	for(int i=r;i<=n;i++)
    {
        bool allzero=true;
        for(int j=1;j<=n;j++)
            if(fabs(a[i][j])>eps)
            {   allzero=false;
                break;
            }
        if(allzero && fabs(a[i][n+1])>eps)return -1 ;//无解
    }
    if(r<=n)return 0 ;  //无穷解
    return 1; //唯一解 矩阵的秩是 r-1 此时 r-1=n
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n+1;j++)
			cin>>a[i][j];
	int ret=gauss();
	if(ret==0)cout<<0;
	else if(ret==-1) cout<<-1;
	else for(int i=1;i<=n;i++)
			printf("x%d=%0.2lf\n",i,a[i][n+1]/a[i][i]);

	return 0;
}

---

更多应用请查看【例题】高斯消元法应用

---

学习完毕

{{ select(1) }}

• YES
• NO