27.34 가우스 소거법(Gaussian Elimination)과 행 사다리꼴 형식

1. 가우스 소거법의 기본 원리

가우스 소거법(Gaussian elimination)은 연립 일차방정식을 체계적으로 풀기 위한 알고리즘으로, 기본 행 연산을 통해 계수 행렬을 상삼각 형태로 변환한 후 후방 대입법으로 해를 구하는 절차이다. 이 방법의 핵심은 방정식에 허용된 연산을 적용하여 해 집합을 변화시키지 않으면서 시스템을 단순화하는 데 있다.

세 가지 기본 행 연산은 다음과 같으며, 이들은 연립방정식의 해 집합을 보존한다.

두 방정식(행)의 교환: $R_i \leftrightarrow R_j$
한 방정식에 0이 아닌 상수를 곱함: $R_i \leftarrow cR_i$ ( $c \neq 0$ )
한 방정식에 다른 방정식의 상수배를 더함: $R_i \leftarrow R_i + cR_j$

이 연산들이 해 집합을 보존하는 이유는, 각 연산이 가역이기 때문이다. 연산의 결과로 얻은 시스템에 역연산을 적용하면 원래 시스템으로 복원된다.

2. 행 사다리꼴 형식(Row Echelon Form)

행렬이 행 사다리꼴 형식(REF)이라 함은 다음 조건을 만족하는 것이다.

영이 아닌 행은 모두 영 행 위에 위치한다.
각 영이 아닌 행의 선행 원소(leading entry, 피벗)는 바로 위 행의 선행 원소보다 오른쪽에 위치한다.
피벗 아래의 모든 원소는 0이다.

예를 들어 다음은 행 사다리꼴 형식이다 (피벗을 $\boxed{\cdot}$ 로 표시).

$\begin{pmatrix} \boxed{2} & 3 & 1 & 5 \\ 0 & \boxed{1} & -2 & 3 \\ 0 & 0 & 0 & \boxed{4} \\ 0 & 0 & 0 & 0 \end{pmatrix}$

기약 행 사다리꼴 형식(Reduced Row Echelon Form, RREF): REF에 다음 조건이 추가된 형태이다.

각 피벗은 1이다.
피벗이 있는 열에서 피벗 이외의 모든 원소는 0이다.

위 행렬의 RREF는 다음과 같다.

$\begin{pmatrix} 1 & 0 & 7/2 & 0 \\ 0 & 1 & -2 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \end{pmatrix}$

RREF는 주어진 행렬에 대하여 유일하다는 중요한 성질이 있다. REF는 유일하지 않을 수 있지만, RREF는 항상 유일하게 결정된다.

3. 전방 소거 알고리즘

가우스 소거법의 전방 소거(forward elimination) 과정을 단계별로 설명한다.

확대 행렬 $[\mathbf{A} \mid \mathbf{b}]$ 에서 시작하여, 왼쪽부터 오른쪽으로 열을 순회하며 피벗을 설정한다.

$k$ 번째 단계 ( $k = 1, 2, \ldots$ ):

$k$ 열에서 $k$ 행 이하의 원소 중 0이 아닌 원소를 찾는다. 없으면 다음 열로 이동한다.
부분 피벗팅: 절댓값이 가장 큰 원소가 있는 행을 $k$ 행과 교환한다.
$k$ 행 아래의 모든 행 $i$ ( $i > k$ )에 대하여, 승수(multiplier) $m_{ik} = a_{ik}/a_{kk}$ 를 계산하고 $R_i \leftarrow R_i - m_{ik}R_k$ 를 수행한다.

모든 열에 대해 이 과정을 완료하면 행 사다리꼴 형식이 된다.

구체적 예를 살펴보자.

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

$R_2 \leftarrow R_2 - 2R_1$ , $R_3 \leftarrow R_3 + 3R_1$ :

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

$R_3 \leftarrow R_3 + \frac{7}{3}R_2$ :

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

이제 후방 대입으로 풀면: $-2x_3 = -4 \Rightarrow x_3 = 2$ , $-3x_2 = -3 \Rightarrow x_2 = 1$ , $x_1 + 2(1) - 2 = 3 \Rightarrow x_1 = 3$ 이다.

4. 계산 복잡도

$n \times n$ 시스템에 대한 가우스 소거법의 연산 횟수를 분석하자. 전방 소거의 $k$ 번째 단계에서 $(n-k)$ 개의 행 각각에 대하여 $(n-k+1)$ 번의 곱셈과 뺄셈이 필요하다. 총 곱셈 횟수는 다음과 같다.

$\sum_{k=1}^{n-1}(n-k)(n-k+1) = \sum_{j=1}^{n-1}j(j+1) = \frac{n^3 - n}{3} \approx \frac{n^3}{3}$

후방 대입에는 $\frac{n^2}{2}$ 연산이 추가로 필요하다. 따라서 전체 복잡도는 $O(n^3/3)$ 이며, 이는 역행렬 계산( $O(n^3)$ )보다 상수 계수가 작다. 이것이 연립방정식을 풀 때 역행렬을 직접 계산하지 않고 가우스 소거법을 사용하는 이유이다.

확대 행렬의 우변이 $p$ 개의 열 벡터인 경우(즉, $\mathbf{A}\mathbf{X} = \mathbf{B}$ 에서 $\mathbf{B} \in \mathbb{R}^{n \times p}$ ), 전방 소거는 한 번만 수행하고 후방 대입을 $p$ 번 반복하면 된다. 총 복잡도는 $O(n^3/3 + n^2 p/2)$ 이다.

5. 피벗팅 전략

피벗팅은 가우스 소거법의 수치적 안정성을 확보하기 위해 필수적이다.

피벗 없는 경우의 문제점: 피벗 원소가 0이면 나눗셈이 불가능하고, 0에 가까우면 매우 큰 승수가 발생하여 반올림 오차가 증폭된다. 예를 들어, 부동소수점 산술에서 $a_{kk} = 10^{-15}$ 이면 승수 $m_{ik} = a_{ik}/a_{kk} \approx 10^{15}$ 이 되어, 다른 원소에 비해 과도하게 큰 수가 등장하고 유효 자릿수가 소실된다.

부분 피벗팅(Partial Pivoting): 각 단계에서 피벗 열의 $k$ 행 이하 원소 중 절댓값이 가장 큰 원소를 피벗으로 선택하여 행을 교환한다. 이를 통해 모든 승수 $|m_{ik}| \leq 1$ 이 보장된다. 부분 피벗팅의 추가 비용은 $O(n^2/2)$ 의 비교 연산으로, 전체 복잡도에 비해 무시할 수 있다. 실용적으로 대부분의 경우 부분 피벗팅만으로 충분한 수치적 안정성이 달성된다.

완전 피벗팅(Complete Pivoting): 피벗 위치 아래와 오른쪽의 모든 원소에서 절댓값이 가장 큰 원소를 선택하여 행과 열 모두를 교환한다. 이론적으로 더 안정적이나, 추가 비용이 $O(n^3/3)$ 으로 소거법 자체와 같은 차수이므로 실용적 이점이 제한적이다.

6. LU 분해와의 관계

가우스 소거법은 본질적으로 LU 분해를 수행하는 과정이다. 전방 소거에서 사용한 승수들을 기록하면 하삼각 행렬 $\mathbf{L}$ 을 구성할 수 있다.

$l_{ij} = \begin{cases} m_{ij} & \text{if } i > j \\ 1 & \text{if } i = j \\ 0 & \text{if } i < j \end{cases}$

전방 소거의 결과인 상삼각 행렬이 $\mathbf{U}$ 이다. 이로써 $\mathbf{A} = \mathbf{L}\mathbf{U}$ 가 성립한다. 부분 피벗팅을 적용한 경우 $\mathbf{P}\mathbf{A} = \mathbf{L}\mathbf{U}$ 이며, 여기서 $\mathbf{P}$ 는 행 교환을 기록한 순열 행렬이다.

LU 분해의 장점은 한 번의 분해로 여러 우변 벡터에 대한 해를 효율적으로 구할 수 있다는 것이다. 분해 후 $\mathbf{L}\mathbf{y} = \mathbf{P}\mathbf{b}$ (전방 대입), $\mathbf{U}\mathbf{x} = \mathbf{y}$ (후방 대입)로 각각 $O(n^2)$ 에 풀 수 있다.

7. 딥러닝에서의 연립방정식 풀이

딥러닝에서 연립방정식을 직접 푸는 상황은 제한적이지만, 관련 수치 기법은 여러 맥락에서 활용된다.

정규 방정식의 해: 선형 회귀에서 $(\mathbf{X}^\top\mathbf{X})\mathbf{w} = \mathbf{X}^\top\mathbf{y}$ 는 대칭 양의 정부호 시스템이며, 촐레스키 분해를 적용하면 가우스 소거법보다 약 2배 효율적이다.

사전 조건부 반복법(Preconditioned Iterative Methods): 대규모 시스템에서는 직접법 대신 반복법이 사용된다. 사전 조건부 행렬 $\mathbf{M} \approx \mathbf{A}$ 의 불완전 LU 분해(incomplete LU factorization)가 사전 조건부로 활용되며, 이는 가우스 소거법의 근사 버전이다. 반복법은 행렬-벡터 곱만 필요하므로 희소 행렬에 특히 적합하며, 그래프 신경망(GNN)이나 물리 시뮬레이션 기반 학습에서 활용된다.

자동 미분과 선형 시스템: 자동 미분 시스템에서 $\mathbf{A}\mathbf{x} = \mathbf{b}$ 의 해 $\mathbf{x}$ 에 대한 기울기를 구할 때, 수반 방정식(adjoint equation) $\mathbf{A}^\top\boldsymbol{\lambda} = \frac{\partial\mathcal{L}}{\partial\mathbf{x}}$ 을 풀어야 한다. 이때 원래의 LU 분해를 재활용할 수 있으며, $\mathbf{L}^\top\mathbf{U}^\top\boldsymbol{\lambda} = \frac{\partial\mathcal{L}}{\partial\mathbf{x}}$ 로 추가 분해 없이 $O(n^2)$ 에 풀 수 있다.