用C++实现齐次线性方程组的求解

齐次线性方程组指的是形如 $Ax=0$ 的方程组，其中 $A$ 是 $n\times m$ 的系数矩阵，$x$ 是 $m\times 1$ 的未知向量。下面是用 C++ 实现求解齐次线性方程组的代码：

#include <iostream>
#include <vector>

using namespace std;

typedef vector<vector<double>> Matrix;

// 高斯消元法求解齐次线性方程组
void gauss_elimination(Matrix &A, int n, int m) {
    int r = 0; // 当前处理的行数
    for (int i = 0; i < m; i++) { // 对每一列进行处理
        int j = r;
        while (j < n && A[j][i] == 0) j++; // 找到第一个非零元素所在的行
        if (j == n) continue; // 如果这一列全是零，则继续处理下一列
        if (j != r) swap(A[j], A[r]); // 如果第一个非零元素不在第 r 行，则交换两行
        for (int k = r + 1; k < n; k++) { // 将第 r+1 到第 n 行的第 i 列消成零
            double f = A[k][i] / A[r][i];
            for (int l = i; l < m; l++)
                A[k][l] -= f * A[r][l];
        }
        r++; // 处理下一行
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    Matrix A(n, vector<double>(m));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> A[i][j];
    gauss_elimination(A, n, m);
    int r = 0; // 非零行的数量
    for (int i = 0; i < n; i++) {
        bool all_zero = true;
        for (int j = 0; j < m; j++)
            if (A[i][j] != 0) {
                all_zero = false;
                break;
            }
        if (!all_zero) r++;
    }
    cout << "rank of A: " << r << endl; // A 的秩
    cout << "null space: ";
    for (int i = 0; i < m; i++) {
        bool all_zero = true;
        for (int j = 0; j < r; j++)
            if (A[j][i] != 0) {
                all_zero = false;
                break;
            }
        if (all_zero) cout << "x" << i+1 << " ";
    }
    cout << endl;
    return 0;
}

这个程序读入一个 $n\times m$ 的系数矩阵 $A$，然后用高斯消元法将其化为阶梯形矩阵，最后输出矩阵 $A$ 的秩和其零空间的一组基。

我们可以用以下步骤实现高斯消元法：

1. 初始化当前处理的行数 $r=0$。
2. 对于每一列 $i$，从第 $r$ 行开始寻找第一个非零元素所在的行 $j$，如果这一列全是零，则跳过这一列。
3. 如果 $j\ne r$，则交换第 $j$ 行和第 $r$ 行。
4. 将第 $r+1$ 到第 $n$ 行的第 $i$ 列消成零。具体地，对于第 $k$ 行，令 $f=A[k][i]/A[r][i]$，然后将第 $r$ 行乘上 $f$，再减去第 $k$ 行即可。
5. 处理下一行，即 $r\gets r+1$，继续处理下一列。

处理完所有的列之后，矩阵 $A$ 就被化为了阶梯形矩阵。我们接着计算矩阵 $A$ 的秩和其零空间的一组基。矩阵 $A$ 的秩等于其非零行的数量，而零空间的一组基可以通过观察阶梯形矩阵得到。特别地，如果一个未知量 $x_i$ 没有出现在阶梯形矩阵的非零行中，那么它就是矩阵 $A$ 的一组零空间基向量的系数。