高斯消元法和高斯-约旦消元法都是用来解形如
的方程的解的。
两个算法的比较
| 高斯消元法 | 高斯-约旦消元法 | |
|---|---|---|
| 有无回代 | 有 | 无 |
| 可否判无解和无穷解 | 可 | 不可 |
也就是说，普通的高斯消元法需要回代，代码比较繁琐，但可以分辨无解和无穷解；而高斯-约旦消元法则不需要回代，代码较简洁 （其实都挺简洁的） 但在它眼里无解和无穷解莫得区别。
前置芝士
都是七下数学书里的东西~
代入消元法
简称代入法
比如说，我们有方程组(left{egin{matrix}
ax+by=c \
y=dx+e \
end{matrix}
ight.)，其中 (a,b,c,d,e) 都是常数。那么，我们就可以把 (dx+e) 代入到第一个方程，得到方程 (ax+b(dx+e)=c)，然后求解。
多元一次方程组同理
加减消元法
简称加减法
又比如说，我们有另一个方程组(left{egin{matrix}
ax+by=c \
ax+dy=e \
end{matrix}
ight.)，(a,b,c,d,e)依然都是常数。那么，我们就可以把上式减下式（或下式减上式）得到方程 (by-dy=c-e)，然后求解。
又或者，再拿出来一个方程组(left{egin{matrix}
ax+by=c \
-ax+dy=e
end{matrix}
ight.)，(a,b,c,d,e)都是常数，那么，我们就可以把上式加下式，得到方程 (by+dy=c+e)，然后求解。
多元一次方程组同理
普通高斯消元法
原理
以一个三元一次方程组为例。
我们以 (x,y,z) 的顺序一个个消，先消 (x)。
首先我们随便拎一个方程出（一般拎要消的元的系数的绝对值最大的那个方程，这样可以减小精度损失（然鹅我并不知道为什么QwQ））：
我们要保留 (5x)，然后把另外的方程中的 (x) 的系数变为 (0)。
使用加减法。
先拿①式减②式（我们拎出来的那个） ( imes frac{3}{5})（这样才能消去 (x)）：
得到
再把这个方程作为新的①式。
然后再以同样的方法消③式，得
接着，再消 (y)，拎出③式，然后减一减（②式不用减），得
这时，我们发现①式只剩下 (z) 了，于是我们可以解出
然后代入③式，就可以解得
再把它们代入②式，解得
形式化过程
上面的过程是不是显得杂乱无章？
那么让我们把他形式化。
先找到 (x) 的系数的绝对值最大的方程，放到最前面
用它消掉下面的式子的 (x)
解的过程中如果拎出来的式子要消的元为 (0)，则无解或有无穷解（因为拎出来的方程的元的系数的绝对值已经最大了还是 (0)，所以其他的也就都是 (0) 了（感性理解下QwQ？））
然后再找到剩下的方程中 (y) 的系数的绝对值最大的那个，提上来
然后消掉它下面的式子的 (y)
然后一步步代入，解方程。
最后这一步我们把它叫做回代
代码实现
代码实现又有些不同。
上面的介绍中是在最后才把系数化为 (1) 的，但实际上，我们在选好方程的时候，就可以把系数化为 (1) 了，这样还可以减少码量。
//n表示未知数的数量
//a[i][j]代表第i个方程中第j个未知数的系数（其实和开头给出的格式一样啦~），特殊的，a[i][n+1]表示等式的右边
for(int i=1;i<=n;i++)
{
int res=i;
for(int k=i+1;k<=n;k++)
if(Abs(a[k][i])>Abs(a[res][i])) res=k;
for(int j=1;j<=n+1;j++) swap(a[i][j],a[res][j]);
if(a[i][i]==0){puts("No Solution");return 0;}
for(int j=i+1;j<=n+1;j++) a[i][j]/=a[i][i];
a[i][i]=1;
for(int k=i+1;k<=n;k++)
{
for(int j=i+1;j<=n+1;j++) a[k][j]-=a[k][i]*a[i][j];
a[k][i]=0;
}
}
for(int i=n-1;i>=1;i--)
for(int k=i+1;k<=n;k++)
a[i][n+1]-=a[i][k]*a[k][n+1];
判无解还是无穷解
在回代完后扫一遍，如果遇到 (a_{i,i}=0) 而 (a_{i,n+1}=0) 则有无穷解，如果遇到 (a_{i,i}=0) 而 (a_{i,n+1}
ot= 0) 则无解。
注意，如果一个方程无解则整个方程组都无解，所以要先判无解再判无穷解。
不过好像还是会被某些毒瘤数据卡掉的说
所以要打压这种毒瘤题！
高斯-约旦消元法
原理
还是这个方程组为例。
我们也保留要消的元的系数绝对值最大的那个方程，然后排下顺序就是
（注意本来 (z) 系数最大应该是 (5x+y+6z=25) 的，但是他被 (x) 抢走了）
我们先消 (x)。
首先我们把选出的方程 (5x+y+6z=25) 的 (x) 的系数化为 (1)：
然后呢，把所有的方程都与它相减使其 (x) 的系数变为 (1)，也是拿一个式子减这个式子乘多少多少，就不细讲了：
然后消 (y)。
注意除了选择的那个方程，要把其他所有的方程的 (y) 的系数都变成 (0) 哦。
最后消 (z)：
于是就能得到答案：
所以和普通高斯消元比起来，高斯-约旦消元真的方便好多
代码实现
然鹅实现起来好像差不多（（（
//n表示未知数的数量
//a[i][j]代表第i个方程中第j个未知数的系数（其实和开头给出的格式一样啦~），特殊的，a[i][n+1]表示等式的右边
for(int i=1;i<=n;i++)
{
int res=i;
for(int k=i+1;k<=n;k++)
if(Abs(a[k][i])>Abs(a[res][i])) res=k;
for(int j=1;j<=n+1;j++) swap(a[i][j],a[res][j]);
if(a[i][i]==0){puts("No Solution");return 0;}
for(int j=i+1;j<=n+1;j++) a[i][j]/=a[i][i];
a[i][i]=1;
for(int k=1;k<=n;k++)
if(k!=i)
{
for(int j=i+1;j<=n+1;j++) a[k][j]-=a[k][i]*a[i][j];
a[k][i]=0;
}
}