QR 분해

QR 분해(QR decomposition)는 임의의 행렬을 직교행렬과 상삼각행렬의 곱으로 분해하는 방법이다. QR 분해는 선형 최소제곱법을 풀 때나 고유벡터를 구할 때 등의 상황에 사용된다. 방법으로는 그람-슈미트 직교정규화 혹은 하우스홀더의 방법 등이 있다.

분해 방법

그람-슈미트 방법

그람-슈미트 직교정규화를 사용하여 QR 분해를 할 수 있다. 행렬 $A = [\mathbf{a}_1, \mathbf{a}_2, \cdots, \mathbf{a}_n]$에 대해, 그람-슈미트 직교정규화를 사용하면

$\mathrm{proj}_{\mathbf{e}}\mathbf{a} = \frac{\left\langle\mathbf{e},\mathbf{a}\right\rangle}{\left\langle\mathbf{e},\mathbf{e}\right\rangle}\mathbf{e}$

인 사영 연산자를 이용해서

$\mathbf{u}_i = \mathbf{a}_i - \sum_{j=1}^{i-1} \mathrm{proj}_{\mathbf{e}_j} \mathbf{a}_i$

$\mathbf{e}_i = \frac {\mathbf{u}_i} {\|\mathbf{u}_i\|}$

와 같이 직교정규기저 $\mathbf{e}_1, \mathbf{e}_2, \cdots, \mathbf{e}_n$를 얻을 수 있다. 이 식을 다시 정리하면

$\mathbf{a}_i = \sum_{j=1}^{i} \langle \mathbf{e}_j, \mathbf{a}_i \rangle \mathbf{e}_j$

가 되므로,

$Q = [\mathbf{e}_1, \mathbf{e}_, \cdots, \mathbf{e}_n]$

$R = \begin{pmatrix} \langle\mathbf{e}_1,\mathbf{a}_1\rangle & \langle\mathbf{e}_1,\mathbf{a}_2\rangle & \langle\mathbf{e}_1,\mathbf{a}_3\rangle & \ldots \\ 0 & \langle\mathbf{e}_2,\mathbf{a}_2\rangle & \langle\mathbf{e}_2,\mathbf{a}_3\rangle & \ldots \\ 0 & 0 & \langle\mathbf{e}_3,\mathbf{a}_3\rangle & \ldots \\ \vdots & \vdots & \vdots & \ddots \end{pmatrix}$

와 같이 놓으면 $A = QR$이 성립한다.

하우스홀더 방법

하우스홀더 리플렉터를 이용하여 한 열씩을 상삼각행렬로 바꾸어감으로써 Q와 R을 구할 수 있다. 이 방법은 Q행렬을 하우스홀더 행렬의 곱으로 구해주기 때문에, 직접 Q를 구할 필요가 없을 때 유용하다. 또, 그람-슈미트 방법과는 달리, 부동소수점 연산에서도 오차가 누적되지 않기 때문에, 실제로 더 많이 활용된다.