数学知识（三）

一、高斯消元

高斯消元

高斯消元是用来求解多元线性方程组的方法，时间复杂度为O(n³)。

初等行列变换

1. 把某一行乘以一个非0的数
2. 交换某两行
3. 将某行的若干倍加到零一行

【1】处理后形成阶梯型则有解

【2】不是阶梯型

左边均为0，右边非0，无解
左右均为0，有解
算法步骤
枚举每一列寻找绝对值最大的一行（使主元不为0）
将改行交换至最上方
将该行第一个数变为1
将所有行当前列全部消为0
固定当前行，重复此流程

int gauss(){
    int r,c;
    for(r=c=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+1){
        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[i][j]*a[j][n+1];
    return 0;
}

高斯-约旦消元
将稀疏矩阵变成主对角矩阵，再除以主元
主元所在行不变，主元所在列变为0