6.49 QR 분해의 원리와 계산

1. 도입

QR 분해(QR decomposition)는 임의의 행렬을 직교 행렬과 상삼각 행렬의 곱으로 표현하는 행렬 분해이다. 이 분해는 수치 선형대수학에서 가장 핵심적인 도구 중 하나로, 최소 제곱 문제, 고유값 계산, 선형 시스템의 안정적인 해법, 그리고 직교 기저의 명시적 구성에서 광범위하게 활용된다. QR 분해의 우수한 수치적 성질과 풍부한 응용은 그것을 현대 수치 계산 라이브러리의 표준 도구로 자리 잡게 하였다.

2. QR 분해의 정의

정의. 행렬 $A \in \mathbb{R}^{m \times n}$ ( $m \geq n$ )에 대하여 QR 분해는 다음의 형태로 표현된다.

$A = QR$

여기서

$Q \in \mathbb{R}^{m \times m}$ 는 직교 행렬, 즉 $Q^\top Q = QQ^\top = I_m$ 이다.
$R \in \mathbb{R}^{m \times n}$ 는 상삼각 형태의 행렬이다. 즉, $i > j$ 인 모든 원소 $R_{ij}$ 가 영이다.

이 형식을 전체 QR 분해(full QR decomposition)라 하며, $Q$ 는 정사각 직교 행렬이다.

3. 축소 QR 분해

전체 QR 분해는 종종 다음의 축소된 형태로 표현된다.

$A = Q_1 R_1$

여기서

$Q_1 \in \mathbb{R}^{m \times n}$ 는 정규 직교 열을 가지는 행렬, 즉 $Q_1^\top Q_1 = I_n$ 이다.
$R_1 \in \mathbb{R}^{n \times n}$ 는 정사각 상삼각 행렬이다.

축소 형식은 전체 형식의 첫 $n$ 개의 열과 $R$ 의 첫 $n$ 개의 행만을 유지한 것이다. 즉, 전체 형식 $A = QR$ 에서 $Q = (Q_1, Q_2)$ , $R = \binom{R_1}{0}$ 로 분할하면 $A = Q_1 R_1$ 이 얻어진다. 두 형식은 동등한 정보를 담고 있지만, 저장 공간과 계산량 측면에서 축소 형식이 더 효율적이다.

4. QR 분해의 존재성과 유일성

정리. 임의의 $A \in \mathbb{R}^{m \times n}$ ( $m \geq n$ )에 대하여 QR 분해 $A = QR$ 가 존재한다. 또한 $A$ 가 열 만랭크인 경우, $R$ 의 대각 원소가 양수가 되도록 정하면 분해는 유일하다.

존재성은 그람-슈미트 과정, 하우스홀더 변환, 또는 기븐스 회전 등 여러 가지 구성적 방법으로 증명될 수 있다. 유일성은 다음과 같이 증명된다. $A = Q_1 R_1 = Q_2 R_2$ 가 두 가지 분해라 하자. 그러면 $Q_2^\top Q_1 = R_2 R_1^{-1}$ 이며, 좌변은 직교 행렬이고 우변은 상삼각 행렬이다. 직교이면서 상삼각인 행렬은 대각 행렬이며, 그 대각 원소는 $\pm 1$ 이다. 대각 원소를 양수로 정하는 규약 하에서는 이 행렬이 단위 행렬이어야 하므로 $Q_1 = Q_2$ , $R_1 = R_2$ 이다.

5. 그람-슈미트 방식

QR 분해의 가장 직관적인 구성 방법은 그람-슈미트 정규 직교화 과정을 행렬 $A$ 의 열에 적용하는 것이다. 행렬 $A$ 의 열을 $\mathbf{a}_1, \mathbf{a}_2, \ldots, \mathbf{a}_n$ 이라 하자. 그람-슈미트 과정으로 얻어진 정규 직교 벡터들 $\mathbf{q}_1, \mathbf{q}_2, \ldots, \mathbf{q}_n$ 이 $Q_1$ 의 열을 이루며, $R_1$ 의 원소는 다음과 같이 결정된다.

$R_{ij} = \begin{cases} \mathbf{q}_i^\top \mathbf{a}_j & i \leq j \\ 0 & i > j \end{cases}$

이 방법은 개념적으로 단순하고 명시적이지만, 고전적 그람-슈미트의 수치적 불안정성으로 인하여 실제 계산에서는 수정 그람-슈미트를 사용하여야 한다.

6. 하우스홀더 변환 방식

수치적으로 가장 안정한 QR 분해 방법은 하우스홀더 변환(Householder transformation)을 활용하는 것이다. 하우스홀더 변환은 다음과 같이 정의되는 직교 대칭 행렬이다.

$H = I - 2 \frac{\mathbf{v}\mathbf{v}^\top}{\mathbf{v}^\top \mathbf{v}}$

여기서 $\mathbf{v}$ 는 비영벡터이다. 이 행렬은 $\mathbf{v}$ 에 수직인 초평면에 대한 거울 반사를 표현하며, $H^\top = H = H^{-1}$ 의 성질을 가진다.

6.1 하우스홀더 벡터의 선택

주어진 벡터 $\mathbf{x} \neq \mathbf{0}$ 에 대하여 첫 번째 표준 기저 벡터 $\mathbf{e}_1$ 의 양의 배수로 사상하는 하우스홀더 변환을 구성하려면 다음과 같이 $\mathbf{v}$ 를 선택한다.

$\mathbf{v} = \mathbf{x} + \mathrm{sign}(x_1) \|\mathbf{x}\| \mathbf{e}_1$

이 선택은 수치적 자릿수 손실을 방지하기 위하여 부호를 조정한 것이다. 이렇게 구성된 $H$ 에 대하여

$H\mathbf{x} = -\mathrm{sign}(x_1) \|\mathbf{x}\| \mathbf{e}_1$

이 성립한다.

6.2 하우스홀더 QR 분해 알고리듬

하우스홀더 변환을 활용한 QR 분해 알고리듬은 다음과 같이 진행된다.

$A^{(0)} = A$ 로 초기화한다.
$k = 1, 2, \ldots, \min(m-1, n)$ 에 대하여:
(a) $A^{(k-1)}$ 의 $k$ 번째 열의 부분 벡터 $\mathbf{x}^{(k)} = (A^{(k-1)}_{kk}, A^{(k-1)}_{k+1,k}, \ldots, A^{(k-1)}_{mk})^\top$ 를 추출한다.
(b) 이 벡터를 첫 번째 좌표축으로 사상하는 하우스홀더 벡터 $\mathbf{v}^{(k)}$ 를 계산한다.
(c) 대응하는 하우스홀더 행렬 $H^{(k)}$ 를 $A^{(k-1)}$ 의 우하단 부분 행렬에 적용하여 $A^{(k)}$ 를 얻는다.
모든 단계가 완료된 후 $R = A^{(n)}$ 이고, $Q = H^{(1)} H^{(2)} \cdots H^{(n)}$ 이다.

각 하우스홀더 변환은 한 열의 대각 아래 원소들을 모두 영으로 만들며, 누적된 변환들이 최종적으로 상삼각 형태의 $R$ 을 산출한다.

6.3 명시적 $Q$ 의 형성과 저장

실제 구현에서는 명시적인 $Q$ 행렬을 구성하지 않고, 하우스홀더 벡터들 $\mathbf{v}^{(1)}, \mathbf{v}^{(2)}, \ldots$ 만을 저장하는 것이 일반적이다. $Q$ 가 작용하는 결과만이 필요한 경우, 저장된 하우스홀더 벡터들을 차례로 적용함으로써 $Q\mathbf{x}$ 또는 $Q^\top \mathbf{x}$ 를 계산할 수 있다. 이 접근법은 저장 공간과 계산량을 절감한다.

7. 기븐스 회전 방식

또 다른 안정한 QR 분해 방법은 기븐스 회전(Givens rotation)을 활용하는 것이다. 기븐스 회전은 두 좌표 평면에서의 회전을 표현하는 직교 행렬이며, 한 번에 한 원소만을 영으로 만든다.

7.1 기븐스 회전의 정의

$(i, j)$ 평면에서의 기븐스 회전 $G(i, j, \theta)$ 는 단위 행렬에서 $(i,i), (i,j), (j,i), (j,j)$ 원소를 다음과 같이 변경한 행렬이다.

$\begin{pmatrix} G_{ii} & G_{ij} \\ G_{ji} & G_{jj} \end{pmatrix} = \begin{pmatrix} c & -s \\ s & c \end{pmatrix}, \qquad c = \cos\theta, \quad s = \sin\theta$

이 행렬을 벡터에 곱하면 $i$ 번째와 $j$ 번째 좌표만이 영향을 받으며, $c$ 와 $s$ 를 적절히 선택하여 그 중 하나를 영으로 만들 수 있다.

7.2 기븐스 QR 분해 알고리듬

기븐스 회전을 활용한 QR 분해는 행렬의 대각 아래 원소들을 하나씩 영으로 만들어 가는 방식으로 진행된다. 일반적으로 열별로 진행하며, 각 열의 가장 아래 원소부터 위로 올라가면서 회전을 적용한다. 모든 대각 아래 원소가 영이 된 후의 행렬이 $R$ 이며, 적용된 회전들의 곱이 $Q^\top$ 이다.

기븐스 회전의 장점은 각 회전이 두 행에만 영향을 미치므로 희소 행렬의 구조를 잘 보존한다는 점이다. 또한 점진적 갱신이 자연스럽게 가능하여 새로운 데이터가 추가될 때 효율적으로 분해를 갱신할 수 있다.

8. 세 가지 방식의 비교

항목	그람-슈미트	하우스홀더	기븐스
수치 안정성	낮음 (수정형: 중간)	매우 높음	매우 높음
일반적 비용	$2mn^2$	$2mn^2 - \frac{2}{3}n^3$	$3mn^2$
희소 행렬 처리	부적합	부적합	적합
점진적 갱신	자연스러움	어려움	자연스러움
명시적 $Q$ 필요성	자동 생성	묵시적 저장 가능	자동 생성

응용의 특성에 따라 적절한 방법을 선택하여야 한다. 일반적인 직사각 밀집 행렬에 대해서는 하우스홀더 방법이 표준이며, 희소 행렬이나 점진적 갱신이 필요한 경우에는 기븐스 방법이 선호된다.

9. QR 분해의 핵심 응용

9.1 최소 제곱 문제

선형 시스템 $A\mathbf{x} = \mathbf{b}$ 가 과결정인 경우 ( $m > n$ ) 정확한 해는 일반적으로 존재하지 않으며, 잔차 노름을 최소화하는 최소 제곱 해를 구하여야 한다. QR 분해 $A = Q_1 R_1$ 을 활용하면 다음과 같이 효율적으로 해결된다.

$\|A\mathbf{x} - \mathbf{b}\|^2 = \|Q^\top(A\mathbf{x} - \mathbf{b})\|^2 = \left\| \binom{R_1\mathbf{x} - Q_1^\top \mathbf{b}}{-Q_2^\top \mathbf{b}} \right\|^2$

마지막 항은 $\mathbf{x}$ 에 의존하지 않으므로, 비용을 최소화하는 것은 $R_1 \mathbf{x} = Q_1^\top \mathbf{b}$ 를 푸는 것과 동등하다. 상삼각 행렬에 대한 후진 대입을 통하여 해를 직접 얻는다.

이 접근법은 정규 방정식 $A^\top A \mathbf{x} = A^\top \mathbf{b}$ 를 직접 푸는 것보다 수치적으로 훨씬 안정하다. 그 이유는 정규 방정식의 조건수가 원래 행렬 조건수의 제곱이 되지만, QR 방법은 원래 조건수만을 다루기 때문이다.

9.2 직교 기저의 구성

QR 분해는 행렬의 열 공간에 대한 정규 직교 기저를 명시적으로 제공한다. $Q_1$ 의 열은 정확히 $A$ 의 열 공간의 정규 직교 기저이며, $Q_2$ 의 열은 좌영 공간의 정규 직교 기저이다.

9.3 고유값 계산을 위한 QR 알고리듬

대칭 또는 일반 행렬의 고유값을 계산하는 표준적인 알고리듬은 QR 알고리듬이다. 이는 행렬을 반복적으로 QR 분해하고 그 곱의 순서를 바꾸는 절차로, 결과적으로 행렬을 슈어 표준형 또는 거의 대각 형태로 수렴시킨다. QR 알고리듬은 LAPACK과 같은 표준 수치 라이브러리에서 고유값 계산의 기본 방법으로 사용된다.

9.4 선형 시스템의 안정한 해법

정사각 가역 행렬의 선형 시스템 $A\mathbf{x} = \mathbf{b}$ 도 QR 분해를 통하여 풀 수 있다. $A = QR$ 이면 $\mathbf{x} = R^{-1} Q^\top \mathbf{b}$ 이며, 후진 대입을 통하여 직접 계산된다. LU 분해보다 계산 비용은 약간 크지만, 추가적인 안정성을 제공한다.

10. 점진적 QR 갱신

새로운 행이 추가되거나 기존 행이 수정될 때 전체 QR 분해를 다시 계산하는 것은 비효율적이다. 점진적 갱신 알고리듬은 기존의 분해로부터 $O(n^2)$ 의 연산으로 새로운 분해를 얻을 수 있게 한다. 기븐스 회전이 이 갱신에 자연스럽게 적합하며, 재귀적 최소 제곱 방법, 칼만 필터의 제곱근 형식, 그리고 적응형 신호 처리에서 광범위하게 활용된다.

11. 수치적 정확도

QR 분해의 수치적 정확도는 사용된 알고리듬에 따라 달라진다. 하우스홀더와 기븐스 방법은 후방 안정한(backward stable) 알고리듬이다. 즉, 계산된 분해 $\hat{Q} \hat{R}$ 는 약간 섭동된 입력 $A + E$ 의 정확한 분해이며, $\|E\|/\|A\|$ 는 기계 정밀도 정도이다. 이는 QR 분해가 가능한 가장 정확한 결과를 제공함을 의미한다.

12. 로봇공학에서의 응용

12.1 운동학적 매개 변수 추정

로봇의 운동학적 매개 변수를 실험 데이터로부터 식별하는 문제는 일반적으로 과결정 선형 시스템으로 정식화된다. QR 분해는 이 시스템의 안정한 최소 제곱 해를 제공하며, 측정 잡음에 대한 견고성을 보장한다.

12.2 동역학 매개 변수 보정

매니퓰레이터의 질량, 관성, 관절 마찰 등의 동역학 매개 변수를 추정하는 문제도 회귀 행렬에 대한 최소 제곱 문제로 변환된다. QR 분해는 이러한 매개 변수의 효율적이고 안정한 추정을 가능하게 한다.

12.3 칼만 필터의 제곱근 형식

칼만 필터의 표준 형식은 공분산 행렬의 양정치성을 수치적으로 보장하지 못할 수 있다. QR 분해 기반의 제곱근 형식은 공분산 행렬의 제곱근을 직접 갱신함으로써 양정치성을 자동으로 유지한다. 이는 정밀한 항법과 자세 추정에서 결정적인 이점을 제공한다.

12.4 자코비안의 영 공간 추출

매니퓰레이터의 자코비안 행렬에 대한 QR 분해는 영 공간의 명시적인 정규 직교 기저를 제공한다. 이 기저는 여유 자유도 로봇의 부차 작업 수행과 영 공간 사영에 직접 활용된다.

12.5 그래프 SLAM의 정보 행렬

그래프 SLAM에서 정보 행렬은 일반적으로 큰 희소 행렬이며, 그 분해는 기븐스 회전 기반 QR 분해로 효율적으로 수행될 수 있다. 새로운 측정이 추가될 때마다 점진적 갱신을 통하여 분해를 유지한다.

12.6 시스템 식별과 부분 공간 방법

데이터 기반 시스템 식별의 부분 공간 방법은 한켈 행렬에 대한 QR 분해를 핵심 단계로 활용한다. 이를 통하여 시스템의 차수와 매개 변수가 효율적으로 추출된다.

12.7 모델 예측 제어

모델 예측 제어의 매 시간 단계에서 형성되는 제약 조건이 있는 이차 계획법 문제는 종종 QR 분해를 활용하여 풀어진다. 특히 활성 제약의 변화를 다루는 알고리듬에서 점진적 QR 갱신이 핵심적이다.

참고문헌

Trefethen, L. N., & Bau, D. (2022). Numerical Linear Algebra (25th Anniversary ed.). SIAM.
Golub, G. H., & Van Loan, C. F. (2013). Matrix Computations (4th ed.). Johns Hopkins University Press.
Demmel, J. W. (1997). Applied Numerical Linear Algebra. SIAM.
Björck, Å. (1996). Numerical Methods for Least Squares Problems. SIAM.
Higham, N. J. (2002). Accuracy and Stability of Numerical Algorithms (2nd ed.). SIAM.
Anderson, E., et al. (1999). LAPACK Users’ Guide (3rd ed.). SIAM.

Version: 1.0