QR 분해

1. 개요

QR 분해 QR Decomposition
분해 형태	A = QR
Q	정규직교행렬 (QTQ = I)
R	상삼각행렬
대표 알고리즘	그람-슈미트, 하우스홀더, 기븐스
비용 (m×n, Q 미형성)	2mn2 − (2/3)n3 flops
직교성 손실	하우스홀더 O(u) · MGS O(uκ) · CGS O(uκ2)
존재성	임의의 실/복소 행렬에 대해 항상 존재
주요 응용	최소자승법, 고유값 문제

“직교로 만들면 다 편해진다”는 선형대수의 오래된 진리.

QR 분해(QR Decomposition)는 행렬 $A$를 정규직교 열을 가진 행렬 $Q$와 상삼각행렬 $R$의 곱 $A = QR$로 나타내는 분해다. 여기서 $Q^{\mathsf T} Q = I$이고 $R$은 위쪽 삼각형만 채워진 행렬이다. LU 분해가 소거법의 자연스러운 산물이라면, QR 분해는 “$A$의 열공간에 정규직교 기저를 씌우는” 작업의 결과물이다. 직교행렬은 곱해도 벡터 길이(2-노름)를 보존하기 때문에, QR 분해는 수치적으로 안정적인 계산의 대명사가 됐다.¹

핵심 용도는 두 가지다. 하나는 최소자승법 — 과결정 연립방정식을 안정적으로 푸는 표준 도구. 다른 하나는 고유값 문제 — QR 반복을 통해 대칭·비대칭 행렬의 고유값을 몽땅 뽑아내는 QR 알고리즘의 심장이다.

2. 축약 QR 와 완전 QR

같은 이름으로 크기가 다른 두 물건이 유통되므로 먼저 정리해 둔다. $m \ge n$인 $m \times n$ 행렬 $A$에 대해

• 축약(thin/economy) QR: $Q$는 $m \times n$, $R$은 $n \times n$. $Q$의 열은 $A$의 열공간의 정규직교 기저다. 최소자승법에 필요한 건 이쪽뿐이다.
• 완전(full) QR: $Q$는 $m \times m$ 직교행렬, $R$은 $m \times n$ (아래쪽 $m-n$행은 0). 남는 $m-n$개 열은 $A$의 열공간의 직교보공간 기저가 되어, 잔차 공간을 직접 다룰 때 쓸모가 있다.

$A$가 열에 대해 완전계수(full column rank)이면 $R$의 대각을 양수로 고정하는 조건 아래 축약 QR은 유일하다. 하우스홀더 구현은 본래 완전 QR을 만들지만 $Q$를 명시적으로 쌓지 않고 반사자들의 곱으로 들고 다니는데, LAPACK의 dgeqrf가 반사자 계수만 남기고 필요할 때 dormqr로 곱해 주는 이유가 그것이다.

3. 세 가지 계산법

같은 $Q$, $R$을 얻는 길이 여럿이다. 각각 안정성과 비용의 트레이드오프가 다르다.

3.1. 그람-슈미트 직교화

가장 직관적인 방법. $A$의 열벡터를 하나씩 가져와 이전 벡터들에 대한 성분을 빼고 정규화하면 정규직교 기저가 나온다. 개념은 아름답지만, 고전 그람-슈미트(CGS)는 반올림 오차에 취약해 직교성이 처참하게 무너지는 것으로 악명 높다. 뺄셈 순서를 살짝 바꾼 **수정 그람-슈미트(MGS)**가 훨씬 안정적이라, 손으로 짤 땐 무조건 MGS를 쓴다. 자세한 비교는 그람-슈미트 문서가 다룬다.²

3.2. 하우스홀더 변환

실무 표준. 벡터를 한 방에 특정 축으로 반사시키는 하우스홀더 변환(반사행렬 $H = I - 2vv^{\mathsf T}$, 단위벡터 $v$)을 연달아 적용해 $A$를 상삼각형으로 만든다.

$$H_{n} \cdots H_2 H_1 A = R, \qquad Q = H_1 H_2 \cdots H_{n}$$

각 반사는 직교변환이라 노름을 보존하고, 오차 누적이 거의 없다. LAPACK의 조밀 QR이 바로 이 방식. 밀집 행렬이면 하우스홀더가 국룰이다.

3.3. 기븐스 회전

2차원 평면에서 한 번에 원소 하나씩만 0으로 만드는 회전변환. 한 성분만 건드리므로 희소행렬이나 이미 거의 삼각형에 가까운 행렬(헤센베르크 형태 등)에서 효율적이고, 병렬화·점진적 갱신에도 유리하다. 행 하나를 추가하거나 삭제해 QR을 갱신(updating/downdating)하는 재귀 최소자승은 사실상 기븐스 회전의 밥벌이다. 낭비가 없는 대신 밀집 행렬 전체를 처리하기엔 하우스홀더보다 느리다.

3.4. 검산: 직교성 손실은 알고리즘마다 다르게 자란다

“CGS가 나쁘다”는 말은 정성적 구호가 아니라 정량적 예측이다. 이론이 주는 직교성 손실 상한은 CGS가 $O(u\kappa^2)$, MGS가 $O(u\kappa)$, 하우스홀더가 $O(u)$로 조건수 의존성 자체가 다르다($u = 2^{-53} \approx 1.11 \times 10^{-16}$은 배정밀도 단위 반올림). 조건수를 키운 반데르몬드 행렬($2n \times n$)로 $\lVert Q^{\mathsf T}Q - I \rVert_F$를 실제로 재면 예측이 그대로 나온다.

$n$	$\kappa(A)$	CGS 실측	$u\kappa^2$	MGS 실측	$u\kappa$	하우스홀더 실측
6	3.13e+03	9.14e-11	1.09e-09	1.64e-13	3.47e-13	1.67e-15
8	1.08e+05	1.22e-07	1.29e-06	2.62e-12	1.20e-11	1.65e-15
10	3.79e+06	2.36e-02	1.60e-03	1.61e-10	4.21e-10	2.81e-15
12	1.35e+08	2.44e+00	2.03e+00	3.57e-09	1.50e-08	2.99e-15

CGS는 $\kappa \approx 10^8$에서 손실이 $O(1)$에 도달해 직교성이 완전히 소멸한다(2.44는 “거의 직교”가 아니라 “남이나 다름없다”는 뜻이다). MGS는 같은 자리에서 $10^{-9}$를 지키고, 하우스홀더는 조건수가 다섯 자리 올라가도 $10^{-15}$에 눌러앉아 꿈쩍하지 않는다. 안정성을 돈으로 사는 게 아니라 알고리즘 선택으로 공짜로 얻는 드문 사례다.

4. 최소자승 해법

QR 분해가 진짜로 밥값을 하는 곳은 최소자승법 $\min_x \lVert Ax - b \rVert_2$다. $A = QR$을 대입하면 직교행렬이 노름을 보존하는 성질 덕에

$$\lVert Ax - b \rVert_2 = \lVert Q(Rx) - b \rVert_2 = \lVert Rx - Q^{\mathsf T} b \rVert_2$$

가 되고, $R$이 상삼각이므로 후진대입 한 번으로 해가 나온다. 흔히 쓰는 정규방정식 $A^{\mathsf T}A x = A^{\mathsf T}b$는 조건수를 제곱으로 악화시켜 정밀도를 날려 먹는데, QR은 이 제곱을 피해 간다.³ 특이값 분해만큼 만능은 아니지만 훨씬 싸서, 랭크가 온전한 문제에선 QR이 먼저 손이 간다.

4.1. 검산: 정규방정식이 얼마나 손해인가

$\kappa(A^{\mathsf T}A) = \kappa(A)^2$은 어림이 아니라 등식이다. 반데르몬드 행렬로 두 조건수를 직접 계산하면 $n = 5, 7, 9$에서 비가 각각 1.0000으로 떨어진다($3.22\times10^5$, $3.35\times10^8$, $3.69\times10^{11}$).

그래서 해의 정확도가 갈린다. 정확해가 $x = (1,1,\dots,1)^{\mathsf T}$가 되도록 $b = Ax$를 만들어 두고 두 경로로 풀어 최대 성분 오차를 재면 이렇게 된다.

$n$	$\kappa(A)$	QR 경로 오차	정규방정식 오차	배율
6	3.21e+03	4.23e-13	1.76e-11	42배
8	1.05e+05	2.85e-11	1.89e-07	6.6e+03배
10	3.52e+06	5.48e-10	6.27e-04	1.1e+06배

$\kappa \approx 3.5 \times 10^6$은 배정밀도로 여유가 한참 남은 조건수인데도 정규방정식은 이미 유효숫자 셋을 잃었다($6.3\times10^{-4}$). 같은 자리에서 QR은 $5\times10^{-10}$을 지킨다. 배율이 대략 $\kappa$에 비례해 자라는 것도 이론과 맞는다 — 정규방정식의 오차가 $\kappa^2 u$, QR이 $\kappa u$ 규모이므로 비가 $\kappa$다.

5. 연산량

$Q$를 명시적으로 만들지 않는 밀집 $m \times n$ 하우스홀더 QR의 표준 비용은 다음과 같다.

$$2mn^2 - \tfrac{2}{3}n^3 \ \text{flops}$$

반사자 적용 연산을 하나하나 세어 보면 $m=300, n=150$에서 실측 $1.151\times10^7$ 대 공식 $1.125\times10^7$로 비가 1.023이다($m=60, n=30$에서 1.116 → $n$이 커지며 저차항이 묻혀 1로 수렴한다). 정사각 $n \times n$이면 위 식이 $\frac{4}{3}n^3$이 되어 LU 분해의 $\frac{2}{3}n^3$의 정확히 두 배인데, 실측 비도 $n=240$에서 2.035로 나온다. 안정성 값이 그만큼 비싸다는 통념은 “두 배”라는 구체적 가격표를 갖고 있다.

6. 랭크 결핍과 열 피벗 QR

보통의 QR은 $A$의 랭크가 온전하다고 믿고 달린다. 랭크가 모자라거나 아슬아슬하면 $R$의 대각에 0에 가까운 값이 나타나며 후진대입이 폭발한다. 이때 쓰는 것이 열 피벗 QR(column-pivoting QR)로, 남은 열 중 노름이 가장 큰 것을 매 단계 앞으로 끌어와 $A\Pi = QR$ 형태의 열 순서 교환 $\Pi$를 함께 낸다. 그러면 $R$의 대각이 대체로 감소 순서가 되어, 어디서 뚝 떨어지는지 보고 수치 랭크를 읽을 수 있다(LAPACK dgeqp3).

다만 이것은 휴리스틱이다. 카한(Kahan)의 유명한 반례처럼 열 피벗 QR이 랭크 결핍을 놓치는 행렬이 존재해서, 랭크를 진짜로 믿어야 하면 특이값 분해나 절단 특이값 분해로 넘어가는 게 정석이다. 열 피벗 QR의 위치는 “SVD보다 훨씬 싸고 대개는 맞다”쯤이다.

7. QR 알고리즘: 고유값을 향하여

QR 분해의 화려한 응용은 **QR 알고리즘**이다. 아이디어는 어이없을 정도로 단순하다. 행렬을 QR로 쪼갠 뒤 순서를 바꿔 다시 곱하는 것을 반복한다.

$$A_k = Q_k R_k, \qquad A_{k+1} = R_k Q_k$$

이렇게 반복하면 $A_{k+1} = Q_k^{\mathsf T} A_k Q_k$라 $A_k$와 닮음(similar)이어서 고유값이 보존되면서도, 점점 상삼각형(대칭이면 대각형)으로 수렴한다. 그러면 대각 원소가 바로 고유값이다. 실제 구현은 먼저 헤센베르크/삼중대각 형태로 만들고 이동(shift) 전략과 기븐스 회전을 얹어 수렴을 가속하는데, 이 방식이 20세기 최고의 알고리즘 10선에 당당히 이름을 올렸다.⁴

8. 친척 분해들과 선택 가이드

$Q$가 “회전”, $R$이 “늘이기”라는 감각을 공유하는 이웃들이 있다. 극분해는 $A = UP$로 직교 부분과 대칭양정치 부분을 나누고, 슈어 분해는 $A = QTQ^{\mathsf T}$로 상삼각 $T$에 고유값을 늘어놓으며, 특이값 분해는 양쪽에서 직교변환을 걸어 대각화한다. 셋 다 QR보다 비싸고, 셋 다 QR 계산을 내부에서 쓴다.

• 정사각 선형계 → LU 분해가 싸다. 대칭양정치면 촐레스키 분해.
• 과결정 최소자승, 랭크 온전 → QR.
• 고유값 전부 → QR 알고리즘.
• 랭크 결핍 의심 → 열 피벗 QR로 싸게 보고, 확신이 필요하면 특이값 분해.
• 거대 희소계 → 직접 분해를 포기하고 크리로프 부분공간법으로. 그 안쪽의 아놀디 알고리즘이 다시 그람-슈미트로 직교화한다.

수치해석 강의에서 “왜 굳이 두 배 비싼 QR을 쓰냐”는 질문이 나오면, 조교는 위 검산표의 마지막 줄을 보여주는 것으로 답을 대신한다. 두 배를 아끼려다 유효숫자 셋을 버리는 거래는 아무도 원하지 않는다.

9. 관련 문서

• LU 분해 · 촐레스키 분해 · 특이값 분해
• 그람-슈미트 · 하우스홀더 변환 · 기븐스 회전
• QR 알고리즘 · 고유값 문제
• 최소자승법 · 조건수
• 슈어 분해 · 극분해
• 가우스 소거법 · 희소행렬
• 크리로프 부분공간법 · 아놀디 알고리즘
• 수치해석

10. Footnotes

1. 직교행렬 $Q$는 $\lVert Qx \rVert_2 = \lVert x \rVert_2$를 만족한다. 길이를 바꾸지 않으니 오차도 뻥튀기하지 않는다. 수치해석에서 “직교”는 곧 “믿을 만하다”의 동의어다. ↩

2. 고전 그람-슈미트로 직교화한 벡터들의 내적을 찍어 보면 0이 아니라 0.3쯤 나와서 학생을 좌절시키는 게 통과의례다. 위 검산표의 $n=12$ 줄이 바로 그 좌절의 정량적 초상이다. MGS로 바꾸면 대개 해결되지만, 극단적으로 병적인 경우엔 재직교화(reorthogonalization) 한 방을 더 먹여야 한다. ↩

3. $\kappa(A^{\mathsf T}A) = \kappa(A)^2$. 이 제곱 하나 때문에 유효숫자 절반이 증발한다. 정규방정식이 편하다고 남발하면 언젠가 뒤통수를 맞는다. 단 잔차가 크고 조건수가 온건한 문제에서는 정규방정식의 오차도 $\kappa$ 규모에 머물러, “항상 두 배 나쁘다”로 외우면 그것도 틀린다. ↩

4. 동가라와 설리번이 Computing in Science & Engineering 2000년 1·2월호에 꼽은 “20세기의 알고리즘 톱 10”에 1959–61년 프랜시스(J. G. F. Francis)의 QR 알고리즘이 독립 항목으로 올라 있다. 크리로프 부분공간 반복(1947)과 “행렬 계산의 분해적 접근”(1951)도 각각 따로 이름을 올렸으니, 열 자리 중 셋이 이 문서 주변에서 나온 셈이다. 단순한 반복 하나가 반세기 넘게 세계의 고유값을 책임지고 있다. ↩