1 이 절의 위치
Ch.4의 마지막 절이다. 앞 절들이 “왜”를 다뤘다면, §4.4는 “어떻게 효율적으로”를 다룬다.
§4.1 네 부분공간의 직교성 — 왜 열공간에 투영할 수 있는가
↓
§4.2 투영 — p = A(AᵀA)⁻¹Aᵀb
↓
§4.3 최소제곱법 — AᵀAx̂ = Aᵀb (정규방정식)
↓ "그런데 AᵀA의 역행렬 계산이 비싸고 수치적으로 불안정하다"
§4.4 Gram-Schmidt & QR 분해 ← 지금 여기§4.4의 핵심 메시지는 단 하나다.
기저가 정규직교(orthonormal)하면, \(\mathbf{A}^\top \mathbf{A} = \mathbf{I}\) 가 되어 모든 공식이 극적으로 단순해진다.
그리고 어떤 선형 독립 기저라도 Gram-Schmidt로 정규직교 기저로 변환할 수 있다.
2 정규직교의 정의
2.1 직교 + 단위 길이
벡터 \(\mathbf{q}_1, \ldots, \mathbf{q}_n\) 이 정규직교하다 ⟺ 다음 두 조건을 모두 만족한다.
\[\mathbf{q}_i^\top \mathbf{q}_j = \begin{cases} 0 & i \neq j \quad \text{(직교)} \\ 1 & i = j \quad \text{(단위 길이)} \end{cases}\]
크로네커 델타 기호로 쓰면: \(\mathbf{q}_i^\top \mathbf{q}_j = \delta_{ij}\)
직관: “직교 기저(orthogonal basis)”는 서로 수직인 막대 \(n\) 개, “정규직교 기저(orthonormal basis)”는 그 막대들을 모두 길이 1로 맞춘 것. 표준 기저 \(\mathbf{e}_1, \mathbf{e}_2, \ldots, \mathbf{e}_n\) 이 가장 익숙한 예시다.
2.2 왜 굳이 “단위 길이”를 요구하는가
직교만으로도 많은 것이 된다. 그러나 단위 길이까지 확보하면 분모에 나타나는 \(\|\mathbf{q}_i\|^2\) 항이 모두 1이 되어 사라진다. 이 “0.1cm의 차이”가 실제 계산에서는 “1톤의 단순화”를 만든다.
3 행렬 \(\mathbf{Q}\) 의 정의
3.1 \(\mathbf{Q}^\top \mathbf{Q} = \mathbf{I}\)
정규직교 벡터들을 열로 가진 행렬을 \(\mathbf{Q}\) 라 부른다.
\[\mathbf{Q} = \begin{bmatrix} | & | & & | \\ \mathbf{q}_1 & \mathbf{q}_2 & \cdots & \mathbf{q}_n \\ | & | & & | \end{bmatrix}\]
\(\mathbf{Q}^\top \mathbf{Q}\) 의 \((i, j)\) 성분은 \(\mathbf{q}_i^\top \mathbf{q}_j = \delta_{ij}\) 이므로:
\[\boxed{\mathbf{Q}^\top \mathbf{Q} = \mathbf{I}_n}\]
주의: \(\mathbf{Q}\) 가 직사각 (\(m > n\))이면 \(\mathbf{Q}^\top \mathbf{Q} = \mathbf{I}_n\) 은 성립하지만 \(\mathbf{Q}\mathbf{Q}^\top \neq \mathbf{I}_m\) 이다. \(\mathbf{Q}^\top\) 은 왼쪽 역원일 뿐이다.
3.2 정사각 \(\mathbf{Q}\): “직교 행렬(orthogonal matrix)”
\(\mathbf{Q}\) 가 \(n \times n\) 정사각 행렬이고 \(\mathbf{Q}^\top \mathbf{Q} = \mathbf{I}\) 이면, \(\mathbf{Q}^\top = \mathbf{Q}^{-1}\) 이다. 그러면 \(\mathbf{Q}\mathbf{Q}^\top = \mathbf{I}\) 도 자동으로 성립한다.
수학 용어의 역사적 실수: “직교 행렬(orthogonal matrix)”이라고 부르지만, 실제로는 정규직교 열을 가진 정사각 행렬이다. “정규직교 행렬(orthonormal matrix)”이 더 정확한 이름이었겠지만, 전통을 따라 “직교 행렬”로 부른다. 정사각이 아닌 \(\mathbf{Q}\) 는 “직교 행렬”이라 부르지 않는다 — 단지 “정규직교 열을 가진 행렬”이라고 한다.
4 직교 행렬의 대표 예시
4.1 예시 1: 회전 행렬
\[\mathbf{Q} = \begin{bmatrix} \cos\theta & -\sin\theta \\ \sin\theta & \cos\theta \end{bmatrix}\]
검증: - 열 1 길이: \(\cos^2\theta + \sin^2\theta = 1\) ✓ - 열 2 길이: \(\sin^2\theta + \cos^2\theta = 1\) ✓ - 두 열 내적: \(-\cos\theta\sin\theta + \sin\theta\cos\theta = 0\) ✓
직관: 회전은 “단순한 좌표계 이동”이다. 모든 벡터가 같은 각도만큼 돌아간다. 길이가 변하지 않는 것은 당연하고, 이것이 \(\mathbf{Q}^\top \mathbf{Q} = \mathbf{I}\) 의 기하적 의미이다.
\(\mathbf{Q}^{-1}\) 는 \(-\theta\) 만큼 회전. \(\cos(-\theta) = \cos\theta\), \(\sin(-\theta) = -\sin\theta\) 이므로 \(\mathbf{Q}^{-1} = \mathbf{Q}^\top\) 이 자동 성립.
4.2 예시 2: 치환 행렬
\[\mathbf{P} = \begin{bmatrix} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{bmatrix}\]
각 열이 단위 벡터 \(\mathbf{e}_i\) 이므로 모두 길이 1. 서로 다른 단위 벡터는 직교. 따라서 모든 치환 행렬은 직교 행렬이다.
직관: 치환은 “성분의 순서만 바꾸는” 변환이므로 길이와 각도가 보존된다. 당연히 직교.
4.3 예시 3: 반사 행렬 (하우스홀더 반사)
단위 벡터 \(\mathbf{u}\) 에 대해 \(\mathbf{Q} = \mathbf{I} - 2\mathbf{u}\mathbf{u}^\top\) 로 정의되는 반사 행렬.
검증:
\[\mathbf{Q}^\top \mathbf{Q} = (\mathbf{I} - 2\mathbf{u}\mathbf{u}^\top)(\mathbf{I} - 2\mathbf{u}\mathbf{u}^\top) = \mathbf{I} - 4\mathbf{u}\mathbf{u}^\top + 4\mathbf{u}(\mathbf{u}^\top \mathbf{u})\mathbf{u}^\top\]
\(\mathbf{u}\) 가 단위 벡터이므로 \(\mathbf{u}^\top \mathbf{u} = 1\):
\[\mathbf{Q}^\top \mathbf{Q} = \mathbf{I} - 4\mathbf{u}\mathbf{u}^\top + 4\mathbf{u}\mathbf{u}^\top = \mathbf{I}\]
직관: 거울에 대한 반사. 두 번 반사하면 원래대로 돌아온다 (\(\mathbf{Q}^2 = \mathbf{I}\)). \(\mathbf{Q} = \mathbf{Q}^\top = \mathbf{Q}^{-1}\) 이 한꺼번에 성립하는 특별한 직교 행렬.
이 반사 행렬이 수치적으로 가장 안정적인 QR 분해의 도구가 된다 (§ 뒤에서 언급).
5 직교 행렬의 기하학적 성질
5.1 길이 보존
\(\mathbf{Q}\) 가 정규직교 열을 가지면:
\[\|\mathbf{Q}\mathbf{x}\|^2 = (\mathbf{Q}\mathbf{x})^\top (\mathbf{Q}\mathbf{x}) = \mathbf{x}^\top \mathbf{Q}^\top \mathbf{Q} \mathbf{x} = \mathbf{x}^\top \mathbf{I} \mathbf{x} = \mathbf{x}^\top \mathbf{x} = \|\mathbf{x}\|^2\]
\[\boxed{\|\mathbf{Q}\mathbf{x}\| = \|\mathbf{x}\|}\]
직관: 직교 변환은 “자(ruler)를 돌리거나 뒤집는 것”이다. 자의 눈금은 변하지 않는다.
5.2 각도 보존 (내적 보존)
\[(\mathbf{Q}\mathbf{x})^\top (\mathbf{Q}\mathbf{y}) = \mathbf{x}^\top \mathbf{Q}^\top \mathbf{Q} \mathbf{y} = \mathbf{x}^\top \mathbf{y}\]
내적이 보존되므로 \(\cos\theta = \mathbf{x}^\top\mathbf{y} / (\|\mathbf{x}\|\|\mathbf{y}\|)\) 도 보존. 두 벡터 사이의 각도가 그대로다.
의미: 직교 변환은 강체 운동(rigid motion) 이다. 도형을 구부리거나 늘이지 않고, 단지 회전/반사/조합만 한다.
5.3 수치 안정성
“길이를 늘리지 않는다”는 성질이 수치 계산에서 결정적이다. 행렬을 반복해서 곱할 때 일반 행렬은 오차가 지수적으로 증폭될 수 있지만, \(\mathbf{Q}\) 를 곱하는 연산은 오차를 증폭시키지 않는다.
LAPACK, BLAS 같은 수치 라이브러리가 가능한 한 직교 행렬로 연산을 대체하는 이유다.
6 투영 공식의 단순화: \(\mathbf{A}\) 대신 \(\mathbf{Q}\)
여기가 §4.4의 심장부다. §4.2에서 유도한 투영 공식에 \(\mathbf{A} \to \mathbf{Q}\) 를 대입한다.
6.1 일반 공식 (§4.2 복습)
| 양 | 공식 |
|---|---|
| 최소제곱 해 | \(\hat{\mathbf{x}} = (\mathbf{A}^\top \mathbf{A})^{-1} \mathbf{A}^\top \mathbf{b}\) |
| 투영 벡터 | \(\mathbf{p} = \mathbf{A}(\mathbf{A}^\top \mathbf{A})^{-1} \mathbf{A}^\top \mathbf{b}\) |
| 투영 행렬 | \(\mathbf{P} = \mathbf{A}(\mathbf{A}^\top \mathbf{A})^{-1} \mathbf{A}^\top\) |
6.2 \(\mathbf{Q}\) 를 대입
\(\mathbf{Q}^\top \mathbf{Q} = \mathbf{I}\) 이므로 \((\mathbf{Q}^\top \mathbf{Q})^{-1} = \mathbf{I}\) 이고, 역행렬 계산이 완전히 사라진다.
| 양 | 공식 |
|---|---|
| 최소제곱 해 | \(\hat{\mathbf{x}} = \mathbf{Q}^\top \mathbf{b}\) |
| 투영 벡터 | \(\mathbf{p} = \mathbf{Q}\mathbf{Q}^\top \mathbf{b}\) |
| 투영 행렬 | \(\mathbf{P} = \mathbf{Q}\mathbf{Q}^\top\) |
세 번 강조:
\[\boxed{\hat{\mathbf{x}} = \mathbf{Q}^\top \mathbf{b}, \quad \mathbf{p} = \mathbf{Q}\mathbf{Q}^\top \mathbf{b}, \quad \mathbf{P} = \mathbf{Q}\mathbf{Q}^\top}\]
6.3 “n 개의 독립적인 1차원 투영”
\(\hat{\mathbf{x}} = \mathbf{Q}^\top \mathbf{b}\) 의 의미를 풀어쓰면:
\[\hat{x}_i = \mathbf{q}_i^\top \mathbf{b}\]
즉 \(i\) 번째 좌표는 단순히 \(\mathbf{b}\) 와 \(\mathbf{q}_i\) 의 내적이다. 투영 벡터는:
\[\mathbf{p} = \mathbf{Q}\hat{\mathbf{x}} = \sum_{i=1}^n \hat{x}_i \mathbf{q}_i = \sum_{i=1}^n (\mathbf{q}_i^\top \mathbf{b}) \mathbf{q}_i\]
직관: \(\mathbf{b}\) 를 각 \(\mathbf{q}_i\) 방향으로 독립적으로 투영한 뒤 그 결과들을 단순히 더한다. 각 방향의 투영이 서로 간섭하지 않는다 (coupling-free).
일반 기저였다면 \(\mathbf{A}^\top \mathbf{A}\) 의 비대각 원소가 “다른 방향과의 간섭”을 표현했다. 정규직교 기저에서는 \(\mathbf{Q}^\top \mathbf{Q} = \mathbf{I}\) 이므로 비대각 원소가 모두 0이다. 즉 기저 벡터들이 정보를 중복하지 않고 완전히 분리된 방향으로 기여한다.
6.4 정사각 \(\mathbf{Q}\): 전체 공간 재구성
\(\mathbf{Q}\) 가 정사각 (\(m = n\))이면 \(C(\mathbf{Q}) = \mathbb{R}^n\) 이고, \(\mathbf{b}\) 를 전체 공간에 투영하는 것이므로 \(\mathbf{p} = \mathbf{b}\). 그러면:
\[\mathbf{b} = (\mathbf{q}_1^\top \mathbf{b})\mathbf{q}_1 + (\mathbf{q}_2^\top \mathbf{b})\mathbf{q}_2 + \cdots + (\mathbf{q}_n^\top \mathbf{b})\mathbf{q}_n\]
이것이 푸리에 급수의 일반화 형태다. 함수를 sin/cos 기저로 분해하는 것은 무한 차원 벡터 공간에서의 위 공식과 같다. 각 “계수”는 함수와 기저의 내적으로 구해진다. 디지털 신호의 FFT, 이미지의 DCT, 웨이블릿 변환 — 모두 같은 아이디어의 변주다.
import numpy as np
import matplotlib.pyplot as plt
# Strang 교재 예시 4
Q = np.array([[-1, 2, 2],
[2, -1, 2],
[2, 2, -1]], dtype=float) / 3
print("Q =")
print(Q)
print(f"\nQᵀQ =\n{Q.T @ Q}") # 거의 단위행렬
print(f"\nQQᵀ =\n{Q @ Q.T}") # 거의 단위행렬 (정사각이므로)
# b = (0, 0, 1)를 세 개의 1차원 투영으로 분해
b = np.array([0, 0, 1], dtype=float)
# 각 qᵢ 방향 성분
for i in range(3):
q_i = Q[:, i]
coeff = q_i @ b
p_i = coeff * q_i
print(f"\nq{i+1}ᵀ b = {coeff:.4f}")
print(f"{coeff:.4f} * q{i+1} = {p_i}")
# 모두 더하면 b 복원
x_hat = Q.T @ b
reconstruction = Q @ x_hat
print(f"\n재구성 p = QQᵀb = {reconstruction}")
print(f"원래 b = {b}")
print(f"(정사각 Q → p = b ✓)")7 Gram-Schmidt 과정: 직교화 알고리즘
7.1 질문
임의의 선형 독립 벡터 \(\mathbf{a}, \mathbf{b}, \mathbf{c}\) 가 주어졌을 때, 같은 부분공간을 스팬하는 정규직교 벡터 \(\mathbf{q}_1, \mathbf{q}_2, \mathbf{q}_3\) 를 어떻게 만드는가?
7.2 핵심 아이디어
“새 벡터에서 이미 확정된 방향 성분을 빼면, 그 방향에 수직인 부분만 남는다.”
이것이 Gram-Schmidt의 모든 것이다. 한 번에 한 방향씩 직교화한다.
7.3 Step 1: 첫 벡터 그대로
\(\mathbf{A} = \mathbf{a}\) (방향 선택은 자유로우므로 \(\mathbf{a}\) 를 그대로 쓴다.)
7.4 Step 2: 두 번째 벡터에서 \(\mathbf{A}\) 성분 제거
\(\mathbf{b}\) 에서 \(\mathbf{A}\) 방향 투영 성분을 빼면 \(\mathbf{A}\) 에 수직인 부분만 남는다.
\[\mathbf{B} = \mathbf{b} - \frac{\mathbf{A}^\top \mathbf{b}}{\mathbf{A}^\top \mathbf{A}} \mathbf{A}\]
수직성 검증: \(\mathbf{A}^\top \mathbf{B} = \mathbf{A}^\top \mathbf{b} - \frac{\mathbf{A}^\top \mathbf{b}}{\mathbf{A}^\top \mathbf{A}}\mathbf{A}^\top \mathbf{A} = \mathbf{A}^\top \mathbf{b} - \mathbf{A}^\top \mathbf{b} = 0\) ✓
직관: 이것은 §4.2에서 본 “직선 위의 투영”의 나머지 = 수직 부분을 구하는 과정. \(\mathbf{B}\) 는 “\(\mathbf{b}\) 중에서 \(\mathbf{A}\) 와 수직인 부분”이다.
왜 \(\mathbf{B}\) 는 영벡터가 아닌가: 만약 \(\mathbf{B} = \mathbf{0}\) 이라면 \(\mathbf{b}\) 가 \(\mathbf{A}\) 의 스칼라 배수 — 즉 \(\mathbf{a}\) 와 종속이다. 입력 벡터들이 선형 독립이라는 전제에 모순.
7.5 Step 3: 세 번째 벡터에서 \(\mathbf{A}, \mathbf{B}\) 두 성분 제거
\(\mathbf{c}\) 에서 \(\mathbf{A}\) 방향과 \(\mathbf{B}\) 방향 성분을 모두 뺀다.
\[\mathbf{C} = \mathbf{c} - \frac{\mathbf{A}^\top \mathbf{c}}{\mathbf{A}^\top \mathbf{A}} \mathbf{A} - \frac{\mathbf{B}^\top \mathbf{c}}{\mathbf{B}^\top \mathbf{B}} \mathbf{B}\]
수직성 검증:
\[\mathbf{A}^\top \mathbf{C} = \mathbf{A}^\top \mathbf{c} - \frac{\mathbf{A}^\top \mathbf{c}}{\mathbf{A}^\top \mathbf{A}}\mathbf{A}^\top \mathbf{A} - \frac{\mathbf{B}^\top \mathbf{c}}{\mathbf{B}^\top \mathbf{B}}\underbrace{\mathbf{A}^\top \mathbf{B}}_{=0} = 0\]
(마지막 항이 0인 이유는 Step 2에서 \(\mathbf{B}\) 가 이미 \(\mathbf{A}\) 에 수직이도록 만들었기 때문이다.) \(\mathbf{B}^\top \mathbf{C} = 0\) 도 같은 방식으로 확인 가능.
7.6 Step 4: 정규화
마지막으로 각 직교 벡터를 길이로 나누어 단위 벡터로 만든다.
\[\mathbf{q}_1 = \frac{\mathbf{A}}{\|\mathbf{A}\|}, \quad \mathbf{q}_2 = \frac{\mathbf{B}}{\|\mathbf{B}\|}, \quad \mathbf{q}_3 = \frac{\mathbf{C}}{\|\mathbf{C}\|}\]
왜 마지막에 정규화하는가: 중간 단계에서 정규화하면 나중의 투영 계산이 “나누어떨어지지 않는 수”로 가득찬다. 마지막까지 \(\mathbf{A}, \mathbf{B}, \mathbf{C}\) 형태를 유지하면 계산이 더 깔끔하다.
7.7 기하학적 그림
Step 1: A = a (그대로)
Step 2: b를 A에 투영 → 뺀 것이 B (A에 수직)
Step 3: c를 A에 투영하고 B에도 투영 → 둘 다 뺀 것이 C (A, B 둘 다에 수직)
Step 4: A, B, C를 각각 단위화 → q₁, q₂, q₃8 Gram-Schmidt 예시
Strang 교재의 고전 예시 (Ch.4 Example 5):
\[\mathbf{a} = \begin{bmatrix} 1 \\ -1 \\ 0 \end{bmatrix}, \quad \mathbf{b} = \begin{bmatrix} 2 \\ 0 \\ -2 \end{bmatrix}, \quad \mathbf{c} = \begin{bmatrix} 3 \\ -3 \\ 3 \end{bmatrix}\]
8.1 Step 1: \(\mathbf{A} = \mathbf{a}\)
\(\mathbf{A}^\top \mathbf{A} = 1 + 1 + 0 = 2\)
8.2 Step 2: \(\mathbf{B}\) 계산
\(\mathbf{A}^\top \mathbf{b} = 1 \cdot 2 + (-1) \cdot 0 + 0 \cdot (-2) = 2\)
\[\mathbf{B} = \mathbf{b} - \frac{2}{2}\mathbf{A} = \begin{bmatrix} 2 \\ 0 \\ -2 \end{bmatrix} - \begin{bmatrix} 1 \\ -1 \\ 0 \end{bmatrix} = \begin{bmatrix} 1 \\ 1 \\ -2 \end{bmatrix}\]
검증: \(\mathbf{A}^\top \mathbf{B} = 1 - 1 + 0 = 0\) ✓, \(\mathbf{B}^\top \mathbf{B} = 1 + 1 + 4 = 6\)
8.3 Step 3: \(\mathbf{C}\) 계산
\(\mathbf{A}^\top \mathbf{c} = 3 + 3 + 0 = 6\), \(\mathbf{B}^\top \mathbf{c} = 3 - 3 - 6 = -6\)
\[\mathbf{C} = \mathbf{c} - \frac{6}{2}\mathbf{A} - \frac{-6}{6}\mathbf{B} = \mathbf{c} - 3\mathbf{A} + \mathbf{B}\]
\[= \begin{bmatrix} 3 \\ -3 \\ 3 \end{bmatrix} - \begin{bmatrix} 3 \\ -3 \\ 0 \end{bmatrix} + \begin{bmatrix} 1 \\ 1 \\ -2 \end{bmatrix} = \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}\]
검증: - \(\mathbf{A}^\top \mathbf{C} = 1 - 1 + 0 = 0\) ✓ - \(\mathbf{B}^\top \mathbf{C} = 1 + 1 - 2 = 0\) ✓
8.4 Step 4: 정규화
- \(\|\mathbf{A}\| = \sqrt{2}\), \(\|\mathbf{B}\| = \sqrt{6}\), \(\|\mathbf{C}\| = \sqrt{3}\)
\[\mathbf{q}_1 = \frac{1}{\sqrt{2}}\begin{bmatrix} 1 \\ -1 \\ 0 \end{bmatrix}, \quad \mathbf{q}_2 = \frac{1}{\sqrt{6}}\begin{bmatrix} 1 \\ 1 \\ -2 \end{bmatrix}, \quad \mathbf{q}_3 = \frac{1}{\sqrt{3}}\begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}\]
주의: 원래 벡터들 \(\mathbf{a}, \mathbf{b}, \mathbf{c}\) 는 정수로 깔끔했지만, 직교 벡터 \(\mathbf{A}, \mathbf{B}, \mathbf{C}\) 도 우연히 깔끔했다. 하지만 정규화하면 거의 항상 제곱근이 등장한다. 이것이 Gram-Schmidt의 “작은 흠”이다.
import numpy as np
# Strang 예시 5
a = np.array([1, -1, 0], dtype=float)
b_vec = np.array([2, 0, -2], dtype=float)
c = np.array([3, -3, 3], dtype=float)
# Gram-Schmidt 수동 실행
A = a.copy()
B = b_vec - (A @ b_vec) / (A @ A) * A
C = c - (A @ c) / (A @ A) * A - (B @ c) / (B @ B) * B
print(f"A = {A}")
print(f"B = {B}")
print(f"C = {C}")
# 직교성 확인
print(f"\nA·B = {A @ B}") # 0
print(f"A·C = {A @ C}") # 0
print(f"B·C = {B @ C}") # 0
# 정규화
q1 = A / np.linalg.norm(A)
q2 = B / np.linalg.norm(B)
q3 = C / np.linalg.norm(C)
print(f"\nq1 = {q1} (‖q1‖ = {np.linalg.norm(q1):.4f})")
print(f"q2 = {q2} (‖q2‖ = {np.linalg.norm(q2):.4f})")
print(f"q3 = {q3} (‖q3‖ = {np.linalg.norm(q3):.4f})")
# Q 행렬 구성 및 QᵀQ = I 확인
Q = np.column_stack([q1, q2, q3])
print(f"\nQᵀQ =\n{np.round(Q.T @ Q, 10)}")9 일반 Gram-Schmidt 공식
\(k\) 번째 단계에서, 새 벡터 \(\mathbf{a}_k\) 에서 이전에 확정된 모든 방향 \(\mathbf{q}_1, \ldots, \mathbf{q}_{k-1}\) 의 성분을 뺀다.
\[\mathbf{u}_k = \mathbf{a}_k - \sum_{j=1}^{k-1} (\mathbf{q}_j^\top \mathbf{a}_k) \mathbf{q}_j\]
\[\mathbf{q}_k = \frac{\mathbf{u}_k}{\|\mathbf{u}_k\|}\]
모든 단계에서 같은 아이디어 반복: 그동안 쌓은 직교 기저에 대한 투영을 모두 빼면, 나머지가 새로운 직교 방향. 이것이 수학적 귀납법처럼 작동한다 — “\(k-1\) 단계까지 직교 기저가 있다” ⟹ “\(k\) 단계의 \(\mathbf{q}_k\) 도 직교”이다.
9.1 Modified Gram-Schmidt (수치 안정성)
위 공식은 “한 번에 모든 투영을 뺀다” (Classical Gram-Schmidt). 실제 수치 계산에서는 “한 번에 하나씩 투영을 뺀다” 가 더 안정적이다.
k 번째 단계, 수정된 방식:
u = a_k
for j = 1 to k-1:
u = u - (q_j^T u) q_j ← 누적된 u에서 투영을 뺀다 (원래 a_k가 아니라)
q_k = u / ‖u‖차이점: Classical은 모두 \(\mathbf{a}_k\) 기준으로 투영을 계산한다. Modified는 “그 전 단계까지 직교화된 결과” 기준으로 투영을 계산한다. 수학적으로는 같지만, 부동소수점 오차가 축적되는 양상이 다르다. Modified 방식이 약간 더 안정적이다.
10 \(\mathbf{A} = \mathbf{Q}\mathbf{R}\) 분해
10.1 동기: “어떻게 \(\mathbf{A}\) 와 \(\mathbf{Q}\) 가 연결되는가”
Gram-Schmidt 시작: \(\mathbf{A}\) 의 열 \(\mathbf{a}_1, \mathbf{a}_2, \ldots, \mathbf{a}_n\). Gram-Schmidt 결과: 정규직교 벡터 \(\mathbf{q}_1, \mathbf{q}_2, \ldots, \mathbf{q}_n\).
두 행렬 사이에 어떤 관계가 있어야 한다. 그 관계가 \(\mathbf{A} = \mathbf{Q}\mathbf{R}\) 이고, 여기서 \(\mathbf{R}\) 은 상삼각 행렬이다.
10.2 왜 \(\mathbf{R}\) 이 상삼각인가
Gram-Schmidt의 결정적 성질 — “나중 \(\mathbf{q}\) 는 이전 \(\mathbf{a}\) 에 관여하지 않는다”:
- \(\mathbf{a}_1\) 은 \(\mathbf{q}_1\) 만의 배수
- \(\mathbf{a}_2\) 는 \(\mathbf{q}_1, \mathbf{q}_2\) 의 조합 (단, \(\mathbf{q}_3, \mathbf{q}_4, \ldots\) 는 쓰이지 않음)
- \(\mathbf{a}_k\) 는 \(\mathbf{q}_1, \ldots, \mathbf{q}_k\) 의 조합 (단, \(\mathbf{q}_{k+1}, \ldots\) 는 쓰이지 않음)
이것을 행렬 곱 형태로 쓰면:
\[\mathbf{A} = \mathbf{Q}\mathbf{R} = \begin{bmatrix} | & | & & | \\ \mathbf{q}_1 & \mathbf{q}_2 & \cdots & \mathbf{q}_n \\ | & | & & | \end{bmatrix} \begin{bmatrix} r_{11} & r_{12} & \cdots & r_{1n} \\ 0 & r_{22} & \cdots & r_{2n} \\ \vdots & & \ddots & \vdots \\ 0 & 0 & \cdots & r_{nn} \end{bmatrix}\]
\(\mathbf{R}\) 의 \(k\) 번째 열은 “\(\mathbf{a}_k\) 를 \(\mathbf{q}_1, \ldots, \mathbf{q}_k\) 로 표현한 계수들”이고, \(k\) 번째 행 이후는 모두 0이다. 이것이 \(\mathbf{R}\) 이 상삼각이 되는 기하학적 이유다.
10.3 \(\mathbf{R}\) 의 성분 계산
\(\mathbf{A} = \mathbf{Q}\mathbf{R}\) 양변에 \(\mathbf{Q}^\top\) 을 왼쪽에서 곱하면 \(\mathbf{Q}^\top \mathbf{A} = \mathbf{Q}^\top \mathbf{Q} \mathbf{R} = \mathbf{R}\).
\[\boxed{\mathbf{R} = \mathbf{Q}^\top \mathbf{A}}\]
성분별로: \(r_{ij} = \mathbf{q}_i^\top \mathbf{a}_j\). \(i > j\) 이면 \(\mathbf{q}_i\) 는 \(\mathbf{a}_j\) 가 만들어낸 부분공간 \(\text{span}\{\mathbf{a}_1, \ldots, \mathbf{a}_j\}\) 에 수직이므로 \(r_{ij} = 0\) — 이것이 상삼각 구조.
10.4 구체 예시 (위 Strang 예시 계속)
\(\mathbf{A} = [\mathbf{a} \mid \mathbf{b} \mid \mathbf{c}]\) 의 QR 분해는:
\[\mathbf{A} = \begin{bmatrix} 1 & 2 & 3 \\ -1 & 0 & -3 \\ 0 & -2 & 3 \end{bmatrix}\]
\(\mathbf{R} = \mathbf{Q}^\top \mathbf{A}\) 성분별 계산:
- \(r_{11} = \mathbf{q}_1^\top \mathbf{a} = \|\mathbf{A}\| = \sqrt{2}\)
- \(r_{12} = \mathbf{q}_1^\top \mathbf{b} = \sqrt{2}\)
- \(r_{13} = \mathbf{q}_1^\top \mathbf{c} = \sqrt{18} = 3\sqrt{2}\)
- \(r_{22} = \mathbf{q}_2^\top \mathbf{b} = \|\mathbf{B}\| = \sqrt{6}\)
- \(r_{23} = \mathbf{q}_2^\top \mathbf{c} = -\sqrt{6}\)
- \(r_{33} = \mathbf{q}_3^\top \mathbf{c} = \|\mathbf{C}\| = \sqrt{3}\)
- 하삼각 (\(r_{21}, r_{31}, r_{32}\)) = 모두 0
\[\mathbf{R} = \begin{bmatrix} \sqrt{2} & \sqrt{2} & 3\sqrt{2} \\ 0 & \sqrt{6} & -\sqrt{6} \\ 0 & 0 & \sqrt{3} \end{bmatrix}\]
대각 성분의 의미: \(r_{kk} = \|\mathbf{u}_k\|\) — 각 직교화 단계에서 “새로 만들어진 직교 방향의 길이”다. 이것이 모두 양수이면 \(\mathbf{R}\) 이 가역이고, 따라서 원래 벡터들이 선형 독립이라는 증거가 된다.
# QR 분해 수치 계산
A_mat = np.column_stack([a, b_vec, c])
print("A =")
print(A_mat)
# NumPy QR
Q_np, R_np = np.linalg.qr(A_mat)
print(f"\nQ =\n{Q_np}")
print(f"\nR =\n{R_np}")
# 손 계산 결과와 비교 (부호 차이 가능)
print(f"\nQᵀQ =\n{np.round(Q_np.T @ Q_np, 10)}") # 단위행렬
print(f"\nQR 복원 = A?\n{np.round(Q_np @ R_np, 10)}")
print(f"A =\n{A_mat}")
# R 대각 성분 = ‖A‖, ‖B‖, ‖C‖ (부호 무시)
print(f"\nR 대각 (절대값): {np.abs(np.diag(R_np))}")
print(f"이론 값: [{np.sqrt(2):.4f}, {np.sqrt(6):.4f}, {np.sqrt(3):.4f}]")11 QR로 최소제곱 풀기
§4.3의 정규방정식 \(\mathbf{A}^\top \mathbf{A} \hat{\mathbf{x}} = \mathbf{A}^\top \mathbf{b}\) 가 QR 분해로 극적으로 단순해진다.
11.1 유도
\(\mathbf{A} = \mathbf{Q}\mathbf{R}\) 을 대입:
\[\mathbf{A}^\top \mathbf{A} = (\mathbf{Q}\mathbf{R})^\top (\mathbf{Q}\mathbf{R}) = \mathbf{R}^\top \mathbf{Q}^\top \mathbf{Q} \mathbf{R} = \mathbf{R}^\top \mathbf{R}\]
\[\mathbf{A}^\top \mathbf{b} = \mathbf{R}^\top \mathbf{Q}^\top \mathbf{b}\]
정규방정식은:
\[\mathbf{R}^\top \mathbf{R} \hat{\mathbf{x}} = \mathbf{R}^\top \mathbf{Q}^\top \mathbf{b}\]
\(\mathbf{R}^\top\) 은 가역이므로 양변에 왼쪽에서 \((\mathbf{R}^\top)^{-1}\) 을 곱하면:
\[\boxed{\mathbf{R}\hat{\mathbf{x}} = \mathbf{Q}^\top \mathbf{b}}\]
11.2 왜 이것이 획기적인가
\(\mathbf{R}\) 이 상삼각이다. 상삼각 행렬의 방정식은 후치환(back substitution) 한 번으로 풀린다. \(n \times n\) 상삼각 시스템은 \(\mathcal{O}(n^2)\) 연산만 필요하다 (일반 역행렬은 \(\mathcal{O}(n^3)\)).
더 중요한 이점: 수치적 안정성. \(\mathbf{A}^\top \mathbf{A}\) 를 직접 계산하면 조건수가 제곱된다 (\(\kappa(\mathbf{A}^\top \mathbf{A}) = \kappa(\mathbf{A})^2\)). QR 분해를 쓰면 조건수가 \(\kappa(\mathbf{A})\) 그대로 유지된다.
따라서 LAPACK, NumPy, MATLAB 등 모든 현대 수치 라이브러리는 최소제곱을 QR (또는 SVD)로 푼다. 정규방정식은 이론적 이해의 도구일 뿐이다.
# QR로 최소제곱 풀기
# 예시: §4.3에서 쓴 3점 직선 적합
t = np.array([0, 1, 2], dtype=float)
b = np.array([6, 0, 0], dtype=float)
A = np.column_stack([np.ones_like(t), t])
# 방법 1: 정규방정식 (교과서 방식)
x_normal = np.linalg.solve(A.T @ A, A.T @ b)
print(f"정규방정식 x̂ = {x_normal}")
# 방법 2: QR 분해 + 후치환
Q, R = np.linalg.qr(A)
# R x̂ = Qᵀ b
rhs = Q.T @ b
# 상삼각이므로 후치환
x_qr = np.linalg.solve(R, rhs)
print(f"QR 분해 x̂ = {x_qr}")
# 일치 확인
print(f"차이: {np.abs(x_normal - x_qr).max():.2e}")
# NumPy lstsq (내부적으로 SVD 사용)
x_lstsq, *_ = np.linalg.lstsq(A, b, rcond=None)
print(f"lstsq x̂ = {x_lstsq}")12 QR 분해의 두 형태: Reduced vs Full
\(\mathbf{A}\) 가 \(m \times n\) 직사각 행렬 (\(m > n\))일 때 QR 분해는 두 가지 형태로 표현 가능.
| 형태 | \(\mathbf{Q}\) 크기 | \(\mathbf{R}\) 크기 | 설명 |
|---|---|---|---|
| Reduced (Economy) | \(m \times n\) | \(n \times n\) | \(\mathbf{Q}\) 의 열이 \(C(\mathbf{A})\) 의 정규직교 기저만 |
| Full (Complete) | \(m \times m\) | \(m \times n\) | \(\mathbf{Q}\) 가 정사각. 추가 \(m - n\) 개 열은 \(C(\mathbf{A})^\perp = N(\mathbf{A}^\top)\) 기저 |
Full 형태는 네 부분공간을 완전히 보여준다 — \(\mathbf{Q}\) 의 처음 \(n\) 열은 열공간, 나머지 \(m - n\) 열은 좌영공간의 기저. Reduced 형태는 필요한 부분만 계산해서 메모리를 절약한다.
대부분의 실무에서는 Reduced 형태를 사용한다.
12.1 정사각 \(\mathbf{A}\) 의 역행렬도 QR 로 계산할 수 있다
\(\mathbf{A}\) 가 \(n \times n\) 정사각 가역 행렬이면 \(\mathbf{Q}\) 도 정사각이므로 \(\mathbf{Q}^{-1} = \mathbf{Q}^\top\). 따라서:
\[\mathbf{A}^{-1} = (\mathbf{Q}\mathbf{R})^{-1} = \mathbf{R}^{-1} \mathbf{Q}^{-1} = \mathbf{R}^{-1} \mathbf{Q}^\top\]
\(\mathbf{Q}^\top\) 은 전치만 하면 되므로 \(\mathcal{O}(n^2)\) 에 구해지고, \(\mathbf{R}^{-1}\) 은 상삼각 행렬의 역이므로 후치환으로 \(\mathcal{O}(n^2)\) 에 적용할 수 있다. 수치적으로도 직접 가우스-조르단 역행렬 계산보다 훨씬 안정적.
실무 주의: 이것도 결국 “역행렬 계산”이므로 np.linalg.inv 와 마찬가지로 피해야 할 경우가 많다. \(\mathbf{A}^{-1}\mathbf{b}\) 를 구하고 싶다면 \(\mathbf{R}\mathbf{x} = \mathbf{Q}^\top \mathbf{b}\) 후치환 한 번으로 끝난다 — 역행렬을 먼저 만들고 곱하는 것보다 빠르다. 역행렬을 명시적으로 들고 있어야 하는 경우에만 \(\mathbf{R}^{-1}\mathbf{Q}^\top\) 을 쓴다.
# Reduced vs Full QR
A = np.random.randn(5, 3) # 5x3 직사각 행렬
Q_red, R_red = np.linalg.qr(A, mode='reduced')
Q_full, R_full = np.linalg.qr(A, mode='complete')
print(f"Reduced: Q {Q_red.shape}, R {R_red.shape}")
print(f"Full: Q {Q_full.shape}, R {R_full.shape}")
# Full 형태에서 추가된 열은 좌영공간의 기저
left_null_basis = Q_full[:, 3:]
print(f"\n좌영공간 차원: {left_null_basis.shape[1]}")
print(f"Aᵀ (좌영공간 기저) = {np.round(A.T @ left_null_basis, 10)}") # 013 Householder 반사: 실전에서 더 쓰이는 방법
13.1 동기
Modified Gram-Schmidt도 큰 행렬에서는 수치 오차가 쌓인다. 완전히 다른 접근이 필요하다. LAPACK 같은 최고 수준의 라이브러리는 Householder 반사(reflection) 를 쓴다.
13.2 아이디어
앞서 본 반사 행렬 \(\mathbf{H} = \mathbf{I} - 2\mathbf{u}\mathbf{u}^\top\) 을 영리하게 선택하여 \(\mathbf{A}\) 의 첫 열의 아랫부분을 모두 0으로 만든다. 이 연산을 반복하면 \(\mathbf{A}\) 가 상삼각 \(\mathbf{R}\) 로 변환되고, 누적된 반사들의 곱이 \(\mathbf{Q}\) 가 된다.
\[\mathbf{H}_n \mathbf{H}_{n-1} \cdots \mathbf{H}_1 \mathbf{A} = \mathbf{R} \implies \mathbf{A} = \underbrace{(\mathbf{H}_1 \cdots \mathbf{H}_n)}_{\mathbf{Q}} \mathbf{R}\]
장점: 1. 각 반사가 직교 행렬이므로 오차가 증폭되지 않음 2. 연산량이 Gram-Schmidt와 비슷하면서 수치적으로 훨씬 안정 3. 행렬이 sparse할 때 특히 유리
NumPy의 np.linalg.qr 는 내부적으로 LAPACK의 Householder 기반 구현을 호출한다.
의미: Gram-Schmidt는 교육용·개념용이고, Householder는 실전용이다. 하지만 이 두 방법 모두 같은 \(\mathbf{A} = \mathbf{Q}\mathbf{R}\) 분해를 만들어낸다.
14 \(\mathbf{A} = \mathbf{Q}\mathbf{R}\) 의 요약
| 측면 | 내용 |
|---|---|
| 정의 | \(\mathbf{A}\) = (정규직교 열 행렬 \(\mathbf{Q}\)) × (상삼각 행렬 \(\mathbf{R}\)) |
| 존재 조건 | \(\mathbf{A}\) 의 열이 선형 독립이면 존재 |
| \(\mathbf{R}\) 의 구성 | \(r_{ij} = \mathbf{q}_i^\top \mathbf{a}_j\), 상삼각 |
| 대각 성분 | \(r_{kk} = \|\mathbf{u}_k\| > 0\) (직교화 후 잔여 길이) |
| 최소제곱 | \(\mathbf{R}\hat{\mathbf{x}} = \mathbf{Q}^\top \mathbf{b}\) (후치환) |
| 역행렬 (\(\mathbf{A}\) 정사각) | \(\mathbf{A}^{-1} = \mathbf{R}^{-1}\mathbf{Q}^\top\) |
15 응용
15.1 1. 푸리에 급수와 신호처리
정사각 \(\mathbf{Q}\) 의 \(\mathbf{b} = \mathbf{Q}\mathbf{Q}^\top \mathbf{b}\) 분해는 변환의 본질이다. 푸리에 행렬, 이산 코사인 변환(DCT), 웨이블릿 변환 — 모두 정규직교 기저로의 분해다. 각 계수는 내적으로 독립 계산되어 효율적이고 수치 안정적이다.
15.2 2. PCA (주성분 분석)
데이터 공분산 행렬의 고유벡터들이 정규직교 기저를 이룬다. 데이터를 이 기저로 분해하면 성분들이 서로 무상관 — 정보가 중복되지 않는 방향으로 표현된다. 차원 축소 시 가장 정보가 많은 몇 개의 방향만 선택할 수 있다.
15.3 3. QR 알고리즘 (고윳값 계산)
\(\mathbf{A} = \mathbf{Q}\mathbf{R}\) 로 분해한 뒤 \(\mathbf{A}' = \mathbf{R}\mathbf{Q}\) 를 만들면, \(\mathbf{A}'\) 의 고윳값이 \(\mathbf{A}\) 와 같다. 이것을 반복하면 \(\mathbf{A}\) 가 상삼각 행렬로 수렴하고, 그 대각선이 고윳값이 된다. 거의 모든 수치 고윳값 계산이 이 QR 알고리즘을 기반으로 한다.
15.4 4. 최소제곱 회귀
위에서 설명한 대로, 모든 현대 통계·머신러닝 라이브러리의 선형회귀 구현은 QR 또는 SVD를 사용한다. sklearn.linear_model.LinearRegression, R의 lm(), MATLAB의 \ 모두 QR/SVD 기반이다.
| 분야 | QR의 역할 |
|---|---|
| 통계 회귀 | 수치 안정적 계수 추정 |
| 신호처리 | 직교 변환 (DFT, DCT) |
| 머신러닝 | PCA, 선형회귀 기반 모델 |
| 수치해석 | 고윳값 계산 (QR 알고리즘) |
| 컴퓨터 그래픽스 | 회전·반사 변환의 분해 |
| 양자 역학 | 상태 벡터의 직교 기저 전개 |
16 핵심 요약
정규직교: qᵢᵀ qⱼ = δᵢⱼ
↓
Q 행렬: QᵀQ = I
정사각 Q: Qᵀ = Q⁻¹ (직교 행렬)
길이·각도·내적 보존
투영 공식의 단순화 (A → Q)
x̂ = Qᵀb (역행렬 없음!)
p = QQᵀb
P = QQᵀ
→ n 개의 독립 1차원 투영의 합
Gram-Schmidt (선형 독립 → 정규직교)
A = a
B = b - proj_A(b)
C = c - proj_A(c) - proj_B(c)
qₖ = (해당 벡터) / (길이)
A = QR 분해
Q: 정규직교 열, R: 상삼각
R = QᵀA, rᵢⱼ = qᵢᵀaⱼ
최소제곱: Rx̂ = Qᵀb (후치환)
수치 안정성: κ(AᵀA) = κ(A)² 회피
실전에서는: LAPACK이 Householder 반사로 QR을 계산한다
Gram-Schmidt는 개념 이해용17 관련 주제
선행 지식
- Ch.4 §4.2 — Projections — 투영 공식이 단순해지는 동기
- Ch.4 §4.3 — Least Squares Approximations — 정규방정식의 수치적 문제
동일 챕터 연결
- Ch.4 §4.1 — Four Subspaces Orthogonality — Full QR의 좌영공간 해석
응용 연결
- SVD (예정) — QR의 “양쪽 정규직교” 버전, 네 부분공간의 직교 기저 완성
- 푸리에 급수 (예정) — 함수 공간의 정규직교 기저
- PCA (예정) — 데이터 공분산의 정규직교 주성분