QR 분해

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

정의

실수체 또는 복소수체 $𝕂$ 성분의 $m\times n$ 행렬 $M$은 항상 다음과 같이 분해할 수 있으며, 이를 $M$의 (두꺼운) QR 분해(틀:Llang)라고 한다.틀:Rp

$M=QR$

여기서

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

얇은 분해

실수체 또는 복소수체 $𝕂$ 성분의 $m\times n$ 행렬 $M$에 대하여, 만약 $m\ge n$이라면, $M$을 다음과 같이 분해할 수 있으며, 이를 $M$의 얇은 QR 분해(틀:Llang)라고 한다.틀:Rp

$M=Q^{\prime }{R}^{\prime }$

여기서

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

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

$Q=\left(\begin{array}{cc}{Q}^{\prime }& Q^{″}\end{array}\right)$

$R=\left(\begin{array}{c}{R}^{\prime }\\ 0\end{array}\right)$

이므로

$M=QR=\left(\begin{array}{cc}{Q}^{\prime }& Q^{″}\end{array}\right)\left(\begin{array}{c}{R}^{\prime }\\ 0\end{array}\right)=Q^{\prime }{R}^{\prime }+Q^{″}0=Q^{\prime }{R}^{\prime }$

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

가역 행렬과 유일성

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

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

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

• $M$은 가역 행렬이다.

만약 $\mathrm{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}\ne 0$. 즉, $R^{\prime }$은 가역 행렬이다.
• $R_{ii}>0$ ($i=1,\dots ,n$)인 경우로 제한하면, $R$이나 $R^{\prime }$은 유일하며, $Q^{\prime }$도 유일하다. 이 경우, $R^{\prime }$은 $A^{†}A$의 숄레스키 분해의 상삼각 성분과 같다. 그러나 $Q^{″}$은 부분 공간의 정규 직교 기저를 전체 공간의 정규 직교 기저로 확충하는 방법에 대응하므로, 일반적으로 유일하지 않다.

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

방법

그람-슈미트 과정

틀:본문 벡터 ${𝐚}_1,{𝐚}_2,\cdots ,{𝐚}_n\in {ℝ}^m$이 일차독립이라 하자. 행렬 $A=[\begin{array}{cccc}{𝐚}_1& {𝐚}_2& \cdots & {𝐚}_n\end{array}]$ 에 대해, 그람-슈미트 직교정규화를 사용하면

${\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{𝐞}𝐚=\frac{⟨𝐞,𝐚⟩}{⟨𝐞,𝐞⟩}𝐞$

인 사영 연산자를 이용해서

${𝐮}_i={𝐚}_i-\sum _{j=1}^{i-1}{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{j}}_{{𝐮}_j}{𝐚}_i$

${𝐞}_i=\frac{{𝐮}_i}{\Vert {𝐮}_i\Vert }$

와 같이 직교정규기저 $\{{𝐞}_1,{𝐞}_2,\cdots ,{𝐞}_n\}$를 얻을 수 있다.

$⟨\cdot ,\cdot ⟩$은 내적 $,\Vert \Vert$는 노름

위 식을 다시 정리하면

${𝐚}_i=\sum _{j=1}^i⟨{𝐞}_j,{𝐚}_i⟩{𝐞}_j$

가 되므로,

$Q=[\begin{array}{cccc}{𝐞}_1& {𝐞}_2& \cdots & {𝐞}_n\end{array}]$

$R=\left(\begin{array}{cccc}⟨{𝐞}_1,{𝐚}_1⟩& ⟨{𝐞}_1,{𝐚}_2⟩& ⟨{𝐞}_1,{𝐚}_3⟩& \dots \\ 0& ⟨{𝐞}_2,{𝐚}_2⟩& ⟨{𝐞}_2,{𝐚}_3⟩& \dots \\ 0& 0& ⟨{𝐞}_3,{𝐚}_3⟩& \dots \\ ⋮& ⋮& ⋮& \ddots \end{array}\right)$

와 같이 놓으면 $A=QR$이 성립한다.

예

$A=\left(\begin{array}{ccc}12& -51& 4\\ 6& 167& -68\\ -4& 24& -41\end{array}\right)$

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

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

$U=\left(\begin{array}{ccc}{u}_1& u_2& u_3\end{array}\right)=\left(\begin{array}{ccc}12& -69& -58/5\\ 6& 158& 6/5\\ -4& 30& -33\end{array}\right)$

$Q=\left(\begin{array}{ccc}\frac{u_1}{\Vert u_1\Vert }& \frac{u_2}{\Vert u_2\Vert }& \frac{u_3}{\Vert u_3\Vert }\end{array}\right)=\left(\begin{array}{ccc}12/14& -69/175& -58/(5\times 35)\\ 6/14& 158/175& 6/(5\times 35)\\ -4/14& 30/175& -33/(1\times 35)\end{array}\right)=\left(\begin{array}{ccc}6/7& -69/175& -58/175\\ 3/7& 158/175& 6/175\\ -2/7& 6/35& -33/35\end{array}\right)$

그리고,

$Q^{T}A=Q^{T}QR=R$

$R=Q^{T}A=\left(\begin{array}{ccc}14& 21& -14\\ 0& 175& -70\\ 0& 0& 35\end{array}\right)$

확인해보면,

$A=QR$이므로,

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

$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=\left(\begin{array}{ccc}12& -51& 4\\ 6& 167& -68\\ -4& 24& -41\end{array}\right)$

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

$\Vert a_1\Vert e_1=(14,0,0{)}^T$에서,

벡터 $a_1=(12,6,-4{)}^T$

$u=x-\alpha e_1$

$v=\frac{u}{\Vert u\Vert }$

$\alpha =14$

$x=a_1=(12,6,-4{)}^T$

따라서,

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

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

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

$Q_1=I-2\frac{\left(\begin{array}{c}-1\\ 3\\ -2\end{array}\right)}{\sqrt{14}}\frac{\left(\begin{array}{ccc}-1& 3& -2\end{array}\right)}{\sqrt{14}}$

$Q_1=I-\frac{2}{\sqrt{14}\sqrt{14}}\left(\begin{array}{c}-1\\ 3\\ -2\end{array}\right)\left(\begin{array}{ccc}-1& 3& -2\end{array}\right)$

$=I-\frac{1}{7}\left(\begin{array}{ccc}1& -3& 2\\ -3& 9& -6\\ 2& -6& 4\end{array}\right)$

$=\left(\begin{array}{ccc}6/7& 3/7& -2/7\\ 3/7& -2/7& 6/7\\ -2/7& 6/7& 3/7\end{array}\right).$

확인해보면,

$Q_{1}A=\left(\begin{array}{ccc}14& 21& -14\\ 0& -49& -14\\ 0& 168& -77\end{array}\right)$

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

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

$A^{\prime }=M_{11}=\left(\begin{array}{cc}-49& -14\\ 168& -77\end{array}\right)$

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

$Q_2=\left(\begin{array}{ccc}1& 0& 0\\ 0& -7/25& 24/25\\ 0& 24/25& 7/25\end{array}\right)$

$Q_1,Q_2$에서 각각 전치행렬을 수행한 후 프로세스가 올바르게 작동하는지 확인해보고,

$Q_1=Q_1^T,Q_2=Q_2^T$ 그리고나서,

$Q=Q_1^T{Q}_2^T=\left(\begin{array}{ccc}6/7& -69/175& 58/175\\ 3/7& 158/175& -6/175\\ -2/7& 6/35& 33/35\end{array}\right)$

그리고,

$Q=Q_1^T{Q}_2^T=\left(\begin{array}{ccc}0.8571& -0.3943& 0.3314\\ 0.4286& 0.9029& -0.0343\\ -0.2857& 0.1714& 0.9429\end{array}\right)$

$R=Q_2{Q}_{1}A=Q^{T}A=\left(\begin{array}{ccc}14& 21& -14\\ 0& 175& -70\\ 0& 0& -35\end{array}\right)$

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

기븐스 회전

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

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

예

$A=\left(\begin{array}{ccc}{a}_{11}& a_{12}& a_{13}\\ a_{21}& a_{22}& a_{23}\\ a_{31}& a_{32}& a_{33}\end{array}\right)$

$A=\left(\begin{array}{ccc}12& -51& 4\\ 6& 167& -68\\ -4& 24& -41\end{array}\right)$

${𝐚}_{31}=-4$

$G_1,(12,-4)$

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

$G_1=\left(\begin{array}{ccc}\cos (\theta )& 0& -\sin (\theta )\\ 0& 1& 0\\ \sin (\theta )& 0& \cos (\theta )\end{array}\right)$

$=\left(\begin{array}{ccc}0.94868...& 0& -0.31622...\\ 0& 1& 0\\ 0.31622...& 0& 0.94868...\end{array}\right)$

$G_1\cdot A$는 ${𝐚}_{31}=0$으로 조작된다.

$G_{1}A=\left(\begin{array}{ccc}12.64911...& -55.97231...& 16.76007...\\ 6& 167& -68\\ 0& 6.64078...& -37.6311...\end{array}\right)$

$G_2$ 그리고 $G_3$ 도 이러한 절차를 반복한다.

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

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

$G_3\cdot G_2\cdot G_1=Q^T$

$G_3{G}_2{G}_{1}A=Q^{T}A=R$

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

직교행렬에서,

$Q^T=Q^{-1},Q{Q}^T=Q^{T}Q=I$

그리고, $QR=A$이다.

$A=QR$로 분해된다.

같이 보기

• LU 분해
• 특잇값 분해

외부 링크

• 틀:매스월드