QR 분해

선형대수학에서 **QR 분해**(QR decomposition, QR factorization)는 실수 성분 정사각 행렬을 직교 행렬와 상삼각 행렬의 곱으로 나타내는 행렬 분해 M=QR이다.isbn=978-0-321-38517-8 그람-슈미트 과정이나 하우스홀더 행렬이나 기븐스 회전을 통해 얻을 수 있으며, 선형 최소 제곱법이나 QR 알고리즘 따위에서 쓰인다.
# 정의
실수체 또는 복소수체 \mathbb K 성분의 m\times n 행렬 M은 항상 다음과 같이 분해할 수 있으며, 이를 M의 **(두꺼운) QR 분해**((thick) QR decomposition)라고 한다.lccn=2012943449246, Theorem 5.2.1 :M=QR 여기서 * Q는 \mathbb K 성분의 m\times m 정사각 행렬이며, Q의 열들은 그 선형 생성의 정규 직교 기저를 이룬다. 즉, Q는 \mathbb K=\mathbb R일 때 직교 행렬, \mathbb K=\mathbb C일 때 유니터리 행렬이다. * R는 \mathbb K 성분의 m\times n 행렬이며, i>j에 대하여 R_{ij}=0이다. 즉, 상삼각 행렬이다.
## 얇은 분해
실수체 또는 복소수체 \mathbb K 성분의 m\times n 행렬 M에 대하여, 만약 m\ge n이라면, M을 다음과 같이 분해할 수 있으며, 이를 M의 **얇은 QR 분해**(thin QR decomposition, reduced QR decomposition)라고 한다.248, Theorem 5.2.3 :M=Q'R' 여기서 * Q'은 \mathbb K 성분의 m\times n 행렬이며, Q'의 열들은 그 선형 생성의 정규 직교 기저를 이룬다. 그러나, 정사각 행렬일 필요가 없으므로 직교 행렬이나 유니터리 행렬이 아닐 수 있다. * R'은 \mathbb K 성분의 n\times n 상삼각 행렬이다. 물론, 정사각 행렬의 경우 (m=n) QR 분해와 얇은 QR 분해를 구분할 필요가 없다. 얇은 QR 분해는 QR 분해의 특수한 경우이다. 구체적으로, m\ge n이며, QR 분해 M=QR가 주어졌다고 하자. Q'이 Q의 첫 n열 들로 이루어진 m\times n 행렬, R'이 R의 첫 n행들로 이루어진 n\times n 행렬이라고 하였을 때, :Q=\begin{pmatrix}Q'&Q;*\end{pmatrix} :R=\begin{pmatrix}R'\\\0\end{pmatrix} 이므로 :M=QR=\begin{pmatrix}Q'&Q;*\end{pmatrix}\begin{pmatrix}R'\\\0\end{pmatrix}=Q'R'+Q''0=Q'R' 이며, 이는 M의 얇은 QR 분해를 이룬다. 또한, 모든 얇은 QR 분해는 이러한 방식으로 얻을 수 있다.
## 가역 행렬과 유일성
다음 두 조건이 서로 동치이다. * \operatorname{rank}M=n. 여기서 \operatorname{rank}는 행렬 계수이다. * M의 열들이 선형 독립 집합을 이룬다. 또한, 이 조건은 m\ge n을 함의한다. m=n인 경우, 추가로 다음 조건이 이와 동치이다. * M은 가역 행렬이다. 만약 \operatorname{rank}M=n이라면, 다음이 성립한다. * Q의 열들은 M의 열들의 선형 생성의 정규 직교 기저를 이룬다. 보다 일반적으로, k=1,\dots,n에 대하여, Q의 첫 k열은 M의 첫 k열들의 선형 생성의 정규 직교 기저를 이룬다. M의 j번째 열이 Q의 첫 j열들의 선형 결합인 사실은 R의 상삼각성에 대응한다. * Q의 n+1번째 열과 m번째 열 사이의 열들은 M의 열들의 선형 생성의 직교 여공간의 정규 직교 기저를 이룬다. * i=1,\dots,n에 대하여, R_{ii}\ne0. 즉, R'은 가역 행렬이다. * R_{ii}>0 (i=1,\dots,n)인 경우로 제한하면, R이나 R'은 유일하며, Q'도 유일하다. 이 경우, R'은 A^\dagger A의 숄레스키 분해의 상삼각 성분과 같다. 그러나 Q''은 부분 공간의 정규 직교 기저를 전체 공간의 정규 직교 기저로 확충하는 방법에 대응하므로, 일반적으로 유일하지 않다. 이에 따라, QR 분해는 일반적으로 유일하지 않으며, \operatorname{rank}M=n이라고 가정하더라도 m>n인 경우 유일하지 않다. 다만, 만약 \operatorname{rank}M=n이라면, M의 얇은 QR 분해는 유일하다. 특히, 가역 행렬의 QR 분해는 유일하다.
# 방법

## 그람-슈미트 과정
그람-슈미트 과정 벡터 \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}] 에 대해, 그람-슈미트 직교정규화를 사용하면 :\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{u}_j} \mathbf{a}_i :\mathbf{e}_i = \frac {\mathbf{u}_i} {\|\mathbf{u}_i\|} 와 같이 직교정규기저 \\{\mathbf{e}_1, \mathbf{e}_2, \cdots, \mathbf{e}_n\\}를 얻을 수 있다. : {\langle \cdot,\cdot \rangle} 은 내적 ,\;\; {\|{ }\|} 는 노름 위 식을 다시 정리하면 :\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}] :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 = \begin{pmatrix} 12 & -51 & 4 \\\ 6 & 167 & -68 \\\ -4 & 24 & -41 \end{pmatrix} 정규 직교 행렬 Q는 Q^T \,Q = I의 성질을 갖고있고, 따라서, Q는 다음과 같이 그람-슈미트 절차를 따라서, : 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} : 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\times35\right) \\\ 6/14 & 158/175 & 6/\left(5\times35\right) \\\ -4/14 & 30/175 & -33/\left(1\times35\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} 그리고, : Q^{T} A = Q^{T}Q\,R = R : R = Q^{T}A = \begin{pmatrix} 14 & 21 & -14 \\\ 0 & 175 & -70 \\\ 0 & 0 & 35 \end{pmatrix} 확인해보면, :A= QR이므로, : \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} :QR=A이다. :QR분해 된다. 그러나, 분수에의한 부동소수점연산이 관계함으로 오차가 발생할 수 있다.
### RQ 분해와의 관계
RQ 분해는 행렬 A를 상삼각행렬 R (직각 삼각형이라고도 함) 및 직교 행렬 Q 의 곱으로 변환한다. QR 분해와의 유일한 차이점은 행렬의 순서이다. QR 분해는 첫 번째 열에서 시작된 A 행렬의 열의 그람-슈미트 직교화이다. RQ 분해는 마지막 행에서 시작하는 A 행렬의 행의 그람-슈미트 직교화이다.
### 장점과 단점
그람-슈미트 프로세스는 본질적으로 수치적으로 불안정할 수 있다. 투영법의 적용에는 직교화에 대한 주요한 기하학적 유추가 있지만 직교화 자체는 수치 오류가 발생하기 쉽다. 그러나 구현의 용이함이 중요한 장점이다. 사전 작성된 선형 대수 라이브러리(library)를 사용할 수 없거나 용이하지 않은 경우, 이 알고리즘을 프로토타입(prototype)에 사용할 수 있는 유용한 알고리즘으로 적용할 수 있다.
## 하우스홀더 방법
하우스홀더 변환 하우스홀더 리플렉터(하우스홀더 변환,Householder reflection)를 이용하여 한 열씩을 상삼각행렬로 바꾸어감으로써 Q와 R을 구할 수 있다. 이 방법은 Q행렬을 하우스홀더 행렬의 곱으로 구해주기 때문에, 직접 Q를 구할 필요가 없을 때 유용하다. 또, 그람-슈미트 방법은 컴퓨터를 활용하여 계산할 때 0으로 계산되어야 하는 R의 성분이 0이 아닌 값들을 가지는 경우가 많다. 이는 그람-슈미트 방법은 분수의 연산을 수반하고 이에 따른 부동소수점 연산의 오차가 발생하기 때문이다. 크기가 작은 행렬에서는 이 문제가 크게 작용하지 않으나, 크기가 커질수록 오차도 커지게 된다. 때문에 오차를 줄이기 위해서 하우스홀더 변환을 사용하며 본질적으로 이 변환은 R의 특정 성분을 0으로 만들어 상삼각행렬이 되도록 하기 때문에 수치적으로 안정하다. 하지만, 새로운 0 성분을 만드는 모든 변환이 Q와 R 모두를 바꾸기 때문에 하우스홀더 변환 알고리즘은 대역폭이 넓고 병렬화가 불가능하다는 단점이 있다.
### 예
: A = \begin{pmatrix} 12 & -51 & 4 \\\ 6 & 167 & -68 \\\ -4 & 24 & -41 \end{pmatrix} 먼저 행렬 A 의 첫 번째 열을 벡터로 변환하는 리플렉션을 찾아야한다. :\|{a}_1\| \;{e}_1 = (14, 0, 0)^T에서, :벡터 {a}_1 = (12, 6, -4)^T : {u} = {x} - \alpha{e}_1 : {v} = u}\over\|{u}\|} : \alpha = 14 :{x} = {a}_1 = (12, 6, -4)^T 따라서, : {u} = (-2, 6, -4)^T=({2})(-1, 3, -2)^T :{v} = (-1, 3, -2)^T} \over {\sqrt{14 } 하우스홀더 행렬 Q = I - 2{v v^T\over{1에서, :Q_1 = I - 2\begin{pmatrix} -1 \\\ 3 \\\ -2 \end{pmatrix \over \sqrt{14} }\begin{pmatrix} -1 & 3 & -2 \end{pmatrix \over \sqrt{14} } :Q_1 = I - {2 \over \sqrt{14} \sqrt{14 \begin{pmatrix} -1 \\\ 3 \\\ -2 \end{pmatrix}\begin{pmatrix} -1 & 3 & -2 \end{pmatrix} : = I - {1 \over 7}\begin{pmatrix} 1 & -3 & 2 \\\ -3 & 9 & -6 \\\ 2 & -6 & 4 \end{pmatrix} : = \begin{pmatrix} 6/7 & 3/7 & -2/7 \\\ 3/7 &-2/7 & 6/7 \\\ -2/7 & 6/7 & 3/7 \\\ \end{pmatrix}. 확인해보면, :Q_1A = \begin{pmatrix} 14 & 21 & -14 \\\ 0 & -49 & -14 \\\ 0 & 168 & -77 \end{pmatrix} 삼각행렬에 접근하고 있음을 알 수 있다. 3행2열에서 (3, 2)의 성분 값을 0으로 만들면 상삼각행렬을 얻게 된다. (1, 1) 소행렬식에서 다시 위의 절차를 반복해보면, :A' = M_{11} = \begin{pmatrix} -49 & -14 \\\ 168 & -77 \end{pmatrix} 위와 같은 방법으로 하우스홀더 변환(Householder transformation)된 행렬을 얻고, :Q_2 = \begin{pmatrix} 1 & 0 & 0 \\\ 0 & -7/25 & 24/25 \\\ 0 & 24/25 & 7/25 \end{pmatrix} :Q_1 , Q_2에서 각각 전치행렬을 수행한 후 프로세스가 올바르게 작동하는지 확인해보고, Q_1 = Q_1^T , Q_2 = Q_2^T 그리고나서, :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} 그리고, :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} :R=Q_2Q_1A=Q^T A=\begin{pmatrix} 14 & 21 & -14 \\\ 0 & 175 & -70 \\\ 0 & 0 & -35 \end{pmatrix} 행렬 Q는 직교행렬이고 R 은 상삼각행렬이되고 QR=A 로 QR 분해된다.
## 기븐스 회전
기븐스 행렬은 특정위치에서 성분값을 0으로 조작할 수 있는 방법으로 기븐스 회전을 제공한다. 이것은 임의의 행렬을 직교행렬과 특정위치의 성분값이 0 인 상삼각행렬로 분해되게 유도할 수 있게된다.
### 예
: A = \begin{pmatrix} a_{11} & a_{12} & a_{13} \\\ a_{21} & a_{22} & a_{23}\\\ a_{31} & a_{32} & a_{33} \end{pmatrix} : A = \begin{pmatrix} 12 & -51 & 4 \\\ 6 & 167 & -68 \\\ -4 & 24 & -41 \end{pmatrix} :\mathbf{a}_{31} = -4 :G_1 , (12,-4) :\theta = \arctan\left({-(-4) \over 12}\right) : G_1 = \begin{pmatrix} \cos(\theta) & 0 & -\sin(\theta) \\\ 0 & 1 & 0 \\\ \sin(\theta) & 0 & \cos(\theta) \end{pmatrix} := \begin{pmatrix} 0.94868... & 0 & -0.31622... \\\ 0 & 1 & 0 \\\ 0.31622... & 0 & 0.94868... \end{pmatrix} :G_1 \cdot A는 \mathbf{a}_{31} =0으로 조작된다. :G_1A = \begin{pmatrix} 12.64911... & -55.97231... & 16.76007... \\\ 6 & 167 & -68 \\\ 0 & 6.64078... & -37.6311... \end{pmatrix} G_2 그리고 G_3 도 이러한 절차를 반복한다. :a_{21}=0 그리고 a_{32}=0으로 조작된다. 결과로 상삼각행렬R을 얻는다. 따라서, : G_3 \cdot G_2 \cdot G_1=Q^T :G_3G_2G_1A= Q^TA = R : \left( Q^T \right)^T = Q 직교행렬에서, :Q^T = Q^{-1}, Q Q^T = Q^T Q = I 그리고, QR=A이다. :A=QR로 분해된다.