Chapter 03

연립방정식과 가우스 소거

미지수가 둘이면 중학교에서 배운 대로 한 식을 다른 식에서 빼면 됩니다. 미지수가 백만 개라면 어떨까요? 놀랍게도 방법은 같습니다. 한 식의 몇 배를 다른 식에서 빼서 미지수를 하나씩 지우고, 맨 아래 식부터 거꾸로 풀어 올라갑니다. 이 단순한 절차가 가우스 소거이고, 다리의 응력 해석, 회로 시뮬레이터, 일기 예보 모델, 머신러닝의 최소제곱이 모두 그 위에서 돌아갑니다. 이 장에서는 연립방정식을 두 가지 그림(직선과 평면이 만나는 행 그림, 열벡터를 섞는 열 그림)으로 보고, 소거를 한 단계씩 직접 돌려 본 뒤, 소거가 언제 멈추는지, 컴퓨터에서 왜 틀릴 수 있는지, 얼마나 오래 걸리는지까지 따져 봅니다.

연립방정식 $A\mathbf{x} = \mathbf{b}$ 를 행 그림(직선·평면의 교점)과 열 그림(열벡터의 선형 결합)으로 해석하고, 해가 하나·없음·무수히 많음 세 경우만 있음을 설명한다.
첨가 행렬 $[A \mid \mathbf{b}]$ 에 행 연산을 적용해 상삼각 형태로 만들고, 피벗과 승수 $\ell_{ij}$ 를 정확히 구한다.
후진 대입으로 상삼각 연립방정식을 풀고, 피벗 n개가 모두 0이 아니면 해가 유일함을 안다.
0인 피벗을 행 교환으로 넘기는 경우와, 피벗이 영영 사라지는 특이(singular) 경우를 구별하고, 특이일 때 해가 없는지 무수히 많은지 판정한다.
소거의 각 단계를 기본 행렬 $E_{ij}$ ·치환 행렬 $P_{ij}$ 로 쓰고, 소거 전체를 $EA = U$ 라는 행렬 곱으로 표현한다.
작은 피벗이 반올림 오차를 키우는 이유와 부분 피벗팅의 규칙을 설명하고, 소거의 연산량이 약 $\tfrac{2}{3}n^3$ 임을 유도한다.

이 수식이 없었다면쓰러지지 않는 다리와 빌딩의 설계

교량이나 고층 건물을 설계할 때 구조 엔지니어는 구조물을 작은 요소 수십만 개로 나누고, 마디마다 "들어오는 힘과 나가는 힘이 평형을 이룬다"는 식을 세웁니다. 미지수는 마디의 변위이고, 식 하나하나는 이웃 마디 몇 개만 묶는 선형 방정식입니다. 결국 문제는 미지수 수십만~수백만 개짜리 연립방정식 $K\mathbf{u} = \mathbf{f}$ 하나가 됩니다.

이 크기를 손으로 풀 방법은 없습니다. 하지만 컴퓨터에게 일을 시키려면 "기계적으로 반복할 수 있는 절차"가 필요합니다. 한 식의 몇 배를 빼서 미지수를 하나씩 지우는 소거법이 바로 그 절차입니다. 기원후 1세기 무렵 정리된 중국의 『구장산술』 제8장 「방정(方程)」에 이미 산가지 배열로 계수를 늘어놓고 열끼리 빼는 방법이 있었고, 19세기 초 가우스가 소행성 궤도 계산에서 체계적으로 쓰면서 오늘날 그의 이름이 붙었습니다. 지금 구조 해석 프로그램이 돌리는 것도 본질적으로 같은 소거(정확히는 다음 장의 LU 분해)입니다.

마디마다 힘의 평형→미지수 수십만 개→가우스 소거→상삼각 → 거꾸로 대입→몇 초 만에 변위·응력

행 그림: 직선과 평면이 만나는 곳

두 센서가 가리키는 한 점

위치를 모르는 물체를 두 센서가 관측합니다. 센서 1은 "물체는 $x + y = 3$ 위에 있다", 센서 2는 "물체는 $x - y = 1$ 위에 있다"고 알려 줍니다. 물체는 어디 있을까요? 센서 2가 고장 나 $x + y = 1$ 을 보냈다면? 센서 2가 센서 1과 똑같은 정보를 두 배로 부풀려 $2x + 2y = 6$ 을 보냈다면?

식 하나를 한 행으로 보는 관점이 행 그림(row picture)입니다. 미지수가 둘인 선형 방정식 $a x + b y = c$ 는 평면 위의 직선 하나이고, 연립방정식의 해는 모든 직선 위에 동시에 있는 점, 즉 교점입니다. 두 직선이 만나는 방식은 셋뿐입니다. 한 점에서 만나거나, 평행해서 만나지 않거나, 아예 같은 직선이라 겹치거나.

정의 3.1 (선형 연립방정식) 미지수

x_1, \dots, x_n

에 대한 식

m

개

a_{i1}x_1 + a_{i2}x_2 + \cdots + a_{in}x_n = b_i \qquad (i = 1, \dots, m)

를 선형 연립방정식이라 하고, 계수를 모은

m\times n

행렬

A = [a_{ij}]

, 미지수 벡터

\mathbf{x}

, 우변

\mathbf{b}

로

A\mathbf{x} = \mathbf{b}

라 쓴다. 모든 식을 만족하는

\mathbf{x}

를 해, 해 전체의 모임을 해집합이라 한다. 해가 하나라도 있으면 무모순(consistent), 없으면 모순(inconsistent)이라 한다.

아래 시뮬레이터에서 두 식의 계수를 바꿔 보세요. 칸은 왼쪽부터 $a, b \mid c$ 이고, 두 직선의 교점이 해입니다.

SIMULATOR

행 그림: 두 직선의 교점

첨가 행렬 [a b | c]

프리셋 두 번째 식의 c를 흔들기

판정—

해 (x, y)—

두 직선 사이 각—

해볼 것: ① '거의 평행'을 고르고 아래 슬라이더로 c를 ±0.05만 흔들어 보세요. 우변이 조금 바뀌었을 뿐인데 교점은 멀리 달아납니다(7절의 조건수 이야기). ② '평행'에서 한 계수만 살짝 바꾸면 갑자기 해가 생깁니다. ③ 두 번째 줄을 첫 줄의 정확한 배수로 만들어 보세요. 모델: 실수 계수 2×2 연립방정식. 직선 각도는 법선벡터 (a, b) 사이의 각입니다.

미지수가 셋이면 식 $a x + b y + c z = d$ 하나는 3차원 공간의 평면입니다. 두 평면은 (평행이 아니라면) 직선에서 만나고, 그 직선이 세 번째 평면을 한 점에서 뚫으면 해가 하나입니다. 하지만 평면 셋은 훨씬 다양하게 어긋날 수 있습니다. 세 평면이 책장을 펼친 듯 한 직선을 공유할 수도, 두 장씩만 만나 삼각 기둥을 이룰 수도 있습니다.

SIMULATOR

세 평면은 어떻게 만나는가

좌우로 끌면 돌아갑니다

배치

[A | b] (3×4)

시점 회전 두 평면의 교선 그리기

평면 1평면 2평면 3교선·교점

판정—

해—

rank A / rank [A|b]—

해볼 것: ① '삼각 기둥'을 돌려 보며 세 교선이 모두 평행이라는 것을 확인하세요. 어느 두 평면도 평행하지 않은데 해가 없습니다. ② '책장'에서 세 번째 식의 우변 1을 1.5로 바꾸면 책장이 삼각 기둥으로 바뀝니다. ③ 계수를 직접 고쳐 세 평면이 한 점에서 만나게 해 보세요. 모델: 각 평면의 일부(정사각형 조각)만 사선 투영으로 그립니다. rank는 다음 장들에서 정식으로 정의할 '독립인 식의 개수'입니다.

그림을 아무리 바꿔도 해의 개수는 0, 1, ∞ 중 하나뿐입니다. 해가 정확히 두 개, 세 개인 선형 연립방정식은 없습니다. 이것은 우연이 아니라 선형성에서 바로 나옵니다.

정리 3.1 (해의 개수) 선형 연립방정식

A\mathbf{x} = \mathbf{b}

의 해는 없거나, 정확히 하나이거나, 무수히 많다.

증명. 서로 다른 해 $\mathbf{x}$ 와 $\mathbf{y}$ 가 있다고 하자. 임의의 실수 $t$ 에 대해 $\mathbf{z} = \mathbf{x} + t(\mathbf{y} - \mathbf{x})$ 를 넣으면 $A\mathbf{z} = A\mathbf{x} + t(A\mathbf{y} - A\mathbf{x}) = \mathbf{b} + t(\mathbf{b} - \mathbf{b}) = \mathbf{b}$ . 즉 두 해를 잇는 직선 위의 모든 점이 해다. 서로 다른 $t$ 는 서로 다른 $\mathbf{z}$ 를 주므로 해가 무수히 많다. ∎

그림으로 말하면 "두 점에서 만나는 두 직선은 같은 직선"이라는 사실의 일반화입니다. 평면이든 n차원의 초평면이든, 선형 방정식이 그리는 도형은 휘지 않으니 두 번 만나면 끝까지 만납니다.

열 그림: 열벡터를 섞어 b 만들기

두 가지 원료로 목표 조성 맞추기

합금 A는 1 kg당 구리 2 kg·아연 1 kg 비율의 성분을, 합금 B는 구리 1 kg·아연 2 kg 비율의 성분을 준다고 합시다(단위는 편의상 정한 것). 구리 4, 아연 5를 정확히 얻으려면 A와 B를 얼마씩 섞어야 할까요? 이 질문에는 "직선의 교점"보다 "두 재료 벡터를 몇 개씩 더하나"가 더 자연스러운 그림입니다.

같은 연립방정식을 세로로 읽어 봅시다. 1장에서 본 대로 행렬–벡터 곱은 열들의 선형 결합입니다.

\begin{aligned} 2x + y &= 4 \\ x + 2y &= 5 \end{aligned} \quad\Longleftrightarrow\quad x\begin{bmatrix}2\\1\end{bmatrix} + y\begin{bmatrix}1\\2\end{bmatrix} = \begin{bmatrix}4\\5\end{bmatrix}

왼쪽은 식 두 개(행 그림), 오른쪽은 벡터 방정식 하나(열 그림). "A의 열

\mathbf{a}_1, \mathbf{a}_2

를 몇 배씩 더해야

\mathbf{b}

가 되나?"를 묻는다. 답은

x = 1, y = 2

이것이 열 그림(column picture)입니다. 행 그림에서는 식마다 도형을 하나씩 그렸다면, 열 그림에서는 미지수마다 벡터를 하나씩 그리고 그 벡터들의 조합이 목표 $\mathbf{b}$ 에 닿는지 봅니다. 해가 없다는 것은 "어떻게 섞어도 $\mathbf{b}$ 에 닿지 못한다", 해가 무수히 많다는 것은 "닿는 방법이 여러 가지"라는 뜻이 됩니다.

SIMULATOR

열 그림: x·a₁ + y·a₂ 로 b에 닿기

a₁, a₂, b 끝점을 끌 수 있습니다

x (a₁의 개수) y (a₂의 개수)

x·a₁ + y·a₂—

남은 거리 |Ax − b|—

정답 (x, y)—

해볼 것: ① 슬라이더만으로 b에 닿아 보세요(남은 거리 0). ② a₂를 a₁과 같은 방향으로 끌어 두 열을 나란히 만들면, 조합이 한 직선 위에만 머물러 대부분의 b에 닿지 못합니다(해 없음). 그 직선 위에 b를 두면 닿는 방법이 무수히 많아집니다. 모델: 2×2, 끈 점은 0.1 단위로 맞춰집니다.

	행 그림	열 그림
그리는 것	식 하나 = 직선·평면 하나	미지수 하나 = 열벡터 하나
해란	모든 도형의 교점	$\mathbf{b}$ 에 닿는 섞는 비율
해 없음	평행한 직선, 삼각 기둥	$\mathbf{b}$ 가 열들이 만드는 공간 밖
해 무수히	도형이 직선·평면을 공유	열들이 서로 겹쳐 같은 $\mathbf{b}$ 를 여러 방법으로 만든다
n이 커지면	n차원 초평면 n개 — 상상하기 어렵다	벡터 n개의 조합 — 여전히 "섞기"

열 그림이 주는 핵심 질문

A\mathbf{x} = \mathbf{b}

에 해가 있다

\iff

\mathbf{b}

가

A

의 열들의 선형 결합이다. 열들의 선형 결합 전체를 열공간이라 부르며 5장에서 정식으로 다룹니다. 3×3 행렬의 세 열이 한 평면에 놓여 있으면(앞 시뮬레이터의 '책장'과 '삼각 기둥'), 열공간은 평면뿐이라 대부분의

\mathbf{b}

는 닿을 수 없습니다.

소거: 한 식의 몇 배를 빼서 미지수 지우기

그림 없이 푸는 법

행 그림과 열 그림은 해가 무엇인지 보여 주지만 해를 계산해 주지는 않습니다. 미지수가 넷만 넘어도 그림은 그릴 수조차 없습니다. 사람이든 컴퓨터든 따라 할 수 있는, 몇 번 반복하면 반드시 끝나는 절차가 필요합니다.

계산에는 $x, y, z$ 라는 이름이 필요 없습니다. 계수와 우변만 모아 첨가 행렬(augmented matrix) $[A \mid \mathbf{b}]$ 를 만들고, 다음 세 가지 기본 행 연산(elementary row operation)만 씁니다.

① 빼기행 i ← 행 i − ℓ · 행 j한 식의 ℓ배를 다른 식에서 뺀다. 소거의 주력 연산.

② 교환행 i ↔ 행 j두 식의 순서를 바꾼다. 피벗이 0일 때 필요하다.

③ 배수행 i ← c · 행 i (c ≠ 0)식 전체에 0이 아닌 수를 곱한다. 손계산을 깔끔하게 할 때 쓴다.

세 연산 모두 되돌릴 수 있습니다(빼었으면 다시 더하고, 바꿨으면 다시 바꾸고, 곱했으면 나누면 된다). 그래서 연산 전후의 연립방정식은 해집합이 정확히 같습니다. 이것이 소거가 정당한 이유입니다.

정의 3.2 (피벗과 승수) 소거의 k번째 단계에서 k번째 행의 대각 원소

u_{kk}

를 피벗(pivot)이라 한다. 피벗 아래의 원소

a_{ik}

를 0으로 만들기 위해 행 i에서 행 k를 빼는 배수

\ell_{ik} = \frac{a_{ik}}{u_{kk}} = \frac{\text{지울 원소}}{\text{피벗}}

를 승수(multiplier)라 한다. 피벗은 나눗셈의 분모이므로 0이 될 수 없다.

예제 3.1 · 3×3 소거를 손으로

다음 연립방정식을 소거로 상삼각 형태까지 만들어 보자.

\begin{aligned} 2x + y + z &= 3 \\ 4x + y \phantom{{}+z} &= 6 \\ -2x + 2y + z &= 1 \end{aligned} \qquad\longrightarrow\qquad \left[\begin{array}{rrr|r} 2 & 1 & 1 & 3 \\ 4 & 1 & 0 & 6 \\ -2 & 2 & 1 & 1 \end{array}\right]

1열, 피벗 2. $\ell_{21} = 4/2 = 2$ : 행 2 ← 행 2 − 2·행 1 → $[0,\ -1,\ -2 \mid 0]$ . $\ell_{31} = -2/2 = -1$ : 행 3 ← 행 3 − (−1)·행 1 = 행 3 + 행 1 → $[0,\ 3,\ 2 \mid 4]$ .
2열, 피벗 −1. $\ell_{32} = 3/(-1) = -3$ : 행 3 ← 행 3 + 3·행 2 → $[0,\ 0,\ -4 \mid 4]$ .

\left[\begin{array}{rrr|r} 2 & 1 & 1 & 3 \\ 0 & -1 & -2 & 0 \\ 0 & 0 & -4 & 4 \end{array}\right] = [\,U \mid \mathbf{c}\,], \qquad \text{피벗 } 2,\ -1,\ -4

세 피벗이 모두 0이 아니므로 해가 하나 있다. 대각선 아래가 모두 0인 이 모양을 상삼각(upper triangular)이라 한다. 승수 세 개 $\ell_{21} = 2,\ \ell_{31} = -1,\ \ell_{32} = -3$ 은 버리지 말자. 다음 장에서 이 숫자들이 그대로 행렬 $L$ 이 된다.

아래 시뮬레이터는 이 절차를 기계처럼 한 단계씩 실행합니다. 계수를 직접 고치거나 프리셋을 골라 '다음 단계'를 눌러 보세요. 테두리 친 칸이 피벗, 색칠된 행이 지금 고치는 행입니다.

SIMULATOR

가우스 소거 한 단계씩

예제

[A | b] 직접 고치기

부분 피벗팅 (가장 큰 피벗 고르기)

—

단계—

피벗—

곱셈·나눗셈 누적—

해볼 것: ① 예제 3.1을 끝까지 넘기며 위의 손계산과 승수(2, −1, −3)가 같은지 확인하세요. ② '피벗 0 → 행 교환'에서 2단계 피벗 자리에 0이 생기는 순간을 보세요. ③ '4×4 띠 행렬'에서는 0인 원소를 건너뛰므로 연산 수가 일반 4×4보다 훨씬 적습니다. 모델: 배정밀도 실수 연산, 크기가 10⁻¹²보다 작은 값은 0으로 봅니다. 표시는 분모 12 이하의 분수로 나타낼 수 있으면 분수로 보여 줍니다.

후진 대입: 맨 아래 식부터 거꾸로

상삼각이면 왜 쉬운가

소거가 끝난 $[U \mid \mathbf{c}]$ 의 맨 아래 식에는 미지수가 하나만 남아 있습니다. 그것을 풀어 바로 위 식에 넣으면, 그 식에도 새 미지수가 하나만 남습니다. 도미노처럼 위로 올라가면 끝입니다.

예제 3.1의 $[U \mid \mathbf{c}]$ 에서 $-4z = 4$ 이므로 $z = -1$ . 둘째 식 $-y - 2z = 0$ 에 넣으면 $-y + 2 = 0$ , $y = 2$ . 첫째 식 $2x + y + z = 3$ 에서 $2x + 2 - 1 = 3$ , $x = 1$ . 해는 $\mathbf{x} = (1, 2, -1)$ 이고, 원래 세 식에 넣어 검산하면 $3, 6, 1$ 이 정확히 나옵니다. 일반적으로

x_n = \frac{c_n}{u_{nn}}, \qquad x_i = \frac{1}{u_{ii}}\Bigl(c_i - \sum_{j=i+1}^{n} u_{ij}\,x_j\Bigr) \quad (i = n-1, \dots, 1)

이것이 후진 대입(back substitution)이다. i번째 줄에서 곱셈

n - i

번, 나눗셈 1번이 필요하므로 모두 합해 약

n^2/2

번의 곱셈. 아래삼각

L\mathbf{y} = \mathbf{b}

를 위에서부터 푸는 짝은 전진 대입(forward substitution)이다.

정리 3.2 (피벗 n개 ⇒ 유일한 해)

n\times n

행렬

A

를 행 교환을 허용한 소거로 상삼각

U

까지 만들었을 때 피벗

n

개가 모두 0이 아니면, 모든

\mathbf{b}

에 대해

A\mathbf{x} = \mathbf{b}

의 해가 정확히 하나 있다.

증명 개요. 행 연산은 해집합을 바꾸지 않는다. 피벗이 모두 0이 아니면 후진 대입의 모든 나눗셈이 가능하고, 각 단계에서 $x_i$ 의 값이 하나로 정해진다. 따라서 해가 존재하고 그 해뿐이다. ∎

시뮬레이터에서 '끝까지'를 누르면 상삼각이 된 뒤 후진 대입 단계가 이어집니다. 각 $x_i$ 가 어떤 수로 정해지는지 노트 줄의 계산식을 따라가 보세요.

검산 습관 손으로 푼 해는 반드시 원래 식에 넣어 확인하세요. 소거된 식에 넣으면 소거 과정의 실수를 잡을 수 없습니다. 컴퓨터에서도 같은 원리로 잔차

\mathbf{r} = \mathbf{b} - A\mathbf{x}

를 계산해 답의 품질을 봅니다(7절).

소거가 멈출 때: 행 교환과 특이 행렬

피벗 자리에 0이 나타나면

소거 도중 다음 피벗이 들어갈 대각 자리가 0이 되었습니다. 0으로 나눌 수는 없습니다. 이 방정식은 풀 수 없는 걸까요, 아니면 순서만 잘못된 걸까요?

두 경우를 구별해야 합니다. 피벗 자리가 0이어도 그 아래 행 중 하나가 0이 아니면 두 행을 바꾸면 됩니다. 식의 순서를 바꾸는 것은 해에 아무 영향이 없으니 이것은 일시적 실패입니다. 반면 피벗 자리와 그 아래가 모두 0이면 어떤 교환으로도 피벗을 만들 수 없습니다. 이것은 영구적 실패이고, 이런 정사각 행렬을 특이 행렬(singular matrix)이라 합니다.

\left[\begin{array}{rrr|r} 1 & 2 & 1 & 4 \\ 2 & 4 & 3 & 9 \\ 1 & 3 & 2 & 6 \end{array}\right] \xrightarrow{\ \text{1열 소거}\ } \left[\begin{array}{rrr|r} 1 & 2 & 1 & 4 \\ 0 & \mathbf{0} & 1 & 1 \\ 0 & 1 & 1 & 2 \end{array}\right] \xrightarrow{\ P_{23}\ } \left[\begin{array}{rrr|r} 1 & 2 & 1 & 4 \\ 0 & 1 & 1 & 2 \\ 0 & 0 & 1 & 1 \end{array}\right]

2행의 피벗 자리가 0이 되었지만 아래 3행의 같은 자리가 1이라 교환으로 해결된다. 피벗 1, 1, 1 → 해

(1, 1, 1)

특이일 때는 우변이 판결을 내립니다. 소거 끝에 계수가 모두 0인 행 $[0\ 0\ 0 \mid c]$ 이 남으면 그 행은 식 $0 = c$ 입니다. $c \ne 0$ 이면 거짓인 식이므로 해가 없고, $c = 0$ 이면 아무 정보도 없는 식이라 남은 식들만으로는 미지수 하나가 자유롭게 남아 해가 무수히 많습니다.

그림 3-1. 소거가 끝났을 때 [U | c]의 세 가지 모양. 피벗 개수가 n이면 해가 하나, n보다 적으면 0 = c 꼴의 행이 해가 없는지(c ≠ 0) 무수히 많은지(c = 0)를 정한다.

예제 3.2 · 특이 행렬과 우변

$A = \begin{bmatrix}1&1&1\\1&2&3\\2&3&4\end{bmatrix}$ 에서 셋째 행은 첫째 행과 둘째 행의 합이다. 소거하면

$\ell_{21} = 1,\ \ell_{31} = 2$ → 행 2 = $[0, 1, 2]$ , 행 3 = $[0, 1, 2]$ .
$\ell_{32} = 1$ → 행 3 = $[0, 0, 0]$ . 피벗은 1, 1 두 개뿐이다.

$\mathbf{b} = (3, 6, 10)$ 이면 우변이 $3 \to 3 \to 10 - 6 - 3 = 1$ 이 되어 $0 = 1$ : 해 없음. $\mathbf{b} = (3, 6, 9)$ 이면 $0 = 0$ : $z$ 를 자유롭게 정하면 $y = 3 - 2z,\ x = z$ 로 해가 직선 하나만큼 있다. 같은 $A$ 인데 우변이 셋째 성분 1만큼 달랐을 뿐이다. 시뮬레이터의 '특이' 두 프리셋이 이 예제다.

특이성은 A만의 성질 피벗이 n개 나오느냐는

A

만 보고 정해집니다(우변은 소거 과정에서 따라갈 뿐).

A

가 특이가 아니면 어떤

\mathbf{b}

에도 해가 하나, 특이면 어떤

\mathbf{b}

에도 "없거나 무수히"입니다. 다음 장에서 이것이 "역행렬이 있다"와 같은 말임을 봅니다.

소거를 행렬 곱으로: 기본 행렬과 EA = U

절차를 공식으로 바꾸기

"2행에서 1행의 2배를 빼라" 같은 지시는 말로 된 절차입니다. 이것을 행렬로 쓸 수 있다면 소거 전체가 행렬 곱셈 몇 번이 되고, 행렬의 대수(결합 법칙, 역행렬)를 소거에 그대로 쓸 수 있습니다.

열 그림을 행에 적용해 봅시다. $EA$ 의 i번째 행은 " $E$ 의 i번째 행이 정한 비율로 $A$ 의 행들을 섞은 것"입니다. 그러니 단위 행렬에서 한 칸만 바꾼 행렬로 행 연산 하나를 정확히 표현할 수 있습니다.

E_{21} = \begin{bmatrix}1&0&0\\-\ell_{21}&1&0\\0&0&1\end{bmatrix}, \qquad P_{23} = \begin{bmatrix}1&0&0\\0&0&1\\0&1&0\end{bmatrix}, \qquad E_{21}^{-1} = \begin{bmatrix}1&0&0\\\ell_{21}&1&0\\0&0&1\end{bmatrix}

E_{21}A

: 2행 ← 2행 −

\ell_{21}

·1행, 나머지 행은 그대로.

P_{23}A

: 2행과 3행 교환. 되돌리기

E_{21}^{-1}

은 빼었던 것을 다시 더하는 것이라 부호만 바뀐다.

이런 행렬을 기본 행렬(elementary matrix), 행을 바꾸는 것을 치환 행렬(permutation matrix)이라 합니다. 예제 3.1의 소거 세 단계는 행렬 곱 하나로 요약됩니다.

E_{32}\,E_{31}\,E_{21}\,A = U, \qquad E = E_{32}E_{31}E_{21} = \begin{bmatrix}1&0&0\\-2&1&0\\-5&3&1\end{bmatrix}

\ell_{21}=2,\ \ell_{31}=-1,\ \ell_{32}=-3

을 넣어 곱하면 위와 같다. 오른쪽 행렬이 먼저 작용하므로 첫 단계

E_{21}

이 가장 오른쪽에 온다.

E

의 (3,1) 칸 −5는 승수 셋이 얽힌 결과라 깔끔하지 않지만, 역행렬

E^{-1}

은 승수가 제자리에 그대로 앉은

\begin{bmatrix}1&0&0\\2&1&0\\-1&-3&1\end{bmatrix}

이 된다. 이것이 4장의

L

이다.

시뮬레이터에서 각 소거 단계마다 오른쪽에 그 단계의 기본 행렬이 함께 표시됩니다. 행 교환 단계에서는 치환 행렬이 나타납니다. 직접 곱해 보면 표시된 행렬을 왼쪽에 곱한 결과가 다음 상태와 같다는 것을 확인할 수 있습니다.

그림 3-2. 예제 3.1의 소거를 기본 행렬 세 개의 곱으로 본 그림. 색칠한 행이 그 단계에서 바뀐 행이다. 각 Eᵢⱼ는 단위 행렬의 (i, j) 칸에 −ℓᵢⱼ를 넣은 것이다.

정리 3.3 (소거의 행렬 표현) 행 교환이 필요 없는 소거는 아래삼각 기본 행렬들의 곱

E

로

EA = U

이다. 행 교환이 필요하면 교환을 미리 모은 치환 행렬

P

가 있어

PA

는 교환 없이 소거된다. 기본 행렬과 치환 행렬은 모두 가역이므로 소거는 정보를 잃지 않는다. 피벗이 n개가 아닐 때 잃는 것은 소거가 아니라

A

자체가 이미 가진 정보 부족이다.

컴퓨터의 소거: 반올림 오차와 부분 피벗팅

0은 아니지만 아주 작은 피벗

피벗이 정확히 0이면 행을 바꾸라고 배웠습니다. 그럼 피벗이 $10^{-17}$ 이면? 수학적으로는 아무 문제가 없습니다. 하지만 유효 숫자가 16자리 남짓인 컴퓨터에서는 해가 완전히 틀릴 수 있습니다.

가장 작은 예를 봅시다. $\varepsilon$ 이 아주 작은 양수일 때

\begin{bmatrix}\varepsilon & 1\\ 1 & 1\end{bmatrix}\begin{bmatrix}x\\y\end{bmatrix} = \begin{bmatrix}1\\2\end{bmatrix}, \qquad \text{정확한 해 } x = \frac{1}{1-\varepsilon} \approx 1,\quad y = \frac{1-2\varepsilon}{1-\varepsilon} \approx 1

피벗

\varepsilon

으로 소거하면 승수

\ell_{21} = 1/\varepsilon

이 거대해지고, 2행이

1 - 1/\varepsilon

, 우변이

2 - 1/\varepsilon

이 된다. 컴퓨터에서

1 - 10^{20}

은

-10^{20}

으로 반올림되어 원래 행의 "1"과 "2"라는 정보가 사라진다.

그 결과 $y$ 는 거의 정확하게 1로 나오지만, $x = (1 - y)/\varepsilon$ 를 계산하는 순간 작은 오차가 $1/\varepsilon$ 배로 불어나 $x$ 가 0이나 엉뚱한 값이 됩니다. 처방은 간단합니다. 두 행을 바꿔 절댓값이 큰 1을 피벗으로 쓰면 승수가 $\varepsilon$ 으로 작아지고 아무것도 지워지지 않습니다.

정의 3.3 (부분 피벗팅) k번째 단계에서 k번째 열의 k행 이하 원소 중 절댓값이 가장 큰 것을 골라 그 행을 k행과 바꾼 뒤 소거한다. 그러면 모든 승수가

|\ell_{ik}| \le 1

이 되어, 한 단계에서 행에 더해지는 양이 피벗 행보다 커지지 않는다. LAPACK 같은 표준 라이브러리의 일반 연립방정식 풀이기는 기본으로 이 방식을 쓴다.

SIMULATOR

작은 피벗의 함정: 피벗팅 있이 vs 없이

피벗 ε = 10^k

계산 정밀도

피벗팅 없이 (x, y)—

부분 피벗팅 (x, y)—

승수 ℓ₂₁ (없이 / 있을 때)—

해볼 것: ① 배정밀도에서 ε를 10⁻¹까지 올렸다 10⁻¹⁸까지 내려 보세요. 피벗팅 없이 얻은 x의 오차(빨강)가 1/ε에 비례해 커지다가 ε가 10⁻¹⁶ 근처를 넘으면 x = 0이 됩니다. ② 유효 4자리로 바꾸면 ε = 10⁻⁵만 되어도 이미 완전히 틀립니다. 부분 피벗팅(초록)은 내내 반올림 수준의 오차입니다. 모델: 매 연산 뒤 결과를 지정한 유효 자리로 반올림(배정밀도는 자바스크립트 기본 실수). 그래프의 0 오차는 10⁻¹⁷로 표시합니다.

부분 피벗팅이 만능은 아닙니다. 피벗팅으로도 구할 수 없는 것은 문제 자체가 예민한 경우입니다. 1절의 '거의 평행한 두 직선'은 어떤 알고리즘으로 풀어도 우변의 작은 흔들림이 해를 크게 움직입니다. 이 예민함을 재는 수가 조건수이고, 14·16장에서 특이값으로 정확히 정의합니다. 정리하면 오차의 원인은 둘입니다.

원인	예	처방
알고리즘이 불안정	작은 피벗으로 소거 (위 시뮬레이터)	부분 피벗팅 — 알고리즘을 바꾸면 해결
문제가 예민함(조건수가 큼)	거의 평행한 직선 (1절)	알고리즘으로는 해결 불가. 측정을 늘리거나 문제를 다시 세운다

부분 피벗팅은 얼마나 안전한가 수치 해석가 윌킨슨은 부분 피벗팅을 쓴 소거의 오차를 "원소가 소거 중에 얼마나 커지는가"(성장 인자)로 묶었습니다. 최악의 경우 성장 인자가

2^{n-1}

인 행렬을 인위적으로 만들 수 있지만, 실제 응용에서 그런 행렬은 극히 드물어 부분 피벗팅은 사실상 표준이 되었습니다. 더 안전한 완전 피벗팅(행과 열을 모두 바꿈)은 비용이 커서 특별한 경우에만 씁니다.

얼마나 걸리나: 연산량 2n³/3

미지수가 10배면 시간은 몇 배?

미지수 1,000개짜리 문제를 노트북이 0.1초에 푼다면, 10,000개짜리는 몇 초 걸릴까요? 1초? 10초? 100초? 계산 모델의 해상도를 높일지 정하려면 이 질문에 답할 수 있어야 합니다.

k번째 단계에서 피벗 아래 $n - k$ 개 행 각각에 대해, 그 행의 남은 $n - k$ 개 칸을 고칩니다(칸마다 곱셈 하나와 뺄셈 하나). 단계마다 약 $(n-k)^2$ 번의 곱셈이 드니

\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} \ \text{곱셈}, \qquad \text{덧셈과 뺄셈까지} \ \approx \frac{2}{3}n^3 \ \text{flop}

우변

\mathbf{b}

를 따라 고치는 데

n^2/2

, 후진 대입에

n^2/2

곱셈이 더 든다. n이 클 때는

n^3

항이 압도한다. flop은 부동소수점 연산 한 번.

그래서 답은 "약 1,000배"입니다. n이 10배면 시간은 $10^3$ 배, n이 2배면 8배. 반대로 우변만 바꿔 다시 풀 때는 소거 결과(다음 장의 LU)를 재활용해 $n^2$ 만 들기 때문에, 한 번 분해해 두면 같은 행렬로 우변 수천 개를 싸게 풀 수 있습니다.

SIMULATOR

n³의 벽: 연산량과 실측 시간

미지수 개수 n 계산 속도

소거 2n³/3—

후진 대입 n²—

예상 시간 (소거)—

실측: n 두 배 → 시간—

해볼 것: ① n을 10³에서 10⁴로 올리면 예상 시간이 1,000배가 되는 것을 보세요. ② '실측'을 누르면 이 브라우저가 n = 50~400 문제를 실제로 소거하고 걸린 시간을 주황 점으로 찍습니다(n = 400의 실측 속도로 flop에 환산했으므로, 점들이 소거 직선과 같은 기울기 3을 따르는지가 핵심). n이 두 배일 때 시간이 8배에 가까운지 확인하세요(작은 n에서는 오버헤드 때문에 덜 늘어납니다). 모델: 밀집 행렬, 피벗팅 비용 무시. 계산 속도 10⁹ flop/s는 단순한 자바스크립트 수준, 고성능 라이브러리를 쓰는 노트북 CPU는 10¹⁰~10¹¹, 큰 슈퍼컴퓨터는 10¹⁷ 이상입니다.

n	소거 flop ≈ 2n³/3	10¹⁰ flop/s에서	해당 규모의 예
100	6.7 × 10⁵	0.07 ms	작은 회로, 트러스 구조
10³	6.7 × 10⁸	0.07 s	중간 크기 회귀 문제
10⁴	6.7 × 10¹¹	67 s	2D 유한요소 메시
10⁶	6.7 × 10¹⁷	약 2년	3D 구조·유체 해석 — 밀집 소거로는 불가능

그럼 백만 개는 어떻게 푸나 실제 공학 문제의 행렬은 대부분 0입니다(마디 하나는 이웃 몇 개와만 연결). 시뮬레이터의 '4×4 띠 행렬'처럼 0을 건너뛰면 연산이 크게 줄어, 삼중대각 행렬은

O(n)

에 풀립니다(4장). 더 일반적인 희소 행렬에는 채움(fill-in)을 줄이는 순서 바꾸기와 반복법(16장)을 씁니다. 크라메르 공식을 여인수 전개로 계산하는 방법은

n!

에 비례해 n = 25만 되어도 우주의 나이로도 모자라므로, 계산 도구로는 쓰지 않습니다(10장).

응용: 회로의 노드 해석

휘트스톤 브리지의 가운데 전류

저항 다섯 개가 마름모 모양으로 연결된 휘트스톤 브리지는 센서(스트레인 게이지, 온도 센서)의 작은 저항 변화를 읽는 표준 회로입니다. 가운데 다리 $R_5$ 에 흐르는 전류는 얼마일까요? 직렬·병렬 공식만으로는 이 회로를 줄일 수 없습니다.

회로 시뮬레이터(SPICE 계열)가 쓰는 방법은 노드 해석(nodal analysis)입니다. 미지수를 마디의 전압으로 두고, 마디마다 키르히호프 전류 법칙 "나가는 전류의 합 = 0"을 씁니다. 저항 $R$ 을 지나는 전류는 $(v_i - v_j)/R$ 로 전압에 선형이므로 결과는 연립방정식 $G\mathbf{v} = \mathbf{i}$ 입니다. 여기서 $G$ 는 컨덕턴스(1/R) 행렬입니다.

\begin{bmatrix} g_s + g_1 + g_2 & -g_1 & -g_2 \\ -g_1 & g_1 + g_3 + g_5 & -g_5 \\ -g_2 & -g_5 & g_2 + g_4 + g_5 \end{bmatrix}\begin{bmatrix}v_A\\v_B\\v_C\end{bmatrix} = \begin{bmatrix} g_s V \\ 0 \\ 0 \end{bmatrix}, \qquad g_k = \frac{1}{R_k}

마디 A는 내부 저항

R_s

를 거쳐 전원

V

에, B·C는 브리지의 양쪽, 바닥 마디 D는 접지(0 V). 대각 원소는 그 마디에 붙은 컨덕턴스의 합, 비대각 원소는 두 마디를 잇는 컨덕턴스의 음수. 그래서

G

는 대칭이고 대각이 크다(13장의 양의 정부호 행렬).

SIMULATOR

휘트스톤 브리지를 소거로 풀기

전원 V R₄ (센서) R₅ (검류계)

vA, vB, vC—

I₅ (B → C)—

브리지—

해볼 것: ① R₄를 움직여 I₅가 0이 되는 점을 찾으세요. R₁ = 1 kΩ, R₂ = 2 kΩ, R₃ = 1.5 kΩ이므로 R₄ = 3 kΩ에서 균형입니다. 균형점은 V에도 R₅에도 무관합니다. ② 균형점 근처에서 R₄를 10 Ω만 바꿔도 I₅의 부호가 바뀝니다. 이 민감함이 브리지를 센서 회로로 쓰는 이유입니다. 모델: 이상적인 직류 전원과 선형 저항, Rₛ = 100 Ω. 3×3 노드 방정식을 부분 피벗팅 가우스 소거로 풉니다. 행렬 줄은 mS(밀리지멘스) 단위입니다.

실제 회로 시뮬레이터는 마디가 수만~수백만 개인 집적 회로에서 이 연립방정식을 세웁니다. 트랜지스터처럼 비선형 소자가 있으면 뉴턴법으로 선형화해 매 반복마다 $G\mathbf{v} = \mathbf{i}$ 를 다시 풀고, 시간에 따라 변하는 회로는 시간 간격마다 또 풉니다. 그래서 회로 시뮬레이터 시간의 큰 몫이 희소 행렬의 소거(LU)에 쓰입니다. 같은 구조가 구조물의 강성 행렬 $K\mathbf{u} = \mathbf{f}$ , 열전도의 이산화, 관망의 유량 계산에도 그대로 나타납니다. "연결된 것끼리 주고받는 양이 차이에 비례한다"는 모델은 언제나 이런 대칭 행렬을 만듭니다.

이 도구가 쓰이는 곳

가우스 소거는 선형대수에서 가장 많이 실행되는 알고리즘입니다. 이 책의 다음 장들과 시리즈의 다른 책이 이 장의 절차 위에 서 있습니다.

LINEARBOOK · 4장역행렬과 LU 분해
소거의 기록(승수)을 L로 모아 A = LU. 한 번 분해해 우변 여러 개를 n²에 풀기. MATHBOOK행렬은 변환이다
Ax = b를 "어떤 입력이 b로 가나"로 보는 기하 그림과 조건수의 직관. MATHBOOK컴퓨터는 어떻게 틀리는가
부동소수점, 상쇄 오차, 안정성. 이 장의 작은 피벗 문제의 배경. 확률과 통계회귀 분석
최소제곱의 정규 방정식 AᵀAx = Aᵀb도 결국 소거로 푼다. TCADBOOK소자·공정 시뮬레이션
포아송·드리프트–확산 방정식을 격자로 이산화하면 거대한 희소 연립방정식이 된다. ANALOGBOOK아날로그 회로
노드 해석과 회로 시뮬레이션. 브리지·증폭기의 동작점 계산.

핵심 정리

행 그림: 식 하나 = 직선·평면·초평면 하나, 해 = 교점. 열 그림: 미지수 하나 = 열벡터 하나, 해 = $\mathbf{b}$ 를 만드는 섞는 비율. $A\mathbf{x} = \mathbf{b}$ 에 해가 있다 ⟺ $\mathbf{b}$ 가 $A$ 의 열들의 선형 결합.
선형 연립방정식의 해는 0개, 1개, 무수히 중 하나다(두 해가 있으면 그 사이 직선 전체가 해).
가우스 소거: 첨가 행렬에 "행 i − ℓ·행 k", 행 교환을 적용해 상삼각 $[U \mid \mathbf{c}]$ 로 만든다. 승수 $\ell_{ik}$ = 지울 원소 / 피벗. 행 연산은 해집합을 바꾸지 않는다.
후진 대입: 맨 아래부터 $x_i = (c_i - \sum_{j>i} u_{ij}x_j)/u_{ii}$ . 피벗 n개가 모두 0이 아니면 해가 유일하다.
피벗 자리가 0이면 아래 행과 교환(일시적 실패). 아래도 모두 0이면 특이(영구적 실패)이고, 마지막 행 $0 = c$ 에서 $c \ne 0$ 이면 해 없음, $c = 0$ 이면 해가 무수히 많다.
소거 한 단계 = 기본 행렬 $E_{ij}$ 곱하기, 행 교환 = 치환 행렬 $P_{ij}$ . 전체 소거는 $EA = U$ (교환이 있으면 $PA$ 를 소거).
작은 피벗은 승수를 키워 반올림 오차를 증폭한다. 부분 피벗팅(열에서 절댓값 최대를 피벗으로)은 $|\ell| \le 1$ 을 보장하는 표준 처방이다. 문제 자체가 예민한(조건수가 큰) 경우는 알고리즘으로 고칠 수 없다.
연산량은 소거 약 $\tfrac{2}{3}n^3$ flop, 후진 대입 약 $n^2$ . n이 2배면 시간 8배. 큰 공학 문제는 희소성을 이용해야 풀린다.

확인 퀴즈

Q1. 선형 연립방정식이 서로 다른 해를 정확히 두 개 가질 수 있는가?

정리 3.1. 해 x, y가 있으면 x + t(y − x)도 모든 t에 대해 해이므로 해가 무수히 많다. 선형 방정식이 그리는 도형(직선·평면)은 휘지 않기 때문이다.

Q2. 첨가 행렬의 첫 열이 (3, 6, −9)이고 피벗이 3이다. 승수 $\ell_{21}, \ell_{31}$ 은?

승수 = 지울 원소 / 피벗. 6/3 = 2, −9/3 = −3. 행 2 ← 행 2 − 2·행 1, 행 3 ← 행 3 − (−3)·행 1 = 행 3 + 3·행 1로 두 원소가 0이 된다.

Q3. 소거 도중 2행의 피벗 자리가 0인데 3행의 같은 열 원소는 5다. 어떻게 해야 하나?

일시적 실패다. 식의 순서를 바꾸는 것은 해에 영향이 없으므로 치환 행렬 P₂₃을 곱하고 피벗 5로 소거를 계속한다. 피벗 자리와 그 아래가 모두 0일 때만 특이다.

Q4. 소거가 끝난 첨가 행렬의 마지막 행이 $[0\ 0\ 0 \mid 2]$ 이다. 결론은?

이 행은 0x + 0y + 0z = 2, 즉 0 = 2라는 거짓 식이다. 원래 연립방정식은 모순이다. 마지막 행이 [0 0 0 | 0]이었다면 해가 무수히 많았다.

Q5. $E_{31} = \begin{bmatrix}1&0&0\\0&1&0\\4&0&1\end{bmatrix}$ 을 A의 왼쪽에 곱하면 무슨 일이 생기나?

EA의 3행 = E의 3행 (4, 0, 1)이 정한 비율로 A의 행을 섞은 것 = 4·(1행) + (3행). 열 연산은 오른쪽에 곱할 때 일어난다. "행 3 − ℓ·행 1"로 쓰면 ℓ₃₁ = −4다.

Q6. 부분 피벗팅의 주된 목적은?

열에서 절댓값이 가장 큰 원소를 피벗으로 고르면 모든 승수의 절댓값이 1 이하가 된다. 연산량은 그대로이고, 특이 행렬은 여전히 특이이며, 조건수가 큰 문제의 예민함은 알고리즘으로 없앨 수 없다.

Q7. 노트북이 밀집 행렬 n = 2,000 연립방정식을 소거로 0.5초에 푼다. n = 8,000이면 대략?

연산량 ∝ n³이므로 n이 4배면 시간은 4³ = 64배, 0.5 × 64 = 32초. (메모리 n²도 16배가 된다는 점도 함께 기억하자.)

Q8. 우변 $\mathbf{b}$ 만 다른 같은 행렬의 연립방정식 100개를 풀어야 한다. 가장 효율적인 방법은?

소거의 비싼 부분(2n³/3)은 A에만 의존한다. 승수를 저장해 두면 새 우변은 전진 대입과 후진 대입으로 약 2n²만에 풀린다. 이것이 다음 장의 LU 분해다. 우변을 더해 풀면 해의 합만 얻는다(선형성).