【C言語】掃き出し法で逆行列を求める方法

2023-07-202024-07-23

この記事では、C言語を使って行列の逆行列を求める方法について解説します。

具体的には、掃き出し法という手法を使って逆行列を計算する手順を説明し、実際にC言語でプログラムを作成します。

また、挿入ソートという基本的なソートアルゴリズムについても紹介し、その動作や比較回数について詳しく解説します。

目次から探す

掃き出し法とは

掃き出し法の概要

掃き出し法(ガウス・ジョルダン法)は、連立一次方程式の解を求めたり、行列の逆行列を求めたりするためのアルゴリズムです。

この方法は、行列を段階的に変形していくことで、最終的に単位行列を得ることを目指します。

単位行列を得る過程で、元の行列の逆行列も同時に求めることができます。

掃き出し法の数学的背景

掃き出し法は、行列の行基本変形を用いて行列を簡約化する手法です。

行基本変形には以下の3つの操作があります：

行の交換
行の定数倍
行の加減

これらの操作を駆使して、行列を上三角行列、さらには単位行列に変形していきます。

具体的には、行列の各行を操作して、対角成分が1、それ以外の成分が0になるようにします。

この過程で、元の行列に対する逆行列も同時に求められます。

掃き出し法の利点と欠点

利点

汎用性：掃き出し法は、任意の正方行列に対して適用可能です。
直接法：反復法と異なり、有限のステップで解が得られます。
理解しやすい：行基本変形という直感的な操作を用いるため、理解しやすいです。

欠点

計算量：行列のサイズが大きくなると、計算量が急増します。

特に、$O(n^3)$の計算量が必要です。

数値安定性：行列の成分が非常に大きいか非常に小さい場合、数値的に不安定になることがあります。
メモリ使用量：大きな行列を扱う場合、メモリ使用量が増加します。

掃き出し法は、行列の逆行列を求めるための基本的な手法として広く使われていますが、計算量や数値安定性の問題を考慮する必要があります。

次のセクションでは、具体的な手順とC言語での実装方法について詳しく解説します。

掃き出し法による逆行列の求め方

掃き出し法の手順

掃き出し法を用いて逆行列を求める手順は以下の通りです。

行基本変形

行基本変形とは、行列の行に対して行う基本的な操作のことです。

行基本変形には以下の3つの操作があります。

行の交換: 2つの行を入れ替える。
行の定数倍: ある行を定数倍する。
行の加減算: ある行に他の行の定数倍を加える。

これらの操作を用いて、行列を段階的に変形していきます。

単位行列の作成

次に、元の行列の右側に単位行列を追加します。

単位行列とは、対角線上に1があり、それ以外の要素が0である行列のことです。

例えば、3×3の単位行列は以下のようになります。

1 0 0
0 1 0
0 0 1

元の行列と単位行列を並べた拡大行列を作成し、行基本変形を行っていきます。

逆行列の導出

行基本変形を繰り返し、元の行列部分を単位行列に変形します。

このとき、拡大行列の右側にある行列が元の行列の逆行列となります。

掃き出し法の具体例

2×2行列の例

具体的な例として、2×2行列の逆行列を求めてみましょう。

以下の行列Aの逆行列を求めます。

A = | 2 1 |
    | 1 3 |

拡大行列を作成します。

| 2 1 | 1 0 |
| 1 3 | 0 1 |

行基本変形を行います。

まず、1行目を2で割ります。

| 1 0.5 | 0.5 0 |
| 1 3   | 0   1 |

次に、2行目から1行目を引きます。

| 1 0.5 | 0.5 0   |
| 0 2.5 | -0.5 1 |

2行目を2.5で割ります。

| 1 0.5 | 0.5 0   |
| 0 1   | -0.2 0.4 |

最後に、1行目から0.5倍の2行目を引きます。

| 1 0 | 0.6 -0.2 |
| 0 1 | -0.2 0.4 |

これで、右側の行列が逆行列となります。

A^(-1) = | 0.6 -0.2 |
         | -0.2 0.4 |

3×3行列の例

次に、3×3行列の逆行列を求めてみましょう。

以下の行列Bの逆行列を求めます。

B = | 2 1 1 |
    | 1 3 2 |
    | 1 0 0 |

拡大行列を作成します。

| 2 1 1 | 1 0 0 |
| 1 3 2 | 0 1 0 |
| 1 0 0 | 0 0 1 |

行基本変形を行います。

まず、1行目を2で割ります。

| 1 0.5 0.5 | 0.5 0 0 |
| 1 3   2   | 0   1 0 |
| 1 0   0   | 0   0 1 |

次に、2行目と3行目から1行目を引きます。

| 1 0.5 0.5 | 0.5 0 0 |
| 0 2.5 1.5 | -0.5 1 0 |
| 0 -0.5 -0.5 | -0.5 0 1 |

2行目を2.5で割ります。

| 1 0.5 0.5 | 0.5 0 0 |
| 0 1 0.6 | -0.2 0.4 0 |
| 0 -0.5 -0.5 | -0.5 0 1 |

3行目に0.5倍の2行目を加えます。

| 1 0.5 0.5 | 0.5 0 0 |
| 0 1 0.6 | -0.2 0.4 0 |
| 0 0 -0.2 | -0.6 0.2 1 |

3行目を-0.2で割ります。

| 1 0.5 0.5 | 0.5 0 0 |
| 0 1 0.6 | -0.2 0.4 0 |
| 0 0 1 | 3 -1 5 |

1行目と2行目から3行目を引きます。

| 1 0.5 0 | -2 0.5 -2.5 |
| 0 1 0 | -2 1 3 |
| 0 0 1 | 3 -1 5 |

これで、右側の行列が逆行列となります。

B^(-1) = | -2 0.5 -2.5 |
         | -2 1 3 |
         | 3 -1 5 |

C言語での実装

必要なライブラリと準備

C言語で掃き出し法を実装するためには、標準ライブラリを使用します。

特に、stdio.hとstdlib.hが必要です。

これらのライブラリは、入力と出力、メモリの動的確保などに使用されます。

#include <stdio.h>
#include <stdlib.h>

行列の入力と出力

行列の入力方法

行列の入力は、ユーザーから行列の要素を受け取る形で行います。

以下のコードは、ユーザーから行列の要素を入力する方法の例です。

void inputMatrix(double **matrix, int size) {
    printf("行列の要素を入力してください:\n");
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) {
            printf("matrix[%d][%d] = ", i, j);
            scanf("%lf", &matrix[i][j]);
        }
    }
}

行列の出力方法

行列の出力は、行列の要素を整形して表示する形で行います。

以下のコードは、行列を出力する方法の例です。

void printMatrix(double **matrix, int size) {
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) {
            printf("%8.3f ", matrix[i][j]);
        }
        printf("\n");
    }
}

掃き出し法の実装

行基本変形の関数

行基本変形は、行列の行を操作して目的の形に変形するための関数です。

以下のコードは、行基本変形を行う関数の例です。

void rowOperation(double **matrix, int size, int row, int col) {
    double pivot = matrix[row][col];
    for (int j = 0; j < size; j++) {
        matrix[row][j] /= pivot;
    }
    for (int i = 0; i < size; i++) {
        if (i != row) {
            double factor = matrix[i][col];
            for (int j = 0; j < size; j++) {
                matrix[i][j] -= factor * matrix[row][j];
            }
        }
    }
}

単位行列の作成関数

単位行列は、対角要素が1でその他の要素が0の行列です。

以下のコードは、単位行列を作成する関数の例です。

void createIdentityMatrix(double **matrix, int size) {
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) {
            if (i == j) {
                matrix[i][j] = 1.0;
            } else {
                matrix[i][j] = 0.0;
            }
        }
    }
}

逆行列の計算関数

逆行列の計算は、元の行列と単位行列を連結して掃き出し法を適用することで行います。

以下のコードは、逆行列を計算する関数の例です。

void calculateInverseMatrix(double **matrix, double **inverse, int size) {
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) {
            inverse[i][j] = matrix[i][j];
        }
    }
    for (int i = 0; i < size; i++) {
        rowOperation(inverse, size, i, i);
    }
}

完成したプログラムの例

コード全体の説明

以下に、行列の入力、出力、掃き出し法による逆行列の計算を行う完全なプログラムを示します。

#include <stdio.h>
#include <stdlib.h>
void inputMatrix(double **matrix, int size) {
    printf("行列の要素を入力してください:\n");
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) {
            printf("matrix[%d][%d] = ", i, j);
            scanf("%lf", &matrix[i][j]);
        }
    }
}
void printMatrix(double **matrix, int size) {
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) {
            printf("%8.3f ", matrix[i][j]);
        }
        printf("\n");
    }
}
void rowOperation(double **matrix, int size, int row, int col) {
    double pivot = matrix[row][col];
    for (int j = 0; j < size; j++) {
        matrix[row][j] /= pivot;
    }
    for (int i = 0; i < size; i++) {
        if (i != row) {
            double factor = matrix[i][col];
            for (int j = 0; j < size; j++) {
                matrix[i][j] -= factor * matrix[row][j];
            }
        }
    }
}
void createIdentityMatrix(double **matrix, int size) {
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) {
            if (i == j) {
                matrix[i][j] = 1.0;
            } else {
                matrix[i][j] = 0.0;
            }
        }
    }
}
void calculateInverseMatrix(double **matrix, double **inverse, int size) {
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) {
            inverse[i][j] = matrix[i][j];
        }
    }
    for (int i = 0; i < size; i++) {
        rowOperation(inverse, size, i, i);
    }
}
int main() {
    int size;
    printf("行列のサイズを入力してください: ");
    scanf("%d", &size);
    double **matrix = (double **)malloc(size * sizeof(double *));
    double **inverse = (double **)malloc(size * sizeof(double *));
    for (int i = 0; i < size; i++) {
        matrix[i] = (double *)malloc(size * sizeof(double));
        inverse[i] = (double *)malloc(size * sizeof(double));
    }
    inputMatrix(matrix, size);
    createIdentityMatrix(inverse, size);
    calculateInverseMatrix(matrix, inverse, size);
    printf("逆行列:\n");
    printMatrix(inverse, size);
    for (int i = 0; i < size; i++) {
        free(matrix[i]);
        free(inverse[i]);
    }
    free(matrix);
    free(inverse);
    return 0;
}

実行結果の例

以下は、上記のプログラムを実行した際の例です。

行列のサイズを入力してください: 3
行列の要素を入力してください:
matrix[0][0] = 2
matrix[0][1] = -1
matrix[0][2] = 0
matrix[1][0] = -1
matrix[1][1] = 2
matrix[1][2] = -1
matrix[2][0] = 0
matrix[2][1] = -1
matrix[2][2] = 2
逆行列:
   0.750  0.500  0.250 
   0.500  1.000  0.500 
   0.250  0.500  0.750

このプログラムは、ユーザーから入力された行列の逆行列を計算し、結果を表示します。

行列のサイズや要素を変更することで、さまざまな行列に対して逆行列を求めることができます。

挿入ソートとは

挿入ソートの基本概念

挿入ソートは、ソートアルゴリズムの一つで、特に小規模なデータセットに対して効率的に動作します。

このアルゴリズムは、データの一部が既にソートされている場合や、データがほぼソートされている場合に非常に効果的です。

挿入ソートの基本的な考え方は、未ソートのデータを一つずつ取り出し、それを適切な位置に挿入していくというものです。

これにより、データが徐々にソートされていきます。

挿入ソートのアルゴリズム

挿入ソートのアルゴリズムは以下のように動作します：

配列の最初の要素をソート済みと見なします。
次の要素を取り出し、ソート済みの部分に適切な位置に挿入します。
これを配列の最後の要素まで繰り返します。

具体的な手順は以下の通りです：

配列の2番目の要素から始めます。
その要素を一時的に保存し、ソート済み部分の最後の要素と比較します。
保存した要素がソート済み部分の最後の要素よりも小さい場合、ソート済み部分の要素を一つ右にシフトします。
保存した要素が適切な位置に挿入されるまで、これを繰り返します。

挿入ソートの擬似コード

以下に挿入ソートの擬似コードを示します：

for i from 1 to length(A) - 1 do
    key = A[i]
    j = i - 1
    while j >= 0 and A[j] > key do
        A[j + 1] = A[j]
        j = j - 1
    end while
    A[j + 1] = key
end for

この擬似コードでは、Aはソート対象の配列を表しています。

keyは現在挿入しようとしている要素を一時的に保存するための変数です。

jはソート済み部分の最後の要素のインデックスを示します。

このアルゴリズムの時間計算量は、最悪の場合でO(n^2)ですが、データがほぼソートされている場合には非常に高速に動作します。

挿入ソートは、シンプルで理解しやすいアルゴリズムであり、特に小規模なデータセットに対して有効です。