QR 분해 문서 원본 보기

{{위키데이터 속성 추적}}
[[선형대수학]]에서 '''QR 분해'''({{llang|en|QR decomposition, QR factorization}})는 [[실수]] 성분 [[정사각 행렬]]을 [[직교 행렬]]와 [[상삼각 행렬]]의 곱으로 나타내는 [[행렬 분해]] <math>M=QR</math>이다.<ref name="Lay">{{서적 인용
|성=Lay
|이름=David C.
|제목=Linear Algebra and Its Applications
|url=https://archive.org/details/isbn_9781256761792
|판=4
|출판사=Pearson Education
|날짜=2012
|isbn=978-0-321-38517-8
}}</ref> [[그람-슈미트 과정]]이나 [[하우스홀더 행렬]]이나 [[기븐스 회전]]을 통해 얻을 수 있으며, [[선형 최소 제곱법]]이나 [[QR 알고리즘]] 따위에서 쓰인다.

== 정의 ==
실수체 또는 복소수체 <math>\mathbb K</math> 성분의 <math>m\times n</math> 행렬 <math>M</math>은 항상 다음과 같이 분해할 수 있으며, 이를 <math>M</math>의 '''(두꺼운) QR 분해'''({{llang|en|(thick) QR decomposition}})라고 한다.<ref name="Golub">{{서적 인용|성1=Golub|이름1=Gene H.|성2=Van Loan|이름2=Charles F.|제목=Matrix computations|url=https://archive.org/details/matrixcomputatio0004golu|언어=en|판=4|총서=Johns Hopkins Studies in the Mathematical Sciences|출판사=The Johns Hopkins University Press|위치=Baltimore|날짜=2013|isbn=978-1-4214-0794-4|mr=3024913|zbl=1268.65037|lccn=2012943449}}</ref>{{rp|246, Theorem 5.2.1}}
:<math>M=QR</math>
여기서
* <math>Q</math>는 <math>\mathbb K</math> 성분의 <math>m\times m</math> [[정사각 행렬]]이며, <math>Q</math>의 열들은 그 [[선형 생성]]의 [[정규 직교 기저]]를 이룬다. 즉, <math>Q</math>는 <math>\mathbb K=\mathbb R</math>일 때 [[직교 행렬]], <math>\mathbb K=\mathbb C</math>일 때 [[유니터리 행렬]]이다.
* <math>R</math>는 <math>\mathbb K</math> 성분의 <math>m\times n</math> 행렬이며, <math>i>j</math>에 대하여 <math>R_{ij}=0</math>이다. 즉, [[상삼각 행렬]]이다.

=== 얇은 분해 ===
실수체 또는 복소수체 <math>\mathbb K</math> 성분의 <math>m\times n</math> 행렬 <math>M</math>에 대하여, 만약 <math>m\ge n</math>이라면, <math>M</math>을 다음과 같이 분해할 수 있으며, 이를 <math>M</math>의 '''얇은 QR 분해'''({{llang|en|thin QR decomposition, reduced QR decomposition}})라고 한다.<ref name="Golub" />{{rp|248, Theorem 5.2.3}}
:<math>M=Q'R'</math>
여기서
* <math>Q'</math>은 <math>\mathbb K</math> 성분의 <math>m\times n</math> 행렬이며, <math>Q'</math>의 열들은 그 [[선형 생성]]의 [[정규 직교 기저]]를 이룬다. 그러나, [[정사각 행렬]]일 필요가 없으므로 [[직교 행렬]]이나 [[유니터리 행렬]]이 아닐 수 있다.
* <math>R'</math>은 <math>\mathbb K</math> 성분의 <math>n\times n</math> [[상삼각 행렬]]이다.
물론, [[정사각 행렬]]의 경우 (<math>m=n</math>) QR 분해와 얇은 QR 분해를 구분할 필요가 없다. 얇은 QR 분해는 QR 분해의 특수한 경우이다. 구체적으로, <math>m\ge n</math>이며, QR 분해 <math>M=QR</math>가 주어졌다고 하자. <math>Q'</math>이 <math>Q</math>의 첫 <math>n</math>열 들로 이루어진 <math>m\times n</math> 행렬, <math>R'</math>이 <math>R</math>의 첫 <math>n</math>행들로 이루어진 <math>n\times n</math> 행렬이라고 하였을 때,
:<math>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''</math>은 부분 공간의 정규 직교 기저를 전체 공간의 정규 직교 기저로 확충하는 방법에 대응하므로, 일반적으로 유일하지 않다.
이에 따라, QR 분해는 일반적으로 유일하지 않으며, <math>\operatorname{rank}M=n</math>이라고 가정하더라도 <math>m>n</math>인 경우 유일하지 않다. 다만, 만약 <math>\operatorname{rank}M=n</math>이라면, <math>M</math>의 얇은 QR 분해는 유일하다. 특히, [[가역 행렬]]의 QR 분해는 유일하다.

== 방법 ==
=== 그람-슈미트 과정 ===
{{본문|그람-슈미트 과정}}
벡터 <math>\mathbf{a}_1,\mathbf{a}_2,\cdots,\mathbf{a}_n\in\mathbb{R}^m</math>이 [[일차독립]]이라 하자. 행렬 <math>A = [\begin{array}{llll}\mathbf{a}_1 &\mathbf{a}_2 &\cdots &\mathbf{a}_n\end{array}]</math> 에 대해, 그람-슈미트 직교정규화를 사용하면
:<math>\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}</math> <!-- <math>\;\;,\;\; {\langle \cdot,\cdot \rangle}  </math>은  [[내적 공간|내적]] -->
인 [[사영]] 연산자를 이용해서
:<math>\mathbf{u}_i = \mathbf{a}_i - \sum_{j=1}^{i-1} \mathrm{proj}_{\mathbf{u}_j} \mathbf{a}_i</math>
:<math>\mathbf{e}_i = \frac {\mathbf{u}_i} {\|\mathbf{u}_i\|}</math>  <!--  <math>\;\;,\;\;  {\|{ }\|} </math>는 [[노름]] -->
와 같이 직교정규기저 <math>\{\mathbf{e}_1, \mathbf{e}_2, \cdots, \mathbf{e}_n\}</math>를 얻을 수 있다.
:<math> {\langle \cdot,\cdot \rangle}  </math>은  [[내적 공간|내적]] <math>,\;\;  {\|{ }\|} </math>는 [[노름]]
위 식을 다시 정리하면
:<math>\mathbf{a}_i = \sum_{j=1}^{i} \langle \mathbf{e}_j, \mathbf{a}_i \rangle \mathbf{e}_j</math>
가 되므로,
:<math>Q = [\begin{array}{llll}\mathbf{e}_1& \mathbf{e}_2& \cdots& \mathbf{e}_n\end{array}]</math>
:<math>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}</math>
와 같이 놓으면 <math>A = QR</math>이 성립한다.

==== 예 ====
:<math>A = 
\begin{pmatrix}
12 & -51 & 4 \\
6 & 167 & -68 \\
-4 & 24 & -41
\end{pmatrix}
</math>

정규 [[직교 행렬]] <math>Q</math>는 <math> Q^T \,Q = I</math>의 성질을 갖고있고,

따라서,  <math>Q</math>는 다음과 같이 그람-슈미트 절차를 따라서,
:<math>
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}
</math>

:<math>
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}
</math>
그리고,
:<math>

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

</math>
:<math>

 R = Q^{T}A =

\begin{pmatrix}
    14  &  21          &            -14 \\
     0  & 175          &           -70 \\
     0  &   0          &           35
\end{pmatrix}
</math>
확인해보면,
:<math>A= QR</math>이므로,
:<math>
\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}
 </math>

:<math>QR=A</math>이다.
:<math>QR</math>분해 된다.
그러나,

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

====RQ 분해와의 관계====

<math>RQ</math> 분해는 행렬 <math>A</math>를 [[상삼각행렬]]<math> R</math> (직각 삼각형이라고도 함) 및 직교 행렬<math> Q</math> 의 곱으로 변환한다. <math>QR </math>분해와의 유일한 차이점은 행렬의 순서이다.

<math>QR </math>분해는 첫 번째 열에서 시작된 <math>A</math> 행렬의 열의 그람-슈미트 직교화이다.

<math>RQ</math> 분해는 마지막 행에서 시작하는 <math> A</math> 행렬의 행의 그람-슈미트 직교화이다.

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

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

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

==== 예 ====
: <math>A = \begin{pmatrix}
12 & -51 & 4 \\
6 & 167 & -68 \\
-4 & 24 & -41 \end{pmatrix}</math>

먼저 행렬 <math>A</math> 의 첫 번째 열을 벡터로 변환하는 리플렉션을 찾아야한다. 
:<math>\|{a}_1\| \;{e}_1 = (14, 0, 0)^T</math>에서,
:벡터 <math>{a}_1 = (12, 6, -4)^T</math>

: <math>{u} = {x} - \alpha{e}_1</math>

: <math>{v} = {{u}\over\|{u}\|}</math>

: <math>\alpha = 14</math> 
:<math>{x} = {a}_1 = (12, 6, -4)^T</math>

따라서,
: <math>{u} = (-2, 6, -4)^T=({2})(-1, 3, -2)^T</math>
:<math>{v} = {{(-1, 3, -2)^T} \over {\sqrt{14}} }</math>
[[하우스홀더 행렬]] <math>Q = I - 2{{{v v^T}}\over{1}}</math>에서,
:<math>Q_1 = I - 2{{\begin{pmatrix} -1 \\ 3 \\ -2 \end{pmatrix}} \over \sqrt{14} }{{\begin{pmatrix} -1 & 3 & -2 \end{pmatrix}} \over \sqrt{14} }  </math>
:<math>Q_1 = I - {2 \over \sqrt{14} \sqrt{14}} \begin{pmatrix} -1 \\ 3 \\ -2 \end{pmatrix}\begin{pmatrix} -1 & 3 & -2 \end{pmatrix}</math>

:<math> = I - {1 \over 7}\begin{pmatrix}
1 & -3  & 2 \\
-3 & 9 & -6 \\
2  & -6  & 4
\end{pmatrix}</math>
:<math> = \begin{pmatrix}
6/7 & 3/7   &  -2/7 \\
3/7  &-2/7  &  6/7 \\
-2/7 & 6/7  &   3/7 \\
\end{pmatrix}.</math>

확인해보면,
:<math>Q_1A = \begin{pmatrix}
14 & 21 & -14 \\
0 & -49 & -14 \\
0 & 168 & -77 \end{pmatrix}</math>
삼각행렬에 접근하고 있음을 알 수 있다.
<math>3</math>행<math>2</math>열에서 <math>(3, 2)</math>의 성분 값을 <math>0</math>으로 만들면 [[상삼각행렬]]을 얻게 된다.

<math>(1, 1)</math> [[소행렬식]]에서 다시 위의 절차를 반복해보면,
:<math>A' = M_{11} = \begin{pmatrix}
-49 & -14 \\
168 & -77 \end{pmatrix}</math>
위와 같은 방법으로 하우스홀더 변환(Householder transformation)된 행렬을 얻고,
:<math>Q_2 = \begin{pmatrix}
1 & 0 & 0 \\
0 & -7/25 & 24/25 \\
0 & 24/25 & 7/25 \end{pmatrix}</math>
:<math>Q_1 , Q_2</math>에서 각각 [[전치행렬]]을 수행한 후 프로세스가 올바르게 작동하는지 확인해보고,
<math>Q_1 = Q_1^T ,  Q_2 = Q_2^T</math>
그리고나서,
:<math>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} </math>
그리고,
:<math>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} </math>

:<math>R=Q_2Q_1A=Q^T A=\begin{pmatrix}
14 & 21 & -14 \\
0 & 175 & -70 \\
0 & 0 & -35 \end{pmatrix}</math>
행렬 <math>Q</math>는 [[직교행렬]]이고 <math>R</math> 은 [[상삼각행렬]]이되고 <math>QR=A </math>로 <math>QR</math> 분해된다.

=== 기븐스 회전 ===
[[기븐스 행렬]]은 특정위치에서 성분값을 <math>0</math>으로 조작할 수 있는 방법으로 [[기븐스 회전]]을 제공한다.

이것은 임의의 행렬을 [[직교행렬]]과 특정위치의 성분값이 <math>0</math> 인 [[상삼각행렬]]로 분해되게 유도할 수 있게된다.

==== 예 ====
: <math>A = \begin{pmatrix}
a_{11} & a_{12} & a_{13} \\
a_{21} & a_{22} & a_{23}\\
a_{31} & a_{32} & a_{33}
 \end{pmatrix}</math>
: <math>A = \begin{pmatrix}
12 & -51 & 4 \\
6 & 167 & -68 \\
-4 & 24 & -41 \end{pmatrix}</math>

:<math>\mathbf{a}_{31} = -4</math>
:<math>G_1 , (12,-4)</math>
:<math>\theta = \arctan\left({-(-4) \over 12}\right)</math> 
:<math>
G_1 = \begin{pmatrix}
\cos(\theta) & 0 & -\sin(\theta) \\
0 & 1 & 0 \\
\sin(\theta) & 0  & \cos(\theta)
\end{pmatrix}
</math>
:<math>= \begin{pmatrix}
0.94868... & 0 & -0.31622... \\
0 & 1 & 0 \\
0.31622... & 0 & 0.94868... 
\end{pmatrix}</math>

:<math>G_1 \cdot A</math>는 <math>\mathbf{a}_{31} =0</math>으로 조작된다.
:<math>G_1A = \begin{pmatrix}
12.64911... & -55.97231... & 16.76007... \\
6 & 167 & -68 \\
0 & 6.64078... & -37.6311... 
\end{pmatrix}</math>

<math>G_2</math> 그리고 <math>G_3</math> 도 이러한 절차를 반복한다.
:<math>a_{21}=0</math> 그리고 <math>a_{32}=0</math>으로 조작된다.
결과로 상삼각행렬<math>R</math>을 얻는다.
따라서,
:<math> G_3 \cdot G_2 \cdot G_1=Q^T </math>
:<math>G_3G_2G_1A= Q^TA = R</math>
:<math> \left( Q^T \right)^T = Q</math>   
직교행렬에서,
:<math>Q^T = Q^{-1}, Q Q^T = Q^T Q = I</math>
그리고, <math>QR=A</math>이다.
:<math>A=QR</math>로 분해된다.

== 같이 보기 ==
* [[LU 분해]]
* [[특잇값 분해]]

== 참고 문헌 ==
{{각주}}

== 외부 링크 ==
* {{매스월드|id=QRDecomposition|title=QR decomposition}}

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