QR 분해

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

분해 방법

그람-슈미트 방법

벡터 $\mathbf {a} _{1},\mathbf {a} _{2},\cdots ,\mathbf {a} _{n}\in \mathbb {R} ^{m}$${\mathbf {a}}_{1},{\mathbf {a}}_{2},\cdots ,{\mathbf {a}}_{n}\in {\mathbb {R}}^{m}$이 일차독립이라 하자. 행렬 $A=[{\begin{array}{llll}\mathbf {a} _{1}&\mathbf {a} _{2}&\cdots &\mathbf {a} _{n}\end{array}}]$$A=[{\begin{array}{llll}{\mathbf {a}}_{1}&{\mathbf {a}}_{2}&\cdots &{\mathbf {a}}_{n}\end{array}}]$ 에 대해, 그람-슈미트 직교정규화를 사용하면

$\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}$${\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 {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}}_{i}={\frac {{\mathbf {u}}_{i}}{\|{\mathbf {u}}_{i}\|}}$

와 같이 직교정규기저 $\{\mathbf {e} _{1},\mathbf {e} _{2},\cdots ,\mathbf {e} _{n}\}$$\{{\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}$${\mathbf {a}}_{i}=\sum _{{j=1}}^{{i}}\langle {\mathbf {e}}_{j},{\mathbf {a}}_{i}\rangle {\mathbf {e}}_{j}$

가 되므로,

$Q=[{\begin{array}{llll}\mathbf {e} _{1}&\mathbf {e} _{2}&\cdots &\mathbf {e} _{n}\end{array}}]$$Q=[{\begin{array}{llll}{\mathbf {e}}_{1}&{\mathbf {e}}_{2}&\cdots &{\mathbf {e}}_{n}\end{array}}]$

$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}}$$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$$A=QR$이 성립한다.

하우스홀더 방법

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

함께 보기

• LU 분해
• 특이값 분해