가우스 소거법과 연립일차방정식 해법
연립일차방정식 \(A \mathbf{x} = \mathbf{b}\)의 해를 구하는 전통적이고도 강력한 방법 중 하나가 바로 가우스 소거법(Gaussian Elimination)이다. 가우스 소거법은 계수행렬과 상수항을 함께 다루는 증분행렬(augmented matrix)에 일련의 행 연산(row operation)을 적용하여, 방정식을 단계적으로 단순화한다. 이를 통해 해의 유일성, 무수히 많은 해, 해가 없는 경우 등을 명확히 판별할 수 있으며, 실제 해를 계산하는 과정도 체계적으로 진행된다.
정의 1. (행 연산과 증분행렬)
연립일차방정식 \[ A \mathbf{x} = \mathbf{b} \] 에 대하여, 계수행렬 \(A\)와 상수항 벡터 \(\mathbf{b}\)를 옆으로 나란히 붙인 행렬 \[ [A \mid \mathbf{b}] \] 를 증분행렬(augmented matrix)이라 한다. 이때 가우스 소거법은 증분행렬에 다음과 같은 행 연산(row operation)을 반복 적용하여, 방정식을 점차 간단한 형태로 만드는 절차이다.
행 연산에는 세 가지 유형이 있다.
- Ri ↔ Rj : 두 행을 맞교환(swap)한다.
- Ri ← k Ri : 어떤 행을 0이 아닌 상수로 곱한다.
- Ri ← Ri + k Rj : 어떤 행에 다른 행의 배수를 더한다.
이러한 행 연산은 연립방정식 전체의 해 집합을 바꾸지 않거나, 해가 유일하다면 이를 쉽게 다시 조정할 수 있다는 점에서, 해석적 타당성을 지닌다. 결과적으로 행 연산을 통해 얻어진 최종 증분행렬에서 방정식의 해를 직접 읽어낼 수 있다.
핵심 아이디어는, 여러 개의 방정식을 동시에 다루면서 “계수행렬을 삼각 형태 또는 더 단순한 형태로 만드는 것”이다. 예를 들어, 3개의 미지수를 갖는 3×3 계수행렬이 주어졌다면, 가우스 소거법을 통해 계수행렬을 상삼각행렬(upper triangular form)이나 계단형(row echelon form)으로 바꾼 뒤, 뒤에서부터 해를 계산(대입)하는 식으로 해법을 진행한다. 이 과정을 전진 소거(forward elimination)와 후진 대입(back substitution)이라고 부르기도 한다.
정리 1. (가우스 소거법의 유효성)
연립일차방정식 \(\displaystyle A \mathbf{x} = \mathbf{b}\) 에 대하여 증분행렬 \(\displaystyle [A \mid \mathbf{b}]\) 에 적절한 행 연산을 반복 적용하면, 다음 두 가지 결과 중 하나가 나온다.
- 해가 존재하는 경우: 축약된 계단형(reduced row echelon form)에서 미지수를 직접 풀어낼 수 있으며, 유일해인지 무수히 많은 해를 갖는지 판별 가능하다.
- 해가 없는 경우: 일정 단계에서 모순된 형태(예: \(0 = 1\)과 같이 말이 안 되는 식)가 드러나므로, 해가 존재하지 않음을 알 수 있다.
이는 증분행렬에 적용되는 행 연산이 본질적으로 “동일한 해 집합”을 유지하거나, 해가 유일한 경우에는 행 교환을 통해서도 해를 복원 가능하다는 점에 기인한다. 따라서 행 연산 과정에서 해의 구조가 바뀌지 않는다는 점이 가우스 소거법의 유효성을 뒷받침한다.
이론적 관점에서는 행렬의 랭크(rank)를 사용하여 해의 존재성을 판별할 수도 있지만, 실질적인 계산 측면에서 가우스 소거법은 모든 단계가 단순한 사칙연산으로 이루어져 있어, 큰 규모의 문제(고차원)까지도 범용적으로 해석할 수 있게 해 준다.
보기 1.
다음 3×3 연립일차방정식을 가우스 소거법으로 풀어 보자.
\[ \begin{cases} 2x_1 + x_2 - x_3 \;=\; 1, \\ x_1 \;-\; 3x_2 + 2x_3 \;=\; 2, \\ 3x_1 + 2x_2 + 4x_3 \;=\; 7. \end{cases} \]
먼저 증분행렬을 구성한다.
\[ [A \mid \mathbf{b}] = \left[ \begin{array}{ccc|c} 2 & 1 & -1 & 1 \\ 1 & -3 & 2 & 2 \\ 3 & 2 & 4 & 7 \end{array} \right]. \]
- R1과 R2를 맞교환(R1 ↔ R2)하여 계산 편의 확보: \[ \left[ \begin{array}{ccc|c} 1 & -3 & 2 & 2 \\ 2 & 1 & -1 & 1 \\ 3 & 2 & 4 & 7 \end{array} \right]. \]
- R2 ← R2 - 2R1: \[ \begin{aligned} R_2 &\leftarrow (2,1,-1,1) - 2 \cdot (1,-3,2,2)\\ &\;=\; (2 - 2,\; 1 + 6,\; -1 - 4,\; 1 - 4)\\ &\;=\; (0,\; 7,\; -5,\; -3). \end{aligned} \] \[ \left[ \begin{array}{ccc|c} 1 & -3 & 2 & 2 \\ 0 & 7 & -5 & -3 \\ 3 & 2 & 4 & 7 \end{array} \right]. \]
- R3 ← R3 - 3R1: \[ \begin{aligned} R_3 &\leftarrow (3,2,4,7) - 3 \cdot (1,-3,2,2)\\ &\;=\; (3 - 3,\; 2 + 9,\; 4 - 6,\; 7 - 6)\\ &\;=\; (0,\; 11,\; -2,\; 1). \end{aligned} \] \[ \left[ \begin{array}{ccc|c} 1 & -3 & 2 & 2 \\ 0 & 7 & -5 & -3 \\ 0 & 11 & -2 & 1 \end{array} \right]. \]
- R3 ← R3 - \(\tfrac{11}{7}\)R2 (R2가 7이므로 활용): \[ \begin{aligned} R_3 &\leftarrow (0,11,-2,1) - \frac{11}{7} \cdot (0,7,-5,-3) \\ &= \bigl(0,\, 11 - 11,\; -2 - \bigl(-\tfrac{55}{7}\bigr),\; 1 - \bigl(-\tfrac{33}{7}\bigr)\bigr)\\ &= \bigl(0,\; 0,\; -2 + \tfrac{55}{7},\; 1 + \tfrac{33}{7}\bigr)\\ &= \Bigl(0,\; 0,\; -\tfrac{14}{7} + \tfrac{55}{7},\; \tfrac{7}{7} + \tfrac{33}{7}\Bigr)\\ &= \bigl(0,\; 0,\; \tfrac{41}{7},\; \tfrac{40}{7}\bigr). \end{aligned} \] \[ \left[ \begin{array}{ccc|c} 1 & -3 & 2 & 2 \\ 0 & 7 & -5 & -3 \\ 0 & 0 & \frac{41}{7} & \frac{40}{7} \end{array} \right]. \]
- R3 ← \(\tfrac{7}{41}\) R3 하여 주대각원소(pivot)를 1로 만드는 작업(필요할 경우): \[ R_3 \leftarrow (0,0,1,\; \tfrac{40}{41}). \] \[ \left[ \begin{array}{ccc|c} 1 & -3 & 2 & 2 \\ 0 & 7 & -5 & -3 \\ 0 & 0 & 1 & \frac{40}{41} \end{array} \right]. \]
이제 \(\displaystyle x_3 = \tfrac{40}{41}\)이 되고, R2와 R1를 역방향으로 대입(back substitution)하면, \(x_2, x_1\)을 차례로 구해낼 수 있다. 이런 방식으로 가우스 소거법을 이용하여 해(\(x_1, x_2, x_3\))를 직접 도출한다.
이처럼 가우스 소거법은 행렬 연산을 통해 연립일차방정식을 단계적으로 단순화하는 매우 효율적인 알고리즘이다. 이후 배우게 될 가우스-조르단 소거법(Gauss-Jordan Elimination)은 추가적인 연산을 통해 증분행렬을 축약된 계단형(RREF)으로 만들어, 미지수 값이 즉시 읽히도록 하는 방법이다. 두 방법 모두 기본 아이디어는 같으며, 규모가 큰 문제에서도 빠르게 해를 구할 수 있도록 설계되어 있다.
가우스-조르단 소거법(Gauss-Jordan Elimination)
가우스-조르단 소거법은 가우스 소거법을 한 단계 더 발전시킨 방법으로, 연립일차방정식을 풀기 위해 증분행렬을 축약된 계단형(Reduced Row Echelon Form, RREF)까지 변형하는 절차를 말한다. 이를 통해 최종 행렬에서 미지수를 곧바로 읽어낼 수 있으며, 해가 여러 개 있거나(무수히 많을 경우) 아예 존재하지 않는 경우 역시 직관적으로 판별 가능해진다.
정의 2. (축약된 계단형, RREF)
증분행렬 축약된 계단형(Reduced Row Echelon Form)이란, 다음 조건들을 모두 만족하는 행렬을 말한다.
- 모든 영행(행이 전부 0인 행)은 행렬의 맨 아래쪽에 위치한다.
- 행렬 내의 모든 피벗(pivot) 원소는 1이며, 그 열에서는 피벗을 제외한 모든 원소가 0이다.
- 한 행의 피벗은 그 위쪽 행의 피벗보다 오른쪽 열에 위치한다(계단 형태).
가우스-조르단 소거법은 행 연산을 통해 행렬을 정확히 이 형태로 만들기 때문에, 최종 변형 결과만 보고도 각 미지수의 해를 직접 확인할 수 있다.
축약된 계단형을 기약행사다리꼴이라고 부르기도 한다.
가우스-조르단 소거법과 가우스 소거법과의 차이점은 후진 대입(back substitution) 과정마저 행 연산으로 대체한다는 데 있다. 가우스 소거법에서는 보통 상삼각형 형태로 만든 뒤, 위쪽으로 거슬러 올라가면서 미지수를 대입·계산한다. 반면 가우스-조르단 소거법은 필요한 모든 행 연산을 수행하여, 이미 각 미지수를 대표하는 축(pivot) 열 외의 모든 항이 0이 되도록 만들기 때문에, 추가적인 대입 과정 없이도 해를 바로 읽어낼 수 있다.
정리 2. (가우스-조르단 소거법의 알고리즘)
연립일차방정식 \(A \mathbf{x} = \mathbf{b}\)가 주어졌다고 하자. 증분행렬 \([A \mid \mathbf{b}]\)에 다음 단계들을 반복 적용한다.
- 가능하면 피벗 열을 정하여, 해당 열에서 맨 위(또는 현재 소거 중인 ‘윗행’)의 행을 피벗 행으로 선택한다.
- 피벗 행이 될 행을 교환하여 맨 위로 올린 뒤, 피벗이 1이 되도록 행 전체를 적절한 상수로 나눈다.
- 피벗 열에서 피벗을 제외한 모든 원소를 0으로 만들도록, 다른 행에 행 연산(Ri ← Ri + k Rpivot)을 실행한다.
- 피벗을 잡은 다음 행으로 이동하여, 위 과정을 반복한다.
모든 열(또는 행)을 순회하여 가능한 모든 피벗을 세운 후에는, 최종 행렬이 축약된 계단형(RREF)이 된다. 이때, 미지수 \(\mathbf{x}\)의 값(혹은 여러 개의 해 구조)을 바로 읽어낼 수 있다.
보기 2.
다음 연립방정식을 가우스-조르단 소거법으로 풀어 보자.
\[ \begin{cases} x_1 + 2x_2 - x_3 = 2, \\ 2x_1 + 5x_2 + x_3 = 9, \\ -x_1 + 3x_2 + 2x_3 = 4. \end{cases} \]
증분행렬은 \(\displaystyle [A \mid \mathbf{b}] = \begin{pmatrix} 1 & 2 & -1 & 2\\ 2 & 5 & 1 & 9\\ -1 & 3 & 2 & 4 \end{pmatrix} \). 가우스-조르단 소거법을 간단히 진행해 보면 다음과 같다 (단계마다 주요 행 연산만 표시).
- 첫 번째 행의 피벗은 이미 1이므로, 이를 기준으로 R2 ← R2 - 2R1, R3 ← R3 + R1 등을 수행하여 첫 열 피벗을 제외한 원소를 0으로 만든다.
- 두 번째 행에서 두 번째 열 피벗을 1로 만들고, 나머지 행의 원소를 0으로 만든다.
- 세 번째 행에서는 가능한 경우 세 번째 열도 피벗을 잡아 1로 만들고, 다른 행에 대하여 해당 열을 0으로 만든다.
최종적으로 증분행렬이 축약된 계단형이 되면, \(\mathbf{x}\)를 바로 읽어낼 수 있다. 예를 들어, 결과가 \[ \begin{pmatrix} 1 & 0 & 0 & 3\\ 0 & 1 & 0 & 1\\ 0 & 0 & 1 & 2 \end{pmatrix} \] 이라면, \(\displaystyle x_1 = 3,\; x_2 = 1,\; x_3 = 2\) 임을 즉시 알 수 있다.
정리하자면, 가우스-조르단 소거법은 가우스 소거법의 변형된 절차로서, “후진 대입” 과정을 추가적인 행 연산만으로 대체하여 축약된 계단형에 도달한다. 이를 통해 큰 규모의 선형시스템을 체계적으로 해결할 수 있으며, 랭크 판별이나 역행렬 계산 등에도 활용된다.
