27.28 역행렬의 계산 방법: 가우스-조르단 소거법(Gauss-Jordan Elimination)

1. 가우스-조르단 소거법의 원리

가우스-조르단 소거법은 확대 행렬(augmented matrix) $[\mathbf{A} \mid \mathbf{I}]$ 에 기본 행 연산(elementary row operations)을 적용하여, 왼쪽 부분을 단위 행렬로 변환하는 과정이다. 변환이 완료되면 오른쪽 부분에 $\mathbf{A}^{-1}$ 이 나타난다.

$[\mathbf{A} \mid \mathbf{I}_n] \xrightarrow{\text{행 연산}} [\mathbf{I}_n \mid \mathbf{A}^{-1}]$

이 과정이 성립하는 이유는 다음과 같다. 기본 행 연산의 연속은 기본 행렬(elementary matrix)들의 곱 $\mathbf{E} = \mathbf{E}_k \cdots \mathbf{E}_2 \mathbf{E}_1$ 으로 표현된다. $\mathbf{E}\mathbf{A} = \mathbf{I}$ 이면 $\mathbf{E} = \mathbf{A}^{-1}$ 이고, 동시에 $\mathbf{E}\mathbf{I} = \mathbf{E} = \mathbf{A}^{-1}$ 이다. 따라서 왼쪽 부분에 적용한 동일한 행 연산이 오른쪽의 단위 행렬을 역행렬로 변환하는 것이다.

2. 기본 행 연산

가우스-조르단 소거법에서 사용하는 세 가지 기본 행 연산은 다음과 같다.

행 교환(Row Interchange): $i$ 번째 행과 $j$ 번째 행을 교환한다. $R_i \leftrightarrow R_j$ 로 표기한다. 대응하는 기본 행렬은 단위 행렬에서 $i$ 행과 $j$ 행을 교환한 순열 행렬(permutation matrix)이다.

행 스케일링(Row Scaling): $i$ 번째 행에 0이 아닌 스칼라 $c$ 를 곱한다. $R_i \leftarrow cR_i$ 로 표기한다. 대응하는 기본 행렬은 $\mathbf{I}$ 의 $(i,i)$ 원소를 $c$ 로 바꾼 대각 행렬이다.

행 덧셈(Row Addition): $j$ 번째 행에 $i$ 번째 행의 $c$ 배를 더한다. $R_j \leftarrow R_j + cR_i$ 로 표기한다. 대응하는 기본 행렬은 단위 행렬의 $(j,i)$ 위치에 $c$ 를 놓은 행렬이다.

세 유형의 기본 행렬은 모두 가역이며, 각각의 역행렬도 같은 유형의 기본 행렬이다. 행 교환의 역은 같은 행 교환이고, 스케일링 $c$ 의 역은 스케일링 $1/c$ 이며, $c$ 배 덧셈의 역은 $-c$ 배 덧셈이다.

3. 알고리즘의 단계적 절차

$n \times n$ 행렬 $\mathbf{A}$ 의 역행렬을 구하는 가우스-조르단 소거법의 절차는 다음과 같다.

1단계: 확대 행렬 구성. $[\mathbf{A} \mid \mathbf{I}_n]$ 을 구성한다. 이 행렬은 $n \times 2n$ 크기이다.

2단계: 전방 소거(Forward Elimination). 첫 번째 열부터 순서대로 피벗(pivot)을 설정하고, 피벗 아래의 모든 원소를 0으로 만든다. $k$ 번째 단계에서:

$k$ 번째 열에서 $k$ 행 이하의 원소 중 절댓값이 가장 큰 원소가 있는 행을 찾아 $k$ 행과 교환한다(부분 피벗팅).
$k$ 행의 피벗 원소 $a_{kk}$ 로 $k$ 행 전체를 나누어 피벗을 1로 만든다.
$k$ 행 아래의 모든 행 $i$ ( $i > k$ )에 대하여, $R_i \leftarrow R_i - a_{ik}R_k$ 를 수행하여 $k$ 열의 원소를 0으로 만든다.

3단계: 후방 소거(Back Elimination). 마지막 열부터 역순으로, 피벗 위의 원소를 0으로 만든다. $k$ 번째 단계에서 $k$ 행 위의 모든 행 $i$ ( $i < k$ )에 대하여, $R_i \leftarrow R_i - a_{ik}R_k$ 를 수행한다.

4단계: 결과 확인. 왼쪽 부분이 $\mathbf{I}_n$ 이 되면, 오른쪽 부분이 $\mathbf{A}^{-1}$ 이다. 전방 소거 과정에서 피벗 위치에 0이 아닌 원소를 찾을 수 없으면, $\mathbf{A}$ 는 특이 행렬이므로 역행렬이 존재하지 않는다.

4. 구체적 계산 예

$3 \times 3$ 행렬의 역행렬을 가우스-조르단 소거법으로 구해 보자.

$\mathbf{A} = \begin{pmatrix} 2 & 1 & 1 \\ 4 & 3 & 3 \\ 8 & 7 & 9 \end{pmatrix}$

확대 행렬을 구성한다.

$\left(\begin{array}{ccc|ccc} 2 & 1 & 1 & 1 & 0 & 0 \\ 4 & 3 & 3 & 0 & 1 & 0 \\ 8 & 7 & 9 & 0 & 0 & 1 \end{array}\right)$

$R_1 \leftarrow \frac{1}{2}R_1$ :

$\left(\begin{array}{ccc|ccc} 1 & 1/2 & 1/2 & 1/2 & 0 & 0 \\ 4 & 3 & 3 & 0 & 1 & 0 \\ 8 & 7 & 9 & 0 & 0 & 1 \end{array}\right)$

$R_2 \leftarrow R_2 - 4R_1$ , $R_3 \leftarrow R_3 - 8R_1$ :

$\left(\begin{array}{ccc|ccc} 1 & 1/2 & 1/2 & 1/2 & 0 & 0 \\ 0 & 1 & 1 & -2 & 1 & 0 \\ 0 & 3 & 5 & -4 & 0 & 1 \end{array}\right)$

$R_3 \leftarrow R_3 - 3R_2$ :

$\left(\begin{array}{ccc|ccc} 1 & 1/2 & 1/2 & 1/2 & 0 & 0 \\ 0 & 1 & 1 & -2 & 1 & 0 \\ 0 & 0 & 2 & 2 & -3 & 1 \end{array}\right)$

$R_3 \leftarrow \frac{1}{2}R_3$ :

$\left(\begin{array}{ccc|ccc} 1 & 1/2 & 1/2 & 1/2 & 0 & 0 \\ 0 & 1 & 1 & -2 & 1 & 0 \\ 0 & 0 & 1 & 1 & -3/2 & 1/2 \end{array}\right)$

후방 소거: $R_2 \leftarrow R_2 - R_3$ , $R_1 \leftarrow R_1 - \frac{1}{2}R_3$ :

$\left(\begin{array}{ccc|ccc} 1 & 1/2 & 0 & 0 & 3/4 & -1/4 \\ 0 & 1 & 0 & -3 & 5/2 & -1/2 \\ 0 & 0 & 1 & 1 & -3/2 & 1/2 \end{array}\right)$

$R_1 \leftarrow R_1 - \frac{1}{2}R_2$ :

$\left(\begin{array}{ccc|ccc} 1 & 0 & 0 & 3/2 & -1/2 & 0 \\ 0 & 1 & 0 & -3 & 5/2 & -1/2 \\ 0 & 0 & 1 & 1 & -3/2 & 1/2 \end{array}\right)$

따라서 $\mathbf{A}^{-1} = \begin{pmatrix} 3/2 & -1/2 & 0 \\ -3 & 5/2 & -1/2 \\ 1 & -3/2 & 1/2 \end{pmatrix}$ 이다.

5. 계산 복잡도와 수치적 고려사항

가우스-조르단 소거법으로 $n \times n$ 행렬의 역행렬을 구하는 데 필요한 부동소수점 연산 횟수는 약 $\frac{8}{3}n^3$ 이다. 전방 소거에 $\frac{2}{3}n^3$ , 후방 소거와 우측의 변환에 추가로 $2n^3$ 이 소요된다.

부분 피벗팅(Partial Pivoting): 수치적 안정성을 위해 각 단계에서 피벗 열의 절댓값이 가장 큰 원소를 피벗으로 선택하는 부분 피벗팅을 적용해야 한다. 피벗 원소가 0에 가까우면 나눗셈에서 큰 수가 발생하여 반올림 오차가 증폭되기 때문이다.

역행렬의 직접 계산 회피: 실무에서는 $\mathbf{A}^{-1}\mathbf{b}$ 를 계산할 때 역행렬을 명시적으로 구하지 않고, $\mathbf{A}\mathbf{x} = \mathbf{b}$ 를 연립방정식으로 풀어 $\mathbf{x}$ 를 구하는 것이 표준적 접근이다. LU 분해를 사용하면 $O(n^3/3)$ 에 분해를 수행하고, 이후 각 우변 벡터에 대해 $O(n^2)$ 에 해를 구할 수 있다. 역행렬의 직접 계산은 저장 공간과 연산량 모두에서 비효율적이며, 수치적 오차도 더 크다.

6. 딥러닝에서의 실용적 의미

딥러닝에서 대규모 행렬의 역행렬을 직접 계산하는 경우는 드물다. 매개변수 수가 수백만에서 수십억에 이르는 현대 모델에서 $O(n^3)$ 역행렬 계산은 현실적으로 불가능하다. 대신 다음과 같은 간접적 방법들이 사용된다.

반복법(Iterative Methods): 켤레 기울기법(conjugate gradient method)은 $\mathbf{A}\mathbf{x} = \mathbf{b}$ 형태의 문제를 역행렬 없이 반복적으로 풀 수 있으며, 행렬-벡터 곱 $\mathbf{A}\mathbf{v}$ 만 계산하면 된다. 이는 행렬을 명시적으로 저장하지 않아도 되므로 메모리 효율적이다.

우드버리 항등식(Woodbury Identity): 저순위 갱신(low-rank update) $(\mathbf{A} + \mathbf{U}\mathbf{C}\mathbf{V})^{-1}$ 을 $\mathbf{A}^{-1}$ 로부터 효율적으로 계산하는 공식이다. $\mathbf{U} \in \mathbb{R}^{n \times k}$ , $\mathbf{V} \in \mathbb{R}^{k \times n}$ 에서 $k \ll n$ 이면, $O(n^2k)$ 복잡도로 갱신된 역행렬을 구할 수 있다.

$(\mathbf{A} + \mathbf{U}\mathbf{C}\mathbf{V})^{-1} = \mathbf{A}^{-1} - \mathbf{A}^{-1}\mathbf{U}(\mathbf{C}^{-1} + \mathbf{V}\mathbf{A}^{-1}\mathbf{U})^{-1}\mathbf{V}\mathbf{A}^{-1}$

이 항등식은 적응적 학습률 방법이나 가우시안 과정의 효율적 갱신에서 활용된다.