Kwangmin Kim - Ch.2 Solving Linear Equations

1 챕터 2 전체 로드맵

Ch.2는 선형대수의 핵심 문제인 \(Ax = b\) 를 체계적으로 푸는 방법을 다룬다. 단순히 “연립방정식을 푸는 알고리즘” 이상이다. — 소거법을 행렬 언어로 추상화하면 LU 분해라는 강력한 수치 도구가 탄생하고, 이것이 현대 과학 계산의 근간이 된다.

절	제목	핵심 질문
§2.1	Vectors and Linear Equations	Ax=b를 어떻게 시각화하는가?
§2.2	The Idea of Elimination	미지수를 하나씩 제거하려면?
§2.3	Elimination Using Matrices	행 연산을 행렬로 표현하면?
§2.4	Rules for Matrix Operations	행렬 곱셈의 규칙은?
§2.5	Inverse Matrices	\(A^{-1}\) 은 언제 존재하는가?
§2.6	Elimination = Factorization: A = LU	소거가 왜 분해인가?
§2.7	Transposes and Permutations	전치·치환 행렬의 역할은?

2 §2.1 — 선형 방정식의 세 가지 시각

2.1 문제 설정

\(n\) 개의 미지수에 \(n\) 개의 방정식이 주어진 연립방정식은 세 가지 방식으로 읽을 수 있다. 가장 단순한 2변수 예시로 시작한다.

\[ x - 2y = 1 \qquad 3x + 2y = 11 \]

계수 행렬과 우변을 정리하면 다음과 같다.

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

2.2 행 그림 (Row Picture)

각 방정식을 하나의 직선(2D) 또는 평면(3D)으로 본다. 해 \(x = 3,\, y = 1\) 은 두 직선이 만나는 교점이다.

\[ \begin{cases} x - 2y = 1 & \text{(직선 1)} \\ 3x + 2y = 11 & \text{(직선 2)} \end{cases} \implies (x, y) = (3, 1) \]

3변수 시스템에서는 세 평면이 한 점에서 만나는 그림이 된다.

2.3 열 그림 (Column Picture)

같은 방정식을 열벡터의 선형 결합으로 읽는다.

\[ x \begin{bmatrix} 1 \\ 3 \end{bmatrix} + y \begin{bmatrix} -2 \\ 2 \end{bmatrix} = \begin{bmatrix} 1 \\ 11 \end{bmatrix} \]

“어떤 계수 \(x, y\) 로 열벡터들을 결합해야 우변 \(b\) 를 만들 수 있는가?”라는 질문이다. \(x = 3,\, y = 1\) 을 대입하면 \(3(1, 3)^\top + 1(-2, 2)^\top = (1, 11)^\top\) 이 성립한다.

노트

왜 열 그림이 더 중요한가?

고차원에서 행 그림은 초평면(hyperplane)의 교점을 상상해야 하므로 직관이 급격히 어려워진다. 반면 열 그림은 “벡터들의 선형 결합”이라는 단일 개념으로 10차원, 100차원 문제를 동일하게 다룬다. Strang은 열 그림을 강력히 선호한다. Ch.3의 열 공간(Column Space) 개념도 이 시각에서 출발한다.

2.4 행렬 형태 (Matrix Form)

행 그림과 열 그림은 같은 수 \(A, x, b\) 를 다른 방식으로 보는 것이다. 행렬 방정식 \(Ax = b\) 는 두 관점을 하나로 통합한다.

\[ Ax = b \iff \begin{bmatrix} 1 & -2 \\ 3 & 2 \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} = \begin{bmatrix} 1 \\ 11 \end{bmatrix} \]

\(Ax\) 를 계산하는 두 가지 방법:

행 방법 (Row Method): 각 행과 \(x\) 의 내적 — \(Ax\) 의 \(i\) 번째 성분 \(= (\text{row } i) \cdot x\)
열 방법 (Column Method): \(Ax = x_1(\text{col 1}) + x_2(\text{col 2}) + \cdots + x_n(\text{col } n)\)

3변수 예시: \(Ax = b\) 의 해는 \(x = 0,\, y = 0,\, z = 2\)

\[ \begin{bmatrix} 1 & 2 & 3 \\ 2 & 5 & 2 \\ 6 & -3 & 1 \end{bmatrix} \begin{bmatrix} 0 \\ 0 \\ 2 \end{bmatrix} = 2 \begin{bmatrix} 3 \\ 2 \\ 1 \end{bmatrix} = \begin{bmatrix} 6 \\ 4 \\ 2 \end{bmatrix} \]

열 그림의 힘: \(b = (6, 4, 2)^\top\) 가 세 번째 열의 2배임을 바로 파악할 수 있다.

3 §2.2–§2.3 — 소거법과 행렬 표현

3.1 소거법의 핵심 아이디어

\(Ax = b\) 에서 피벗(pivot)을 이용해 아래 원소를 0으로 만들어 상삼각행렬 \(U\) 를 만든다.

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

소거 완료 후 후방 대입(Back Substitution)으로 해를 구한다. \(Ux = c\) 를 아래에서 위로 풀면 된다.

3.2 피벗과 승수

각 소거 단계에서 피벗 \(a_{kk}\) 와 승수 \(\ell_{ik} = a_{ik} / a_{kk}\) 를 정의한다. \(i\) 행에서 \(\ell_{ik}\) 배의 \(k\) 행을 빼는 연산이 소거이다.

\[ \text{새 } i\text{행} \leftarrow \text{기존 } i\text{행} - \ell_{ik} \times k\text{행} \]

피벗이 0이 되면 행 교환(Row Exchange)으로 해결한다. 아래에 교환할 비영(non-zero) 원소조차 없으면 \(A\) 는 특이 행렬(Singular Matrix)이다.

3.3 소거 행렬 \(E_{ij}\)

각 소거 연산은 단위 행렬에 한 원소만 바꾼 행렬 \(E_{ij}\) 로 표현된다.

\[ E_{21} = \begin{bmatrix} 1 & 0 & 0 \\ -\ell_{21} & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \]

전체 소거 과정을 행렬 곱으로 표현하면:

\[ E_{32} (E_{21} A) = U \implies (E_{32} E_{21}) A = U \]

역행렬 \(E_{21}^{-1}\) 은 승수의 부호만 바꾼 행렬이다 — “뺐으면 역은 더한다.”

4 §2.4 — 행렬 연산의 규칙

4.1 행렬 곱셈의 두 가지 관점

\(AB = C\) 에서 \(C\) 의 \((i, j)\) 원소는 \(A\) 의 \(i\) 행과 \(B\) 의 \(j\) 열의 내적이다.

\[ c_{ij} = \sum_{k=1}^{n} a_{ik} b_{kj} = (\text{row } i \text{ of } A) \cdot (\text{col } j \text{ of } B) \]

열 방법으로 보면: \(B\) 의 각 열은 \(A\) 의 열들의 선형 결합으로 나타난다.

\[ AB = A \begin{bmatrix} | & & | \\ b_1 & \cdots & b_n \\ | & & | \end{bmatrix} = \begin{bmatrix} | & & | \\ Ab_1 & \cdots & Ab_n \\ | & & | \end{bmatrix} \]

4.2 핵심 규칙 요약

규칙	성립 여부
결합 법칙 \(A(BC) = (AB)C\)	성립
분배 법칙 \(A(B + C) = AB + AC\)	성립
교환 법칙 \(AB = BA\)	일반적으로 불성립
\((AB)^\top = B^\top A^\top\)	성립

행렬 곱셈이 비가환적(non-commutative)이라는 사실은 선형대수 전체에서 중요한 주의사항이다.

5 §2.5 — 역행렬

5.1 역행렬의 정의와 존재 조건

\(n \times n\) 행렬 \(A\) 의 역행렬 \(A^{-1}\) 은 다음을 만족하는 행렬이다.

\[ A^{-1} A = I = A A^{-1} \]

역행렬이 존재할 조건:

\(n\) 개의 피벗이 모두 0이 아닌 경우
\(A\) 가 특이 행렬(Singular)이 아닌 경우
\(Ax = 0\) 의 해가 \(x = 0\) 뿐인 경우 (세 조건은 동치)

5.2 가우스-조르당 소거법으로 역행렬 계산

\([A \mid I]\) 에 소거법을 적용하면 \([I \mid A^{-1}]\) 이 된다.

\[ [A \mid I] \xrightarrow{\text{소거}} [I \mid A^{-1}] \]

\(2 \times 2\) 행렬의 역행렬 공식:

\[ A = \begin{bmatrix} a & b \\ c & d \end{bmatrix} \implies A^{-1} = \frac{1}{ad - bc} \begin{bmatrix} d & -b \\ -c & a \end{bmatrix} \]

행렬식(Determinant) \(ad - bc = 0\) 이면 역행렬이 존재하지 않는다.

5.3 역행렬의 성질

\[ (AB)^{-1} = B^{-1} A^{-1} \qquad (A^\top)^{-1} = (A^{-1})^\top \]

곱의 역행렬에서 순서가 뒤집히는 것에 주의한다 — 이것도 비가환성의 결과이다.

6 §2.6 — A = LU: 소거법은 곧 분해다

6.1 핵심 통찰

소거 행렬 \(E_{ij}\) 로 \(A\) 를 \(U\) 로 변환하는 과정을 역순으로 읽으면 \(A = LU\) 가 된다.

\[ E_{32} E_{21} A = U \implies A = E_{21}^{-1} E_{32}^{-1} U = LU \]

여기서 \(L = E_{21}^{-1} E_{32}^{-1}\) 은 하삼각행렬(Lower Triangular Matrix)이고, 대각 원소는 모두 1이다.

\[ L = \begin{bmatrix} 1 & 0 & 0 \\ \ell_{21} & 1 & 0 \\ \ell_{31} & \ell_{32} & 1 \end{bmatrix}, \quad U = \begin{bmatrix} u_{11} & u_{12} & u_{13} \\ 0 & u_{22} & u_{23} \\ 0 & 0 & u_{33} \end{bmatrix} \]

\(L\) 의 원소들은 정확히 소거 과정에서 구한 승수 \(\ell_{ij}\) 들이다.

6.2 왜 LU 분해인가?

\(Ax = b\) 를 한 번만 소거하는 대신, \(A = LU\) 로 분해해 두면:

\(L\mathbf{c} = b\) 를 전방 대입(Forward Substitution)으로 풀어 \(c\) 를 구한다.
\(U\mathbf{x} = c\) 를 후방 대입(Back Substitution)으로 풀어 \(x\) 를 구한다.

\(A = LU\) 를 한 번 계산(\(O(n^3/3)\))하면, 서로 다른 \(b\) 에 대해 각 \(O(n^2)\) 으로 해를 구할 수 있다.

단계	연산	비용
LU 분해 (1회)	\(A \to L, U\)	\(O(n^3/3)\)
전방 대입 (매번)	\(L\mathbf{c} = b\)	\(O(n^2/2)\)
후방 대입 (매번)	\(U\mathbf{x} = c\)	\(O(n^2/2)\)

6.3 행 교환이 있을 때: PA = LU

소거 중 행 교환이 필요하면 치환 행렬 \(P\) 를 도입하여 \(PA = LU\) 로 분해한다. \(P\) 는 행들의 순서를 재배치하는 행렬이다.

7 §2.7 — 전치 행렬과 치환 행렬

7.1 전치 행렬 \(A^\top\)

\(A\) 의 행과 열을 바꾼 행렬이다.

\[ (A^\top)_{ij} = A_{ji} \]

중요한 성질:

\[ (AB)^\top = B^\top A^\top \qquad (A^\top)^\top = A \]

대칭 행렬(Symmetric Matrix): \(S = S^\top\). 이 클래스의 행렬은 Ch.6-7에서 핵심 역할을 한다.

7.2 치환 행렬 \(P\)

\(n \times n\) 단위 행렬의 행을 재배치한 행렬이다. \(PA\) 는 \(A\) 의 행 순서를 바꾼다.

\[ P^{-1} = P^\top \]

\(n \times n\) 치환 행렬은 \(n!\) 개 존재한다. 소거법에서 피벗이 0이 되면 \(P\) 를 사용한다.

7.3 완전한 분해: \(PA = LU\)

행 교환을 포함한 일반적인 경우, 소거법은 다음을 보장한다.

\[ PA = LU \]

\(A\) 가 가역이면 항상 이 분해가 존재한다. NumPy의 scipy.linalg.lu 등 모든 LU 분해 함수가 이 형태를 반환한다.

8 왜 Ch.2가 중요한가 — ML/DL 연결

8.1 선형 회귀의 정규 방정식

선형 회귀에서 최적 파라미터 \(\hat{w}\) 는 정규 방정식을 푸는 것이다.

\[ A^\top A \hat{w} = A^\top b \]

\(A^\top A\) 는 양정치 대칭 행렬이므로 LU(실제로는 Cholesky) 분해로 효율적으로 풀 수 있다. 특성 수 \(p\) 가 작을 때(\(p \lesssim 10^4\)) 경사 하강법보다 빠르고 정확하다.

8.2 딥러닝에서의 역할

신경망 학습의 각 레이어는 \(\mathbf{y} = W\mathbf{x} + \mathbf{b}\), 즉 \(Ax = b\) 형태이다. 역전파(Backpropagation)는 자코비안 행렬(Jacobian)의 곱이며, Ch.2의 행렬 곱셈 규칙이 그대로 적용된다.

8.3 수치 안정성: 피벗 선택이 왜 중요한가

소거법에서 피벗이 매우 작으면 반올림 오차(Round-off Error)가 폭발적으로 증폭된다. 이를 막기 위해 부분 피벗팅(Partial Pivoting) — 현재 열에서 가장 큰 절댓값을 피벗으로 선택 — 을 사용한다. numpy.linalg.solve는 내부적으로 이 방식을 기본 적용한다.

9 코드로 확인하기

9.1 Step 1 — 소거법 직접 구현 (NumPy 없이)

def gaussian_elimination(A, b):
    """Ax = b를 가우스 소거법으로 풀기 (행 교환 없음)"""
    import copy
    n = len(b)
    A = [list(row) for row in A]
    b = list(b)

    # 전방 소거 (Forward Elimination)
    for k in range(n):
        pivot = A[k][k]
        if abs(pivot) < 1e-12:
            raise ValueError(f"피벗이 0: {k}열에서 특이 행렬 감지")
        for i in range(k + 1, n):
            multiplier = A[i][k] / pivot
            for j in range(k, n):
                A[i][j] -= multiplier * A[k][j]
            b[i] -= multiplier * b[k]

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

    return x

# §2.1 예시: x - 2y = 1, 3x + 2y = 11
A = [[1, -2], [3, 2]]
b = [1, 11]
x = gaussian_elimination(A, b)
print(f"해: x = {x[0]:.1f}, y = {x[1]:.1f}")   # x = 3.0, y = 1.0

9.2 Step 2 — LU 분해 (SciPy)

import numpy as np
from scipy.linalg import lu, lu_factor, lu_solve

# 3×3 예시: §2.1 3변수 시스템
A = np.array([[1, 2, 3],
              [2, 5, 2],
              [6, -3, 1]], dtype=float)
b = np.array([6, 4, 2], dtype=float)

# LU 분해: PA = LU
P, L, U = lu(A)
print("L =\n", L)
print("U =\n", U)
print("P =\n", P)

# PA = LU 검증
print("PA - LU =\n", P @ A - L @ U)  # 모든 원소 ≈ 0

# 실제로 Ax = b 풀기 (LU 분해 활용)
lu_fac = lu_factor(A)
x = lu_solve(lu_fac, b)
print(f"\n해: x = {x}")               # [0. 0. 2.]
print("검증 Ax - b =", A @ x - b)    # [0. 0. 0.]

9.3 Step 3 — 여러 우변에 재사용

import numpy as np
from scipy.linalg import lu_factor, lu_solve

# 계수 행렬 A가 고정, 우변만 바뀌는 경우 — LU 분해의 이점
A = np.array([[2, 1, 1],
              [4, 3, 3],
              [8, 7, 9]], dtype=float)

# LU 분해 1회 (O(n^3/3))
lu_fac = lu_factor(A)

# 여러 우변 b에 대해 각 O(n^2)으로 해결
b_list = [
    np.array([1, 1, 1], dtype=float),
    np.array([2, 5, 8], dtype=float),
    np.array([0, 1, 0], dtype=float),
]

for i, b in enumerate(b_list):
    x = lu_solve(lu_fac, b)
    print(f"b{i+1} = {b}, x = {x.round(4)}")

10 관련 주제

이 챕터에서 다루는 세부 포스트

선행 지식

후속 주제