高斯消元学习笔记

· · 个人记录

高斯消元，是一种求解线性方程组的办法（虽然我感觉好麻烦，但毕竟电脑的思维不能跟我们相提并论）

首先，我们可以把 n 个方程组的系数列出来，类似于一个矩阵

例如：

& x_1+2x_2-x_3=-6\\ & 2x_1+x_2-3x_3=-9\\ & -x_1-x_2+2x_3=7 \end{cases} \Rightarrow \begin{bmatrix} 1 & 2 & -1 & -6\\ 2 & 1 & -3 & -9\\ -1 & -1 & 2 & 7 \end{bmatrix}

初等行列变换：（就是高斯消元的几种方式）

  1. 用一个非零整数乘以某一行

  2. 将其中的一行整数加到其他行上

  3. 交换两行的位置

算法步骤：

  1. 枚举每一列 i ，也就是第 i 个未知数

  2. 运用初等行列变换 1 ，将第 i 行第 i 位变成 1

  3. 运用初等行列变换 2 ，将其他行第 i 位变成 0

举例：

1 & 2 & -1 & -6\\ 2 & 1 & -3 & -9\\ -1 & -1 & 2 & 7 \end{bmatrix} \Rightarrow 2.\begin{bmatrix} 1 & 2 & -1 & -6\\ 2 & 1 & -3 & -9\\ -1 & -1 & 2 & 7 \end{bmatrix} \Rightarrow 3.\begin{bmatrix} 1 & 2 & -1 & -6\\ 0 & 1 & 1/3 & -1\\ 0 & 1 & 1 & 1 \end{bmatrix} 1 & 2 & -1 & -6\\ 0 & 1 & 1/3 & -1\\ 0 & 1 & 1 & 1 \end{bmatrix} \Rightarrow 2.\begin{bmatrix} 1 & 2 & -1 & -6\\ 0 & 1 & 1/3 & -1\\ 0 & 1 & 1 & 1 \end{bmatrix} \Rightarrow 3.\begin{bmatrix} 1 & 0 & -5/3 & -4\\ 0 & 1 & 1/3 & -1\\ 0 & 0 & 2/3 & 2 \end{bmatrix} 1 & 0 & -5/3 & -4\\ 0 & 1 & 1/3 & -1\\ 0 & 0 & 2/3 & 2 \end{bmatrix} \Rightarrow 2.\begin{bmatrix} 1 & 0 & -5/3 & -4\\ 0 & 1 & 1/3 & -1\\ 0 & 0 & 1 & 3 \end{bmatrix} \Rightarrow 3.\begin{bmatrix} 1 & 0 & 0 & 1\\ 0 & 1 & 0 & -2\\ 0 & 0 & 1 & 3 \end{bmatrix}

最后就求解完毕了

注意事项：

  1. 若出现 \begin{bmatrix} ... & ... & ... & ...\\ 0 & ... & 0 & k(k \in \mathbb N_+)\\ ... & ... & ... & ...\end{bmatrix} 的情况，则显然方程组无解

  2. 若出现 k 个\begin{bmatrix} 0 & ... & 0 & 0\end{bmatrix} 的情况，则方程组有无数个解（前提不满足 1），且主元有 n-k 个，自由元有 k 个

代码实现中会遇到一些问题，需要酌情调整，Gauss消元部分代码如下

void gauss()
{
    for(int i=1;i<=n;i++)
    {
        int maax=i;
        for(int j=i+1;j<=n;j++) 
        if(fabs(t[j].a[i])>fabs(t[maax].a[i])) maax=j; //fabs为浮点数绝对值，找出当前主元最大的系数
        swap(t[i],t[maax]);
        if(!t[i].a[i]) //最大系数为0，显然无解或无唯一解
        {
            printf("No Solution\n");
            exit(0);
        }
        double tur=t[i].a[i];
        for(int j=1;j<=n+1;j++) t[i].a[j]/=tur;//第二步
        for(int j=1;j<=n;j++)
        {
            if(j==i) continue;
            tur=t[j].a[i];
            for(int k=1;k<=n+1;k++) t[j].a[k]-=tur*t[i].a[k];//第三步
        } 
    }
}

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

例题：

[SDOI2006]线性方程组

[JSOI2008]球形空间产生器

当然上述讲的高斯消元只是单纯的解线性方程，高斯消元还有很多变式。一般来说，高斯消元不会单独出题，常常会和其他知识点一起捆绑出题

异或高斯消元： [JSOI2012]始祖鸟 （题解）