네 분해는 모두 “행렬을 쉬운 조각의 곱으로 쪼갠다”는 점이 같아서, 무엇을 써야 할지 헷갈린다. 가르는 질문은 하나다. 무엇을 하려는가. 방정식을 풀려면 LU, 가장 가까운 근사를 구하려면 QR, 같은 변환을 되풀이하려면 고윳값, 행렬의 구조를 크기 순으로 보거나 압축하려면 SVD다. 그다음 행렬의 모양(정사각인가, 대칭인가)이 쓸 수 있는 분해를 좁힌다1.
어느 쪽일까
C1 회로 시뮬레이션에서 같은 \(1000 \times 1000\) 행렬 \(A\)로 우변 \(\mathbf{b}\)만 바꿔 가며 \(A\mathbf{x} = \mathbf{b}\)를 500번 푼다. 어느 분해가 맞고, SVD는 왜 아닌가?
답: LU(부분 피벗팅). 한 번 \(\frac23n^3\)로 분해하고 풀이마다 \(2n^2\)이라 가장 싸다. SVD도 풀 수는 있지만 분해 비용이 LU의 몇 배이고, 가역인 정사각 행렬에서는 얻는 것이 없다.
C2 측정점 1만 개에 10차 다항식을 맞춘다(최소제곱). 정규방정식을 LU로 푸는 것과 QR 중 무엇이 맞는가?
답: QR. 다항식 기저의 열은 거의 종속이라 \(A\)의 조건수가 크고, \(A^\top A\)를 만들면 조건수가 제곱되어 정밀도를 크게 잃는다. QR은 \(R\hat{\mathbf{x}} = Q^\top\mathbf{b}\)로 조건수를 제곱하지 않는다. 열이 사실상 종속이면(수치 랭크 부족) SVD를 쓴다.
C3 웹 서핑의 마르코프 전이 행렬로 오랜 시간 뒤의 방문 확률(정상 분포)을 구한다. 고윳값 분해와 SVD 중 무엇인가?
답: 고윳값 분해(실제로는 \(\lambda = 1\) 고유벡터를 거듭제곱법으로). 묻는 것이 \(A^k\)의 극한이고, \(A^k = X\Lambda^kX^{-1}\)가 그것을 준다. SVD는 대칭이 아닌 행렬에서 \(A^k\)의 특잇값이 \(\sigma_i^k\)가 아니라 거듭제곱 정보를 주지 않는다.
C4 사용자 100만 명 × 영화 1만 편 평점 행렬을 몇 개의 “취향 축”으로 요약한다. 고윳값 분해와 SVD 중 무엇인가?
답: SVD(큰 특잇값 몇 개만 구하는 방법으로). 직사각 행렬이라 고윳값 분해가 정의되지 않고, 에카르트–영 정리로 랭크 \(k\) 근사 중 가장 가깝다는 보장이 SVD에 있다.
결정적 차이
| 분해 | 꼴 | 쓸 수 있는 행렬 | 비용(\(n \times n\) 밀집) | 드러내는 것 | 대표 용도 |
|---|---|---|---|---|---|
| LU | \(PA = LU\) | 정사각, 가역 | \(\frac23n^3\) | 소거 과정 | 연립방정식 반복 풀이, 행렬식 |
| QR | \(A = QR\) | \(m \ge n\), 열 독립 | 약 \(\frac43n^3\)(하우스홀더) | 직교 기저 | 최소제곱, 고윳값 알고리즘의 부품 |
| 고윳값 | \(A = X\Lambda X^{-1}\) | 정사각, 대각화 가능 | 반복법, \(O(n^3)\) | 방향이 안 바뀌는 축, 성장률 | \(A^k\), 안정성, 마르코프 |
| SVD | \(A = U\Sigma V^\top\) | 모든 행렬 | 반복법, 넷 중 가장 비쌈 | 랭크, 크기 순 방향, 조건수 | 저랭크 근사, 유사역행렬, PCA |
LU (n = 3) PA = L x U
[* * *] [1 0 0] [* * *]
[* * *] [* 1 0] [0 * *]
[* * *] [* * 1] [0 0 *]
QR (m = 4, n = 3) A = Q x R
[* * *] [* * *] [* * *]
[* * *] [* * *] [0 * *]
[* * *] [* * *] [0 0 *]
[* * *] [* * *]
고윳값 (n = 3) A = X x Lambda x X^-1
[* * *] [* * *] [l 0 0] [* * *]
[* * *] [* * *] [0 l 0] [* * *]
[* * *] [* * *] [0 0 l] [* * *]
SVD (m = 4, n = 3) A = U x Sigma x V^T
[* * *] [* * * *] [s 0 0] [* * *]
[* * *] [* * * *] [0 s 0] [* * *]
[* * *] [* * * *] [0 0 s] [* * *]
[* * *] [* * * *] [0 0 0]
*는 아무 수, l은 고윳값 λ, s는 특잇값 σ, 0과 1은 늘 그 값인 칸이다. 길쭉한 A를 받는 것은 QR과 SVD뿐이다. SVD의 Σ는 A와 크기가 같고, 대각 아래 남는 줄은 0으로 채운다2.
- 대칭행렬에서는 겹친다. 대칭이면 고윳값 분해가 \(Q\Lambda Q^\top\)(스펙트럼 정리)이고, 양의 준정부호이면 SVD와 같다.
- 직교 행렬이 들어간 분해(QR, 대칭의 \(Q\Lambda Q^\top\), SVD)는 수치적으로 안정하다. 직교 행렬은 조건수가 1이라 오차를 키우지 않는다. LU는 피벗팅으로 안정성을 챙긴다.
flowchart TD
Q{"무엇을 하려는가"}
Q -->|"Ax = b를 풀기"| LU["LU: 정사각, 가역"]
Q -->|"가장 가까운 근사"| QR["QR: m ≥ n, 열 독립"]
Q -->|"같은 변환을 되풀이"| EIG["고윳값 분해: 정사각, 대각화 가능"]
Q -->|"구조를 크기 순으로 보기, 압축"| SVD["SVD: 모든 행렬"]
LU -.->|"대칭 양의 정부호"| CH["숄레스키 LLᵀ, LU의 절반 비용"]
EIG -.->|"대칭"| SP["QΛQᵀ, 양의 준정부호면 SVD와 같다"]
Q -->|"크고 희소한 행렬"| IT["반복법: 켤레 기울기법, GMRES"]
먼저 하려는 일로 갈래를 고른다. 그다음 점선을 따라 행렬 모양에 맞는 더 싼 방법이 있는지 본다2.
둘 다 아닐 때
- 대칭 양의 정부호: 숄레스키 \(S = LL^\top\)가 LU의 절반 비용이다. 공분산 행렬, 유한요소 강성 행렬이 이 경우다.
- 크고 희소한 행렬: 0이 대부분인 \(10^6 \times 10^6\) 행렬은 분해하면 0이 채워져 메모리가 터진다. 행렬-벡터 곱만 쓰는 반복법(대칭 양의 정부호에는 켤레 기울기법, 일반 행렬에는 GMRES)을 쓴다3.
- 거대한 행렬의 상위 몇 개: 특잇값·고윳값 몇 개만 필요하면 란초스 방법이나 무작위 SVD로 전체 분해 없이 구한다3.
-
Strang, Introduction to Linear Algebra 5판, 2.6절(LU), 4.4절(QR), 6.2절(대각화), 7.2절(SVD), 11.1절(실제 계산). Trefethen·Bau, Numerical Linear Algebra, 2부(QR과 최소제곱), 4부(연립방정식과 숄레스키), 5부(고윳값), 1부(SVD). ↩
-
이 문서
결정적 차이표의 꼴·쓸 수 있는 행렬과 첫 문단,둘 다 아닐 때목록을 옮겼다(Strang 5판 2.6·4.4·6.2·7.2절, Trefethen·Bau). ↩ ↩2 -
켤레 기울기법·GMRES·란초스는 Trefethen·Bau 6부 “Iterative Methods”에, 무작위 SVD는 Halko·Martinsson·Tropp, “Finding structure with randomness”, SIAM Review 53 (2011)에 있다. ↩ ↩2