GSL線形代数ルーチン読解: QR分解（１）

前回までで Householder変換を行う GSL関数を見てみました。

ところで、Householder変換の行列

${\bf H}={\bf E}-\tau$\mbox{\boldmath $\nu$}$\cdot$\mbox{\boldmath $\nu$}$^t$

ですが、これは直交行列になります。

つまり ${\bf H}\cdot{\bf H}^t={\bf H}^t\cdot{\bf H}={\bf E}$

を満たし

式（１）
${\bf H}^{-1}={\bf H}^t$

が成り立ちます。

実際計算してみると

$({\bf H}\cdot{\bf H}^t)_{ij}=\sum_k H_{ik}({\bf H}^t)_{kj}=\sum_k H_{ik}H_{jk}$

$=\delta_{ij}-2\tau\nu_i\nu_j+\tau^2\nu_i\nu_j\sum_k\nu_k^2$

ここで

$$\mbox{\boldmath $\nu$}$=\left( \begin{array}{c} 1\\ v_1 / (\alpha-\beta)\\ \vdots\\ v_{n-1} / (\alpha-\beta) \end{array} \right)$

且つ

$\alpha=\nu_0,\quad\beta=-\mathrm{sign}(\alpha)|$\mbox{\boldmath $\nu$}$|,\quad\tau=\frac{\beta-\alpha}{\beta}$

なので

$\sum_k\nu_k^2=1+\frac{\nu_1^2+\cdots+\nu_{n-1}^2}{(\alpha-\beta)^2}=1+\frac{\beta^2-\alpha^2}{(\alpha-\beta)^2}=\frac{2}{\tau}$

従って

${\bf H}\cdot{\bf H}^t={\bf E}$

が確かめられます。

ここで m x n の行列 A の 1 列ベクトルについて Householder 変換を施すと

${\bf H}_1\cdot{\bf A}=\left( \begin{array}{cccc} a_{11}^{(1)} & a_{12}^{(1)}& \cdots & a_{1n}^{(1)}\\ 0 & a_{22}^{(1)}& \cdots & a_{2n}^{(1)}\\ \vdots & \vdots & & \vdots \\ 0 & a_{n2}^{(1)}& \cdots & a_{nn}^{(1)} \end{array} \right)$

となります。
さらに 2 列ベクトルの 2 行目以降について Householder変換を施すと

${\bf H}_2\cdot{\bf H}_1\cdot{\bf A}=\left( \begin{array}{ccccc} a_{11}^{(1)} & a_{12}^{(1)}& a_{13}^{(1)}& \cdots & a_{1n}^{(1)}\\ 0 & a_{22}^{(2)}& a_{23}^{(2)}& \cdots & a_{2n}^{(2)}\\ 0 & 0 & a_{33}^{(2)}& \cdots & a_{3n}^{(2)}\\ \vdots & \vdots & \vdots & & \vdots \\ 0 & 0 & a_{n3}^{(2)}& \cdots & a_{nn}^{(2)} \end{array} \right)$

となります。
ここで H2 は

${\bf H}_2=\left( \begin{array}{c|c} 1 & {\bf 0} \\ \hline & \\ {\bf 0} & {\bf E}-\tau$\mbox{\boldmath $\nu$}$_2$\mbox{\boldmath $\nu$}$_2^t\\ & \end{array} \right)$

という、右に掛る行列の 2 行 2 列以降を変換する行列です。

これを k = MIN (m, n) 回繰り返すと

${\bf H}_k\cdots{\bf H}_2\cdot{\bf H}_1\cdot{\bf A}=\left( \begin{array}{cccc} a_{11}^{(1)} & a_{12}^{(1)}& \cdots & a_{1n}^{(1)}\\ & a_{22}^{(2)}& \cdots & a_{2n}^{(2)}\\ & & \ddots & \vdots \\ & & & a_{nn}^{(k)} \end{array} \right)$

という上三角行列になります。

で、左辺の行列を

${\bf H}_k\cdots{\bf H}_2\cdot{\bf H}_1={\bf Q}^t$

と置き、右辺の上三角行列を R と置けば

${\bf Q}^t\cdot{\bf A}={\bf R}$

式（１）の H の性質から

式（２）
${\bf A}={\bf Q}\cdot{\bf R}$

が得られます。この式（２）を QR分解といいます。
このQR分解は、連立方程式の解法や固有値問題など様々な問題に利用される重要な行列分解の一つです。
以前 B-spline の計算をした時も QR 分解を用いていましたね。

A を m x n の行列としましたが Q は m x m の正方行列、 R は m x n の行列になります。 m != n の場合 R は

上の図の様に不規則な形の三角行列となります。

ぽんのブログ

自分用の備忘録ブログです。書いてある内容、とくにソースは、後で自分で要点が分かるよう、かなり簡略化してます（というか、いい加減）。あまり信用しないように（汗

GSL線形代数ルーチン読解: QR分解（１）