高斯消元法(含异或方程组求解）

落日映苍穹つ 2022-05-15 10:52 276阅读 0赞

*  # 高斯消元法 #

--------------------

*  ## 梗概： ##

**高斯消元法**（英语：Gaussian Elimination），是[线性代数][Link 1]中的一个[算法][Link 2]，可用来为[线性方程组求解][Link 3]，求出[矩阵的秩][Link 4]，以及求出可逆[方阵][Link 5]的[逆矩阵][Link 6]。当用于一个[矩阵][Link 7]时，高斯消元法会产生出一个**[行梯阵式][Link 8]**。

*  ## 算法： ##

### 思想： ###

通过逐行消去未知数将方程组化简成**上三角形式（*理想，有唯一解情况下*）**，然后由后（**最简的代数式，有唯一解则类型为Xi=val**）往前代入方程组，最终得解。

### 举个栗子（增广矩阵）： ###

![\\begin\{pmatrix\} 2 & 1 & -1 & 8 \\\\ -3 & -1 & 2 & -11 \\\\ -2 & 1 & 2 & -3 \\end\{pmatrix\}][begin_pmatrix_ 2 _ 1 _ -1 _ 8 _ -3 _ -1 _ 2 _ -11 _ -2 _ 1 _ 2 _ -3 _end_pmatrix] ![\\begin\{pmatrix\} 2 & 1 & -1 & 8 \\\\ 0 & \\frac\{1\}\{2\} & \\frac\{1\}\{2\} & 1 \\\\ 0 & 0 & -1 & 1 \\end\{pmatrix\}][begin_pmatrix_ 2 _ 1 _ -1 _ 8 _ 0 _ _frac_1_2_ _ _frac_1_2_ _ 1 _ 0 _ 0 _ -1 _ 1 _end_pmatrix] ![\\begin\{pmatrix\} 1 & 0 & 0 & 2 \\\\ 0 & 1 & 0 & 3 \\\\ 0 & 0 & 1 & -1 \\end\{pmatrix\}][begin_pmatrix_ 1 _ 0 _ 0 _ 2 _ 0 _ 1 _ 0 _ 3 _ 0 _ 0 _ 1 _ -1 _end_pmatrix]

**栗子为理想状况有唯一解**

*  ## 解情况讨论： ##

### 对于非齐次线性方程组： ###

**唯一解：**矩阵的秩（等价于矩阵化阶梯后非零行数）r = n（未知量个数）

**无穷多解：**n != r

**无解：**出现（0 0 0 0 0 0 a）a != 0

**自由变元个数 = n - r**

### 对于齐次线性方程组： ###

**唯一解（*仅有0解*）**：**r = n**

**有非零解（无穷多个）：r < n**

***当齐次线性方程组方程个数<未知量个数，一定有非零解***

***当齐次线性方程组方程个数=未知量个数，有非零解充要|A|=0***

*  ## 普通方程组高斯消元模板： ##

#include<bits/stdc++.h>
    using namespace std;
    #define MAX_SIZE 1048
    int Matrix[MAX_SIZE][MAX_SIZE];
    int Free_x[MAX_SIZE]; //自由变元
    int X_Ans[MAX_SIZE]; //解集
    int Free_num=0;  //自由变元数
    int gcd(int a,int b)
    {
        return b==0? a : gcd(b,a%b);
    }
    int lcm(int a,int b)    //最小公倍数
    {
        return a/gcd(a,b)*b;
    }
    
    int Guass(int Row,int Column) //系数矩阵的行，列
    {
        int row=0,col=0,max_r;
        for(row=0;row<Row&&col<Column;row++,col++)
        {
            max_r=row;
            for(int i=row+1;i<Row;i++)    //找出当前列的最大值
                if(abs(Matrix[i][col])>abs(Matrix[max_r][col]))
                    max_r=i;
            if(Matrix[max_r][col]==0)   //最大值为0，等价有自由元，记录
            {
                row--;
                Free_x[++Free_num]=col+1;
                continue;
            }
            if(max_r!=row)   //将最大值换到当前行
                for(int i=col;i<Column+1;i++)
                    swap(Matrix[row][i],Matrix[max_r][i]);
            for(int i=row+1;i<Row;i++)  //消元
            {
                if(Matrix[i][col]!=0)
                {
                    int LCM=lcm(abs(Matrix[i][col]),abs(Matrix[row][col]));
                    int ta=LCM/abs(Matrix[i][col]);
                    int tb=LCM/abs(Matrix[row][col]);
                    if(Matrix[i][col]*Matrix[row][col]<0)//异号由减变加
                        tb=-tb;
                    for(int j=col;j<Column+1;j++)
                        Matrix[i][j]=Matrix[i][j]*ta-Matrix[row][j]*tb;
                }
            }
        }
        //row跳出时表示矩阵非零行数
        
        for(int i=row;i<Row;i++)  //无解
            if(Matrix[i][Column]!=0)
                return -1;
    
        if(row<Column)   //无穷多解，返回自由变元数
            return Column-row;
            
            
        for(int i=Column-1;i>=0;i--)  //唯一解
        {
            int temp=Matrix[i][Column];
            for(int j=i+1;j<Column;j++)
                if(Matrix[i][j]!=0)
                    temp-=Matrix[i][j]*X_Ans[j];
            X_Ans[i]=temp/Matrix[i][i];
        }
        return 0;
    }

*  ## 异或方程组高斯消元模板： ##

#include<bits/stdc++.h>
    using namespace std;
    #define MAX_SIZE 350
    #define ll long long
    ll Matrix[MAX_SIZE][MAX_SIZE];
    ll Free_x[MAX_SIZE];   //自由变元
    ll X_Ans[MAX_SIZE];  //解集 
    ll Free_num=0;  //自由变元数
    
    ll Guass(ll Row,ll Column)  //系数矩阵的行和列
    {
        ll row=0,col=0,max_r;
        for(row=0;row<Row&&col<Column;row++,col++)
        {
            max_r=row;
            for(ll i=row+1;i<Row;i++)   //找出当前列最大值
                if(abs(Matrix[i][col])>abs(Matrix[max_r][col]))
                    max_r=i;
            if(Matrix[max_r][col]==0)  //记录自由变元
            {
                row--;
                Free_x[Free_num++]=col+1;
                continue;
            }
            if(max_r!=row)  //交换
                for(ll i=col;i<Column+1;i++)
                    swap(Matrix[row][i],Matrix[max_r][i]);
            for(ll i=row+1;i<Row;i++)   //消元
            {
                if(Matrix[i][col]!=0)
                {
                    for(ll j=col;j<Column+1;j++)
                        Matrix[i][j]^=Matrix[row][j];
                }
            }
        }
        for(ll i=row;i<Row;i++)   //无解
            if(Matrix[i][Column]!=0)
                return -1;
    
        if(row<Column)   //无穷多解
            return Column-row;
        
        //唯一解
        for(ll i=Column-1;i>=0;i--)
        {
            X_Ans[i]=Matrix[i][Column];
            for(ll j=i+1;j<Column;j++)
               X_Ans[i]^=(Matrix[i][j]&&X_Ans[j]);
        }
        return 0;
    }

[Link 1]: https://zh.wikipedia.org/wiki/%E7%BA%BF%E6%80%A7%E4%BB%A3%E6%95%B0
[Link 2]: https://zh.wikipedia.org/wiki/%E7%AE%97%E6%B3%95
[Link 3]: https://zh.wikipedia.org/wiki/%E7%BA%BF%E6%80%A7%E6%96%B9%E7%A8%8B%E7%BB%84%E6%B1%82%E8%A7%A3
[Link 4]: https://zh.wikipedia.org/wiki/%E7%9F%A9%E9%99%A3%E7%9A%84%E7%A7%A9
[Link 5]: https://zh.wikipedia.org/wiki/%E6%96%B9%E5%9D%97%E7%9F%A9%E9%98%B5
[Link 6]: https://zh.wikipedia.org/wiki/%E9%80%86%E7%9F%A9%E9%99%A3
[Link 7]: https://zh.wikipedia.org/wiki/%E7%9F%A9%E9%99%A3
[Link 8]: https://zh.wikipedia.org/wiki/%E8%A1%8C%E6%A2%AF%E9%99%A3%E5%BC%8F
[begin_pmatrix_ 2 _ 1 _ -1 _ 8 _ -3 _ -1 _ 2 _ -11 _ -2 _ 1 _ 2 _ -3 _end_pmatrix]: https://wikimedia.org/api/rest_v1/media/math/render/svg/6439f0377fedfd7346e434d2a6173a8cfa5c1425
[begin_pmatrix_ 2 _ 1 _ -1 _ 8 _ 0 _ _frac_1_2_ _ _frac_1_2_ _ 1 _ 0 _ 0 _ -1 _ 1 _end_pmatrix]: https://wikimedia.org/api/rest_v1/media/math/render/svg/3eb55a6453b4b4b4aad1854b7c64cb401d9f93a2
[begin_pmatrix_ 1 _ 0 _ 0 _ 2 _ 0 _ 1 _ 0 _ 3 _ 0 _ 0 _ 1 _ -1 _end_pmatrix]: https://wikimedia.org/api/rest_v1/media/math/render/svg/96761bfc21f1898e3b47cae616d9779251d356db