문제 개요
이 문제에서는 2차원 행렬 mat[][]가 주어지며, 우리의 목표는 가우스-조던 방법(Gauss-Jordan Method)을 사용하여 행렬의 역행렬을 구하는 것입니다.
먼저 문제를 이해하기 위한 기본 개념부터 살펴보겠습니다.
행렬(Matrix)은 숫자들이 행과 열의 형태로 배열된 2차원 배열입니다.
예시
$\begin{bmatrix}2&5&4 \\1&6&7 \\9&3&8\end{bmatrix}$
역행렬(Inverse Matrix)이란?
역행렬 [A⁻¹]은 정방행렬(정사각 행렬)에 대해서만 정의되는 연산입니다. 어떤 행렬 A가 역행렬을 가지려면 다음 조건들을 만족해야 합니다.
주어진 행렬은 반드시 정방행렬(n×n)이어야 합니다.
비특이(non-singular) 행렬, 즉 행렬식이 0이 아닌 행렬이어야 합니다.
행렬 A에 대해 다음 항등식을 만족하는 단위행렬(identity matrix) I가 존재해야 합니다.
$$AA^{-1} = A^{-1}.A = I$$
또한 역행렬은 다음 공식을 통해서도 구할 수 있습니다.
$A^{-1}\:=\:\left(\frac{adj(A)}{det(A)}\right)$
여기서 adj(A)는 행렬 A의 수반 행렬(adjoint), det(A)는 행렬 A의 행렬식(determinant)을 의미합니다.
가우스-조던 방법(Gauss-Jordan Method)
역행렬을 구하는 방법에는 여러 가지가 있지만, 이 글에서는 기본 행 연산(Elementary Row Operation)이라고도 불리는 가우스-조던 방법에 대해 알아보겠습니다.
이 방법은 행렬의 역행렬을 단계별로 구하는 알고리즘으로, 절차는 다음과 같습니다.
단위행렬을 결합하여 확대 행렬(augmented matrix)을 만듭니다.
1단계에서 만든 확대 행렬에 행 축약(row reduction) 연산을 수행하여 사다리꼴(echelon form) 형태로 변환합니다.
이 과정에서 확대 행렬에 적용할 수 있는 연산은 다음과 같습니다.
행 교환(Row Interchange): 임의의 두 행을 서로 맞바꿀 수 있습니다.
스칼라 곱(Multiplication): 한 행의 모든 원소에 0이 아닌 상수를 곱할 수 있습니다.
행 덧셈: 한 행에 다른 행의 상수배를 더한 결과로 해당 행을 대체할 수 있습니다.
C++ 구현 예제
아래는 위 풀이 방법의 동작을 보여주는 프로그램입니다.
#include <iostream>
#include <vector>
using namespace std;
void printMatrixValues(float** arr, int n, int m){
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout<<arr[i][j]<<"\t";
}
cout<<endl;
}
return;
}
void printInverseMatrix(float** arr, int n, int m){
for (int i = 0; i < n; i++) {
for (int j = n; j < m; j++) {
printf("%.3f\t", arr[i][j]);
}
cout<<endl;
}
return;
}
void findInvMatGaussJordan(float** mat, int order){
float temp;
printf("The inverse of matrix : A = \n");
printMatrixValues(mat, order, order);
for (int i = 0; i < order; i++) {
for (int j = 0; j < 2 * order; j++) {
if (j == (i + order))
mat[i][j] = 1;
}
}
for (int i = order - 1; i > 0; i--) {
if (mat[i - 1][0] < mat[i][0]) {
float* temp = mat[i];
mat[i] = mat[i - 1];
mat[i - 1] = temp;
}
}
for (int i = 0; i < order; i++) {
for (int j = 0; j < order; j++) {
if (j != i) {
temp = mat[j][i] / mat[i][i];
for (int k = 0; k < 2 * order; k++) {
mat[j][k] -= mat[i][k] * temp;
}
}
}
}
for (int i = 0; i < order; i++) {
temp = mat[i][i];
for (int j = 0; j < 2 * order; j++) {
mat[i][j] = mat[i][j] / temp;
}
}
cout<<"A' =\n";
printInverseMatrix(mat, order, 2 * order);
return;
}
int main(){
int order = 3;
float** mat = new float*[20];
for (int i = 0; i < 20; i++)
mat[i] = new float[20];
mat[0][0] = 6; mat[0][1] = 9; mat[0][2] = 5;
mat[1][0] = 8; mat[1][1] = 3; mat[1][2] = 2;
mat[2][0] = 1; mat[2][1] = 4; mat[2][2] = 7;
findInvMatGaussJordan(mat, order);
return 0;
}실행 결과
The inverse of matrix : A = 6 9 5 8 3 2 1 4 7 A' = -0.049 0.163 -0.011 0.205 -0.141 -0.106 -0.110 0.057 0.205