C++でグラフ行列の逆行列を求めるプログラムの実装方法

本記事では、グラフ行列の逆行列を求めるC++プログラムについて詳しく解説します。行列の逆行列は、対象となる行列が正則(非特異)である場合、すなわち行列式が0ではない場合にのみ存在します。

逆行列を求める手法は複数ありますが、ここでは随伴行列(余因子行列の転置)と行列式を組み合わせて逆行列を計算する方法を紹介します。

アルゴリズムの手順

逆行列を求める際の処理の流れは以下の通りです。

開始
    行列の逆行列を求める関数 INV() を定義する。
    行列式を計算する関数 DET() を呼び出す。
    随伴行列を生成する関数 ADJ() を呼び出す。
    次の公式に基づいて逆行列を求める。
    逆行列(行列) = 随伴行列(行列) ÷ 行列式(行列)
終了

サンプルコード

#include <bits/stdc++.h>
using namespace std;
#define N 5

// 指定した行p・列qを除いた部分行列(余因子用)を作成する
void getCfactor(int M[N][N], int t[N][N], int p, int q, int n) {
    int i = 0, j = 0;
    for (int r = 0; r < n; r++) {
        for (int c = 0; c < n; c++) {
            // 与えられた行r・列c以外の要素のみコピーする
            if (r != p && c != q) {
                t[i][j++] = M[r][c];
                // 行が埋まったら行インデックスを進め、列インデックスをリセットする
                if (j == n - 1) {
                    j = 0;
                    i++;
                }
            }
        }
    }
}

// 行列式を求める
int DET(int M[N][N], int n) {
    int D = 0;
    if (n == 1)
        return M[0][0];
    int t[N][N];   // 余因子を格納
    int s = 1;     // 符号(正負)の乗数
    // 1行目の各要素に対して繰り返す
    for (int f = 0; f < n; f++) {
        // M[0][f] の余因子を取得
        getCfactor(M, t, 0, f, n);
        D += s * M[0][f] * DET(t, n - 1);
        s = -s;
    }
    return D;
}

// 随伴行列を求める
void ADJ(int M[N][N], int adj[N][N]) {
    if (N == 1) {
        adj[0][0] = 1;
        return;
    }
    int s = 1, t[N][N];
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            // M[i][j] の余因子を取得
            getCfactor(M, t, i, j, N);
            // 行と列のインデックスの和が偶数なら符号は正
            s = ((i + j) % 2 == 0) ? 1 : -1;
            // 行と列を入れ替えて余因子行列の転置を求める
            adj[j][i] = (s) * (DET(t, N - 1));
        }
    }
}

// 逆行列を求める
bool INV(int M[N][N], float inv[N][N]) {
    int det = DET(M, N);
    if (det == 0) {
        cout << "can't find its inverse";
        return false;
    }
    int adj[N][N];
    ADJ(M, adj);
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            inv[i][j] = adj[i][j] / float(det);
    return true;
}

// 行列を表示する
template<class T> void print(T A[N][N]) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++)
            cout << A[i][j] << " ";
        cout << endl;
    }
}

int main() {
    int M[N][N] = {
        {1, 2, 3, 4, -2},
        {-5, 6, 7, 8, 4},
        {9, 10, -11, 12, 1},
        {13, -14, -15, 0, 9},
        {20, -26, 16, -17, 25}
    };
    float inv[N][N];
    cout << "Input matrix is :\n";
    print(M);
    cout << "\nThe Inverse is :\n";
    if (INV(M, inv))
        print(inv);
    return 0;
}

プログラムの構成

• getCfactor():指定した行と列を取り除いた部分行列(余因子計算用の小行列)を作成する関数です。
• DET():余因子展開を再帰的に適用し、行列式を計算する関数です。
• ADJ():各要素の余因子を求め、行と列を入れ替えることで随伴行列を作成する関数です。
• INV():まず行列式が0でないか確認し、その後「随伴行列 ÷ 行列式」によって逆行列を導出する関数です。行列式が0の場合は逆行列が存在しない旨を通知します。

実行結果

Input matrix is :
1 2 3 4 -2
-5 6 7 8 4 
9 10 -11 12 1 
13 -14 -15 0 9 
20 -26 16 -17 25

The Inverse is : 
0.0811847 -0.0643008 0.0493814 -0.0247026 0.0237006 
-0.126819 -0.0161738 0.0745377 -0.0713976 0.0151639 
0.0933664 0.0028245 -0.0111876 -0.0220437 0.0154006 
0.143624 0.0582573 -0.0282371 0.0579023 -0.0175466 
-0.15893 0.0724272 0.0259728 -0.00100988 0.0150219

このように、随伴行列と行列式を利用することで、5×5のような比較的大きなサイズのグラフ行列でも確実に逆行列を求めることができます。なお、行列式が0になる特異行列に対しては逆行列が存在しないため、実際のプログラムでは必ず事前に判定を行うことが重要です。