高斯消元

高斯消元可以用于线性方程组求解或者行列式计算，求矩阵的逆等等，也算是比较基础的一个思想。

消元法

定义

消元法是将方程组中的一方程的未知数用含有另一未知数的代数式表示，并将其带入到另一方程中，这就消去了一未知数，得到一解；或将方程组中的一方程倍乘某个常数加到另外一方程中去，也可达到消去一未知数的目的。消元法主要用于二元一次方程组的求解。

举例：利用消元法求解二元一次线性方程组：

\[\left\{\begin{matrix}3x+2y=110\\x-y=10\end{matrix}\right.\]

我们很容易由二式得到：

\[x=y+10\]

我们把这个式子代入一式，然后得到：

\[3(y+10)+2y=110\]

展开得到：

\[5y+30=110\]

然后一式的未知数由两个变为了一个，我们可以解出：

\[y=16\]

然后代入一式或者二式就可以解出来 \(x\) 的值了。

消元法理论核心

两方程互换，解不变
一方程乘以非零数 \(k\)，解不变
一方程乘以数 \(k\) 加上另一方程，解不变（此时的 \(k\) 可以是 \(0\)）

高斯消元法思想概念

德国数学家高斯对消元法进行了思考分析，得出了如下结论：

在消元法中，参与计算和发生改变的是方程中各变量的系数；
各变量并未参与计算，且没有发生改变；
可以利用系数的位置表示变量，从而省略变量；
在计算中将变量简化省略，方程的解不变。

高斯消元五步法

增广矩阵行初等变换为行最简形
还原线性方程组
求解第一个变量
补充自由未知量
列表示方程组的通解

过程

我看到 OI Wiki 上写的太过复杂，所以我尽量用通俗易懂的语言来叙述。

例如我们需要解下面的线性方程组：

\[\left\{\begin{matrix}2x_{1}+5x_{3}+6x_{4}=9\\x_{3}+x_{4}=-4\\2x_{3}+2x_{4}=-8\end{matrix}\right.\]

增广矩阵初等变换为行最简形

最简形矩阵

定义形如下面矩阵 \(A\) 的矩阵被称为最简形矩阵。

\[A=\begin{bmatrix}1&0&5&6&9\\0&0&1&1&-4\\0&0&0&1&-8\end{bmatrix}\]

其判断的依据可以简记为是否能画出一条阶梯状的线将矩阵分为上下两部分，满足在其下面的元素都是 \(0\)，特别的，画出的线的上方的元素只能是 \(1\) 或 \(0\)。

增广矩阵是由方程组系数矩阵 \(A\) 与常数列 \(b\) 的并生成的新矩阵，即 \((A|b)\)，增广矩阵行初等变换化为最简形，省略了变量而用变量的系数位置来表示变量，增广矩阵中用竖线隔开了系数矩阵和常数列，相当于等于号。

上面的线性方程组可以变换为下面的形式。

\[\begin{bmatrix}\begin{array}{cccc|c}2&0&5&6&9\\0&0&1&1&-4\\0&0&2&2&-8\end{array}\end{bmatrix}\]

我们用第三行减去两倍的第二行，得到：

\[\begin{bmatrix}\begin{array}{cccc|c}2&0&5&6&9\\0&0&1&1&-4\\0&0&0&0&0\end{array}\end{bmatrix}\]

然后第一行除以 \(2\) 得到：

\[\begin{bmatrix}\begin{array}{cccc|c}1&0&2.5&3&4.5\\0&0&1&1&-4\\0&0&0&0&0\end{array}\end{bmatrix}\]

然后我们用第一行减去 \(2.5\) 倍的第二行

\[\begin{bmatrix}\begin{array}{cccc|c}1&0&0&0.5&14.5\\0&0&1&1&-4\\0&0&0&0&0\end{array}\end{bmatrix}\]

至此化为了最简形矩阵

还原线性方程组

\[\left\{\begin{matrix}x_{1}+0.5x_{4}=14.5\\x_{3}+x_{4}=-4\end{matrix}\right.\]

也就是把最简形矩阵重新书写成线性方程组的形式。

求解第一个变量

\[\left\{\begin{matrix}x_{1}=-0.5x_{4}+14.5\\x_{3}=-x_{4}-4\end{matrix}\right.\]

也就是将每一行第一个系数不为 \(0\) 的变量用其他变量表达出来，也就是使左边只有需要表达的变量且系数为 \(1\) ，然后其他的项移到右边。

补充自由未知量

\[\left\{\begin{matrix}x_{1}=-0.5x_{4}+14.5\\x_{2}=x_{2}\\x_{3}=-x_{4}-4\\x_{4}=x_{4}\end{matrix}\right.\]

第三步中得到的方程式只有 \(x_{1}\) 和 \(x_{3}\) 的，说明其他的变量都是不受其他变量约束的，也就是可以取任意值。所以只能是自己等于自己。

列表示方程组的通解

\[\begin{bmatrix}x_{1}\\x_{2}\\x_{3}\\x_{4}\end{bmatrix}=\begin{bmatrix}0\\1\\0\\0\end{bmatrix}x_{2}+\begin{bmatrix}-0.5\\0\\-1\\1\end{bmatrix}x_{4}+\begin{bmatrix}14.5\\0\\-4\\0\end{bmatrix}=\begin{bmatrix}0\\1\\0\\0\end{bmatrix}c_{1}+\begin{bmatrix}-0.5\\0\\-1\\1\end{bmatrix}c_{2}+\begin{bmatrix}14.5\\0\\-4\\0\end{bmatrix}\]

其中的 \(c_{1},c_{2}\) 为任意常数。

由于 \(x_{2}\) 和 \(x_{4}\) 是自由未知量，所以可以随便取值，所以在解的右边令二者分别为任意常数即完成对方程组的求解。

其实可以看做化为一个上三角矩阵然后从下往上依次回代的过程。

我们就是使每一行的对角线上的元素都是 \(1\) 这样刚好对应了每一个变量为 \(1\) 到了最后一行的时候，会获得一个变量的值，然后依次往上回代即可。最后即可求出所有变量的值。

在处理矩阵的时候，我们一般用到以下几种操作：

交换两行
系数化为 \(1\)
某行加上或减去另一行的 \(k\) 倍

首先我们确定第 \(i\) 行选定 \(x_{i}\) 为主元，然后往下找第 \(i\) 列不是零的数，然后交换这两行，将交换后的第 \(i\) 行主元系数化为 \(1\)

然后往下遍历，下面行只要第 \(i\) 列还有值，就加上减去第 \(i\) 行的 \(k\) 倍使其系数化为 \(0\)，如此反复即可。

P3389【模板】高斯消元法 - 洛谷

参考代码：

#include<bits/stdc++.h>
#define DB double
#define N 110 
using namespace std;
int n;
DB a[N][N],x[N],eps=0.000000001;
inline int work()
{
    for(int i=1;i<=n;i++)
    {
        int r=i;//当前变量 
        for(int k=i;k<=n;k++)
          if(fabs(a[k][i])>eps)//大于0 
            {r=k;break;}//存下来 
        if(r!=i)swap(a[r],a[i]);//只要不是相等的就交换行 
        if(fabs(a[i][i])<eps)return 1;//如果当前的系数是0则此变量可以取任意值，无数个解 
        for(int j=n+1;j>=i;j--)//系数化为1 
          a[i][j]/=a[i][i];//到最后自己除自己，一定是1 
        for(int k=i+1;k<=n;k++)//遍历每一行 
          for(int j=n+1;j>=i;j--)//遍历后面每一列 
            a[k][j]-=a[k][i]*a[i][j];//将此列的i变为0 
    }
    for(int i=n-1;i;i--)//遍历每一行 
      for(int j=i+1;j<=n;j++)//遍历每一列 
        a[i][n+1]-=a[i][j]*a[j][n+1];//求解第i个变量的值 
    return 0;//返回有解 
}
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
      for(int j=1;j<=n+1;j++)
        cin>>a[i][j];
    int flag=work();
    if(flag!=0)
    {
        cout<<"No Solution"<<endl;
        return 0;
    }
    for(int i=1;i<=n;i++)
      printf("%.2lf\n",a[i][n+1]);
    return 0;
}

高斯约旦消元法

他和普通的高斯消元的区别就是这个最后得到的矩阵是只有对角线是有值的，其余元素为 \(0\)。

最后得到的矩阵就像下面这样：

\[\begin{bmatrix}\begin{array}{ccc|c}a_{1}&\dots&0&c_{1}\\\vdots&\ddots&\vdots&\vdots\\0&\dots&a_{n}&c_{n}\end{array}\end{bmatrix}\]

其中 \(c_{1}\) 到 \(c_{n}\) 为常数。

这样做的好处就是让每一个变量都直接乘上自己的系数得到一个值，这样就便于计算了。

最后直接循环一下计算即可。

当然弊端就是无法判断无解是没有解还是无数个解。

参考代码

#include<bits/stdc++.h>
#define DB double
#define N 1100
using namespace std;
int n,pl;
DB a[N][N];
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
      for(int j=1;j<=n+1;j++)
        cin>>a[i][j];
    for(int i=1;i<=n;i++)
    {
        pl=i;
        for(int j=i;j<=n;j++)
          if(a[j][i]>a[pl][i])pl=j;
        if(a[pl][i]==0){cout<<"No Solution"<<endl;return 0;}
        swap(a[i],a[pl]);
        DB k=a[i][i];
        for(int j=1;j<=n+1;j++)
          a[i][j]=a[i][j]/k;
        for(int j=1;j<=n;j++)
        {
            if(i!=j)
            {
                DB kk=a[j][i];
                for(int o=1;o<=n+1;o++)
                a[j][o]=a[j][o]-kk*a[i][o];
            }
        }
    }
    for(int i=1;i<=n;i++)
      printf("%.2lf\n",a[i][n+1]); 
    return 0;
}

Aisaka_Taiga

浅谈高斯消元法