线性方程组求解 [笔记]

资料

线性方程组 [Wiki]
https://zh.wikipedia.org/wiki/%E7%BA%BF%E6%80%A7%E6%96%B9%E7%A8%8B%E7%BB%84
高斯消元法 [Wiki]
https://zh.wikipedia.org/wiki/%E9%AB%98%E6%96%AF%E6%B6%88%E5%8E%BB%E6%B3%95
一般线性方程组解的结构
http://202.113.29.3/nankaisource/mathhands/linear%20algebra/s0504/s050402/t0504020001.htm
线性方程组求解教程
http://math.fudan.edu.cn/gdsx/JIAOAN/%E7%BA%BF%E6%80%A7%E6%96%B9%E7%A8%8B%E7%BB%84.pdf
浅谈异或方程组
https://www.zybuluo.com/Kurunie/note/118965
kuangbin的高斯消元模板
http://www.cnblogs.com/kuangbin/archive/2012/09/01/2667044.html

以上是学习的相关资料，自己就只贴个不完整的高斯消元模板

实数方程组求解

//实数线性方程组高斯消元求解
//齐次和非齐次都可解
double a[N][M+1];
double eps = 1e-8;
int gauss(int n, int m){
    //n个方程, m个变元, 增广矩阵的列数为m+1
    //我们只需要处理前m列即可
    int row,col;
    for (row=0,col=0;row<n&&col<m;row++,col++){
        //当前处理第col列, 第row行
        int p_row = row; //p_row 记录当前列元素绝对值最大的行, 做为主元行
        for (int i=row+1;i<n;i++){
            if ( fabs(a[i][col]) > fabs(a[p_row][col]) )
                p_row = i;
        }

        if (p_row!=row){ //把主元行交换至当前行
            for (int j=col;j<m+1;j++)
                swap(a[p_row][j], a[row][j]);
        }

        if ( fabs(a[row][col]) < eps ) {
            row--; //若当前行当前列元素为0则跳过, 同时矩阵的非零行数量(秩)不增加
            continue;
        }

        for (int i=row+1;i<n;i++){
            if ( fabs(a[i][col]) < eps ) continue; //若当前行当前列元素为0则跳过
            double pro = a[i][col]/a[row][col];
            for (int j=col;j<m+1;j++){
                a[i][j] -= pro*a[row][j];
                //对该行做一次初等变换
            }
        }
    }

    //系数矩阵的秩小于增广矩阵的秩 Rank(A) < Rank(A') 则方程组无解
    for (int i=row;i<n;i++){
        if ( fabs(a[i][col]) > eps ) return -1;
        //当前col指向增广矩阵的常数项列, 若row及以下的常数项存在非零项, 说明方程组无解
    }

    //系数矩阵的秩等于增广矩阵的秩, 则方程组有解, 有以下两种情况
    //增广矩阵的秩等于变元数量时, 方程组有唯一解, 自由变元数量为0
    //增广矩阵的秩小于变元数量时, 方程组有无穷多解, 自由变元数量为 m - row
    return m - row; //返回自由变元的个数
}

0/1异或方程组求解

int gauss(int n, int m) {
    //n个方程, m个变元, 增广矩阵的列数为m+1
    int row, col;
    for (row = 0, col = 0;row<n&&col<m;row++, col++) {
        //当前处理第col列, 第row行
        int p_row = row; //p_row 为主元所在行号
        for (int i = row + 1;i<n;i++) {
            if (a[i][col]>a[p_row][col])
                p_row = i;
        }
        if (p_row != row) { //把主元所在行与当前行交换
            for (int j = col;j<m + 1;j++)
                swap(a[p_row][j], a[row][j]);
        }
        if (a[row][col] == 0) { //若当前行主元为0则跳过, 并在下次继续处理此行的下一列元素
            row--;
            continue;
        }
        for (int i = row + 1; i < n;i++) {
            if (a[i][col] == 0) continue; //跳过0元素开头的行
            for (int j = col;j<m + 1;j++)
                a[i][j] ^= a[row][j]; //做一次初等变换
        }
    }
    for (int i = row;i<n;i++) { //方程组无解
        if (a[i][col] != 0) return -1;
    }
    return m - row; //有解, 返回自由变元的个数
}