QR 분해

수치해석 마지막 수정: 2026-07-09 04:33:52

QR 분해 QR Decomposition
분해 형태	A = QR
Q	정규직교행렬 (QᵀQ = I)
R	상삼각행렬
대표 알고리즘	그람-슈미트, 하우스홀더, 기븐스
주요 응용	최소자승법, 고유값 문제

1. 개요[편집]

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

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

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

2. 세 가지 계산법[편집]

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

2.1. 그람-슈미트 직교화[편집]

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

2.2. 하우스홀더 변환[편집]

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

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

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

2.3. 기븐스 회전[편집]

2차원 평면에서 한 번에 원소 하나씩만 0으로 만드는 회전변환. 한 성분만 건드리므로 희소행렬이나 이미 거의 삼각형에 가까운 행렬(헤센베르크 형태 등)에서 효율적이고, 병렬화·점진적 갱신에도 유리하다. 낭비가 없는 대신 밀집 행렬 전체를 처리하기엔 하우스홀더보다 느리다.

3. 최소자승 해법[편집]

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

\|Ax - b\|_2 = \|Q(Rx) - b\|_2 = \|Rx - Q^{\mathsf T} b\|_2

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

4. QR 알고리즘: 고유값을 향하여[편집]

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

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

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

5. 수치 안정성과 현실[편집]

안정성의 근원: 직교변환은 2-노름을 정확히 보존한다. 그래서 QR 기반 알고리즘은 오차가 눈덩이처럼 커지지 않는다. “안정성이 걱정되면 일단 직교화부터 해라”가 정설.
비용: 밀집 $m \times n$ QR은 대략 $2mn^2 - \frac{2}{3}n^3$ 연산으로, LU 분해의 약 두 배다. 안정성 값이 그만큼 비싸다.
선택 가이드: 정사각 선형계 → LU가 싸다. 과결정 최소자승 → QR. 고유값 전부 → QR 알고리즘. 랭크 결핍이거나 병적이면 → 특이값 분해로 도망친다.

수치해석 강의에서 “왜 굳이 두 배 비싼 QR을 쓰냐”는 질문이 나오면, 조교는 정규방정식으로 병적 문제를 풀다 폭발한 그래프를 보여주는 것으로 답을 대신한다.

6. 관련 문서[편집]

직교행렬 $Q$ 는 $\|Qx\|_2 = \|x\|_2$ 를 만족한다. 길이를 바꾸지 않으니 오차도 뻥튀기하지 않는다. 수치해석에서 “직교”는 곧 “믿을 만하다”의 동의어다. ↩
고전 그람-슈미트로 직교화한 벡터들의 내적을 찍어 보면 0이 아니라 0.3쯤 나와서 학생을 좌절시키는 게 통과의례다. MGS로 바꾸면 대개 해결되지만, 극단적으로 병적인 경우엔 재직교화(reorthogonalization) 한 방을 더 먹여야 한다. ↩
조건수 $\kappa(A^{\mathsf T}A) = \kappa(A)^2$ . 이 제곱 하나 때문에 유효숫자 절반이 증발한다. 정규방정식이 편하다고 남발하면 언젠가 뒤통수를 맞는다. ↩
Dongarra & Sullivan(2000)이 선정한 “20세기의 알고리즘 톱 10”에 QR 알고리즘의 조상 격인 크릴로프·고유값 계열이 이름을 올렸다. 단순한 반복 하나가 반세기 넘게 세계의 고유값을 책임지고 있다. ↩