QR 분해

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

## 정의
실수체 또는 복소수체 \mathbb K 성분의 m\times n 행렬 M은 항상 다음과 같이 분해할 수 있으며, 이를 M의 **(두꺼운) QR 분해**()라고 한다.
: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 분해**()라고 한다.
: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}</math>
:<math>R=\begin{pmatrix}R'\\0\end{pmatrix}</math>
이므로
:<math>M=QR=\begin{pmatrix}Q'&Q*\end{pmatrix}\begin{pmatrix}R'\\0\end{pmatrix}=Q'R'+Q*0=Q'R'</math>
이며, 이는 <math>M</math>의 얇은 QR 분해를 이룬다. 또한, 모든 얇은 QR 분해는 이러한 방식으로 얻을 수 있다.

=== 가역 행렬과 유일성 ===
다음 두 조건이 서로 [[동치]]이다.
* <math>\operatorname{rank}M=n</math>. 여기서 <math>\operatorname{rank}</math>는 행렬 [[계수 (선형대수학)|계수]]이다.
* <math>M</math>의 열들이 [[선형 독립 집합]]을 이룬다.
또한, 이 조건은 <math>m\ge n</math>을 함의한다. <math>m=n</math>인 경우, 추가로 다음 조건이 이와 [[동치]]이다.
* <math>M</math>은 [[가역 행렬]]이다.
만약 <math>\operatorname{rank}M=n</math>이라면, 다음이 성립한다.
* <math>Q</math>의 열들은 <math>M</math>의 열들의 [[선형 생성]]의 [[정규 직교 기저]]를 이룬다. 보다 일반적으로, <math>k=1,\dots,n</math>에 대하여, <math>Q</math>의 첫 <math>k</math>열은 <math>M</math>의 첫 <math>k</math>열들의 [[선형 생성]]의 [[정규 직교 기저]]를 이룬다. <math>M</math>의 <math>j</math>번째 열이 <math>Q</math>의 첫 <math>j</math>열들의 [[선형 결합]]인 사실은 <math>R</math>의 [[상삼각 행렬|상삼각성]]에 대응한다.
* <math>Q</math>의 <math>n+1</math>번째 열과 <math>m</math>번째 열 사이의 열들은 <math>M</math>의 열들의 [[선형 생성]]의 [[직교 여공간]]의 [[정규 직교 기저]]를 이룬다.
* <math>i=1,\dots,n</math>에 대하여, <math>R_{ii}\ne0</math>. 즉, <math>R'</math>은 [[가역 행렬]]이다.
* <math>R_{ii}>0</math> (<math>i=1,\dots,n</math>)인 경우로 제한하면, <math>R</math>이나 <math>R'</math>은 유일하며, <math>Q'</math>도 유일하다. 이 경우, <math>R'</math>은 <math>A^\dagger A</math>의 [[숄레스키 분해]]의 상삼각 성분과 같다. 그러나 <math>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}
 &
 \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로 분해된다.

## 같이 보기
* LU 분해
* 특잇값 분해

## 참고 문헌

## 외부 링크
* 

분류:행렬 분해
분류:수치선형대수학