행렬의 QR 분해

개요

효율적인 행렬 분해에는 여러가지 조건이 필요하지만, 효율 이전에 분해 자체를 할 수 있느냐 없느냐가 중요할 수 있다. QR 분해는 정방행렬이라는 조건이 필요 없는 행렬 분해법이다.

정의

계수가 $n$ 인 행렬 $A := \begin{bmatrix} \mathbf{a}_{1} & \cdots & \mathbf{a}_{n} \end{bmatrix} \in \mathbb{C}^{m \times n}_{n}$ 에 대해 $i$번째까지의 열벡터로 생성된 부분공간

$$ S_{i} (A) := \text{sp} \left\{ \mathbf{a}_{1}, \cdots , \mathbf{a}_{i} \right\} $$

을 정의하자. 벡터공간을 생성할 땐 $i$ 가 클수록 많은 열벡터를 사용할 수 있으므로

$$ S_{1} (A) \subset S_{2} (A) \subset \cdots S_{n} (A) $$

가 성립할 것이다.

물론 정규직교벡터로 이루어진 행렬

$$ \widehat{Q} : = \begin{bmatrix} \mathbf{q}_{1} & \cdots & \mathbf{q}_{n} \end{bmatrix} \in \mathbb{C}^{m \times n}_{n} $$

에 대해서도 $S_{1} (\widehat{Q}) \subset S_{2} (\widehat{Q}) \subset \cdots S_{n} (\widehat{Q})$ 는 성립한다.

만약 $S_{i} (A) = S_{i} (\widehat{Q})$ 를 만족하는 관계식 등을 찾을 수 있다면 $\widehat{Q}$ 가 다루기 쉬우므로 행렬 $A$ 도 다루는 게 한결 쉬워질 것이다.

$$ \begin{align*} \mathbf{a}_{1} =& r_{11} \mathbf{q}_{1} \\ \mathbf{a}_{2} =& r_{12} \mathbf{q}_{1} + r_{22} \mathbf{q}_{2} \\ &\vdots \\ \mathbf{a}_{n} =& r_{1n} \mathbf{q}_{1} + \cdots + r_{nn} \mathbf{q}_{n} \end{align*} $$

우리가 구하고 싶은 관계식들은 위와 같은 형태들로 나타날 것이고, 행렬의 곱으로는 아래와 같이 정리된다.

$$ A = \begin{bmatrix} \mathbf{a}_{1} & \cdots & \mathbf{a}_{n} \end{bmatrix} = \begin{bmatrix} \mathbf{q}_{1} & \cdots & \mathbf{q}_{n} \end{bmatrix} \begin{bmatrix} r_{11} & r_{12} & \cdots & r_{1n} \\ 0 & r_{22} & \cdots & r_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & r_{nn} \end{bmatrix} := \widehat{Q} \widehat{R} $$

그리고 이러한 행렬의 곱을 만족시키는

$$ \widehat{Q} : = \begin{bmatrix} \mathbf{q}_{1} & \cdots & \mathbf{q}_{n} \end{bmatrix} \\ \widehat{R} := \begin{bmatrix} r_{11} & r_{12} & \cdots & r_{1n} \\ 0 & r_{22} & \cdots & r_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & r_{nn} \end{bmatrix} $$ 을 찾는 것이 바로 QR 분해다.

알고리즘

$\begin{bmatrix} \mathbf{a}_{1} & \cdots & \mathbf{a}_{n} \end{bmatrix} \in \mathbb{C}^{m \times n}_{n}$ 이라고 하자.

**Step 1. $j=1$

$\mathbf{a}_{1} = r_{11} \mathbf{q}_{1}$ 과 $| \mathbf{q}_{1} | = 1$ 을 만족하는 $r_{11}$ 을 계산한다.

**Step 2. $j= 2, 3, \cdots , n$

**Step 2-1. $i = 1,2, \cdots , j-1$ 에 대해 $r_{ij} = \mathbf{q}_{i}^{\ast}\mathbf{a}_{j}$ 를 계산한다.
Step 2-2. 다음과 같이 임시 벡터를 계산한다. $$ \mathbf{v}_{j} = \mathbf{a}_{j} - \sum_{i = 1}^{j-1} r_{ij} \mathbf{q}_{i} = \mathbf{a}_{j} - \sum_{i=1}^{j-1} (\mathbf{q}_{i}^{\ast}\mathbf{a}_{j} ) \mathbf{q}_{i} $$
**Step 2-3. $r_{jj} = | \mathbf{v}_{j} |$ 를 계산한다.
Step 2-4. 다음을 계산한다. $$ \mathbf{q}_{j} = {{ \mathbf{v}_{j} } \over {r_{jj} }} $$

여기서 $R$ 은 상삼각행렬로 주어지며 $r_{jj} = | \mathbf{v}_{j} |$ 로 계산되므로 항상 $r_{jj} > 0$ 임이 보장되고, 따라서 $R^{-1}$ 이 존재함을 알 수 있다.
한편 $\widehat{Q}$ 와 $\widehat{R}$ 의 표기를 보고 눈치 챘겠지만, 더 자세하게 말하자면 위의 분해는 축소 QR 분해, 즉 rQR 분해라고 부른다.
전체 QR 분해, 즉 fQR 분해는 특이값 분해에서 했던 것과 마찬가지로 정규직교벡터로 이루어진 $Q = \begin{bmatrix} \widehat{Q} & \mathbf{q}_{n+1} & \cdots & \mathbf{q}_{m} \end{bmatrix} \in \mathbb{C}^{m \times m}$ 과 하단에 $0$ 을 채워넣은 $R = \begin{bmatrix} \widehat{R} \\ O \end{bmatrix} \in \mathbb{C}^{m \times n}$ 을 구성함으써 구해진다.

존재성

행렬 $A \in \mathbb{C}^{m \times n}$ 은 반드시 QR 분해를 갖는다.

유일성

가역행렬 $A \in \mathbb{R}^{m \times m}$ 은 단 하나의 rQR 분해를 갖는다.

설명

존재성과 유일성이 보장되어 있는 것은 좋지만 사실상 증명이랄 게 별로 없다. 특히 유일성의 경우엔 유일하다는 걸 증명함에도 불구하고 부호가 반전되는 등에 대해서는 허용하는 등 자세하게 파고들수록 지저분한 팩트기 때문에 그냥 대충 알고 넘어가는 것을 추천한다.