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}とする。

**ステップ1. j=1j=1

a1=r11q1\mathbf{a}_{1} = r_{11} \mathbf{q}_{1}と∣q1∣=1| \mathbf{q}_{1} | = 1を満たすr11r_{11}を計算する。

**ステップ2. j=2,3,⋯ ,nj= 2, 3, \cdots , n

  • ステップ2-1. i=1,2,⋯ ,j−1i = 1,2, \cdots , j-1に対してrij=qi∗ajr_{ij} = \mathbf{q}_{i}^{\ast}\mathbf{a}_{j}を計算する。
  • ステップ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}
  • ステップ2-3. rjj=∣vj∣r_{jj} = | \mathbf{v}_{j} |を計算する。
  • ステップ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分解を持つ。

説明

存在性と一意性が保証されているのはいいが、実際の証明はほとんどない。特に一意性に関しては、一意であることを証明しても、符号が反転するなどに対して許容するなど、詳しく掘り下げれば掘り下げるほど汚い事実であるため、ざっくりと理解しておくことをおすすめする。