QR 분해

선형대수학에서 QR 분해(영어: QR decomposition, QR factorization)는 실수 성분 정사각 행렬을 직교 행렬와 상삼각 행렬의 곱으로 나타내는 행렬 분해 ${\displaystyle M=QR}$이다.^[1] 그람-슈미트 과정이나 하우스홀더 행렬이나 기븐스 회전을 통해 얻을 수 있으며, 선형 최소 제곱법이나 QR 알고리즘 따위에서 쓰인다.

정의

실수체 또는 복소수체 ${\displaystyle \mathbb {K} }$ 성분의 ${\displaystyle m\times n}$ 행렬 ${\displaystyle M}$은 항상 다음과 같이 분해할 수 있으며, 이를 ${\displaystyle M}$의 (두꺼운) QR 분해(영어: (thick) QR decomposition)라고 한다.^{[2]:246, Theorem 5.2.1}

${\displaystyle M=QR}$

여기서

• ${\displaystyle Q}$는 ${\displaystyle \mathbb {K} }$ 성분의 ${\displaystyle m\times m}$ 정사각 행렬이며, ${\displaystyle Q}$의 열들은 그 선형 생성의 정규 직교 기저를 이룬다. 즉, ${\displaystyle Q}$는 ${\displaystyle \mathbb {K} =\mathbb {R} }$일 때 직교 행렬, ${\displaystyle \mathbb {K} =\mathbb {C} }$일 때 유니터리 행렬이다.
• ${\displaystyle R}$는 ${\displaystyle \mathbb {K} }$ 성분의 ${\displaystyle m\times n}$ 행렬이며, ${\displaystyle i>j}$에 대하여 ${\displaystyle R_{ij}=0}$이다. 즉, 상삼각 행렬이다.

얇은 분해

실수체 또는 복소수체 ${\displaystyle \mathbb {K} }$ 성분의 ${\displaystyle m\times n}$ 행렬 ${\displaystyle M}$에 대하여, 만약 ${\displaystyle m\geq n}$이라면, ${\displaystyle M}$을 다음과 같이 분해할 수 있으며, 이를 ${\displaystyle M}$의 얇은 QR 분해(영어: thin QR decomposition, reduced QR decomposition)라고 한다.^{[2]:248, Theorem 5.2.3}

${\displaystyle M=Q'R'}$

여기서

• ${\displaystyle Q'}$은 ${\displaystyle \mathbb {K} }$ 성분의 ${\displaystyle m\times n}$ 행렬이며, ${\displaystyle Q'}$의 열들은 그 선형 생성의 정규 직교 기저를 이룬다. 그러나, 정사각 행렬일 필요가 없으므로 직교 행렬이나 유니터리 행렬이 아닐 수 있다.
• ${\displaystyle R'}$은 ${\displaystyle \mathbb {K} }$ 성분의 ${\displaystyle n\times n}$ 상삼각 행렬이다.

물론, 정사각 행렬의 경우 (${\displaystyle m=n}$) QR 분해와 얇은 QR 분해를 구분할 필요가 없다. 얇은 QR 분해는 QR 분해의 특수한 경우이다. 구체적으로, ${\displaystyle m\geq n}$이며, QR 분해 ${\displaystyle M=QR}$가 주어졌다고 하자. ${\displaystyle Q'}$이 ${\displaystyle Q}$의 첫 ${\displaystyle n}$열 들로 이루어진 ${\displaystyle m\times n}$ 행렬, ${\displaystyle R'}$이 ${\displaystyle R}$의 첫 ${\displaystyle n}$행들로 이루어진 ${\displaystyle n\times n}$ 행렬이라고 하였을 때,

${\displaystyle Q={\begin{pmatrix}Q'&Q''\end{pmatrix}}}$

${\displaystyle R={\begin{pmatrix}R'\\0\end{pmatrix}}}$

이므로

${\displaystyle M=QR={\begin{pmatrix}Q'&Q''\end{pmatrix}}{\begin{pmatrix}R'\\0\end{pmatrix}}=Q'R'+Q''0=Q'R'}$

이며, 이는 ${\displaystyle M}$의 얇은 QR 분해를 이룬다. 또한, 모든 얇은 QR 분해는 이러한 방식으로 얻을 수 있다.

가역 행렬과 유일성

다음 두 조건이 서로 동치이다.

• ${\displaystyle \operatorname {rank} M=n}$. 여기서 ${\displaystyle \operatorname {rank} }$는 행렬 계수이다.
• ${\displaystyle M}$의 열들이 선형 독립 집합을 이룬다.

또한, 이 조건은 ${\displaystyle m\geq n}$을 함의한다. ${\displaystyle m=n}$인 경우, 추가로 다음 조건이 이와 동치이다.

• ${\displaystyle M}$은 가역 행렬이다.

만약 ${\displaystyle \operatorname {rank} M=n}$이라면, 다음이 성립한다.

• ${\displaystyle Q}$의 열들은 ${\displaystyle M}$의 열들의 선형 생성의 정규 직교 기저를 이룬다. 보다 일반적으로, ${\displaystyle k=1,\dots ,n}$에 대하여, ${\displaystyle Q}$의 첫 ${\displaystyle k}$열은 ${\displaystyle M}$의 첫 ${\displaystyle k}$열들의 선형 생성의 정규 직교 기저를 이룬다. ${\displaystyle M}$의 ${\displaystyle j}$번째 열이 ${\displaystyle Q}$의 첫 ${\displaystyle j}$열들의 선형 결합인 사실은 ${\displaystyle R}$의 상삼각성에 대응한다.
• ${\displaystyle Q}$의 ${\displaystyle n+1}$번째 열과 ${\displaystyle m}$번째 열 사이의 열들은 ${\displaystyle M}$의 열들의 선형 생성의 직교 여공간의 정규 직교 기저를 이룬다.
• ${\displaystyle i=1,\dots ,n}$에 대하여, ${\displaystyle R_{ii}\neq 0}$. 즉, ${\displaystyle R'}$은 가역 행렬이다.
• ${\displaystyle R_{ii}>0}$ (${\displaystyle i=1,\dots ,n}$)인 경우로 제한하면, ${\displaystyle R}$이나 ${\displaystyle R'}$은 유일하며, ${\displaystyle Q'}$도 유일하다. 이 경우, ${\displaystyle R'}$은 ${\displaystyle A^{\dagger }A}$의 숄레스키 분해의 상삼각 성분과 같다. 그러나 ${\displaystyle Q''}$은 부분 공간의 정규 직교 기저를 전체 공간의 정규 직교 기저로 확충하는 방법에 대응하므로, 일반적으로 유일하지 않다.

이에 따라, QR 분해는 일반적으로 유일하지 않으며, ${\displaystyle \operatorname {rank} M=n}$이라고 가정하더라도 ${\displaystyle m>n}$인 경우 유일하지 않다. 다만, 만약 ${\displaystyle \operatorname {rank} M=n}$이라면, ${\displaystyle M}$의 얇은 QR 분해는 유일하다. 특히, 가역 행렬의 QR 분해는 유일하다.

방법

그람-슈미트 과정

 이 부분의 본문은 그람-슈미트 과정입니다.

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

${\displaystyle \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} }$

인 사영 연산자를 이용해서

${\displaystyle \mathbf {u} _{i}=\mathbf {a} _{i}-\sum _{j=1}^{i-1}\mathrm {proj} _{\mathbf {u} _{j}}\mathbf {a} _{i}}$

${\displaystyle \mathbf {e} _{i}={\frac {\mathbf {u} _{i}}{\|\mathbf {u} _{i}\|}}}$

와 같이 직교정규기저 ${\displaystyle \{\mathbf {e} _{1},\mathbf {e} _{2},\cdots ,\mathbf {e} _{n}\}}$를 얻을 수 있다.

${\displaystyle {\langle \cdot ,\cdot \rangle }}$은 내적 ${\displaystyle ,\;\;{\|{}\|}}$는 노름

위 식을 다시 정리하면

${\displaystyle \mathbf {a} _{i}=\sum _{j=1}^{i}\langle \mathbf {e} _{j},\mathbf {a} _{i}\rangle \mathbf {e} _{j}}$

가 되므로,

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

${\displaystyle 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}}}$

와 같이 놓으면 ${\displaystyle A=QR}$이 성립한다.

예

${\displaystyle A={\begin{pmatrix}12&-51&4\\6&167&-68\\-4&24&-41\end{pmatrix}}}$

정규 직교 행렬 ${\displaystyle Q}$는 ${\displaystyle Q^{T}\,Q=I}$의 성질을 갖고있고,

따라서, ${\displaystyle Q}$는 다음과 같이 그람-슈미트 절차를 따라서,

${\displaystyle U={\begin{pmatrix}u_{1}&u_{2}&u_{3}\end{pmatrix}}={\begin{pmatrix}12&-69&-58/5\\6&158&6/5\\-4&30&-33\end{pmatrix}}}$

${\displaystyle Q={\begin{pmatrix}{{u_{1}} \over {\|u_{1}\|}}&{{u_{2}} \over {\|u_{2}\|}}&{{u_{3}} \over {\|u_{3}\|}}\end{pmatrix}}={\begin{pmatrix}12/14&-69/175&-58/\left(5\times 35\right)\\6/14&158/175&6/\left(5\times 35\right)\\-4/14&30/175&-33/\left(1\times 35\right)\end{pmatrix}}={\begin{pmatrix}6/7&-69/175&-58/175\\3/7&158/175&6/175\\-2/7&6/35&-33/35\end{pmatrix}}}$

그리고,

${\displaystyle Q^{T}A=Q^{T}Q\,R=R}$

${\displaystyle R=Q^{T}A={\begin{pmatrix}14&21&-14\\0&175&-70\\0&0&35\end{pmatrix}}}$

확인해보면,

${\displaystyle A=QR}$이므로,

${\displaystyle {\begin{pmatrix}6/7&-69/175&-58/175\\3/7&158/175&6/175\\-2/7&6/35&-33/35\end{pmatrix}}\cdot {\begin{pmatrix}14&21&-14\\0&175&-70\\0&0&35\end{pmatrix}}={\begin{pmatrix}12&-51&4\\6&167&-68\\-4&24&-41\end{pmatrix}}}$

${\displaystyle QR=A}$이다.

${\displaystyle QR}$분해 된다.

그러나,

분수에의한 부동소수점연산이 관계함으로 오차가 발생할 수 있다.

RQ 분해와의 관계

${\displaystyle RQ}$ 분해는 행렬 ${\displaystyle A}$를 상삼각행렬${\displaystyle R}$ (직각 삼각형이라고도 함) 및 직교 행렬${\displaystyle Q}$ 의 곱으로 변환한다. ${\displaystyle QR}$분해와의 유일한 차이점은 행렬의 순서이다.

${\displaystyle QR}$분해는 첫 번째 열에서 시작된 ${\displaystyle A}$ 행렬의 열의 그람-슈미트 직교화이다.

${\displaystyle RQ}$ 분해는 마지막 행에서 시작하는 ${\displaystyle A}$ 행렬의 행의 그람-슈미트 직교화이다.

장점과 단점

그람-슈미트 프로세스는 본질적으로 수치적으로 불안정할 수 있다. 투영법의 적용에는 직교화에 대한 주요한 기하학적 유추가 있지만 직교화 자체는 수치 오류가 발생하기 쉽다. 그러나 구현의 용이함이 중요한 장점이다. 사전 작성된 선형 대수 라이브러리(library)를 사용할 수 없거나 용이하지 않은 경우, 이 알고리즘을 프로토타입(prototype)에 사용할 수 있는 유용한 알고리즘으로 적용할 수 있다.

하우스홀더 방법

 이 부분의 본문은 하우스홀더 변환입니다.

하우스홀더 리플렉터(하우스홀더 변환,Householder reflection)를 이용하여 한 열씩을 상삼각행렬로 바꾸어감으로써 ${\displaystyle Q}$와${\displaystyle R}$을 구할 수 있다. 이 방법은 ${\displaystyle Q}$행렬을 하우스홀더 행렬의 곱으로 구해주기 때문에, 직접 ${\displaystyle Q}$를 구할 필요가 없을 때 유용하다.

또, 그람-슈미트 방법은 컴퓨터를 활용하여 계산할 때 0으로 계산되어야 하는 R의 성분이 0이 아닌 값들을 가지는 경우가 많다. 이는 그람-슈미트 방법은 분수의 연산을 수반하고 이에 따른 부동소수점 연산의 오차가 발생하기 때문이다. 크기가 작은 행렬에서는 이 문제가 크게 작용하지 않으나, 크기가 커질수록 오차도 커지게 된다. 때문에 오차를 줄이기 위해서 하우스홀더 변환을 사용하며 본질적으로 이 변환은 ${\displaystyle R}$의 특정 성분을 0으로 만들어 상삼각행렬이 되도록 하기 때문에 수치적으로 안정하다. 하지만, 새로운 0 성분을 만드는 모든 변환이 ${\displaystyle Q}$와 ${\displaystyle R}$ 모두를 바꾸기 때문에 하우스홀더 변환 알고리즘은 대역폭이 넓고 병렬화가 불가능하다는 단점이 있다.

예

${\displaystyle A={\begin{pmatrix}12&-51&4\\6&167&-68\\-4&24&-41\end{pmatrix}}}$

먼저 행렬 ${\displaystyle A}$ 의 첫 번째 열을 벡터로 변환하는 리플렉션을 찾아야한다.

${\displaystyle \|{a}_{1}\|\;{e}_{1}=(14,0,0)^{T}}$에서,

벡터 ${\displaystyle {a}_{1}=(12,6,-4)^{T}}$

${\displaystyle {u}={x}-\alpha {e}_{1}}$

${\displaystyle {v}={{u} \over \|{u}\|}}$

${\displaystyle \alpha =14}$

${\displaystyle {x}={a}_{1}=(12,6,-4)^{T}}$

따라서,

${\displaystyle {u}=(-2,6,-4)^{T}=({2})(-1,3,-2)^{T}}$

${\displaystyle {v}={{(-1,3,-2)^{T}} \over {\sqrt {14}}}}$

하우스홀더 행렬 ${\displaystyle Q=I-2{{vv^{T}} \over {1}}}$에서,

${\displaystyle Q_{1}=I-2{{\begin{pmatrix}-1\\3\\-2\end{pmatrix}} \over {\sqrt {14}}}{{\begin{pmatrix}-1&3&-2\end{pmatrix}} \over {\sqrt {14}}}}$

${\displaystyle Q_{1}=I-{2 \over {\sqrt {14}}{\sqrt {14}}}{\begin{pmatrix}-1\\3\\-2\end{pmatrix}}{\begin{pmatrix}-1&3&-2\end{pmatrix}}}$

${\displaystyle =I-{1 \over 7}{\begin{pmatrix}1&-3&2\\-3&9&-6\\2&-6&4\end{pmatrix}}}$

${\displaystyle ={\begin{pmatrix}6/7&3/7&-2/7\\3/7&-2/7&6/7\\-2/7&6/7&3/7\\\end{pmatrix}}.}$

확인해보면,

${\displaystyle Q_{1}A={\begin{pmatrix}14&21&-14\\0&-49&-14\\0&168&-77\end{pmatrix}}}$

삼각행렬에 접근하고 있음을 알 수 있다. ${\displaystyle 3}$행${\displaystyle 2}$열에서 ${\displaystyle (3,2)}$의 성분 값을 ${\displaystyle 0}$으로 만들면 상삼각행렬을 얻게 된다.

${\displaystyle (1,1)}$ 소행렬식에서 다시 위의 절차를 반복해보면,

${\displaystyle A'=M_{11}={\begin{pmatrix}-49&-14\\168&-77\end{pmatrix}}}$

위와 같은 방법으로 하우스홀더 변환(Householder transformation)된 행렬을 얻고,

${\displaystyle Q_{2}={\begin{pmatrix}1&0&0\\0&-7/25&24/25\\0&24/25&7/25\end{pmatrix}}}$

${\displaystyle Q_{1},Q_{2}}$에서 각각 전치행렬을 수행한 후 프로세스가 올바르게 작동하는지 확인해보고,

${\displaystyle Q_{1}=Q_{1}^{T},Q_{2}=Q_{2}^{T}}$ 그리고나서,

${\displaystyle Q=Q_{1}^{T}Q_{2}^{T}={\begin{pmatrix}6/7&-69/175&58/175\\3/7&158/175&-6/175\\-2/7&6/35&33/35\end{pmatrix}}}$

그리고,

${\displaystyle Q=Q_{1}^{T}Q_{2}^{T}={\begin{pmatrix}0.8571&-0.3943&0.3314\\0.4286&0.9029&-0.0343\\-0.2857&0.1714&0.9429\end{pmatrix}}}$

${\displaystyle R=Q_{2}Q_{1}A=Q^{T}A={\begin{pmatrix}14&21&-14\\0&175&-70\\0&0&-35\end{pmatrix}}}$

행렬 ${\displaystyle Q}$는 직교행렬이고 ${\displaystyle R}$ 은 상삼각행렬이되고 ${\displaystyle QR=A}$로 ${\displaystyle QR}$ 분해된다.

기븐스 회전

기븐스 행렬은 특정위치에서 성분값을 ${\displaystyle 0}$으로 조작할 수 있는 방법으로 기븐스 회전을 제공한다.

이것은 임의의 행렬을 직교행렬과 특정위치의 성분값이 ${\displaystyle 0}$ 인 상삼각행렬로 분해되게 유도할 수 있게된다.

예

${\displaystyle A={\begin{pmatrix}a_{11}&a_{12}&a_{13}\\a_{21}&a_{22}&a_{23}\\a_{31}&a_{32}&a_{33}\end{pmatrix}}}$

${\displaystyle A={\begin{pmatrix}12&-51&4\\6&167&-68\\-4&24&-41\end{pmatrix}}}$

${\displaystyle \mathbf {a} _{31}=-4}$

${\displaystyle G_{1},(12,-4)}$

${\displaystyle \theta =\arctan \left({-(-4) \over 12}\right)}$

${\displaystyle G_{1}={\begin{pmatrix}\cos(\theta )&0&-\sin(\theta )\\0&1&0\\\sin(\theta )&0&\cos(\theta )\end{pmatrix}}}$

${\displaystyle ={\begin{pmatrix}0.94868...&0&-0.31622...\\0&1&0\\0.31622...&0&0.94868...\end{pmatrix}}}$

${\displaystyle G_{1}\cdot A}$는 ${\displaystyle \mathbf {a} _{31}=0}$으로 조작된다.

${\displaystyle G_{1}A={\begin{pmatrix}12.64911...&-55.97231...&16.76007...\\6&167&-68\\0&6.64078...&-37.6311...\end{pmatrix}}}$

${\displaystyle G_{2}}$ 그리고 ${\displaystyle G_{3}}$ 도 이러한 절차를 반복한다.

${\displaystyle a_{21}=0}$ 그리고 ${\displaystyle a_{32}=0}$으로 조작된다.

결과로 상삼각행렬${\displaystyle R}$을 얻는다. 따라서,

${\displaystyle G_{3}\cdot G_{2}\cdot G_{1}=Q^{T}}$

${\displaystyle G_{3}G_{2}G_{1}A=Q^{T}A=R}$

${\displaystyle \left(Q^{T}\right)^{T}=Q}$

직교행렬에서,

${\displaystyle Q^{T}=Q^{-1},QQ^{T}=Q^{T}Q=I}$

그리고, ${\displaystyle QR=A}$이다.

${\displaystyle A=QR}$로 분해된다.

같이 보기

• LU 분해
• 특잇값 분해