가우스 소거법
정의
가우스 소거법(또는 가우스-조던 소거법)은 선형 방정식의 연립 방정식을 행렬 형태로 나타낸 뒤, 일련의 행 연산을 통해 행 사다리꼴 형태(또는 감소 행 사다리꼴 형태)로 변환함으로써 해를 구하는 알고리즘이다. 이 방법은 독일의 수학자 카를 프리드리히 가우스의 이름을 따서 명명되었다.
주요 절차
-
증강 행렬 구성
- 연립 방정식 $A\mathbf{x} = \mathbf{b}$를 계수 행렬 $A$와 상수벡터 $\mathbf{b}$를 결합한 증강 행렬 $[A \mid \mathbf{b}]$로 표현한다.
-
전진 소거(Forward Elimination)
- 첫 번째 열을 기준으로 피봇(pivot) 요소를 선택하고, 해당 피봇 행을 이용해 아래 행들의 해당 열 요소를 0으로 만든다.
- 다음 열로 이동하여 동일한 과정을 반복한다. 이 과정이 완료되면 행 사다리꼴(Upper Triangular) 형태가 된다.
-
후진 대입(Back Substitution)
- 최상위 행부터 시작하여, 이미 구해진 변수 값을 이용해 아래 행의 미지수를 차례로 구한다.
- 혹은 가우스-조던 소거법을 사용하면 전진 소거와 동시에 아래 행도 0으로 만들고, 최종적으로 대각선이 1인 단위 행렬 형태로 변환한다(Reduced Row Echelon Form).
-
해 결정
- 행 사다리꼴 형태에서 각 변수에 대한 식을 풀어 해를 구한다.
- 행이 모두 0이면서 오른쪽 항이 0이 아닌 경우(예: $[0\ 0\ 0 \mid c], c eq0$)는 해가 존재하지 않는다.
- 자유 변수가 존재하면 무한히 많은 해가 존재한다.
역사 및 배경
가우스 소거법은 19세기 초 가우스가 행렬 연산을 체계화하면서 발전하였다. 이후 독일 수학자 요한네스 요단(Johannes J. J. J. Jordan)이 전진·후진 과정을 결합한 ‘가우스-조던 소거법’을 제시하였다. 현대 선형대수학 및 수치 해석에서는 이 알고리즘이 기본적인 시스템 해법으로 자리 잡고 있다.
응용 분야
- 수치 해석: 선형 시스템, 선형 회귀, 최소 제곱 해법 등에서 직접적인 해 구하거나 초기값 제공.
- 컴퓨터 과학: 그래프 이론(연결성 판단), 네트워크 흐름, 전기 회로 해석 등.
- 물리학·공학: 구조 해석, 전기·전자 회로, 제어 시스템 설계 등에서 연립 방정식 풀이.
- 통계학: 다변량 통계 모델(예: 다중 회귀)에서 매개변수 추정.
계산 복잡도
일반적인 경우 $n \times n$ 행렬에 대해 시간 복잡도는 $\mathcal{O}(n^{3})$이며, 메모리 복잡도는 $\mathcal{O}(n^{2})$이다. 대형 희소 행렬에 대해서는 특수화된 변형(예: LU 분해, 스파스 가우스 소거법)이 사용된다.
제한 사항
- 수치적 불안정성: 피봇 선택이 부적절하면 부동소수점 연산에서 큰 오차가 발생할 수 있다. 이를 방지하기 위해 부분 피봇팅(Partial Pivoting)이나 전면 피봇팅(Full Pivoting)이 적용된다.
- 복소수·정수 계수에 대해 정확한 해를 얻기 위해서는 기호 연산(예: 가우스 소거법의 정수형 변형)이나 유리수 연산이 필요할 수 있다.
관련 개념
- LU 분해 (LU Decomposition)
- QR 분해 (QR Decomposition)
- 행렬식(determinant)과 역행렬(inverse matrix) 계산
- 행렬의 계수(rank)와 자유 변수(free variable) 개념
참고 문헌
- G. Strang, Linear Algebra and Its Applications, 5th ed., Cengage Learning, 2016.
- T. A. Davis, Direct Methods for Sparse Linear Systems, SIAM, 2006.
본 서술은 객관적인 백과사전 및 학술 자료에 기반한 내용이며, 확인되지 않은 추정이나 허위 정보는 포함하지 않았다.
