Kwangmin Kim - Ch.2 §2.2 — The Idea of Elimination

1 왜 소거법인가

$Ax = b$ 를 푸는 방법은 이론적으로 여러 가지이다. 그러나 실제 계산에서는 하나의 방법이 압도적으로 쓰인다. 바로 가우스 소거법(Gaussian Elimination)이다.

노트

핵심 아이디어: 소거법(Elimination)

소거법은 $Ax = b$ 를 상삼각행렬 형태 $Ux = c$ 로 변환한다.

\[A \xrightarrow{\text{소거}} U \quad (\text{상삼각행렬})\]

상삼각 구조가 완성되면 후방 대입(Back Substitution)으로 아래에서 위로 미지수를 하나씩 결정할 수 있다.

핵심 연산: $i$ 행에서 $\ell_{ij}$ 배의 $j$ 행을 뺀다 — 이 한 가지 연산만 반복한다.

방법	연산량 ($n \times n$)	실용성
크래머 법칙	$O(n! \cdot n)$	이론 전용
역행렬 직접 계산	$O(n^3)$	보조 도구
가우스 소거법	$\mathbf{O(n^3/3)}$	실전 표준

MATLAB, NumPy, R의 선형 솔버가 내부적으로 소거법(LU 분해)을 사용한다.

2 소거법의 핵심 원리: 왜 방정식을 변형해도 되는가

소거법의 출발점은 단순한 관찰이다.

방정식의 양변에 같은 수를 곱하거나, 두 방정식을 더하거나 빼도 해가 바뀌지 않는다.

이 원리를 정확히 이해하면 소거법의 모든 조작이 자연스럽게 따라온다.

2.1 직관: “참인 문장에서 참인 문장을 빼도 참이다”

방정식 $f(x,y) = c$ 가 성립한다는 것은 $(x, y)$ 가 이 직선 위에 있다는 뜻이다. 두 방정식이 동시에 성립하는 점 $(x^*, y^*)$ 에서는:

\[ a_1 x^* + b_1 y^* = c_1 \quad \text{(방정식 1이 참)} \] \[ a_2 x^* + b_2 y^* = c_2 \quad \text{(방정식 2가 참)} \]

두 등식의 차이도 성립한다:

\[ (a_2 - \ell a_1) x^* + (b_2 - \ell b_1) y^* = c_2 - \ell c_1 \]

해 $(x^*, y^*)$ 는 이 새로운 방정식도 만족한다. 소거는 해를 바꾸지 않는다.

행 그림으로 보면: 소거 후 두 번째 직선의 모양이 바뀌지만, 두 직선의 교점은 그대로이다.

소거 전                    소거 후
3x + 2y = 11   →   8y = 8  (수평선으로 바뀜)
x -  2y = 1        x - 2y = 1 (그대로)

두 직선의 교점 (3, 1)은 변하지 않는다.

2.2 직관: 상삼각행렬이 목표인 이유

소거의 목표는 계수 행렬을 상삼각행렬(Upper Triangular Matrix)로 만드는 것이다.

\[ U = \begin{bmatrix} u_{11} & u_{12} & u_{13} \\ 0 & u_{22} & u_{23} \\ 0 & 0 & u_{33} \end{bmatrix} \]

삼각형 구조가 좋은 이유: 마지막 방정식에 미지수가 하나 $z$ 만 남는다. $z$ 를 구하면 두 번째 방정식에서 $y$ 가 결정된다. $y$ 를 구하면 첫 번째 방정식에서 $x$ 가 결정된다. 아는 것에서 모르는 것으로 순서대로 올라갈 수 있다. 이것이 후방 대입이다.

3 핵심 개념: 피벗과 승수

3.1 피벗 (Pivot) — “무엇으로 나누는가”

피벗(Pivot)은 소거의 각 단계에서 기준이 되는 원소이다. $k$ 번째 단계의 피벗은 소거를 수행하는 행의 $k$ 번째 열 원소이다.

\[\text{피벗}_k = a_{kk}^{(k)} \quad \text{($k-1$ 번 소거 후 드러난 대각 원소)}\]

직관: 피벗은 그 열의 “대표값”이다. 다른 행의 같은 열 원소를 피벗으로 나눠서 승수를 구하고, 그 승수만큼 피벗 행을 빼면 해당 원소가 정확히 0이 된다. 피벗 없이는 나눌 수가 없으므로 소거를 계속할 수 없다.

경고

피벗이 0이면 안 되는 이유

승수 공식은 $\ell_{ij} = (\text{제거할 원소}) / (\text{피벗})$ 이다. 피벗이 0이면 0으로 나누게 되어 승수가 정의되지 않는다. 피벗이 0인 상황은 두 가지이다:

일시적: 그 아래 행에 0이 아닌 원소가 있다면 행 교환으로 새 피벗을 만든다.
영구적: 그 열 전체가 0이면 피벗을 만들 수 없다. 이때 행렬이 특이(Singular)하다.

또한 소거가 완료된 뒤 후방 대입에서도 피벗으로 나눠야 한다($x_k = c_k / u_{kk}$). 피벗이 0이면 나누기가 불가능하다.

피벗들은 소거 전 행렬 $A$ 에서 처음부터 눈에 보이지 않는다. 소거 과정에서 하나씩 드러난다. Strang의 표현: “피벗 1과 4는 원래 시스템에 숨어 있었다. 소거가 그것들을 끄집어냈다.”

3.2 승수 (Multiplier) — “얼마만큼 빼야 0이 되는가”

승수 $\ell_{ij}$는 $i$ 행의 $j$ 열 원소를 정확히 0으로 만들기 위해 $j$ 행에 곱하는 비율이다.

\[\ell_{ij} = \frac{a_{ij}^{(j)}}{a_{jj}^{(j)}} = \frac{\text{제거할 원소 (i행, j열)}}{\text{피벗 (j행, j열)}}\]

직관: “$i$ 행의 $j$ 열 원소를 $j$ 행의 피벗과 같은 비율로 맞춰준다”는 뜻이다. 피벗을 $\ell_{ij}$ 배 하면 $j$ 행 전체가 $\ell_{ij}$ 배가 된다. $i$ 행에서 이것을 빼면 $j$ 열 위치에서 정확히 상쇄가 일어나 0이 된다.

수식으로 확인:

\[ \underbrace{a_{ij}^{(j)}}_{\text{제거 대상}} - \ell_{ij} \cdot \underbrace{a_{jj}^{(j)}}_{\text{피벗}} = a_{ij}^{(j)} - \frac{a_{ij}^{(j)}}{a_{jj}^{(j)}} \cdot a_{jj}^{(j)} = a_{ij}^{(j)} - a_{ij}^{(j)} = 0 \checkmark \]

예: 2행의 $x$ 계수가 3이고 1행의 $x$ 계수(피벗)가 1이면, 1행을 3배 빼야 2행의 $x$ 가 사라진다. 승수 $\ell_{21} = 3/1 = 3$.

소거 연산: $(\text{새 } i\text{행}) \leftarrow (\text{기존 } i\text{행}) - \ell_{ij} \times (j\text{행})$

4 2×2 예시: 소거법의 전 과정

4.1 출발점

\[ \begin{cases} x - 2y = 1 \\ 3x + 2y = 11 \end{cases} \quad \implies \quad A = \begin{bmatrix} 1 & -2 \\ 3 & 2 \end{bmatrix},\; b = \begin{bmatrix} 1 \\ 11 \end{bmatrix} \]

목표: $3x + 2y = 11$ 에서 $x$ 항을 제거하여 $y$ 만 남긴다.

4.2 전방 소거 (Forward Elimination)

피벗: $a_{11} = 1$ (1행 1열의 $x$ 계수)

승수: $\ell_{21} = 3/1 = 3$

“왜 3인가?”: 2행의 $x$ 계수가 3이고, 피벗(1행의 $x$ 계수)이 1이다. 피벗 행을 3배 빼면 2행의 $3x - 3x = 0$ 이 된다.

연산: (2행) $\leftarrow$ (2행) $- 3 \times$ (1행)

\[ \underbrace{(3x + 2y)}_{\text{2행}} - 3 \cdot \underbrace{(x - 2y)}_{\text{1행}} = 3x + 2y - 3x + 6y = 8y \] \[ \underbrace{11}_{\text{우변}} - 3 \cdot \underbrace{1}_{\text{우변}} = 8 \]

\[ \begin{bmatrix} 1 & -2 \\ 3 & 2 \end{bmatrix} \begin{bmatrix} 1 \\ 11 \end{bmatrix} \xrightarrow{R_2 - 3R_1} \begin{bmatrix} 1 & -2 \\ 0 & 8 \end{bmatrix} \begin{bmatrix} 1 \\ 8 \end{bmatrix} \]

두 번째 피벗: $8$. 행렬의 (2,2) 위치에 남은 계수가 두 번째 피벗이다. 이제 상삼각 시스템 $Ux = c$ 가 완성됐다.

\[ \underbrace{\begin{cases} x - 2y = 1 \\ 8y = 8 \end{cases}}_{Ux = c} \]

소거 전후 행 그림의 변화:

소거 전: 두 직선 $x - 2y = 1$ 과 $3x + 2y = 11$ 이 $(3, 1)$ 에서 만난다.
소거 후: 두 번째 직선이 수평선 $8y = 8$ 로 바뀐다. 수평선이므로 $y = 1$ 을 즉시 읽을 수 있다.
교점 $(3, 1)$ 은 바뀌지 않는다. 소거는 해를 바꾸지 않는다.

4.3 후방 대입 (Back Substitution) — 왜 아래에서 위로 푸는가

상삼각행렬의 마지막 방정식에는 미지수가 하나만 남는다. 이것이 핵심이다.

\[ 8y = 8 \implies y = 1 \]

$y$ 가 결정되면 두 번째 방정식(여기서는 첫 번째)에 대입할 수 있다.

\[ x - 2(1) = 1 \implies x = 3 \]

“아래에서 위로”의 직관: 삼각 구조에서 아래 방정식일수록 미지수가 적다. 마지막 행에는 미지수가 1개, 그 위에는 2개, … 이 순서를 따라가면 매 단계에서 미지수가 딱 하나씩 남아 결정된다.

해: $(x, y) = (3, 1)$

4.4 피벗이 달라지면 승수도 달라진다

첫 번째 방정식을 $4x - 8y = 4$ 로 바꿔도 직선은 같다(같은 직선을 4배 한 것). 이 경우:

피벗: $4$
승수: $\ell_{21} = 3/4$

\[ \begin{cases} 4x - 8y = 4 \\ 3x + 2y = 11 \end{cases} \xrightarrow{R_2 - \frac{3}{4}R_1} \begin{cases} 4x - 8y = 4 \\ 8y = 8 \end{cases} \]

피벗과 승수가 달라져도 해는 여전히 $(3, 1)$ 이다. 직선 자체(= 해)는 바뀌지 않았기 때문이다.

5 소거의 실패: 세 가지 시나리오

소거법은 항상 성공하지 않는다. 실패 원인과 결과를 명확히 구분해야 한다.

5.1 시나리오 A: 완전 실패 — 해 없음

\[ \begin{cases} x - 2y = 1 \\ 3x - 6y = 11 \end{cases} \xrightarrow{R_2 - 3R_1} \begin{cases} x - 2y = 1 \\ 0y = 8 \end{cases} \]

$0y = 8$ 은 무슨 뜻인가?

“$0 \cdot y = 8$ 을 만족하는 $y$ 가 있는가?” — 없다. 어떤 $y$ 를 곱해도 $0 \cdot y = 0$ 이므로 $8$ 이 될 수 없다. 이 방정식 자체가 모순이다.

두 번째 피벗이 0이다. 피벗 없이는 소거를 계속할 수 없다 — 이때 소거가 그 불가능성을 드러낸다.

행 그림으로 보면: 두 직선이 평행하다. 기울기가 같고($x - 2y = \text{const}$ 의 구조) 절편이 다르다. 평행선은 만나지 않으므로 해가 없다.

열 그림으로 보면: 열 1 = $(1, 3)^\top$ 과 열 2 = $(-2, -6)^\top = -2 \cdot (1, 3)^\top$ 이 같은 방향이다. 이 두 벡터의 어떤 선형 결합도 이 방향의 직선 위에만 있다. 우변 $b = (1, 11)^\top$ 은 이 직선 위에 없으므로 어떤 결합도 $b$ 를 만들 수 없다 — 해 없음.

5.2 시나리오 B: 완전 실패 — 무한히 많은 해

\[ \begin{cases} x - 2y = 1 \\ 3x - 6y = 3 \end{cases} \xrightarrow{R_2 - 3R_1} \begin{cases} x - 2y = 1 \\ 0y = 0 \end{cases} \]

$0y = 0$ 은 무슨 뜻인가?

$0 \cdot y = 0$ 은 모든 $y$ 에 대해 성립한다. 두 번째 방정식이 정보를 전혀 추가하지 않는다. 실질적으로 방정식이 하나뿐인 것과 같다.

$y$ 를 임의로 정하면 $x = 1 + 2y$ 로 결정된다. $y$ 가 자유 변수(Free Variable)이다. 해의 집합 전체가 직선: $\{(1 + 2t, t) \mid t \in \mathbb{R}\}$.

행 그림으로 보면: 두 방정식 $x - 2y = 1$ 과 $3x - 6y = 3$ 은 같은 직선이다(하나를 3배 하면 다른 하나). 같은 직선 위의 무한히 많은 점이 모두 해이다.

열 그림으로 보면: 우변 $b = (1, 3)^\top$ 이 열 1 = $(1, 3)^\top$ 과 같은 방향이다. $b$ 를 만드는 결합이 하나가 아니라 무수히 많다($x = 1, y = 0$ 도 해이고, $x = 0, y = -1/2$ 도 해).

5.3 시나리오 C: 일시적 실패 — 행 교환으로 복구

\[ \begin{cases} 0x + 2y = 4 \\ 3x - 2y = 5 \end{cases} \]

첫 번째 피벗 위치에 $0$ 이 있다. 하지만 이것은 “지금 이 행이 $x$ 에 대한 정보를 주지 못한다”는 뜻일 뿐이다. 두 번째 행에서 $x$ 계수가 $3 \neq 0$ 이므로 두 번째 행이 피벗 역할을 할 수 있다. 행 교환(Row Exchange)으로 해결한다.

\[ \begin{bmatrix} 0 & 2 \\ 3 & -2 \end{bmatrix} \xrightarrow{R_1 \leftrightarrow R_2} \begin{bmatrix} 3 & -2 \\ 0 & 2 \end{bmatrix} \]

교환 후 이미 상삼각 형태. 피벗은 $3$ 과 $2$ 이다. 두 피벗 모두 비영 → 가역 행렬.

후방 대입: $2y = 4 \implies y = 2$, $3x - 2(2) = 5 \implies x = 3$.

중요한 직관: 행 교환은 방정식의 순서만 바꾼다. 동시에 만족해야 하는 방정식들의 집합은 변하지 않으므로 해도 바뀌지 않는다.

중요

소거 성공의 조건 — 피벗 수로 판단한다

$n \times n$ 행렬 $A$ 에서:

피벗 상황	행렬 상태	해의 상태
$n$ 개 피벗 모두 $\neq 0$ (행 교환 포함)	가역(Invertible)	유일한 해
피벗 위치 0, 아래에 비영 원소 존재	—	행 교환 후 계속
피벗 위치와 그 아래 모두 0 → $0 = c \neq 0$	특이(Singular)	해 없음
피벗 위치와 그 아래 모두 0 → $0 = 0$	특이(Singular)	무한히 많은 해

판단 기준: $n \times n$ 행렬에서 $n$ 개의 0이 아닌 피벗을 확보할 수 있으면 유일한 해가 존재한다.

6 3×3 예시: 단계별 전방 소거

3×3 시스템에서 소거의 전 과정을 단계별로 따라간다. 피벗들이 처음에는 숨어 있다가 소거를 거치면서 드러나는 과정에 주목한다.

\[ \begin{cases} 2x + 4y - 2z = 2 \\ 4x + 9y - 3z = 8 \\ -2x - 3y + 7z = 10 \end{cases} \quad A = \begin{bmatrix} 2 & 4 & -2 \\ 4 & 9 & -3 \\ -2 & -3 & 7 \end{bmatrix},\quad b = \begin{bmatrix} 2 \\ 8 \\ 10 \end{bmatrix} \]

6.1 Step 1: 1열 소거 — 첫 번째 피벗 2

목표: 1열에서 피벗 아래의 원소(4와 -2)를 모두 0으로 만든다.

피벗: $a_{11} = 2$

승수 1: $\ell_{21} = 4/2 = 2$

“왜 4/2인가?”: 2행의 $x$ 계수가 4이다. 피벗 행을 2배 빼면 $4x - 2 \cdot 2x = 0$ 이 된다.

연산: $R_2 \leftarrow R_2 - 2R_1$

\[ \begin{array}{l} \text{좌변: } (4x + 9y - 3z) - 2(2x + 4y - 2z) = 0x + 1y + 1z = y + z \\ \text{우변: } 8 - 2 \cdot 2 = 4 \end{array} \]

승수 2: $\ell_{31} = -2/2 = -1$

“왜 -2/2인가?”: 3행의 $x$ 계수가 $-2$ 이다. 피벗 행을 $-1$ 배 빼는 것은 피벗 행을 더하는 것과 같다. $-2x - (-1) \cdot 2x = -2x + 2x = 0$.

연산: $R_3 \leftarrow R_3 - (-1)R_1 = R_3 + R_1$

\[ \begin{array}{l} \text{좌변: } (-2x - 3y + 7z) + (2x + 4y - 2z) = 0x + 1y + 5z = y + 5z \\ \text{우변: } 10 + 2 = 12 \end{array} \]

Step 1 결과:

\[ \begin{bmatrix} \mathbf{2} & 4 & -2 \\ 0 & 1 & 1 \\ 0 & 1 & 5 \end{bmatrix} \begin{bmatrix} 2 \\ 4 \\ 12 \end{bmatrix} \]

1열 아래가 모두 0이 됐다. 첫 번째 피벗 $\mathbf{2}$ 의 역할이 완료됐다.

6.2 Step 2: 2열 소거 — 두 번째 피벗 1

1행을 무시하고 이제 2×2 부분 행렬에 집중한다.

목표: 2열에서 피벗(2행) 아래의 원소(1)를 0으로 만든다.

피벗: $a_{22}^{(2)} = 1$ — 이 피벗은 Step 1 이후 새로 드러났다.

승수: $\ell_{32} = 1/1 = 1$

연산: $R_3 \leftarrow R_3 - 1 \cdot R_2$

\[ \begin{array}{l} \text{좌변: } (y + 5z) - (y + z) = 4z \\ \text{우변: } 12 - 4 = 8 \end{array} \]

Step 2 결과 (상삼각행렬 $U$ 완성):

\[ U = \begin{bmatrix} \mathbf{2} & 4 & -2 \\ 0 & \mathbf{1} & 1 \\ 0 & 0 & \mathbf{4} \end{bmatrix},\quad c = \begin{bmatrix} 2 \\ 4 \\ 8 \end{bmatrix} \]

세 개의 피벗: $\mathbf{2},\; \mathbf{1},\; \mathbf{4}$ (대각선 위). 이 세 피벗은 원래 $A$ 에서 바로 보이지 않았다. 소거가 이들을 끌어냈다.

6.3 Step 3: 후방 대입 — 삼각 구조를 아래에서 위로

마지막 방정식: 미지수 하나($z$)만 남음

\[ 4z = 8 \implies z = 2 \]

두 번째 방정식: 이제 $z = 2$ 를 알고 있으므로 미지수 하나($y$)만 남음

\[ y + z = 4 \implies y + 2 = 4 \implies y = 2 \]

첫 번째 방정식: 이제 $y = 2$, $z = 2$ 를 알고 있으므로 미지수 하나($x$)만 남음

\[ 2x + 4y - 2z = 2 \implies 2x + 8 - 4 = 2 \implies 2x = -2 \implies x = -1 \]

해: $(x, y, z) = (-1, 2, 2)$

검증 — 원래 $A$ 와 열 방법으로 확인:

\[ (-1)\begin{bmatrix} 2 \\ 4 \\ -2 \end{bmatrix} + 2\begin{bmatrix} 4 \\ 9 \\ -3 \end{bmatrix} + 2\begin{bmatrix} -2 \\ -3 \\ 7 \end{bmatrix} = \begin{bmatrix} -2+8-4 \\ -4+18-6 \\ 2-6+14 \end{bmatrix} = \begin{bmatrix} 2 \\ 8 \\ 10 \end{bmatrix} = b \checkmark \]

6.4 추가 예시 — 모든 피벗이 1인 경우

\[ \begin{cases} x + y + z = 6 \\ x + 2y + 2z = 9 \\ x + 2y + 3z = 10 \end{cases} \]

소거 과정 (모든 승수가 1):

\[ \begin{bmatrix} 1 & 1 & 1 \\ 1 & 2 & 2 \\ 1 & 2 & 3 \end{bmatrix} \xrightarrow{R_2 - R_1,\; R_3 - R_1} \begin{bmatrix} 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 1 & 2 \end{bmatrix} \xrightarrow{R_3 - R_2} \begin{bmatrix} 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{bmatrix} = U \]

우변 변환: $(6, 9, 10) \to (6, 3, 3) \to (6, 3, 1)$

모든 피벗이 1. 후방 대입: $z = 1$, $y + 1 = 3 \implies y = 2$, $x + 2 + 1 = 6 \implies x = 3$.

7 소거법의 핵심 구조: 피벗이 드러나는 패턴

소거가 진행되면서 피벗들이 한 번에 하나씩 드러난다. 이 구조를 $n \times n$ 으로 일반화한다.

7.1 $n \times n$ 소거의 열 단위 진행

초기:           1열 소거 후:    2열 소거 후:    ... U 완성:
[x x x x]      [x x x x]      [x x x x]      [x x x x]
[x x x x]  →   [0 x x x]  →   [0 x x x]  →   [0 x x x]
[x x x x]      [0 x x x]      [0 0 x x]      [0 0 x x]
[x x x x]      [0 x x x]      [0 0 x x]      [0 0 0 x]

각 단계에서 현재 열의 피벗 아래를 모두 0으로 만든다. 그러면 다음 단계에서 더 작은 부분 행렬 문제가 남는다.

재귀적 구조: $n \times n$ 문제 → 1열 소거 → $(n-1) \times (n-1)$ 부분 문제 → … → $1 \times 1$ 문제.

7.2 연산량 분석: 왜 $O(n^3/3)$ 인가

$k$ 번째 피벗 단계에서 처리하는 부분 행렬 크기: $(n-k) \times (n-k)$

각 원소에 대해 1번의 곱셈과 1번의 뺄셈(≈ 2번 연산)이 필요하므로:

\[ \text{전체 연산} \approx \sum_{k=1}^{n-1} (n-k)^2 = \sum_{j=1}^{n-1} j^2 = \frac{(n-1)n(2n-1)}{6} \approx \frac{n^3}{3} \]

후방 대입은:

\[ \sum_{k=1}^{n} (n-k) \approx \frac{n^2}{2} \]

전체 비용은 소거의 $O(n^3/3)$ 이 지배한다.

$n = 1000$ 이면 소거에 약 $3.3 \times 10^8$ 번 연산, 후방 대입에 약 $5 \times 10^5$ 번 연산이다. 후방 대입의 비용은 무시해도 된다.

8 Worked Examples

8.1 예시 1: 삼중 대각 행렬 — 희소 구조의 이점

\[ A = \begin{bmatrix} 1 & -1 & 0 \\ -1 & 2 & -1 \\ 0 & -1 & 2 \end{bmatrix} \]

이 행렬은 대각선과 그 바로 위·아래에만 원소가 있다. 3열은 1행과 겹치지 않으므로 $\ell_{31} = 0/1 = 0$ 이다. 3행에서 1행을 빼는 연산이 필요 없다.

Step 1: $\ell_{21} = -1/1 = -1$ → $R_2 \leftarrow R_2 - (-1)R_1 = R_2 + R_1$

\[ (-1 + 1)x + (2 + (-1))y + (-1 + 0)z = 0 + 1y - 1z \implies \begin{bmatrix} 1 & -1 & 0 \\ 0 & 1 & -1 \\ 0 & -1 & 2 \end{bmatrix} \]

Step 2: $\ell_{32} = -1/1 = -1$ → $R_3 \leftarrow R_3 + R_2$

\[ U = \begin{bmatrix} 1 & -1 & 0 \\ 0 & 1 & -1 \\ 0 & 0 & 1 \end{bmatrix} \]

피벗: $1, 1, 1$. 모두 비영 → $A$ 는 가역.

직관: 삼중 대각 구조 덕분에 소거 중 새로 생기는 비영 원소(Fill-in)가 없다. 이 패턴의 행렬은 계산 비용이 $O(n)$ 으로 줄어든다. 유한 요소법(Finite Element Method)에서 이 구조가 자주 나타나는 이유이다.

8.2 예시 2: 행 교환이 필요한 경우

\[ \begin{cases} x + y + z = 7 \\ x + y - z = 5 \\ x - y + z = 3 \end{cases} \]

Step 1 후 ($\ell_{21} = 1$, $\ell_{31} = 1$):

\[ \begin{bmatrix} 1 & 1 & 1 \\ 0 & 0 & -2 \\ 0 & -2 & 0 \end{bmatrix} \begin{bmatrix} 7 \\ -2 \\ -4 \end{bmatrix} \]

2행 2열 피벗 위치가 $0$ 이다. 하지만 3행 2열은 $-2 \neq 0$ 이다. 행 교환: $R_2 \leftrightarrow R_3$

\[ \begin{bmatrix} 1 & 1 & 1 \\ 0 & -2 & 0 \\ 0 & 0 & -2 \end{bmatrix} \begin{bmatrix} 7 \\ -4 \\ -2 \end{bmatrix} \]

이미 상삼각. 피벗: $1, -2, -2$.

후방 대입: $-2z = -2 \implies z = 1$, $-2y = -4 \implies y = 2$, $x + 2 + 1 = 7 \implies x = 4$.

8.3 예시 3: 완전 실패 감지

\[ \begin{cases} x + y + z = 7 \\ x + y - z = 5 \\ -x - y + z = 3 \end{cases} \]

Step 1 후:

\[ \begin{bmatrix} 1 & 1 & 1 \\ 0 & 0 & -2 \\ 0 & 0 & 2 \end{bmatrix} \begin{bmatrix} 7 \\ -2 \\ 10 \end{bmatrix} \]

2열 전체가 0이다. 행 교환을 해도 2열 피벗이 나오지 않는다 — 특이 행렬 감지.

Step 2: $\ell_{32} = 2/(-2) = -1$ → $R_3 \leftarrow R_3 + R_2$:

\[ 0z = 10 + (-2) = 8 \implies \mathbf{0 = 8} \]

모순 → 해가 없다. 소거법이 불가능을 정확히 감지한다.

왜 모순이 생겼는가? 이 시스템에서 방정식 1 + 방정식 2 - 방정식 3을 계산하면:

\[ (x+y+z) + (x+y-z) - (-x-y+z) = 7 + 5 - 3 \implies 3x + 3y - z + x + y = 9 \]

더 간단하게: 방정식 1과 2를 더하면 $2x + 2y = 12$ 이고, 방정식 3에서 $-x - y + z = 3$ 이므로 방정식 3의 $z$ 항을 보면 $z = 3 + x + y = 3 + 6 = 9$… 실제로는 방정식 1+방정식 2+방정식 3을 보면 $x + y + z + x + y - z - x - y + z = 7 + 5 + 3$ 이 되어 $x + y + z = 15 \neq 7$ 이 되어 모순이 드러난다. 소거법은 이 숨겨진 모순을 $0 = 8$ 로 명시한다.

9 ML/DL에서의 소거법

9.1 수치 안정성: 피벗 크기가 왜 중요한가

소거법에서 승수를 구할 때 피벗으로 나눈다. 피벗이 매우 작으면:

\[ \ell_{ij} = \frac{a_{ij}}{\underbrace{a_{jj}}_{\approx 0}} \implies \ell_{ij} \text{가 매우 크다} \]

승수가 크면 소거 과정에서 컴퓨터의 반올림 오차(Round-off Error)가 승수에 의해 증폭된다. 결과적으로 수치 해가 정확한 해와 크게 달라질 수 있다.

해결책: 부분 피벗팅(Partial Pivoting) — 각 열에서 현재 피벗 아래 원소 중 절댓값이 가장 큰 것을 피벗으로 선택한다. 이렇게 하면 모든 승수의 절댓값이 $\leq 1$ 이 되어 오차 증폭이 억제된다.

# NumPy는 내부적으로 부분 피벗팅을 적용한다
import numpy as np
x = np.linalg.solve(A, b)   # 안정적인 LU + 부분 피벗팅

9.2 정규 방정식의 계산

선형 회귀의 정규 방정식 $A^\top A \hat{w} = A^\top b$ 를 풀 때:

$A^\top A$ 는 양정치 대칭 → 행 교환 없이 소거 가능 (Cholesky 분해, LU의 특수 형태)
소거 연산량: $O(p^3/3)$ ($p$ = 특성 수)

특성 수 $p$ 가 수천 이하이면 경사 하강법보다 소거법이 빠르고 정확하다.

10 코드로 확인하기

10.1 Step 1 — 소거 과정 단계별 출력 (직접 구현)

def gaussian_elimination_verbose(A, b):
    """소거 과정을 단계별로 출력하는 구현"""
    n = len(b)
    A = [list(row) for row in A]
    b = list(b)

    print("=== 초기 확장 행렬 [A | b] ===")
    for i in range(n):
        print(A[i], "|", b[i])

    # 전방 소거
    for j in range(n):   # 피벗 열
        pivot = A[j][j]
        if abs(pivot) < 1e-12:
            raise ValueError(f"피벗 = 0: {j}열에서 소거 실패 (행 교환 필요)")

        print(f"\n--- 피벗 {j+1}: a[{j}][{j}] = {pivot} ---")

        for i in range(j + 1, n):    # 피벗 아래 행들
            multiplier = A[i][j] / pivot
            print(f"  ℓ[{i+1},{j+1}] = {A[i][j]}/{pivot} = {multiplier:.4f}")
            for k in range(j, n):
                A[i][k] -= multiplier * A[j][k]
            b[i] -= multiplier * b[j]
            print(f"  R{i+1} ← R{i+1} - {multiplier:.4f}×R{j+1}: {A[i]} | {b[i]:.4f}")

    print("\n=== 상삼각행렬 U ===")
    for i in range(n):
        print(A[i], "|", b[i])

    # 후방 대입
    x = [0.0] * n
    for i in range(n - 1, -1, -1):
        x[i] = b[i]
        for k in range(i + 1, n):
            x[i] -= A[i][k] * x[k]
        x[i] /= A[i][i]

    return x

# 3×3 예시: 피벗 2, 1, 4
A = [[2, 4, -2], [4, 9, -3], [-2, -3, 7]]
b = [2, 8, 10]
x = gaussian_elimination_verbose(A, b)
print(f"\n해: x={x[0]:.2f}, y={x[1]:.2f}, z={x[2]:.2f}")  # -1, 2, 2

10.2 Step 2 — 행 교환 포함 (부분 피벗팅)

def gaussian_elimination_pivoting(A, b):
    """부분 피벗팅을 포함한 가우스 소거법"""
    n = len(b)
    A = [list(row[:]) for row in A]
    b = list(b)

    for j in range(n):
        # 절댓값이 가장 큰 원소를 피벗으로 선택
        max_idx = max(range(j, n), key=lambda i: abs(A[i][j]))
        if abs(A[max_idx][j]) < 1e-12:
            raise ValueError("특이 행렬: 소거 불가")

        # 행 교환
        if max_idx != j:
            A[j], A[max_idx] = A[max_idx], A[j]
            b[j], b[max_idx] = b[max_idx], b[j]
            print(f"행 교환: R{j+1} ↔ R{max_idx+1}")

        pivot = A[j][j]
        for i in range(j + 1, n):
            multiplier = A[i][j] / pivot
            for k in range(j, n):
                A[i][k] -= multiplier * A[j][k]
            b[i] -= multiplier * b[j]

    # 후방 대입
    x = [0.0] * n
    for i in range(n - 1, -1, -1):
        x[i] = b[i]
        for k in range(i + 1, n):
            x[i] -= A[i][k] * x[k]
        x[i] /= A[i][i]
    return x

# 행 교환이 필요한 예시
A = [[0, 2, 0], [3, -2, 0], [0, 0, 1]]
b = [4, 5, 1]
x = gaussian_elimination_pivoting(A, b)
print(f"해: {x}")

10.3 Step 3 — NumPy로 피벗 확인

import numpy as np
from scipy.linalg import lu

# 3×3 시스템: 소거 과정의 피벗 확인
A = np.array([[2, 4, -2],
              [4, 9, -3],
              [-2, -3, 7]], dtype=float)

# PA = LU 분해
P, L, U = lu(A)
print("L (승수들이 아래 삼각에):\n", L)
print("\nU (피벗들이 대각선에):\n", U)
print("\n피벗:", [round(U[i, i], 4) for i in range(len(U))])  # [2.0, 1.0, 4.0]

# Ax = b 풀기
b = np.array([2, 8, 10], dtype=float)
x = np.linalg.solve(A, b)
print("\n해:", x)          # [-1.  2.  2.]
print("검증 Ax:", A @ x)   # [ 2.  8. 10.]

11 핵심 요약

개념	공식 / 의미
소거의 원리	방정식 덧셈·뺄셈은 해를 바꾸지 않는다
피벗	$a_{kk}^{(k)}$: 소거의 기준 원소, 절대 0이 될 수 없다
승수	$\ell_{ij} = a_{ij}^{(j)} / a_{jj}^{(j)}$: $(i,j)$ 원소를 0으로 만드는 비율
소거 연산	$R_i \leftarrow R_i - \ell_{ij} R_j$, $(i,j)$ 원소를 0으로
목표	$A \to U$ (상삼각행렬)
후방 대입	$Ux = c$ 를 아래에서 위로, 매 단계 미지수 하나씩 결정
전체 비용	소거 $O(n^3/3)$ + 후방 대입 $O(n^2/2)$
성공 조건	$n$ 개의 0이 아닌 피벗 (행 교환 허용)
실패 종류	$0 = c \neq 0$ → 해 없음, $0 = 0$ → 무한 해

12 관련 주제

선행 지식

Ch.2 §2.1 — Vectors and Linear Equations — 행 그림·열 그림·행렬 형태

이 챕터 다음

관련 심화

Ch.2 §2.2 — The Idea of Elimination