ガウスの消去法

概要

掃き出し法です．連立方程式の求根，行列の行列式・逆行列の計算などいろいろできます．

使い方

下三角行列の部分は 0 になることが分かっているのでそのまま残す
できた行列の対角成分の積が行列式になる
正方行列でない場合は正方行列に収まらない右側の部分も同時に処理する
- 逆行列や連立方程式の解を求めるのに使える
かなり誤差る

実装

Matrix gauss_jordan(Matrix A) {
    int n = A.size(), m = A[0].size();
    rep(i, n) {
        int piv = i;
        FOR(j, i, n) if (abs(A[j][i]) > abs(A[piv][i])) piv = j;
        swap(A[i], A[piv]);
        if (abs(A[i][i]) < eps) return {};
        FOR(j, i + 1, m) A[i][j] /= A[i][i];
        rep(j, n) if (i != j) FOR(k, i + 1, m) A[j][k] -= A[j][i] * A[i][k];
    }
    Matrix R(n, Array(m - n));
    rep(i, n) rep(j, m - n) R[i][j] = A[i][n + j];
    return R;
}

検証

AOJ 1328 (Submission)

参考文献

あり本