高斯消元法

$$高斯消元法可以在O(n^{3})的时间复杂度下求解多元线性方程组$$ $$\begin{equation} \left\{ \begin{aligned} a_{11}x_{1}+a_{12}x_{2}+...+a_{1n}x_{n}=b_{1}\\ a_{11}x_{1}+a_{12}x_{2}+...+a_{1n}x_{n}=b_{2}\\ ....\\ a_{n1}x_{1}+a_{n2}x_{2}+...+a_{nn}x_{n}=b_{n} \end{aligned} \right. \end{equation}$$

根据线性代数的知识，我们了解到，方程组的解一共有三种情况：

$$\begin{equation} \left\{ \begin{aligned} 1.无解\\ 2.无穷解\\ 3.有唯一解\\ \end{aligned} \right. \end{equation}$$

可以通过其增广矩阵来解方程组：

$$\left [ \begin{array}{c:c} \begin{matrix} a_{11}&a_{12}&...a_{1n}\\ a_{21}&a_{22}&...a_{2n}\\ ...\\ a_{n1}&a_{n2}&...a_{nn}\\ \end{matrix}& \begin{matrix} b_{1}\\ b_{2}\\ ...\\ b_{n}\\ \end{matrix} \end{array} \right ]$$

通过初等变换转换为上三角的形式：

$$\begin{equation} \left\{ \begin{aligned} a_{11}x_{1}+a_{12}x_{2}+...+a_{1n}x_{n}=b_{1}\\ a_{12}x_{2}+...+a_{1n}x_{n}=b_{2}\\ ....\\ a_{nn}x_{n}=b_{n} \end{aligned} \right. \end{equation}$$

对应增广矩阵为;

$$\left [ \begin{array}{c:c} \begin{matrix} a_{11}&a_{12}&...a_{1n}\\ 0&a_{22}&...a_{2n}\\ ...\\ 0&0&...a_{nn}\\ \end{matrix}& \begin{matrix} b_{1}\\ b_{2}\\ ...\\ b_{n}\\ \end{matrix} \end{array} \right ]$$

高斯消元思路

枚举每一列：

• 找到绝对值最大的一行
• 将这一行换到最上面去
• 将该行的第c个数变成1
• 用第一行将下面所有行的第c列消成0

int gauss(){
    int c,r;
    for(c=1,r=1;c<=n;c++){
        int t=r;
        //第一步找到最大的数
        for(int i=r;i<=n;i++)
            if(fabs(a[i][c])>fabs(a[t][c]))
                t=i;
        
        //第二步符合条件的就交换到第一行
        if(fabs(a[t][c])<eps) continue;
        for(int i=c;i<=n+1;i++) swap(a[r][i],a[t][i]);
        
        //第三步，逐列单位化
        for(int i=n+1;i>=c;i--) a[r][i]/=a[r][c];
        
        //逐行减去
        for(int i=r+1;i<=n;i++)
            if(fabs(a[i][c])>eps)
                for(int j=n+1;j>=c;j--)
                    a[i][j]-=a[i][c]*a[r][j];
        r++;
    }
    if(r<=n){
        for(int i=r;i<=n;i++) //遍历每一行
            if(fabs(a[i][n+1])>eps) return 2;
        return 1;
    }
    for(int i=n-1;i>=1;i--)  //从最后一行开始
        for(int j=i+1;j<=n;j++) //从下一行开始
            a[i][n+1]-=a[j][n+1]*a[i][j];
    return 0;
}