6.24 가우스-조르단 소거법을 이용한 역행렬 계산

1. 가우스-조르단 소거법의 개요

가우스-조르단 소거법(Gauss-Jordan elimination)은 행렬을 기약 행 사다리꼴(reduced row echelon form, RREF)로 환원하는 알고리즘이며, 가우스 소거법의 확장이다. 이 방법은 단순히 선형 시스템을 풀이하는 데 사용될 뿐 아니라, 정방 행렬의 역행렬을 체계적이고 수치적으로 계산하는 표준 절차를 제공한다. 본 절에서는 가우스-조르단 소거법의 원리, 역행렬 계산 절차, 알고리즘적 구현, 그리고 로봇공학에서의 활용을 체계적으로 다룬다.

2. 기본 행 연산의 복습

가우스-조르단 소거법은 다음의 세 가지 기본 행 연산만을 사용한다.

E1 (행 교환): 두 행을 서로 교환한다. 표기: $R_i \leftrightarrow R_j$

E2 (스칼라 곱): 한 행에 0이 아닌 스칼라를 곱한다. 표기: $R_i \to k R_i$

E3 (행 합): 한 행에 다른 행의 스칼라 배를 더한다. 표기: $R_i \to R_i + k R_j$

각 기본 행 연산은 가역이며, 그에 대응하는 기본 행렬(elementary matrix)의 곱셈으로 표현된다. 행렬에 일련의 기본 행 연산을 적용하는 것은 그 기본 행렬들의 곱을 좌측에서 곱하는 것과 동치이다.

3. 역행렬 계산의 원리

가우스-조르단 소거법으로 역행렬을 계산하는 핵심 아이디어는 다음과 같다.

$A$ 를 $I$ 로 환원하는 일련의 기본 행 연산이 존재한다면, 그 기본 행 연산에 대응하는 기본 행렬들의 곱 $E$ 는 $E A = I$ 를 만족한다. 즉 $E = A^{-1}$ 이다. 동일한 기본 행 연산을 $I$ 에 적용하면 $E I = E = A^{-1}$ 이 얻어진다.

이를 효율적으로 구현하기 위해 확장 행렬(augmented matrix) $[A \mid I]$ 를 구성하고, $A$ 부분이 $I$ 가 될 때까지 행 환원을 진행한다. 그 결과는 $[I \mid A^{-1}]$ 형태가 된다.

알고리즘 6.24.1 (가우스-조르단 역행렬 계산).

확장 행렬 $[A \mid I_n]$ 을 구성한다.
가우스-조르단 소거법을 통해 좌측 $A$ 부분을 $I_n$ 으로 환원한다.
환원이 성공하면 우측 부분이 $A^{-1}$ 이다. 환원 과정에서 $A$ 의 어떤 행이 영이 되면 $A$ 는 특이이며 역행렬이 존재하지 않는다.

4. 단계별 절차

가우스-조르단 소거법의 표준 절차는 다음과 같다.

4.1 전진 단계 (forward elimination)

각 열 $j = 1, 2, \ldots, n$ 에 대해:

피벗 선택: $j$ 열에서 $j$ 행 이하의 성분 중 절댓값이 가장 큰 것을 피벗으로 선택한다 (부분 피벗팅, partial pivoting).
행 교환: 피벗 행과 $j$ 행을 교환한다.
피벗 정규화: $j$ 행 전체를 피벗 값으로 나누어 피벗을 1로 만든다.
하방 소거: $j$ 열의 $j$ 행 아래 모든 성분이 0이 되도록 행 합 연산을 수행한다.

4.2 후진 단계 (backward elimination)

각 열 $j = n, n-1, \ldots, 1$ 에 대해:

$j$ 열의 $j$ 행 위 모든 성분이 0이 되도록 행 합 연산을 수행한다.

이 과정이 끝나면 좌측 부분은 $I_n$ 이 되고, 우측 부분이 $A^{-1}$ 이다.

5. 계산 예시: 3 $\times$ 3 행렬

다음의 행렬에 대한 역행렬 계산을 단계별로 수행한다.

$A = \begin{bmatrix} 2 & 1 & 0 \\ 1 & 3 & 2 \\ 0 & 1 & 1 \end{bmatrix}$

확장 행렬을 구성한다.

$\left[ \begin{array}{ccc|ccc} 2 & 1 & 0 & 1 & 0 & 0 \\ 1 & 3 & 2 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 & 0 & 1 \end{array} \right]$

단계 1: $R_1 \to \frac{1}{2} R_1$ 로 첫 피벗을 1로 만든다.

$\left[ \begin{array}{ccc|ccc} 1 & 1/2 & 0 & 1/2 & 0 & 0 \\ 1 & 3 & 2 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 & 0 & 1 \end{array} \right]$

단계 2: $R_2 \to R_2 - R_1$ 로 첫 열의 하방 성분을 소거한다.

$\left[ \begin{array}{ccc|ccc} 1 & 1/2 & 0 & 1/2 & 0 & 0 \\ 0 & 5/2 & 2 & -1/2 & 1 & 0 \\ 0 & 1 & 1 & 0 & 0 & 1 \end{array} \right]$

단계 3: $R_2 \to \frac{2}{5} R_2$ 로 두 번째 피벗을 1로 만든다.

$\left[ \begin{array}{ccc|ccc} 1 & 1/2 & 0 & 1/2 & 0 & 0 \\ 0 & 1 & 4/5 & -1/5 & 2/5 & 0 \\ 0 & 1 & 1 & 0 & 0 & 1 \end{array} \right]$

단계 4: $R_3 \to R_3 - R_2$ 로 두 번째 열의 하방 성분을 소거한다.

$\left[ \begin{array}{ccc|ccc} 1 & 1/2 & 0 & 1/2 & 0 & 0 \\ 0 & 1 & 4/5 & -1/5 & 2/5 & 0 \\ 0 & 0 & 1/5 & 1/5 & -2/5 & 1 \end{array} \right]$

단계 5: $R_3 \to 5 R_3$ 로 세 번째 피벗을 1로 만든다.

$\left[ \begin{array}{ccc|ccc} 1 & 1/2 & 0 & 1/2 & 0 & 0 \\ 0 & 1 & 4/5 & -1/5 & 2/5 & 0 \\ 0 & 0 & 1 & 1 & -2 & 5 \end{array} \right]$

단계 6: $R_2 \to R_2 - \frac{4}{5} R_3$ 로 세 번째 열의 두 번째 행 성분을 소거한다.

$\left[ \begin{array}{ccc|ccc} 1 & 1/2 & 0 & 1/2 & 0 & 0 \\ 0 & 1 & 0 & -1 & 2 & -4 \\ 0 & 0 & 1 & 1 & -2 & 5 \end{array} \right]$

단계 7: $R_1 \to R_1 - \frac{1}{2} R_2$ 로 두 번째 열의 첫 번째 행 성분을 소거한다.

$\left[ \begin{array}{ccc|ccc} 1 & 0 & 0 & 1 & -1 & 2 \\ 0 & 1 & 0 & -1 & 2 & -4 \\ 0 & 0 & 1 & 1 & -2 & 5 \end{array} \right]$

따라서 역행렬은

$A^{-1} = \begin{bmatrix} 1 & -1 & 2 \\ -1 & 2 & -4 \\ 1 & -2 & 5 \end{bmatrix}$

이다. 검증: $A A^{-1}$ 을 직접 계산하여 단위 행렬이 되는지 확인할 수 있다.

6. 알고리즘의 계산 복잡도

가우스-조르단 소거법의 총 연산량은 $O(n^3)$ 이다. 구체적으로 약 $n^3$ 번의 곱셈과 $n^3$ 번의 덧셈이 요구된다. 일반 가우스 소거법과 후진 대입을 결합한 시스템 풀이가 약 $\frac{2}{3} n^3$ 인 데 비해, 가우스-조르단 소거법은 약간 더 많은 연산을 요구한다. 그러나 모든 우변에 대해 동일한 분해를 재사용하지 않고 직접 역행렬을 얻는다는 점에서 의미가 있다.

7. 피벗팅의 중요성

부분 피벗팅(partial pivoting)은 가우스-조르단 소거법의 수치적 안정성을 보장하는 핵심 절차이다. 피벗 값이 매우 작거나 0인 경우 다음의 문제가 발생한다.

0인 피벗: 해당 열의 정규화 단계에서 0으로 나누는 연산이 발생한다.
작은 피벗: 정규화 후 다른 행의 성분이 매우 커져 수치 오차가 증폭된다.

부분 피벗팅은 매 단계에서 가장 큰 절댓값을 가지는 행을 피벗으로 선택함으로써 이러한 문제를 방지한다. 더 정교한 완전 피벗팅(complete pivoting)은 행과 열을 모두 교환하여 가장 큰 피벗을 선택하지만, 추가 연산 비용으로 인해 실용적으로 부분 피벗팅이 표준으로 사용된다.

8. 특이 행렬의 검출

가우스-조르단 환원 과정에서 특정 단계의 피벗 후보가 모두 0이면 행렬은 특이이며 역행렬이 존재하지 않는다. 알고리즘은 이 경우를 명시적으로 검출하고 계산을 중단한다.

수치적으로는 피벗의 절댓값이 사전에 정의된 임계값(예: $10^{-12}$ 또는 $\epsilon \cdot \|A\|$ ) 미만일 때 특이로 간주한다. 이는 부동 소수점 연산의 한계로 인해 정확한 0이 거의 발생하지 않기 때문이다.

9. 다른 역행렬 계산 방법과의 비교

방법	계산 복잡도	수치 안정성	비고
수반 공식	$O(n!)$ 또는 $O(n^4)$	낮음	작은 행렬과 기호 계산에 적합
가우스-조르단	$O(n^3)$	중간 (부분 피벗팅 시)	표준 절차, 직관적
LU 분해	$O(n^3)$	중간	다중 우변 재사용에 유리
QR 분해	$O(n^3)$	높음	병조건 행렬에 적합
SVD	$O(n^3)$	매우 높음	의사 역행렬 계산에 사용

가우스-조르단 소거법은 알고리즘의 단순성과 직관성 면에서 우수하며, 행렬식과 역행렬을 동시에 얻을 수 있다는 장점이 있다. 그러나 대규모 또는 병조건 시스템에서는 LU나 QR 분해 기반의 방법이 더 선호된다.

10. 동시에 얻는 부수적 정보

가우스-조르단 소거법을 수행하면서 다음의 정보를 부수적으로 얻을 수 있다.

1. 행렬식: 사용된 행 교환의 횟수 $s$ 와 정규화 시 사용된 피벗의 곱 $p_1, p_2, \ldots, p_n$ 으로부터 $\det(A) = (-1)^s \prod_i p_i$ 이다.

2. 랭크: 환원 과정에서 0이 아닌 피벗의 개수가 $A$ 의 랭크이다. 정방 행렬이 가역이려면 랭크가 $n$ 이어야 한다.

3. 영 공간 (특이 행렬의 경우): 환원이 완료된 RREF 형태에서 자유 변수에 대응하는 열로부터 영 공간의 기저가 직접 추출된다.

11. 로봇공학에서의 응용

11.1 동차 변환 행렬과 좌표 변환의 일관성 검증

복잡한 좌표 변환의 합성 결과로 얻어진 4 $\times$ 4 행렬이 유효한 동차 변환인지 검증할 때, 그 역행렬을 계산하여 동차 변환의 구조 (회전 부분 직교, 마지막 행이 $[0, 0, 0, 1]$ )를 만족하는지 확인하는 데 사용된다.

11.2 캘리브레이션 행렬의 역계산

카메라-로봇 캘리브레이션, 손-눈 캘리브레이션 등에서 얻어진 행렬을 역으로 계산할 때 가우스-조르단 소거법이 표준 절차로 사용된다. 특히 작은 차원의 행렬과 명시적 검증이 필요한 경우에 적합하다.

11.3 작은 시스템의 닫힌 형식 풀이

평면 매니퓰레이터의 역기구학, 단순한 칼만 필터의 갱신 등에서 발생하는 2 $\times$ 2 또는 3 $\times$ 3 시스템의 풀이는 가우스-조르단 소거법의 결과를 명시적 코드로 펼쳐 구현할 수 있다.

11.4 교육적 도구

가우스-조르단 소거법은 그 절차의 직관성과 시각성으로 인해 로봇공학 교육에서 행렬의 가역성과 역행렬의 의미를 가르치는 데 표준 도구로 사용된다. 학생이 단계별로 행 환원을 추적함으로써 행렬의 구조와 가역성의 관계를 직접 체득할 수 있다.

11.5 수치 검증과 디버깅

대규모 시스템 풀이의 결과를 검증할 때, 작은 부분 시스템에 대해 가우스-조르단 소거법을 손으로 또는 단계별로 추적하여 결과를 확인하는 것이 표준적인 디버깅 기법이다.

11.6 기본 행렬의 명시적 표현

기본 행 연산을 행렬 곱셈으로 표현하는 기본 행렬의 개념은 가우스-조르단 절차에서 가장 명확히 드러나며, 이는 LU 분해의 이론적 기초가 된다. 로봇 동역학 시뮬레이션의 LDLT 분해 등도 같은 원리에 기반한다.

참고문헌

Strang, G. (2023). Introduction to Linear Algebra (6th ed.). Wellesley-Cambridge Press.
Golub, G. H., & Van Loan, C. F. (2013). Matrix Computations (4th ed.). Johns Hopkins University Press.
Trefethen, L. N., & Bau, D. (1997). Numerical Linear Algebra. SIAM.
Anton, H., & Rorres, C. (2014). Elementary Linear Algebra (11th ed.). Wiley.

Version: 1.0