消元法

先来看一下百度百科的定义：

消元法是指将许多关系式中的若干个元素通过有限次地变换，消去其中的某些元素，从而使问题获得解决的一种解题方法。

可能不好懂。

回想一下小学数学中解二元一次方程的方法

比如下面这个二元一次方程：

\[\begin{cases} x + y = 10\\ x - y = 6 \end{cases} \]

通过两式相加，可以得到

\[2x = 16 \]

进而解得

\[x=8 \]

把 \(x\) 代回就可以得到

\[y = 2 \]

发现，在解这个二元一次方程时，通过式子加减，我们把其中一个元 \(y\) 消掉，只剩下了 \(x\)，变成了我们可以直接得出解的形式。

这个解题方法就是消元法

高斯消元其实就是在模拟这个消元过程。

只不过元可能更多，式子可能更复杂，但好在这是计算机考虑的问题，与我们没有什么关系。

高斯消元

高斯-约旦消元法

与后面高斯消元法相比没有回带过程，实现起来也更加简单，精度方面也更加优秀

进行高斯消元后是一个三角矩阵，而高斯-约旦消元法的结果是一个对角线矩阵

举个例子：

求解下面这个方程组

规定从上到下三个式子分别是 \(A\), \(B\), \(C\)。

\[\begin{cases} 3x + 2y + z = 10 \\ 5x + y +6z = 25 \\ 2x + 3y + 4z = 20 \end{cases} \]

把它转化成矩阵形式

\[\begin{bmatrix} 3 & 2 & 1 & \mid & 10 \\ 5 & 1 & 6 & \mid & 25 \\ 2 & 3 & 4 & \mid & 20 \end{bmatrix} \]

左边是每个未知数的常数项，右边是该式结果，中间用一条竖线隔开

我们从第一列开始消元

找到第一列最大的一个，与第一行交换

\[\begin{bmatrix} 5 & 1 & 6 & \mid & 25 \\ 3 & 2 & 1 & \mid & 10 \\ 2 & 3 & 4 & \mid & 20 \end{bmatrix} \]

我们要将第一列的其他两项化为 \(0\)

\(B = B - \frac{3}{5}A\)

\(C = C - \frac{2}{5}A\)

然后变成这样：

\[\begin{bmatrix} 5 & 1 & 6 & \mid & 25 \\ 0 & \frac{7}{5} & -\frac{13}{5} & \mid & -5 \\ 0 & \frac{12}{5} & \frac{2}{5} & \mid & 5 \end{bmatrix} \]

然后在看第二列，把第二列系数最大的那个方程换到第二列。

\[\begin{bmatrix} 5 & 1 & 6 & \mid & 25 \\ 0 & \frac{12}{5} & \frac{2}{5} & \mid & 5 \\ 0 & \frac{7}{5} & -\frac{13}{5} & \mid & -5 \end{bmatrix} \]

继续进行消元操作，不过这次我们要把方程 \(A\) 的第二列的元也消掉

\(A = A - \frac{5}{12}B\)

\(C = C - \frac{7}{12}B\)

矩阵变为：

\[\begin{bmatrix} 5 & 0 & \frac{35}{6} & \mid & \frac{275}{12} \\ 0 & \frac{12}{5} & \frac{2}{5} & \mid & 5 \\ 0 & 0 & \frac{17}{6} & \mid & \frac{95}{12} \end{bmatrix} \]

继续对第三列进行相同操作，矩阵变为：

\[\begin{bmatrix} 5 & 0 & 0 & \mid & \frac{225}{34} \\ 0 & \frac{12}{5} & 0 & \mid & 5 \\ 0 & 0 & \frac{17}{6} & \mid & \frac{66}{17} \end{bmatrix} \]

到此消元结束，发现每个方程只剩下一个变量，直接解出来输出结果即可。

如果不懂的话可以看一下代码实现。

/*
Work by: Suzt_ilymics
Problem: P3389 【模板】高斯消元法
Knowledge: 高斯-约旦消元法 
Time: O(n^3)
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define LL long long
#define orz cout<<"lkp AK IOI!"<<endl

using namespace std;
const int MAXN = 105;
const int INF = 1e9+7;
const int mod = 1e9+7;

int n;
double a[MAXN][MAXN];

int read(){
    int s = 0, f = 0;
    char ch = getchar();
    while(!isdigit(ch))  f |= (ch == '-'), ch = getchar();
    while(isdigit(ch)) s = (s << 1) + (s << 3) + ch - '0' , ch = getchar();
    return f ? -s : s;
}

int main()
{
    n = read();
    for(int i = 1; i <= n; ++i) 
        for(int j = 1; j <= n + 1; ++j) 
            scanf("%lf", &a[i][j]); // 读入方程组 
    
    for(int i = 1; i <= n; ++i) {
        int Max = i; 
        for(int j = i + 1; j <= n; ++j) if(fabs(a[i][j]) > fabs(a[i][j])) Max = j; // 选出该列最大系数 
        for(int j = 1;j <= n + 1; ++j) swap(a[i][j], a[Max][j]);  // 交换这两行 
        if(!a[i][i]) { // 最大值等于 0 则说明该列都为 0，肯定无解 
            puts("No Solution");
            return 0;
        }
        for(int j = 1; j <= n; ++j) { // 对每一列进行加减消元 
            if(j != i) {
                double tmp = a[j][i] / a[i][i];
                for(int k = i + 1; k <= n + 1; ++k) a[j][k] -= a[i][k] * tmp;
            }
        }
    }
    for(int i = 1; i <= n; ++i) printf("%.2lf\n", a[i][n + 1] / a[i][i]);
    return 0;
}

高斯消元法

没写过。

实现起来与高斯-约旦类似，添了一个回带的过程

在这里粘一个 皎月半撒花 大佬的板子

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
double map[111][111];
double ans[111];
double eps=1e-7;
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n+1;j++)
            scanf("%lf",&map[i][j]);
    for(int i=1;i<=n;i++){
        int r=i;
        for(int j=i+1;j<=n;j++)
            if(fabs(map[r][i])<fabs(map[j][i]))
                r=j;//find_the_biggest_number_of_the_first_column（at present) 
        if(fabs(map[r][i])<eps){
            printf("No Solution");
            return 0;
        }
        if(i!=r)swap(map[i],map[r]);//对换一行或一列,属于找最大当前系数的其中一步。（这样就可以只处理当前行的系数啦！） 
        double div=map[i][i];
        for(int j=i;j<=n+1;j++)
            map[i][j]/=div;
        for(int j=i+1;j<=n;j++){
            div=map[j][i];
            for(int k=i;k<=n+1;k++)
                map[j][k]-=map[i][k]*div;
        }
    }
    ans[n]=map[n][n+1];
    for(int i=n-1;i>=1;i--){
        ans[i]=map[i][n+1];
        for(int j=i+1;j<=n;j++)
            ans[i]-=(map[i][j]*ans[j]);
    }//回带操作
    for(int i=1;i<=n;i++)
        printf("%.2lf\n",ans[i]);
}