가우스 소거법(Gaussian Elimination)은 선형 방정식 시스템을 풀기 위한 가장 기본적이고 강력한 방법입니다. 이 방법은 복잡한 n×n 시스템을 차례로 단순한 삼각행렬(upper triangular form)로 변환한 후, 후방 대입(back‑substitution)을 통해 해를 구합니다. 또한, 알고리즘의 연산 비용과 피봇에 0이 나타날 때 발생하는 “소거 중단(Breakdown)” 현상을 이해하는 것은 수치해석과 시스템의 특이성을 파악하는 데 매우 중요합니다.
문제 설정과 기본 절차
예제로 다루는 시스템은 다음과 같습니다.
2u + v + w = 5
4u − 6v = −2
−2u + 7v + 2w = 9
이 시스템은 미지수 u, v, w에 대해 유일한 해 (1, 1, 2)를 갖습니다. 가우스 소거법의 목표는 다음 두 단계로 문제를 해결하는 것입니다.
-
전진 소거 (Forward Elimination):
각 단계마다 피봇(pivot)을 선택하여, 해당 피봇 아래의 원소들을 0으로 만듭니다.
- 예를 들어, 첫 번째 방정식의 u 계수 2를 피봇으로 선택하고,
- 두 번째 행에서는 첫 번째 방정식의 2배를 빼서 u항을 제거하고,
- 세 번째 행에서는 첫 번째 방정식의 –1배(즉, 더하는 효과)를 사용해 u항을 제거합니다.
그 결과, u항이 모두 소거된 두 개의 새로운 방정식, 즉
−8v − 2w = −12, 8v + 3w = 14
가 만들어집니다. -
후방 대입 (Back‑substitution):
전진 소거를 통해 시스템이 상삼각행렬로 변환되면, 가장 단순한 방정식(예, w = 2)부터 시작하여 위로 올라가며 다른 미지수를 차례로 구합니다.
최종적으로 얻은 상삼각 시스템은 다음과 같습니다.
(1) 2u + v + w = 5 (2) −8v − 2w = −12 (3) w = 2
후방 대입을 통해 w = 2, 그 다음 (2)에서 v = 1, 마지막으로 (1)에서 u = 1을 얻어 해 (1, 1, 2)를 구합니다.
연산 비용 분석
가우스 소거법의 전진 소거 단계에서는 각 열마다 피봇 아래의 원소들을 0으로 만드는 연산이 필요합니다.
- 첫 번째 열:
n개의 방정식 중 첫 행은 피봇 역할을 하고, 나머지 n–1개의 행에 대해 피봇 행에 있는 n개의 원소에 대해 연산(나눗셈 및 곱셈‑뺄셈)이 이루어지므로 약 n×(n–1) = n² – n 번의 연산이 필요합니다. - 이후 단계:
남은 k개의 행에 대해 같은 방식으로 약 (k² – k) 번의 연산이 필요합니다. - 전체 연산 횟수:
이를 k = 1부터 n까지 더하면
∑ₖ₌₁ⁿ (k² – k) = [n(n+1)(2n+1)/6] – [n(n+1)/2] = (n³ – n)/3
즉, 대략 (1/3)n³ 번의 연산이 필요합니다. 이는 시스템 규모가 커질수록 연산 비용이 n³에 비례하여 증가함을 보여줍니다
Breakdown
가우스 소거법은 각 단계마다 피봇을 선택하여 소거를 진행하는데, 만약 피봇 자리에서 0이 나타난다면 알고리즘이 중단될 수 있습니다.
- 임시적 소거 중단:
예를 들어, 첫 행 첫 열의 계수가 0이라면 u를 제거할 수 없으므로 행 교환(row exchange)을 통해 다른 행의 0이 아닌 값으로 피봇을 대체할 수 있습니다. 이 경우 시스템은 여전히 비특이(nonsingular)하며, 유일한 해가 존재합니다.
- 치명적 소거 중단:
어떤 경우에는 행 교환을 해도 피봇 자리에서 0을 피할 수 없습니다. 예를 들어, 방정식들이 서로 비례하여 두 번째 피봇 자리에서 0이 발생하는 경우, 해가 아예 없거나 무한히 많은 해가 존재하는 특이 시스템(singular system)이 됩니다.
이러한 소거 중단 현상은 알고리즘의 한계를 보여주며, 후에 행 교환 및 특이 시스템 처리 방법(LU 분해, 피봇 재선택 등)으로 보완됩니다.
결론
가우스 소거법은 전진 소거와 후방 대입을 통해 선형 시스템을 효율적으로 풀 수 있는 강력한 방법입니다.
- 전진 소거 단계에서는 각 단계마다 남은 행의 수에 비례하여 약 (k² – k) 번의 연산이 필요하고, 전체 연산 비용은 약 (1/3)n³ 번입니다.
- 후방 대입은 삼각 시스템에서 해를 구하는데 매우 적은 연산만 필요합니다.
- 소거 과정에서 피봇 자리에 0이 나타나는 “소거 중단” 상황은 행 교환 등으로 임시적으로 해결될 수 있지만, 어떤 경우에는 시스템 자체가 특이해져 유일한 해가 존재하지 않음을 의미합니다.
이러한 분석은 단순한 계산 절차를 넘어서, 알고리즘의 효율성, 확장성, 그리고 수치해석에서의 안정성을 이해하는 데 큰 도움을 줍니다. 앞으로 LU 분해 등 보다 심화된 기법으로 확장되는 기반을 마련하는 중요한 단계라고 할 수 있습니다.
