学习笔记——高斯消元

高斯消元是用来解决N元一次方程的神奇算法

在手搓多元一次方程的时候，我们会用到消元法和换元法，所以高斯消元也是这样滴

我们可以把N元M项方程写成一个矩阵，如下

(left{egin{matrix} x_1&+&x_2&+&x_3&=&6\ x_1&+&2x_2&+&2x_3&=&11\ x_1&+&4x_2&-&x_3&=&6\ end{matrix} ight.)

变为

(egin{bmatrix} 1&1&1&6\ 1&2&2&11\ 1&4&-1&6 end{bmatrix})

---

初等行变换

矩阵以每一行为单位，支持以下运算

1.给其中一行乘上一个非0常数

2.给其中一行加上另一行

3.交换某两行的位置

其正确性类比于手搓消元法qwq

---

对于上面的例子，我们可以通过初等行变换，先考虑(x_1)，选择一个(x_1)系数不为0的行移动至第一行固定，将其余行的第一项全部消掉

如下

(egin{bmatrix} 1&1&1&6\ 0&1&1&5\ 0&3&-2&0 end{bmatrix})

然后从第二行开始找一个(x_2)系数不为0的固定在第二行，消掉其他行的第二项，以此类推。

(egin{bmatrix} 1&0&0&1\ 0&1&1&5\ 0&0&-5&-15 end{bmatrix})

(egin{bmatrix} 1&0&0&1\ 0&1&0&2\ 0&0&-5&-15\ end{bmatrix})

（解出(x_1)=1 , (x_2)=2 , (x_3)=3）

除了最右一列常数项，左边部分构成了对角矩阵，就可以得出xi了

但是，对于更一般的方程，可能会有其他情况，比如下面这个矩阵

多解

(egin{bmatrix} 1&0&0&1\ 0&0&1&1\ 0&0&0&0 end{bmatrix})

可以发现(x_2)项系数为0，为自由元(即0*(x_2)=0恒成立)，所以有无数解，(x_1),(x_3)为主元，有解。

无解

(egin{bmatrix} 0&1 end{bmatrix})

恩0*(x_1)=1无解

---

模板：高斯消元法

第i轮找第i列不为0的行，若找不到则为无解

(Code):

#include<bits/stdc++.h>
#define N 105
#define eps (1e-8)
#define double long double
using namespace std;
double c[N][N];
int n;


int main()
{
    cin>>n;
    for(int i=1;i<=n;++i)
    for(int j=1;j<=n+1;++j)
    cin>>c[i][j];
    for(int i=1;i<=n;++i)
    {
        bool ok=1;
        for(int j=i;j<=n;++j)//这个循环的实际含义是，找到一个未被使用的方程，满足第i项不为0
        {
            if(fabs(c[j][i])>eps)//满足一定精度（不为0）
            {
                for(int k=1;k<=n+1;++k) swap(c[j][k],c[i][k]);
                ok=0;
            }
        }
        if(ok) {cout<<"No Solution"<<endl;goto u;}//这一项没有一行有系数
        for(int j=1;j<=n;++j)
        {
            if(i==j) continue;
            double rate=c[j][i]/c[i][i];//按照这一项的比例来消掉这一项
            for(int k=1;k<=n+1;++k) c[j][k]-=rate*c[i][k];//同时这一行减去每一项对应值
        }
    }
    for(int i=1;i<=n;++i) cout<<fixed<<setprecision(2)<<c[i][n+1]/c[i][i]<<endl;//对角矩阵输出答案
    u:;
    return 0;
}