行列のQR分解

概要

効率的な行列分解にはいくつかの条件が必要だが、効率性よりも前に、分解自体が可能かどうかが重要になる場合がある。QR分解は正方行列という条件が必要ない行列分解法である。

定義

係数が$n$の行列$A := \begin{bmatrix} \mathbf{a}_{1} & \cdots & \mathbf{a}_{n} \end{bmatrix} \in \mathbb{C}^{m \times n}_{n}$に対し、$i$番目までの列ベクトルで生成された部分空間

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

を定義しよう。ベクトル空間を生成するときは、$i$が大きいほど多くの列ベクトルを使用できるので、

$$ S_{1} (A) \subset S_{2} (A) \subset \cdots S_{n} (A) $$

が成立するだろう。

もちろん、正規直交ベクトルで構成される行列

$$ \widehat{Q} : = \begin{bmatrix} \mathbf{q}_{1} & \cdots & \mathbf{q}_{n} \end{bmatrix} \in \mathbb{C}^{m \times n}_{n} $$

に対しても$S_{1} (\widehat{Q}) \subset S_{2} (\widehat{Q}) \subset \cdots S_{n} (\widehat{Q})$は成立する。

もし$S_{i} (A) = S_{i} (\widehat{Q})$を満たす関係式などを見つけることができれば、$\widehat{Q}$が扱いやすいので、行列$A$も扱いやすくなるだろう。

$$ \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 = \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} $$

そして、このような行列の積を満たす

$$ \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分解である。

アルゴリズム

$\begin{bmatrix} \mathbf{a}_{1} & \cdots & \mathbf{a}_{n} \end{bmatrix} \in \mathbb{C}^{m \times n}_{n}$とする。

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

$\mathbf{a}_{1} = r_{11} \mathbf{q}_{1}$と$| \mathbf{q}_{1} | = 1$を満たす$r_{11}$を計算する。

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

ステップ2-1. $i = 1,2, \cdots , j-1$に対して$r_{ij} = \mathbf{q}_{i}^{\ast}\mathbf{a}_{j}$を計算する。
ステップ2-2. 次のように一時的なベクトルを計算する。 $$ \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. $r_{jj} = | \mathbf{v}_{j} |$を計算する。
ステップ2-4. 次を計算する。 $$ \mathbf{q}_{j} = {{ \mathbf{v}_{j} } \over {r_{jj} }} $$

ここで$R$は上三角行列として与えられ、$r_{jj} = | \mathbf{v}_{j} |$によって計算されるため、常に$r_{jj} > 0$であることが保証され、したがって$R^{-1}$の存在がわかる。
一方で、$\widehat{Q}$と$\widehat{R}$の記述を見て気がついたかもしれないが、詳しく言うと、上記の分解は縮小QR分解、つまりrQR分解と呼ばれる。
全体のQR分解、つまりfQR分解は、特異値分解で行ったのと同様に、正規直交ベクトルで構成された$Q = \begin{bmatrix} \widehat{Q} & \mathbf{q}_{n+1} & \cdots & \mathbf{q}_{m} \end{bmatrix} \in \mathbb{C}^{m \times m}$と下に$0$を埋め込んだ$R = \begin{bmatrix} \widehat{R} \\ O \end{bmatrix} \in \mathbb{C}^{m \times n}$を構成することにより実現される。

存在性

行列$A \in \mathbb{C}^{m \times n}$は必ずQR分解を持つ。

一意性

可逆行列$A \in \mathbb{R}^{m \times m}$はただ一つのrQR分解を持つ。

説明

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