30.29 QR 분해(QR Decomposition)의 정의와 구성 절차

1. QR 분해의 정의

$m \times n$ 행렬 $A$ ( $m \geq n$ )의 **QR 분해(QR decomposition, QR factorization)**란 $A$ 를 직교 행렬(또는 직교 열을 갖는 행렬) $Q$ 와 상삼각 행렬(upper triangular matrix) $R$ 의 곱으로 분해하는 것이다.

전체 QR 분해(full QR decomposition):

$A = Q R$

여기서 $Q \in M_{m \times m}(\mathbb{R})$ 는 직교 행렬( $Q^T Q = Q Q^T = I_m$ ), $R \in M_{m \times n}(\mathbb{R})$ 은 상삼각 형태의 행렬이다. $m > n$ 이면 $R$ 의 하단 $m - n$ 개 행은 모두 영행이다.

축소 QR 분해(reduced QR decomposition, thin QR decomposition):

$A = \hat{Q} \hat{R}$

여기서 $\hat{Q} \in M_{m \times n}(\mathbb{R})$ 는 정규 직교 열을 갖는 행렬( $\hat{Q}^T \hat{Q} = I_n$ ), $\hat{R} \in M_{n \times n}(\mathbb{R})$ 는 상삼각 행렬이다.

정방 행렬( $m = n$ )인 경우 전체 QR 분해와 축소 QR 분해는 동일하다.

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

정리 (존재성). 임의의 $m \times n$ 행렬 $A$ ( $m \geq n$ )에 대하여 QR 분해 $A = QR$ 이 존재한다.

정리 (유일성). $A$ 가 열 계수(column rank) $n$ 을 가지면, $\hat{R}$ 의 대각 성분이 모두 양수인 축소 QR 분해 $A = \hat{Q} \hat{R}$ 은 유일하다.

유일성 조건에서 $\hat{R}$ 의 대각 성분이 양수라는 규약을 부가하지 않으면, 각 열에 대한 부호 자유도가 존재하여 유일하지 않다. $r_{kk} > 0$ 으로 규약을 고정하면 $\hat{Q}$ 와 $\hat{R}$ 이 유일하게 결정된다.

3. 그람-슈미트 정규 직교화에 의한 QR 분해

가장 직관적인 QR 분해 구성법은 **그람-슈미트 정규 직교화(Gram-Schmidt orthonormalization)**이다.

3.1 고전적 그람-슈미트(Classical Gram-Schmidt, CGS)

$A$ 의 열벡터를 $a_1, a_2, \ldots, a_n$ 이라 하자. 정규 직교 벡터 $q_1, q_2, \ldots, q_n$ 을 순차적으로 구성한다.

$k = 1, 2, \ldots, n$ 에 대하여:

$u_k = a_k - \sum_{j=1}^{k-1} (q_j^T a_k) \, q_j$

$q_k = \frac{u_k}{\lVert u_k \rVert}$

$R$ 의 성분은 다음과 같이 결정된다:

$r_{jk} = q_j^T a_k \quad (j < k), \qquad r_{kk} = \lVert u_k \rVert$

결과적으로 $A = \hat{Q} \hat{R}$ 이며, $\hat{Q} = (q_1 \mid q_2 \mid \cdots \mid q_n)$ , $\hat{R} = (r_{jk})$ 이다.

3.2 수정 그람-슈미트(Modified Gram-Schmidt, MGS)

고전적 그람-슈미트는 유한 정밀도 산술에서 직교성이 점진적으로 상실되는 수치적 불안정성을 갖는다. **수정 그람-슈미트(Modified Gram-Schmidt, MGS)**는 이를 개선한다.

고전적 방법에서는 $a_k$ 로부터 $q_1, \ldots, q_{k-1}$ 방향의 성분을 한꺼번에 제거하지만, 수정 방법에서는 순차적으로 하나씩 제거한다:

$k = 1, 2, \ldots, n$ 에 대하여:

$u_k^{(0)} = a_k$

$u_k^{(j)} = u_k^{(j-1)} - (q_j^T u_k^{(j-1)}) \, q_j, \quad j = 1, 2, \ldots, k-1$

$q_k = \frac{u_k^{(k-1)}}{\lVert u_k^{(k-1)} \rVert}$

정확한 산술에서 CGS와 MGS는 동일한 결과를 산출하나, 유한 정밀도에서 MGS가 현저히 우수한 직교성을 유지한다.

4. 하우스홀더 변환에 의한 QR 분해

실용적 수치 계산에서 가장 널리 사용되는 QR 분해 방법은 **하우스홀더 반사(Householder reflection)**에 기반한다.

4.1 하우스홀더 반사의 정의

단위 벡터 $v$ ( $\lVert v \rVert = 1$ )에 대하여 **하우스홀더 행렬(Householder matrix)**은

$H = I - 2 v v^T$

로 정의된다. $H$ 는 다음 성질을 갖는다:

$H^T = H$ (대칭)
$H^T H = I$ (직교)
$H^2 = I$ (대합, involution)
$\det(H) = -1$ (반사)

$H$ 는 $v$ 에 수직인 초평면에 대한 **반사(reflection)**를 수행한다.

4.2 하우스홀더 변환으로 열을 소거하는 원리

주어진 벡터 $x \in \mathbb{R}^m$ 에 대하여 $Hx = \pm \lVert x \rVert e_1$ ( $e_1$ 은 첫 번째 표준 기저 벡터)이 되도록 $v$ 를 선택할 수 있다:

$v = \frac{x - \alpha e_1}{\lVert x - \alpha e_1 \rVert}, \quad \alpha = \pm \lVert x \rVert$

수치 안정성을 위하여 $\alpha = -\operatorname{sgn}(x_1) \lVert x \rVert$ 로 선택하는 것이 표준적이다.

4.3 QR 분해 절차

$n$ 번의 하우스홀더 변환을 순차적으로 적용하여 $A$ 를 상삼각 행렬로 변환한다.

단계 1. $A$ 의 첫 번째 열에 대한 하우스홀더 행렬 $H_1$ 을 구성한다. $H_1 A$ 의 첫 번째 열은 $(\alpha_1, 0, \ldots, 0)^T$ 형태가 된다.

단계 2. $H_1 A$ 의 2번째 열 이하, 2번째 행 이하의 부분 행렬에 대하여 하우스홀더 행렬 $\tilde{H}_2$ 를 구성한다. $H_2 = \operatorname{diag}(1, \tilde{H}_2)$ 로 확장하면 $H_2 H_1 A$ 의 처음 두 열이 상삼각 형태가 된다.

단계 $k$ . 이 과정을 $k = 1, 2, \ldots, n$ (또는 $m - 1$ )까지 반복하면

$H_n \cdots H_2 H_1 A = R$

따라서

$Q = H_1 H_2 \cdots H_n, \quad A = QR$

$H_k$ 가 각각 직교 행렬이므로 $Q$ 도 직교 행렬이다.

4.4 계산 복잡도

하우스홀더 QR 분해의 계산 복잡도는 $\frac{2}{3} n^3$ (정방 행렬의 경우) 또는 $2mn^2 - \frac{2}{3}n^3$ ( $m \times n$ 행렬의 경우)이다. 수정 그람-슈미트의 $2mn^2$ 과 동일한 차수이나, 하우스홀더 방법이 수치적으로 더 안정하다.

5. 기븐스 회전에 의한 QR 분해

**기븐스 회전(Givens rotation)**은 2차원 평면 회전을 이용하여 행렬의 특정 성분을 하나씩 소거하는 방법이다.

5.1 기븐스 회전 행렬

$(i, j)$ 평면에서의 기븐스 회전 행렬 $G(i, j, \theta)$ 는 항등 행렬에서 $(i, i)$ , $(i, j)$ , $(j, i)$ , $(j, j)$ 위치만 변경한 것이다:

$g_{ii} = g_{jj} = \cos \theta, \quad g_{ij} = -\sin \theta, \quad g_{ji} = \sin \theta$

$G$ 는 직교 행렬이며, $G x$ 는 $x$ 의 $(i, j)$ 좌표 평면에서 $\theta$ 만큼 회전한 결과이다. $\cos \theta$ 와 $\sin \theta$ 를 적절히 선택하면 $x$ 의 $j$ 번째 성분을 0으로 만들 수 있다.

5.2 QR 분해에의 적용

기븐스 회전을 반복 적용하여 $A$ 의 하삼각 성분을 하나씩 소거한다:

$G_{n,n-1} \cdots G_{3,2} G_{2,1} \cdots A = R$

$Q = G_{2,1}^T G_{3,2}^T \cdots G_{n,n-1}^T \cdots$

기븐스 회전의 계산 복잡도는 일반적으로 하우스홀더 방법보다 크다 ( $O(n^3)$ 대 $O(\frac{2}{3}n^3)$ ). 그러나 희소 행렬이나 하이젠베르크 행렬에서는 소거하여야 할 성분이 적으므로 기븐스 회전이 효율적이다. 하이젠베르크 행렬의 QR 분해는 $n - 1$ 번의 기븐스 회전으로 $O(n^2)$ 에 수행된다.

6. 세 가지 방법의 비교

방법	계산 복잡도 ( $m = n$ )	수치 안정성	적합한 용도
고전적 그람-슈미트	$2n^3$	불안정	이론적 설명용
수정 그람-슈미트	$2n^3$	중간	점진적 QR 분해
하우스홀더 변환	$\frac{2}{3}n^3$	안정	밀집 행렬의 표준 방법
기븐스 회전	$\frac{4}{3}n^3$	안정	희소 행렬, 하이젠베르크 행렬

7. 수치 예시

$A = \begin{pmatrix} 1 & 1 \\ 1 & 2 \\ 0 & 1 \end{pmatrix}$

그람-슈미트 과정을 적용한다.

열 1. $a_1 = (1, 1, 0)^T$ , $\lVert a_1 \rVert = \sqrt{2}$ , $q_1 = \frac{1}{\sqrt{2}}(1, 1, 0)^T$ , $r_{11} = \sqrt{2}$ .

열 2. $r_{12} = q_1^T a_2 = \frac{1}{\sqrt{2}}(1 + 2) = \frac{3}{\sqrt{2}}$ .

$u_2 = a_2 - r_{12} q_1 = \begin{pmatrix} 1 \\ 2 \\ 1 \end{pmatrix} - \frac{3}{\sqrt{2}} \cdot \frac{1}{\sqrt{2}} \begin{pmatrix} 1 \\ 1 \\ 0 \end{pmatrix} = \begin{pmatrix} 1 \\ 2 \\ 1 \end{pmatrix} - \begin{pmatrix} 3/2 \\ 3/2 \\ 0 \end{pmatrix} = \begin{pmatrix} -1/2 \\ 1/2 \\ 1 \end{pmatrix}$

$r_{22} = \lVert u_2 \rVert = \sqrt{1/4 + 1/4 + 1} = \sqrt{3/2}$ , $q_2 = \frac{1}{\sqrt{6}}(-1, 1, 2)^T$ .

결과:

$\hat{Q} = \begin{pmatrix} 1/\sqrt{2} & -1/\sqrt{6} \\ 1/\sqrt{2} & 1/\sqrt{6} \\ 0 & 2/\sqrt{6} \end{pmatrix}, \quad \hat{R} = \begin{pmatrix} \sqrt{2} & 3/\sqrt{2} \\ 0 & \sqrt{3/2} \end{pmatrix}$

검증: $\hat{Q}^T \hat{Q} = I_2$ 이고 $\hat{Q} \hat{R} = A$ 이다.

8. QR 분해의 응용

최소제곱 문제. 과결정(overdetermined) 연립방정식 $Ax \approx b$ ( $m > n$ )의 최소제곱 해는 $A = \hat{Q} \hat{R}$ 을 이용하여 $\hat{R} x = \hat{Q}^T b$ 로 환원되며, 상삼각 행렬의 후방 대입으로 $O(n^2)$ 에 풀 수 있다.

고유값 계산. QR 알고리즘에서 매 반복의 핵심 단계가 QR 분해이다.

직교 기저 계산. $\hat{Q}$ 의 열벡터는 $A$ 의 열 공간(column space)의 정규 직교 기저를 구성한다.

행렬의 계수 결정. $\hat{R}$ 의 대각 성분 중 0인 것의 개수로부터 $A$ 의 계수(rank)를 판별할 수 있다 (수치적으로는 기계 정밀도 이하의 성분을 0으로 간주).