가우스 소거법

수치해석 시뮬레이션 마지막 수정: 2026-07-08 04:11:20

1. 개요[편집]

연립방정식? 그냥 위에서 아래로 하나씩 소거하면 되는 거 아니었어? 응, 맞아. 근데 그게 O(n^3)이라서 문제야.

가우스 소거법(Gaussian elimination)은 선형 연립방정식 $A\mathbf{x} = \mathbf{b}$ 를 풀기 위해 계수행렬을 기본 행 연산(elementary row operation)으로 상삼각행렬(upper triangular matrix) 꼴로 만든 뒤, 후진대입(back substitution)으로 해를 구하는 대표적인 직접법(direct method)이다. 중학교 때 배운 “가감법”을 행렬로 체계화한 것이라고 보면 되는데, 이 단순해 보이는 알고리즘이 수치해석에서 희소행렬 이전 시대를 지배한 만능키였다.

이름은 카를 프리드리히 가우스(Carl Friedrich Gauss)에게서 왔지만, 사실 방법 자체는 기원전 중국 수학서 구장산술에도 등장한다.¹ 가우스는 이걸 최소제곱법 계산에 써먹으며 유명해졌을 뿐. 어쨌든 오늘날 거의 모든 유한요소법·유한체적법 솔버의 밑바닥 어딘가에는 이 소거 과정이 LU 분해의 탈을 쓰고 돌아가고 있다.

2. 알고리즘[편집]

$n \times n$ 행렬에 대한 가우스 소거법은 두 단계로 나뉜다. 첫째는 전진 소거(forward elimination), 둘째는 후진 대입(back substitution)이다.

전진 소거에서는 $k$ 번째 열 아래쪽 성분들을 0으로 만든다. $k$ 번째 행을 기준(pivot row)으로 삼아 $i > k$ 인 각 행에서 배수를 빼주는데, 그 배수(multiplier)는 다음과 같다.

m_{ik} = \frac{a_{ik}}{a_{kk}}, \qquad a_{ij} \leftarrow a_{ij} - m_{ik}\,a_{kj}

이 과정을 $k = 1$ 부터 $n-1$ 까지 반복하면 행렬이 상삼각행렬 $U$ 가 된다. 우변 벡터 $\mathbf{b}$ 도 같이 갱신해준다.

전진 소거가 끝나면 마지막 방정식은 미지수가 하나뿐이므로 바로 풀 수 있다. 이걸 위로 거슬러 올라가며 대입하는 것이 후진 대입이다.

x_i = \frac{1}{u_{ii}}\left( b_i - \sum_{j=i+1}^{n} u_{ij}\,x_j \right), \qquad i = n, n-1, \dots, 1

여기서 눈치 빠른 사람은 알아챘을 것이다. 저 배수 $m_{ik}$ 값들을 버리지 않고 하삼각 자리에 차곡차곡 저장하면 그게 바로 LU 분해다. 가우스 소거법과 LU 분해는 사실상 같은 계산의 두 얼굴이다.

3. 부분 피벗팅[편집]

순진하게 위 공식을 그대로 돌리면 언젠가 큰코다친다. 피벗 $a_{kk}$ 가 0이면 0으로 나누는 참사가 벌어지고, 0은 아니어도 아주 작으면 배수 $m_{ik}$ 가 폭발해서 반올림 오차(round-off error)가 걷잡을 수 없이 증폭된다.² 그래서 실무에서는 반드시 부분 피벗팅(partial pivoting)을 쓴다.

부분 피벗팅은 $k$ 번째 소거 단계에서 $k$ 열의 대각 아래 성분 중 절댓값이 가장 큰 놈을 찾아 그 행을 피벗 행으로 끌어올리는 것이다.

p = \arg\max_{i \ge k} |a_{ik}|

이렇게 하면 배수의 절댓값이 항상 1 이하로 유지되어 수치적으로 안정해진다. 행 교환 정보는 치환행렬(permutation matrix) $P$ 로 기록되며, 그래서 정확한 표현은 $PA = LU$ 가 된다. 완전 피벗팅(complete pivoting)은 열까지 교환해 이론적으로 더 안정하지만, 매 단계 전체를 뒤지는 비용 탓에 실전에서는 거의 안 쓴다. 부분 피벗팅으로도 대부분의 실제 문제는 충분히 안정적으로 풀린다는 게 검증 및 확인을 거친 국룰이다.

4. 계산복잡도[편집]

가우스 소거법의 악명 높은 지점이 바로 여기다. 전진 소거의 각 단계에서 필요한 곱셈·덧셈 연산 수를 다 합치면 다음과 같다.

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

즉 지배적인 항이 $O(n^3)$ 이다. 후진 대입은 $O(n^2)$ 이라 소거 앞에서는 반올림 오차 수준으로 무시된다. 이 세제곱이 왜 무서운가 하면, 미지수가 10배 늘면 계산량은 1000배 늘기 때문이다.

미지수 $n$	대략 연산 수 ( $\tfrac{2}{3}n^3$ )	체감
$10^3$	약 $6.7 \times 10^8$	눈 깜짝
$10^4$	약 $6.7 \times 10^{11}$	커피 한 잔
$10^6$	약 $6.7 \times 10^{17}$	인생 끝날 때까지

그래서 전산유체역학이나 구조해석처럼 미지수가 수백만 개인 실제 문제에서는 밀집(dense) 가우스 소거법을 통째로 돌리는 짓은 절대 하지 않는다. 대신 계수행렬이 희소행렬이라는 점을 이용하거나, 아예 직접법을 버리고 반복법과 크리로프 부분공간법으로 갈아탄다. 밀집 소거법은 어디까지나 수백~수천 규모의 부분 문제나 전처리기 내부에서 조용히 쓰인다.

5. 안정성과 한계[편집]

가우스 소거법의 오차 거동은 성장 인자(growth factor)로 분석한다. 부분 피벗팅을 써도 이론적으로는 성장 인자가 $2^{n-1}$ 까지 커질 수 있는 병적인(pathological) 행렬이 존재하지만³, 현실의 공학 문제에서 그런 행렬은 로또 당첨 수준으로 드물다. 그래서 부분 피벗팅 가우스 소거법은 사실상 후방 안정(backward stable)한 알고리즘으로 대접받는다.

진짜 문제는 조건수(condition number)다. 계수행렬 $A$ 의 조건수 $\kappa(A)$ 가 크면(ill-conditioned) 아무리 알고리즘이 안정해도 입력의 작은 오차가 해에서 크게 증폭된다. 이건 알고리즘 탓이 아니라 문제 자체가 삐뚤어진 것이므로, 소거법을 아무리 정성껏 돌려도 답이 없다. 이럴 땐 전처리기로 문제를 다듬거나, 문제 정식화 자체를 응력과 변형률 관점에서 다시 봐야 한다.

6. 관련 문서[편집]

구장산술(九章算術) 제8장 “방정(方程)“에 나오는 계산법이 사실상 가우스 소거법과 동일하다. 즉 가우스보다 2천 년 앞선 셈. 수학사에서 이름은 마지막에 만진 사람이 다 가져가는 법이다. ↩
작은 피벗으로 나눈다는 건 큰 수를 만들었다가 다시 빼는 과정을 반복한다는 뜻인데, 부동소수점 세계에서 “큰 수끼리의 뺄셈”은 유효숫자가 증발하는 재앙적 소거(catastrophic cancellation)의 지름길이다. ↩
윌킨슨(Wilkinson)이 제시한 악명 높은 반례 행렬이 있다. 하지만 반세기 넘게 실무에서 이 성장 인자가 문제를 일으킨 사례가 거의 보고되지 않아, “왜 부분 피벗팅은 실전에서 잘 되는가”는 수치해석의 오래된 미스터리로 남아 있었다. ↩