logo

행렬의 QR 분해 📂행렬대수

행렬의 QR 분해

개요

효율적인 행렬 분해에는 여러가지 조건이 필요하지만, 효율 이전에 분해 자체를 할 수 있느냐 없느냐가 중요할 수 있다. QR 분해는 정방행렬이라는 조건이 필요 없는 행렬 분해법이다.

정의

계수가 nn 인 행렬 A:=[a1⋯an]∈Cnm×nA := \begin{bmatrix} \mathbf{a}_{1} & \cdots & \mathbf{a}_{n} \end{bmatrix} \in \mathbb{C}^{m \times n}_{n} 에 대해 ii번째까지의 열벡터로 생성된 부분공간

Si(A):=sp{a1,⋯ ,ai} S_{i} (A) := \text{sp} \left\{ \mathbf{a}_{1}, \cdots , \mathbf{a}_{i} \right\}

을 정의하자. 벡터공간을 생성할 땐 ii 가 클수록 많은 열벡터를 사용할 수 있으므로

S1(A)⊂S2(A)⊂⋯Sn(A) S_{1} (A) \subset S_{2} (A) \subset \cdots S_{n} (A)

가 성립할 것이다.

물론 정규직교벡터로 이루어진 행렬

Q^:=[q1⋯qn]∈Cnm×n \widehat{Q} : = \begin{bmatrix} \mathbf{q}_{1} & \cdots & \mathbf{q}_{n} \end{bmatrix} \in \mathbb{C}^{m \times n}_{n}

에 대해서도 S1(Q^)⊂S2(Q^)⊂⋯Sn(Q^)S_{1} (\widehat{Q}) \subset S_{2} (\widehat{Q}) \subset \cdots S_{n} (\widehat{Q}) 는 성립한다.

만약 Si(A)=Si(Q^)S_{i} (A) = S_{i} (\widehat{Q}) 를 만족하는 관계식 등을 찾을 수 있다면 Q^\widehat{Q} 가 다루기 쉬우므로 행렬 AA 도 다루는 게 한결 쉬워질 것이다.

a1=r11q1a2=r12q1+r22q2⋮an=r1nq1+⋯+rnnqn \begin{align*} \mathbf{a}_{1} =& r_{11} \mathbf{q}_{1} \\ \mathbf{a}_{2} =& r_{12} \mathbf{q}_{1} + r_{22} \mathbf{q}_{2} \\ &\vdots \\ \mathbf{a}_{n} =& r_{1n} \mathbf{q}_{1} + \cdots + r_{nn} \mathbf{q}_{n} \end{align*}

우리가 구하고 싶은 관계식들은 위와 같은 형태들로 나타날 것이고, 행렬의 곱으로는 아래와 같이 정리된다.

A=[a1⋯an]=[q1⋯qn][r11r12⋯r1n0r22⋯r2n⋮⋮⋱⋮00⋯rnn]:=Q^R^ A = \begin{bmatrix} \mathbf{a}_{1} & \cdots & \mathbf{a}_{n} \end{bmatrix} = \begin{bmatrix} \mathbf{q}_{1} & \cdots & \mathbf{q}_{n} \end{bmatrix} \begin{bmatrix} r_{11} & r_{12} & \cdots & r_{1n} \\ 0 & r_{22} & \cdots & r_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & r_{nn} \end{bmatrix} := \widehat{Q} \widehat{R}

그리고 이러한 행렬의 곱을 만족시키는

Q^:=[q1⋯qn]R^:=[r11r12⋯r1n0r22⋯r2n⋮⋮⋱⋮00⋯rnn] \widehat{Q} : = \begin{bmatrix} \mathbf{q}_{1} & \cdots & \mathbf{q}_{n} \end{bmatrix} \\ \widehat{R} := \begin{bmatrix} r_{11} & r_{12} & \cdots & r_{1n} \\ 0 & r_{22} & \cdots & r_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & r_{nn} \end{bmatrix} 을 찾는 것이 바로 QR 분해다.

알고리즘

[a1⋯an]∈Cnm×n\begin{bmatrix} \mathbf{a}_{1} & \cdots & \mathbf{a}_{n} \end{bmatrix} \in \mathbb{C}^{m \times n}_{n} 이라고 하자.

**Step 1. j=1j=1

a1=r11q1\mathbf{a}_{1} = r_{11} \mathbf{q}_{1} 과 ∣q1∣=1| \mathbf{q}_{1} | = 1 을 만족하는 r11r_{11} 을 계산한다.

**Step 2. j=2,3,⋯ ,nj= 2, 3, \cdots , n

  • **Step 2-1. i=1,2,⋯ ,j−1i = 1,2, \cdots , j-1 에 대해 rij=qi∗ajr_{ij} = \mathbf{q}_{i}^{\ast}\mathbf{a}_{j} 를 계산한다.
  • Step 2-2. 다음과 같이 임시 벡터를 계산한다. vj=aj−∑i=1j−1rijqi=aj−∑i=1j−1(qi∗aj)qi \mathbf{v}_{j} = \mathbf{a}_{j} - \sum_{i = 1}^{j-1} r_{ij} \mathbf{q}_{i} = \mathbf{a}_{j} - \sum_{i=1}^{j-1} (\mathbf{q}_{i}^{\ast}\mathbf{a}_{j} ) \mathbf{q}_{i}
  • **Step 2-3. rjj=∣vj∣r_{jj} = | \mathbf{v}_{j} | 를 계산한다.
  • Step 2-4. 다음을 계산한다. qj=vjrjj \mathbf{q}_{j} = {{ \mathbf{v}_{j} } \over {r_{jj} }}
  • 여기서 RR 은 상삼각행렬로 주어지며 rjj=∣vj∣r_{jj} = | \mathbf{v}_{j} | 로 계산되므로 항상 rjj>0r_{jj} > 0 임이 보장되고, 따라서 R−1R^{-1} 이 존재함을 알 수 있다.
  • 한편 Q^\widehat{Q} 와 R^\widehat{R} 의 표기를 보고 눈치 챘겠지만, 더 자세하게 말하자면 위의 분해는 축소 QR 분해, 즉 rQR 분해라고 부른다.
  • 전체 QR 분해, 즉 fQR 분해는 특이값 분해에서 했던 것과 마찬가지로 정규직교벡터로 이루어진 Q=[Q^qn+1⋯qm]∈Cm×mQ = \begin{bmatrix} \widehat{Q} & \mathbf{q}_{n+1} & \cdots & \mathbf{q}_{m} \end{bmatrix} \in \mathbb{C}^{m \times m} 과 하단에 00 을 채워넣은 R=[R^O]∈Cm×nR = \begin{bmatrix} \widehat{R} \\ O \end{bmatrix} \in \mathbb{C}^{m \times n} 을 구성함으써 구해진다.

존재성

행렬 A∈Cm×nA \in \mathbb{C}^{m \times n} 은 반드시 QR 분해를 갖는다.

유일성

가역행렬 A∈Rm×mA \in \mathbb{R}^{m \times m} 은 단 하나의 rQR 분해를 갖는다.

설명

존재성과 유일성이 보장되어 있는 것은 좋지만 사실상 증명이랄 게 별로 없다. 특히 유일성의 경우엔 유일하다는 걸 증명함에도 불구하고 부호가 반전되는 등에 대해서는 허용하는 등 자세하게 파고들수록 지저분한 팩트기 때문에 그냥 대충 알고 넘어가는 것을 추천한다.